Является ли Scala стиль идиоматического кодирования просто крутой ловушкой для написания неэффективного кода?

Ответ 1

Обсудить ошибку в вопросе:

Итак, если 99% разработчиков Java пишут более эффективный код, чем 99% Scala разработчики, это огромное препятствие для пересечения для большего Scalaпринятие. Есть ли выход из этой ловушки?

Предполагается, что абсолютно никаких доказательств, подтверждающих это. Если false, вопрос спорный.

Есть ли доказательства обратного? Ну, давайте рассмотрим сам вопрос - он ничего не доказывает, но показывает, что вещи не так понятны.

Полностью не-w62 > идиоматический, нефункциональный, нечеткий, но это очень эффективный. Он перемещает список только один раз!

Из четырех претензий в первом предложении первые три являются истинными, а четвертый, как показано пользователем неизвестным, является ложным! И почему это неверно? Потому что, вопреки тому, что говорится во втором предложении, он перебирает список более одного раза.

Код вызывает на нем следующие методы:

res.append(max)
res.append(x)

и

res.toList

Рассмотрим сначала append.

• append принимает параметр vararg. Это означает, что max и x сначала инкапсулированы в последовательность некоторого типа (a WrappedArray, фактически), а затем передаются как параметр. Лучшим методом было бы +=.

• Хорошо, append вызывает ++=, который делегирует +=. Но, во-первых, он вызывает ensureSize, что является второй ошибкой (+= вызывает это тоже - ++= просто оптимизирует это для нескольких элементов). Поскольку Array представляет собой коллекцию фиксированного размера, это означает, что при каждом изменении размера необходимо скопировать весь Array!

Итак, рассмотрим это. Когда вы изменяете размер, Java сначала очищает память, сохраняя 0 в каждом элементе, затем Scala копирует каждый элемент предыдущего массива в новый массив. Поскольку размер удваивается каждый раз, это случается log (n) раз, при этом количество копируемых элементов увеличивается каждый раз, когда это происходит.

Возьмем, например, n = 16. Он выполняет это четыре раза, копируя 1, 2, 4 и 8 элементов соответственно. Поскольку Java должен очищать каждый из этих массивов, и каждый элемент должен быть прочитан и написан, каждый элемент, скопированный, представляет собой 4 обхода элемента. Добавляем все, что у нас (n - 1) * 4, или, примерно, 4 обхода полного списка. Если вы считаете, что читать и писать как один проход, как люди часто ошибочно делают, то это еще три обхода.

Можно улучшить это путем инициализации ArrayBuffer с начальным размером, равным списку, который будет считан, минус один, поскольку мы будем отбрасывать один элемент. Чтобы получить этот размер, нам нужно прокручивать список один раз.

Теперь рассмотрим toList. Проще говоря, он перебирает весь список для создания нового списка.

Итак, мы имеем 1 обход алгоритма, 3 или 4 обхода для изменения размера и 1 дополнительный обход для toList. Это 4 или 5 обходов.

Оригинальный алгоритм немного сложно проанализировать, потому что take, drop и ::: пересекают переменное число элементов. Однако, все вместе, это эквивалентно 3 обходам. Если бы использовалось splitAt, это уменьшилось бы до 2 обходов. С еще двумя обходами, чтобы получить максимум, мы получаем 5 обходов - такое же число, как нефункциональный, не-сжатый алгоритм!

Итак, рассмотрим улучшения.

В соответствии с императивным алгоритмом, если использовать ListBuffer и +=, тогда все методы являются постоянными, что сводит его к общему обходу.

В функциональном алгоритме его можно было бы переписать как:

val max = xs.max
val (before, _ :: after) = xs span (max !=)
before ::: after

Это уменьшает его до наихудшего случая трех обходов. Конечно, есть другие альтернативы, представленные на основе рекурсии или складки, которые решают ее в одном обходе.

И, что самое интересное, все эти алгоритмы O(n), и единственная, которая почти понесла (случайно) в худшей сложности, была императивной (из-за копирования массива). С другой стороны, характеристики кэша императивного варианта могут сделать его более быстрым, потому что данные смежны в памяти. Это, однако, не связано ни с большим, ни с функциональным, а с императивным, и это только вопрос структур данных, которые были выбраны.

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

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

ИЗМЕНИТЬ

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

Затем у меня есть эталон и результаты, в том числе почти все предлагаемые решения. Два интересных момента:

• В зависимости от размера списка создание объектов может иметь большее влияние, чем множественные обходы списка. Исходный функциональный код Adrian использует тот факт, что списки представляют собой постоянные структуры данных, не копируя элементы справа от максимального элемента вообще. Если вместо этого использовался Vector, обе и левая и правая стороны были бы в основном неизменными, что могло бы привести к еще большей производительности.

• Несмотря на то, что у пользователя, неизвестного и парадигматического, есть похожие рекурсивные решения, парадигматический путь быстрее. Причиной этого является то, что он избегает сопоставления шаблонов. Совпадение шаблонов может быть очень медленным.

Контрольный код здесь, и результаты здесь.

Ответ 2

def removeOneMax (xs: List [Int]) : List [Int] = xs match {                                  
    case x :: Nil => Nil 
    case a :: b :: xs => if (a < b) a :: removeOneMax (b :: xs) else b :: removeOneMax (a :: xs) 
    case Nil => Nil 
}

Вот рекурсивный метод, который выполняется только один раз. Если вам нужна производительность, вы должны думать об этом, если нет, то нет.

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

import annotation.tailrec 
@tailrec
def removeOneMax (xs: List [Int], carry: List [Int] = List.empty) : List [Int] = xs match {                                  
  case a :: b :: xs => if (a < b) removeOneMax (b :: xs, a :: carry) else removeOneMax (a :: xs, b :: carry) 
  case x :: Nil => carry 
  case Nil => Nil 
}

Я не знаю, каковы шансы, что более поздние компиляторы улучшат более медленные вызовы карт так же быстро, как while-loops. Однако: вам редко нужны высокоскоростные решения, но, если они вам понадобятся, вы научитесь их быстро.

Знаете ли вы, насколько велика ваша коллекция, чтобы использовать целую секунду для решения на вашем компьютере?

В качестве oneliner, похоже на решение Daniel C. Sobrals:

((Nil : List[Int], xs(0)) /: xs.tail) ((p, x)=> if (p._2 > x) (x :: p._1, p._2) else ((p._2 :: p._1), x))._1

но это трудно прочитать, и я не оценил эффективную производительность. Нормальный шаблон равен (x/: xs) ((a, b) = > /* something */). Здесь x и a являются парами List-so-far и max-so-far, которые решают проблему, чтобы привести все в одну строку кода, но не очень читабельны. Тем не менее, вы можете заработать репутацию на CodeGolf таким образом, и, возможно, кому-то нравится делать измерение производительности.

И теперь к нашему большому удивлению некоторые измерения:

Обновленный метод синхронизации, чтобы убрать сборку мусора, и разогрейте горячую точку-компилятор, основной и многие методы из этого потока вместе в объекте с именем

object PerfRemMax {

  def timed (name: String, xs: List [Int]) (f: List [Int] => List [Int]) = {
    val a = System.currentTimeMillis 
    val res = f (xs)
    val z = System.currentTimeMillis 
    val delta = z-a
    println (name + ": "  + (delta / 1000.0))
    res
  }

def main (args: Array [String]) : Unit = {
  val n = args(0).toInt
  val funs : List [(String, List[Int] => List[Int])] = List (
    "indexOf/take-drop" -> adrian1 _, 
    "arraybuf"      -> adrian2 _, /* out of memory */
    "paradigmatic1"     -> pm1 _, /**/
    "paradigmatic2"     -> pm2 _, 
    // "match" -> uu1 _, /*oom*/
    "tailrec match"     -> uu2 _, 
    "foldLeft"      -> uu3 _,
    "buf-=buf.max"  -> soc1 _, 
    "for/yield"     -> soc2 _,
    "splitAt"       -> daniel1,
    "ListBuffer"    -> daniel2
    )

  val r = util.Random 
  val xs = (for (x <- 1 to n) yield r.nextInt (n)).toList 

// With 1 Mio. as param, it starts with 100 000, 200k, 300k, ... 1Mio. cases. 
// a) warmup
// b) look, where the process gets linear to size  
  funs.foreach (f => {
    (1 to 10) foreach (i => {
        timed (f._1, xs.take (n/10 * i)) (f._2)
        compat.Platform.collectGarbage
    });
    println ()
  })
}

Я переименовал все методы и должен был немного изменить uu2, чтобы соответствовать объявлению общего метода (List [Int] = > List [Int]).

Из длинного результата я предоставляю только вывод для 1M-вызовов:

scala -Dserver PerfRemMax 2000000
indexOf/take-drop:  0.882
arraybuf:   1.681
paradigmatic1:  0.55
paradigmatic2:  1.13
tailrec match: 0.812
foldLeft:   1.054
buf-=buf.max:   1.185
for/yield:  0.725
splitAt:    1.127
ListBuffer: 0.61

Цифры не являются полностью стабильными, в зависимости от размера выборки, и немного варьируются от запуска до запуска. Например, для трасс от 100 до 1 М, с шагом 100 тыс., Время для splitAt было следующим:

splitAt: 0.109
splitAt: 0.118
splitAt: 0.129
splitAt: 0.139
splitAt: 0.157
splitAt: 0.166
splitAt: 0.749
splitAt: 0.752
splitAt: 1.444
splitAt: 1.127

Исходное решение уже довольно быстро. splitAt является модификацией Даниила, часто быстрее, но не всегда.

Измерение проводилось на одном сердечнике 2Ghz Centrino, работающем на xUbuntu Linux, Scala -2.8 с Sun-Java-1.6 (рабочий стол).

Два урока для меня:

• всегда оценивайте свои улучшения производительности; это очень сложно оценить, если вы не делаете этого на ежедневной основе.
• не только весело, писать функциональный код - иногда результат еще быстрее

Вот ссылка на мой benchmarkcode, если кому-то интересно.

Ответ 3

Прежде всего, поведение методов, которые вы представили, отличается от поведения. Первый сохраняет порядок элементов, а второй - нет.

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

def removeMax1( xs: List[Int] ) = {
  def rec( max: Int, rest: List[Int], result: List[Int]): List[Int] = {
    if( rest.isEmpty ) result
    else if( rest.head > max ) rec( rest.head, rest.tail, max :: result)
    else rec( max, rest.tail, rest.head :: result )
  }
  rec( xs.head, xs.tail, List() )
}

или сверните список:

def removeMax2( xs: List[Int] ) = {
  val result = xs.tail.foldLeft( xs.head -> List[Int]() ) { 
    (acc,x) =>
      val (max,res) = acc
      if( x > max ) x -> ( max :: res )
      else max -> ( x :: res )
  }
  result._2
}

Если вы хотите сохранить первоначальный порядок вставки, вы можете (за счет двух проходов, а не одного) без каких-либо усилий написать что-то вроде:

def removeMax3( xs: List[Int] ) = {
  val max = xs.max
  xs.filterNot( _ == max )
}

что более очевидно, чем ваш первый пример.

Ответ 4

Самая большая неэффективность, когда вы пишете программу, беспокоится о неправильных вещах. Это, как правило, не то, о чем нужно беспокоиться. Почему?

• Время разработки обычно намного дороже процессорного времени - на самом деле, как правило, недостаток первого и избыток последнего.

• В большинстве случаев код не должен быть очень эффективным, потому что он никогда не будет работать с наборами данных из миллиона элементов несколько раз в секунду.

• В большинстве случаев код не нужен, и меньше кода меньше места для скрытия ошибок.

Ответ 5

Пример, который вы дали, на самом деле не очень функциональный. Вот что вы делаете:

// Given a list of Int
def removeMaxCool(xs: List[Int]): List[Int] = {

  // Find the index of the biggest Int
  val maxIndex = xs.indexOf(xs.max);

  // Then take the ints before and after it, and then concatenate then
  xs.take(maxIndex) ::: xs.drop(maxIndex+1)
}

Помните, что это неплохо, но вы знаете, когда функциональный код в лучшем случае, когда он описывает то, что вы хотите, а не как хотите. В качестве незначительной критики, если вы использовали splitAt вместо take и drop, вы могли бы немного улучшить его.

Другой способ сделать это:

def removeMaxCool(xs: List[Int]): List[Int] = {
  // the result is the folding of the tail over the head 
  // and an empty list
  xs.tail.foldLeft(xs.head -> List[Int]()) {

    // Where the accumulated list is increased by the
    // lesser of the current element and the accumulated
    // element, and the accumulated element is the maximum between them
    case ((max, ys), x) => 
      if (x > max) (x, max :: ys)
      else (max, x :: ys)

  // and of which we return only the accumulated list
  }._2
}

Теперь обсудим основной вопрос. Этот код медленнее, чем Java? Несомненно! Является ли код Java медленнее, чем эквивалент C? Вы можете поспорить, что это так, JIT или нет JIT. И если вы напишете его непосредственно на ассемблере, вы можете сделать это еще быстрее!

Но стоимость этой скорости заключается в том, что вы получаете больше ошибок, вы тратите больше времени на то, чтобы понять код для его отладки, и у вас меньше видимости того, что делает общая программа, в отличие от того, что маленький фрагмент кода - что может привести к проблемам с производительностью.

Итак, мой ответ прост: если вы считаете, что ограничение скорости программирования в Scala не стоит того, что он приносит, вам следует программировать на ассемблере. Если вы думаете, что я радикален, то я возражаю против того, что вы просто выбрали знакомого как "идеальный" компромисс.

Думаю, производительность не имеет значения? Не за что! Я думаю, что одним из главных преимуществ Scala является использование выигрышей, часто встречающихся в динамически типизированных языках с производительностью статически типизированного языка! Вопросы производительности, сложность алгоритма имеет большое значение, и постоянные затраты также имеют значение.

Но, когда есть выбор между производительностью, читабельностью и ремонтопригодностью, последний предпочтительнее. Конечно, если производительность должна быть улучшена, тогда нет выбора: вы должны что-то принести в жертву. И если нет потери в удобочитаемости/ремонтопригодности - например, Scala и динамически типизированных языков - обязательно, перейдите на производительность.

Наконец, чтобы получить производительность от функционального программирования, вам нужно знать функциональные алгоритмы и структуры данных. Конечно, 99% Java-программистов с 5-10-летним опытом будут превзойти производительность 99% программистов Scala с 6-месячным опытом. То же самое было верно для императивного программирования и объектно-ориентированного программирования пару десятилетий назад, и история показывает, что это не имеет значения.

ИЗМЕНИТЬ

В качестве побочного примечания ваш "быстрый" алгоритм страдает серьезной проблемой: вы используете ArrayBuffer. Эта коллекция не имеет постоянного добавления времени и имеет линейное время toList. Если вместо этого вы используете ListBuffer, вы получаете добавление постоянного времени и toList.

Ответ 6

Для справки: здесь splitAt определяется в TraversableLike в стандартной библиотеке Scala,

def splitAt(n: Int): (Repr, Repr) = {
  val l, r = newBuilder
  l.sizeHintBounded(n, this)
  if (n >= 0) r.sizeHint(this, -n)
  var i = 0
  for (x <- this) {
    (if (i < n) l else r) += x
    i += 1
  }
  (l.result, r.result)
}

Это не похоже на ваш пример кода того, что может предложить Java-программист.

Мне нравится Scala, потому что, когда важна производительность, изменчивость - разумный путь. Библиотека коллекций - отличный пример; особенно, как он скрывает эту изменчивость за функциональным интерфейсом.

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

Из любопытства я выбрал произвольный большой файл в компиляторе Scala (scala.tools.nsc.typechecker.Typers.scala) и подсчитал что-то вроде 37 для петель, 11 в то время как петли, 6 конкатенаций (++) и 1 раз (это бывает foldRight).

Ответ 7

Как насчет этого?

def removeMax(xs: List[Int]) = {
  val buf = xs.toBuffer
  buf -= (buf.max)
}

Немного более уродливый, но быстрее:

def removeMax(xs: List[Int]) = {
  var max = xs.head
  for ( x <- xs.tail ) 
  yield {
    if (x > max) { val result = max; max = x; result}
    else x
  }
}

Ответ 8

Попробуйте следующее:

(myList.foldLeft((List[Int](), None: Option[Int]))) {
  case ((_, None),     x) => (List(),               Some(x))
  case ((Nil, Some(m), x) => (List(Math.min(x, m)), Some(Math.max(x, m))
  case ((l, Some(m),   x) => (Math.min(x, m) :: l,  Some(Math.max(x, m))
})._1

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

Попробуем объяснить, что здесь происходит. Я постараюсь сделать это как можно более простым, без какой-либо строгости.

A fold - это операция в List[A] (то есть список, содержащий элементы типа A), который примет начальное состояние s0: S (т.е. экземпляр типа S) и функция f: (S, A) => S (то есть функция, которая принимает текущее состояние и элемент из списка и дает следующее состояние, то есть обновляет состояние в соответствии со следующим элементом).

Затем операция будет перебираться по элементам списка, используя каждый, чтобы обновить состояние в соответствии с заданной функцией. В Java это будет что-то вроде:

interface Function<T, R> { R apply(T t); }
class Pair<A, B> { ... }
<State> State fold(List<A> list, State s0, Function<Pair<A, State>, State> f) {
  State s = s0;
  for (A a: list) {
    s = f.apply(new Pair<A, State>(a, s));
  }
  return s;
}

Например, если вы хотите добавить все элементы List[Int], состояние будет частичной суммой, которая должна быть инициализирована до 0, а новое состояние, созданное функцией, просто добавит текущий состояние к обрабатываемому элементу:

myList.fold(0)((partialSum, element) => partialSum + element)

Попробуйте написать fold, чтобы умножить элементы списка, затем еще один, чтобы найти экстремальные значения (max, min).

Теперь приведенная выше сводка немного сложнее, так как состояние состоит из нового списка, создаваемого вместе с максимальным элементом, найденным до сих пор. Функция, которая обновляет состояние, более или менее понятна, когда вы понимаете эти понятия. Он просто помещает в новый список минимум между текущим максимумом и текущим элементом, тогда как другое значение переходит к текущему максимуму обновленного состояния.

Что немного сложнее, чем понимать это (если у вас нет фона FP), нужно придумать это решение. Однако, это только для того, чтобы показать вам, что оно существует, может быть сделано. Это просто совершенно другое мышление.

EDIT: Как вы видите, первый и второй case в предлагаемом решении используются для настройки складки. Это эквивалентно тому, что вы видите в других ответах, когда они делают xs.tail.fold((xs.head, ...)) {...}. Обратите внимание, что предлагаемые до сих пор решения с использованием xs.tail/xs.head не охватывают случай, когда xs является List(), и выдает исключение. Решение выше вернет List() вместо этого. Поскольку вы не указали поведение функции в пустых списках, они действительны.

Ответ 9

Другой соперник. Это использует ListBuffer, например, второе предложение Daniel, но делится хвостом post-max исходного списка, избегая его копирования.

  def shareTail(xs: List[Int]): List[Int] = {
    var res = ListBuffer[Int]()
    var maxTail = xs
    var first = true;
    var x = xs
    while ( x != Nil ) {
      if (x.head > maxTail.head) {
          while (!(maxTail.head == x.head)) {
              res += maxTail.head
              maxTail = maxTail.tail
          }
      }
      x = x.tail
    }
    res.prependToList(maxTail.tail)
  }

Ответ 10

Другой вариант будет:

package code.array

object SliceArrays {
  def main(args: Array[String]): Unit = {
    println(removeMaxCool(Vector(1,2,3,100,12,23,44)))
  }
  def removeMaxCool(xs: Vector[Int]) = xs.filter(_ < xs.max)
}

Используя Vector вместо List, причина в том, что Vector более универсален и имеет лучшую общую производительность и сложность по сравнению с List.

Рассмотрим следующие операции с коллекциями: head, tail, apply, update, prepend, append

Вектор занимает амортизированное постоянное время для всех операций, согласно документации Scala: "Операция фактически занимает постоянное время, но это может зависеть от некоторых предположений, таких как максимальная длина вектора или распределение ключей хеша"

В то время как List занимает постоянное время только для операций head, tail и prepend.

С помощью

скаляк -print

генерирует:

package code.array {
  object SliceArrays extends Object {
    def main(args: Array[String]): Unit = scala.Predef.println(SliceArrays.this.removeMaxCool(scala.'package'.Vector().apply(scala.Predef.wrapIntArray(Array[Int]{1, 2, 3, 100, 12, 23, 44})).$asInstanceOf[scala.collection.immutable.Vector]()));
    def removeMaxCool(xs: scala.collection.immutable.Vector): scala.collection.immutable.Vector = xs.filter({
  ((x$1: Int) => SliceArrays.this.$anonfun$removeMaxCool$1(xs, x$1))
}).$asInstanceOf[scala.collection.immutable.Vector]();
    final <artifact> private[this] def $anonfun$removeMaxCool$1(xs$1: scala.collection.immutable.Vector, x$1: Int): Boolean = x$1.<(scala.Int.unbox(xs$1.max(scala.math.Ordering$Int)));
    def <init>(): code.array.SliceArrays.type = {
      SliceArrays.super.<init>();
      ()
    }
  }
}