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

Question

В книге «Программирование в 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 ), вы можете обнаружить, что они определены как для циклов:

   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 уровня, вложенные в цикл, я думаю, что он будет действительно ужасно работать, когда books велико.

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

Answer 1

Для понимания являются синтаксическим сахаром для монадического преобразования, и, как таковые, полезны во всех видах мест.При этом они гораздо более многословны в 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
}

Answer 2

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

Answer 3

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

Пары filter-> map можно выполнить в одном цикле, используя ленивые представления коллекций (метод итератора)

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

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

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

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

Answer 4

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

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

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

Answer 5

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

(for (book <- books;
      author <- book.authors) yield (book, author)
).groupBy(_._2).filter(_._2.size > 1).keys