Scala для эффективности понимания?

StackOverflow https://stackoverflow.com/questions/4211103

  •  25-09-2019
  •  | 
  •  

Вопрос

В книге «Программирование на Scala», глава 23, автор приводит такой пример:

case class Book(title: String, authors: String*)
val books: List[Book] = // list of books, omitted here
// find all authors who have published at least two books

for (b1 <- books; b2 <- books if b1 != b2;
    a1 <- b1.authors; a2 <- b2.authors if a1 == a2)
yield a1

Автор сказал, что это будет переведено на:

books flatMap (b1 =>
   books filter (b2 => b1 != b2) flatMap (b2 =>
      b1.authors flatMap (a1 =>
        b2.authors filter (a2 => a1 == a2) map (a2 =>
           a1))))

Но если вы посмотрите на определение метода карты и плоской карты (TraversableLike.scala), вы можете обнаружить, что они определены как циклы for:

   def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
    val b = bf(repr)
    b.sizeHint(this) 
    for (x <- this) b += f(x)
    b.result
  }

  def flatMap[B, That](f: A => Traversable[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
    val b = bf(repr)
    for (x <- this) b ++= f(x)
    b.result
  }

Ну, я предполагаю, что это for будет постоянно транслироваться в foreach, а затем транслироваться в оператор while, который является конструкцией, а не выражением. В Scala нет конструкции for, потому что она хочет, чтобы for всегда что-то выдавало.

Итак, я хочу обсудить с вами, почему Scala делает это «Для перевода»?В примере автора используются 4 генератора, которые в конце будут преобразованы в 4-уровневый вложенный цикл for. Я думаю, что производительность будет ужасной, когда books большой.

Scala поощряет людей использовать этот вид «синтаксического сахара», вы всегда можете увидеть коды, которые активно используют фильтры, карты и плоские карты, что кажется, что программисты забывают, что они на самом деле делают, это вкладывают один цикл в другой, и то, что достигается, это всего лишь чтобы коды выглядели немного короче.какая у тебя идея?

Это было полезно?

Решение

Для пониманий являются синтаксический сахар для монадической трансформации, и, как таковые, полезны во всех видах мест. При этом они гораздо более многослойные в Scala, чем эквивалентная конструкция Haskell (конечно, Haskell не строго по умолчанию, поэтому нельзя говорить о производительности конструкции, как в Scala).

Также важно, эта конструкция сохраняет то, что делается ясно, и избегает быстро усаживания вдавливания или ненужного личного метода вложенности.

Что касается окончательного рассмотрения, ли это скрывает сложность или нет, я поставим это:

for {
  b1 <- books
  b2 <- books
  if b1 != b2
  a1 <- b1.authors
  a2 <- b2.authors 
  if a1 == a2
} yield a1

Очень легко увидеть, что делается, и сложность ясна: B ^ 2 * A ^ 2 (фильтр не изменит сложность), для количества книг и количества авторов. Теперь напишите тот же код в Java, либо с глубокими углублениями, либо с частными методами, и попытайтесь выяснить, в быстром виде, какая сложность кода.

Итак, ИМХО, это не скрывает сложность, но, наоборот, делает его понятно.

Для map/flatMap/filter Определения, которые вы упоминаете, они не принадлежат List или любой другой класс, поэтому они не будут применены. В принципе,

for(x <- List(1, 2, 3)) yield x * 2

переводится в

List(1, 2, 3) map (x => x * 2)

и это не то же самое, что

map(List(1, 2, 3), ((x: Int) => x * 2)))

Вот как прошло определение, будет называться. Для записи фактическая реализация map на List является:

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
  val b = bf(repr)
  b.sizeHint(this) 
  for (x <- this) b += f(x)
  b.result
}

Другие советы

Я пишу код так, чтобы его было легко понять и поддерживать.Затем я профилирую.Если есть узкое место, я обращаю на это свое внимание.Если это похоже на то, что вы описали, я подойду к проблеме по-другому.До тех пор я люблю «сахар». Это спасает меня проблему выписать что -то или задуматься об этом.

Есть на самом деле 6 петлей. Один цикл для каждого фильтра / с плоской картой

Пары фильтра-> карты могут быть выполнены в одном цикле с помощью ленивых видов коллекций (метод итератора)

В целом, TT работает 2 вложенных петель для книг, чтобы найти все книжные пары, а затем два вложенных петель, чтобы найти, если автор одной книги находится в списке авторов другого.

Используя простые структуры данных, вы будете делать то же самое при явном порядке.

И, конечно же, пример здесь состоит в том, чтобы показать комплекс «для» петли, не писать наиболее эффективный код. Например, вместо последовательности авторов можно использовать набор, а затем найти, если пересечение не пустое:

for (b1 <- books; b2 <- books; a <- (b1.authors & b2.authors)) yield a

Обратите внимание, что в 2.8, filter звонок был изменен на withFilter который ленивый и позволяет избежать построения промежуточной структуры. Видеть Руководство по переходу из фильтра в сфильтр?.

Я считаю причину того, что for переводится в map, flatMap а также withFilter (а также определения стоимости, если присутствуют) состоит в том, чтобы сделать использование монадских проще.

Как правило, я думаю, если вычисления вы делаете, включают в себя цикл 4 раза, это нормально, используя for петля. Если вычисление может быть сделано более эффективно, и производительность важно, то вы должны использовать более эффективный алгоритм.

Один след за пределами @ Ittayd ответа на эффективность алгоритма. Стоит отметить, что алгоритм в оригинальном посте (и в книге) является Вложенная петля Присоединяется. Отказ На практике это не эффективный алгоритм для больших наборов данных, а большинство баз данных будут использовать Хеш совокупность здесь вместо этого. В Scala, агрегат хеша будет выглядеть что-то вроде:

(for (book <- books;
      author <- book.authors) yield (book, author)
).groupBy(_._2).filter(_._2.size > 1).keys
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top