Scala Set производительность пересечения

Question

Использование Scala's scala.collection.Set[T].Имеется небольшой набор s с несколькими элементами и еще один большой набор b с большим количеством элементов, есть ли разница в производительности между:

s & b // s intersect b

и

b & s // b intersect s.

Если да, какой самый быстрый?

Answer 1

Общая реализация, видимая в GenSetLike с использованием intersect, переопределяется для HashSet реализацией, которая мне кажется довольно сложной (см. scala.collection.immutable.HashSet.HashTrieSet # intersect0 ). Исходя из моего грубого теста, его производительность одинакова для a & b и b & a и аналогична производительности a filter b, что на порядок быстрее, чем b filter a. Мой тестовый код:

object Sets extends App {

  def time[R](block: => R): R = {
    val t0 = System.nanoTime()
    val result = block    // call-by-name
    val t1 = System.nanoTime()
    println("Elapsed time: " + (t1 - t0)/1e6 + "ms")
    result
  }

  val a = (0 until 10000 by 1).toSet      //smaller data
  val b = (0 until 1000000 by 2).toSet


  time {a & b}
  time {b & a}
  time {a & b}
  time {b & a}
  time {a & b}
  time {b & a}

  println("Filter")

  time {a filter b}
  time {b filter a}
  time {a filter b}
  time {b filter a}
  time {a filter b}
  time {b filter a}
}

Результат:

Elapsed time: 6.990442ms
Elapsed time: 4.25017ms
Elapsed time: 4.1089ms
Elapsed time: 4.480789ms
Elapsed time: 3.71588ms
Elapsed time: 3.160159ms
Filter
Elapsed time: 7.781613ms
Elapsed time: 68.33023ms
Elapsed time: 5.858472ms
Elapsed time: 42.491131ms
Elapsed time: 2.982364ms
Elapsed time: 52.762474ms

Answer 2

Ответ: это сложно.

Реализация по умолчанию неизменяемого набора: scala.collection.immutable.Set . Это имеет особых случаев для размеров от 1 до 4. Как только у вас будет более 4 элементов, он будет использовать scala.collection.immutable.HashSet .

Очень маленький с (1..4)

Допустим, у вас есть большой набор b и небольшой набор s, где s содержит <4 элемента. </p>

Тогда получится большая разница:

b & s отфильтрует все элементы b от членства в s и, следовательно, выполнит сравнение равенств b.count * s.count. Поскольку b большое, это будет довольно медленно.

s & b отфильтрует несколько элементов s по отношению к членству в b, которое равно s.length, кратному хэшированию и сравнению на равенство, если хэши совпадают (помните, что b - это HashSet). Поскольку он маленький, он должен быть очень быстрым.

Маленький s (n> 4)

Как только s будет больше, чем 4 элемента, он также станет HashSet. Пересечение для HashSets написано симметрично и очень эффективно. Он объединит древовидные структуры s и b и выполнит сравнение на равенство при совпадении хэшей. Будет использовано максимальное структурное разделение. Например. если b содержит все элементы s, результатом будет тот же экземпляр , что и s, поэтому объекты не будут выделяться.

Общие советы

Если вы просто пишете универсальный код, в котором вас мало заботит высокая производительность, можно использовать реализации по умолчанию, такие как scala.collection.Set. Однако, если вы заботитесь о характеристиках производительности, предпочтительнее использовать конкретную реализацию. Например. если s и b объявлены как scala.collection.immutable.HashSet, вы получите стабильно высокую производительность независимо от порядка при условии, что у вас есть хорошая хеш-функция.

Answer 3

Давайте создадим два набора в соответствии с упомянутым условием

   val a = (0 until 10000 by 1).toSet      //smaller data
   val b = (0 until 1000000 by 2).toSet    //Relatively larger data

мы можем определить функцию времени для проверки времени выполнения, как показано ниже

def time[R](block: => R): R = {
    val t0 = System.nanoTime()
    val result = block    // call-by-name
    val t1 = System.nanoTime()
    println("Elapsed time: " + (t1 - t0) + "ns")
    result
}

Теперь мы можем проверить состояние пересечения

scala> time {a & b}
Elapsed time: 5895220ns
res2: scala.collection.immutable.Set[Int] = Set(892, 5810, 8062, ..)

scala> time {b & a}
Elapsed time: 6038271ns
res3: scala.collection.immutable.Set[Int] = Set(892, 5810, 8062, ...)

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