Слияние огромных наборов (HashSet) в Scala

Question

У меня есть два огромных (как в миллионах записей) набора (HashSet), которые имеют некоторое (<10%) перекрытие между ними. Мне нужно объединить их в один набор (меня не интересует сохранение исходных наборов). </p>

В настоящее время я добавляю все элементы одного набора в другой с помощью:

setOne ++= setTwo

Это займет несколько минут (после нескольких попыток настроить hashCode () для участников).

Есть идеи, как ускорить процесс?

Answer 1

Вы можете немного повысить производительность с помощью API параллельных коллекций в Scala 2.9.0 +:

setOne.par ++ setTwo

или

(setOne.par /: setTwo)(_ + _)

Answer 2

Есть несколько вещей, которые вы можете попробовать:

• Используйте метод sizeHint, чтобы сохранить наборы в ожидаемом размере.
• Позвоните по номеру useSizeMap(true), чтобы улучшить размеры хеш-таблицы.

Мне кажется, что последний вариант дает лучшие результаты, хотя оба показывают улучшение тестов здесь.

Answer 3

Можете ли вы рассказать мне немного больше о данных в наборах? Причина, по которой я спрашиваю, состоит в том, что для такого рода вещей вы обычно хотите что-то немного специализированное. Вот несколько вещей, которые можно сделать:

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

Я использовал первую стратегию для создания гигантского набора из примерно 8 миллионов целых чисел из примерно 40 тысяч меньших наборов примерно за секунду (на мощном оборудовании в Scala).