Выполнение реализаций неизменяемого множества в Scala - PullRequest
Новая
       23

Выполнение реализаций неизменяемого множества в Scala

11 голосов
/ 04 августа 2011

Я недавно погрузился в Scala и (возможно, как и ожидалось) потратил довольно много времени на изучение API неизменяемых коллекций в стандартной библиотеке Scala.

Я пишу приложение, которое обязательно выполняет много + /- операции на больших наборах.По этой причине я хочу убедиться, что выбранная мной реализация представляет собой так называемую «постоянную» структуру данных, чтобы избежать копирования при записи.Я видел этот ответ Мартина Одерского, но это не совсем прояснило для меня проблему.

Я написал следующий тестовый код, чтобы сравнить производительность ListSet и HashSet для операций добавления.: 

import scala.collection.immutable._

object TestListSet extends App {
  var set = new ListSet[Int]
  for(i <- 0 to 100000) {
    set += i
  }
}

object TestHashSet extends App {
  var set = new HashSet[Int]
  for(i <- 0 to 100000) {
    set += i
  }
}

Вот примерное измерение времени выполнения HashSet: 

$ time scala TestHashSet

real    0m0.955s
user    0m1.192s
sys     0m0.147s

И ListSet: 

$ time scala TestListSet

real    0m30.516s
user    0m30.612s
sys     0m0.168s

Минусы в односвязном списке - это константавремя работы, но эта производительность выглядит линейной или хуже.Связано ли это снижение производительности с необходимостью проверки каждого элемента набора на предмет равенства объектов на соответствие инварианту Set без дубликатов?Если это так, я понимаю, что это не связано с «постоянством».

Что касается официальной документации, все, что я мог найти, - это следующая страница, но она кажется неполной: Scala 2.8 API коллекций -Характеристики производительности .Поскольку изначально ListSet, по-видимому, является хорошим выбором для своего объема памяти, возможно, в документации API должна быть некоторая информация о его производительности.

Ответы [ 3 ]

9 голосов
/ 19 июня 2013

Старый вопрос, но также хороший пример выводов, сделанных на неправильном основании.

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

Почему? Потому что JVM делает много других вещей, кроме выполнения кода в ваших примерах. Он загружает классы, выполняет сборку мусора, компилирует байт-код в собственный код и т. Д. Все динамически и на основе различных метрик, выбранных во время выполнения.

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

Чтобы правильно выполнить микро-тест, вы должны:

  1. Прогрев JVM: загрузите все классы, убедитесь, что все пути кода в бенчмарке запущены и горячие точки в коде скомпилированы (например, метод +=).
  2. Запустите тест и убедитесь, что ни GC, ни компилятор не работают во время теста (используйте флаги JVM -XX:-PrintCompilation и -XX:-PrintGC). Если любой из них выполняется во время теста, отмените результат.
  3. Повторите шаг 2 и выберите 10-15 хороших измерений. Рассчитать дисперсию и стандартное отклонение.
  4. Оценка: если среднее значение каждого эталонного теста +/- 3 не пересекается, то вы можете сделать вывод о том, что быстрее. В противном случае это размытый результат (в зависимости от степени совпадения).

Я могу порекомендовать прочитать Рекомендации Oracle по выполнению микро-тестов и отличную статью о подводных камнях Брайана Гетца.

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

8 голосов
/ 05 августа 2011

Ключевая строка из источника ListSet (внутри подкласса Node): 

override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e)

, где вы можете видеть, что элемент добавляется, только если он еще не содержится.Таким образом, добавление к набору O(n).Как правило, можно предположить, что XMap имеет характеристики производительности, аналогичные XSet, и ListMap всегда указывается как линейное время.Вот почему и именно так должен вести себя набор.

PS В случае TestHashSet вы измеряете время запуска.Это более чем в 30 раз быстрее.

5 голосов
/ 05 августа 2011

Поскольку набор должен иметь без дубликатов, перед добавлением элемента, набор должен проверить, чтобы увидеть, содержит ли он уже элемент.Этот поиск в списке, который не имеет гарантии положения элемента, будет O (N) линейным временем.Та же общая идея применима к его операции удаления.

С помощью HashSet класс определяет функцию, которая выбирает местоположение для любого элемента в O (1), что делает метод contains (element) намного быстрее, взатраты на занятие большего пространства, чтобы уменьшить вероятность столкновения местоположения элемента.

...