spiiin: (Default)
Продолжаю сравнивать Scala и Python на небольших прикладных задачках.
На этот раз переписал старый скрипт для выгрузки всех фотографий из альбома Вконтакта.
Небольшие отличия в задаче - 5 лет назад у VK не было api, поэтому url картинок получался парсингом страницы, сейчас обычным запросом к api.

Старый код на python: 136 строк
Новый код на scala: 36 строк

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


  var token: String = ""
  implicit def string2xml(v: String) = XML.loadString(v)

  override def main(args: Array[String]): Unit = {
    implicit val threadPool = ExecutionContext.fromExecutor(Executors.newFixedThreadPool(4))
    val cmdName = "../../vkAuthorizeToOutput/vkAuthorize.exe"
    token = (cmdName.!!).replace("\r\n", "")
    val photosAns = getPhotos("OWNER_ID", "ALBUM_ID")
    val photo_1280 = extractBigPhotos(photosAns)
    val fut = photo_1280.zipWithIndex.map {
      case (url, i) => Future { println(i + " " + url); saveToFile(url, f"C:/users/USERS/desktop/test/$i%03d.jpg") }
    }
    Await.result(Future.sequence(fut), 30 seconds)
    println("END")
  }

  def getPhotos(ownerId: String, album_id: String) = executeCommand("photos.get", token, ("owner_id" -> ownerId), ("album_id" -> album_id))
  def extractBigPhotos(xml: String) = (xml \\ "photo").map(v => (v \ "src_xxbig").text)
  def saveToFile(url: String, filename: String) = new URL(url) #> new File(filename) !!
  def executeCommand(cmd: String, accessToken: String, params: (String, String)*) = {
    val fmt = s"https://api.vkontakte.ru/method/$cmd.xml?access_token=$accessToken" + params.map { case (k, v) => k + "=" + v }.mkString("&", "&", "")
    Source.fromURL(fmt).mkString


Implicits-параметры функций как-то сильно настораживают. За счёт него можно парой строк включить/выключить многопоточность - у конструктора класса Future есть неявный параметр ExecutorContext, и если его опустить, то что именно передастся в конструктор будет зависеть от того, какой именно неявный объект будет находится в области видимости:

import ExecutionContext.Implicits.global //так импортируется  объект implicit lazy val global: ExecutionContextExecutor
implicit val threadPool = ExecutionContext.fromExecutor(Executors.newFixedThreadPool(4)) //так создаётся свой пул потоков
Future { println(i + " " + url); saveToFile(url, f"test/$i%03d.jpg") } //эти объявления повлияют на эту строку (в которой нет никакого упоминания ExecutionContext вообще!)
//лучше всё время указывать неявный параметр явно:
Future { println(i + " " + url); saveToFile(url, f"test/$i%03d.jpg") }(threadPool) //теперь видно, что между создаваемым объектов и местом его выполнения есть связь


Скала не перестаёт удивлять своей идиоматичностью - для каждой подзадачи находится несколько вариантов решения, часто однострочных.
Tags:
spiiin: (Default)
Прослушал лекции Мартина Одерски на курсере по Scala.
Курс читался два раза, и следующего набора пока нет (да и курсера логиниться не даёт с крымским IP, санкции, мать их), поэтому вместо решения предложенных заданий и для теста языка, я решил попробовать портировать Алгоритм разминирования бомб Джеймса Бонда, написанный мной на Python'e 5 лет назад.

За основу взял код Мартина из итоговой лекции, которой использовался для решения задачи The Water Pouring Problem (как получить X литров воды, имея заданное число стаканов разного литража без маркировки), так как она решается в общем случае тем же алгоритмом - методом поиска в ширину.

Именно эту задачу было интересно решить по нескольким причинам:
- В лекции алгоритм оставлен "сырым" (в него добавлен для оптимизации список уже пройденных вершин и кеширование последнего состояния вместо его вычисления, и то, только для того, чтобы он не тормозил на совсем простых данных). В моей задаче исходные данные из игры, из которых одна из загадок методом полного перебора решается очень долго, поэтому алгоритм нужно оптимизировать.
Так что была и простая подзадача - переделать алгоритм для решения задачи с бомбами, а не со стаканами; и более сложная - ускорить его работу.
- После окончания можно сравнить результаты с решением оригинальной задачи. В частности, по количеству строк кода, а то Python нравится как раз лаконичностью и удобным Repl, простые задачки можно решать, не выходя из него.
Так что:
james_bond_jr

Оригинальный код, перезаточенный для решения задачи разминирования бомбы, решил 3 задачи из 5, на остальных стал выдавать "java.lang.OutOfMemoryError: GC overhead limit exceeded" из-за разрастающегося размера массива входных данных.
Решение проблемы - не исследовать все возможные пути, а в первую очередь подробно рассматривать те, которые приближают к ответу.
Для того, чтобы реализовать это, к классу описания пути нужно примешать trait Ordered:

  class Path(path: List[Move], val endState: State) extends Ordered[Path]{
    def compare(that: Path): Int = {
      def diffFromEnd(x:Path) :Int = (x.endState zip endState).count( {case (x,y) => x!=y} )
      diffFromEnd(this) - diffFromEnd(that)
    }
   ...
  }

функции сравнения - количество символов, которые стоят не своих местах (diffFromEnd).

Также надо сменить контейнер, хранящий Path, с Set на Vector или любой другой, поддерживающий хранение данных в отсортированном виде, и в определённый момент (например, после раскрытия всех вершин из начала потока), отсортировать вершины по порядку наибольшей близости к желаемому состоянию endState.

Ещё один шаг оптимизации - можно допустить, что из состояния, более близкого к решению (похожего на решение), до самого решения нужно будет сделать меньшее количество шагов, чем из состояния, менее похожего на решение. Тогда можно отбросить более далёкие от решения варианты и перестать их обрабатывать(при этом есть риск выбросить и само оптимальное решение, всё зависит от качества оценивающей функции). Я решил обрубать по 50000 вариантов - решение при этом всё равно нашлось за 9 ходов, как и в Python-версии:

val sortedMore = (more take 50000).sorted


Итог:
 val initialState: State = Vector(1,2,2,1, 3,4,4,3, 3,4,4,3, 2,4,4,2)
 val endState: State = Vector(4,3,4,2, 3,1,2,4, 4,2,4,3, 2,4,3,1)

MoveLeft(2) //двигаем третью строку влево
MoveUp(3)  //двигаем четвёртый столбец вверх
MoveRight(1) //двигаем вторую строку вправо
MoveDown(2) //двигаем третий столбец вниз
MoveRight(0) //двигаем первую строку вправо
MoveDown(1) //двигаем второй столбец вниз
MoveRight(0) //двигаем первую строку вправо
MoveLeft(2) //двигаем третью строку влево
MoveLeft(2) //двигаем третью строку влево

Что полностью аналогично решению на Python для той же злополучной 4-й ракеты.

В итоге, получилось по строкам кода:
Решение на Python - 120 строк
Решение на Scala    - 65 строк
(выбросил для подсчёта функции вывода результата на python, на scala результат по умолчанию оказался читаем - список из "Имя кейскласса + параметр" - это как раз то, в каком виде хотелось увидеть ответ).
Кажется, можно попробовать поэкспериментировать со Scala Worksheets для решения простых задач вместо Idle with Python.
Tags:

Profile

spiiin: (Default)
spiiin

September 2017

S M T W T F S
     1 2
34 567 89
101112131415 16
17181920212223
24252627282930

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 19th, 2017 11:35 am
Powered by Dreamwidth Studios