LINUX.ORG.RU

Быстро найти процент совпадений между двумя множествами с ~1000 элементами

 , , , ,


1

3

Скажем есть заданное множество типа short, которое нужно сравнить с другими множествами (порядка 1_000_000). В каждом множестве примерно 1000 записей. Размеры множеств не равны.

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

Вопрос собственно в том - на GPU или CPU (какой-нибудь современный доступный Xeon) это делать? И нужно ли использовать какие-нибудь интринсики или компилятор GCC сам всё оптимизирует?

По идее нужно на джаве, но можно вынести эту часть на Си, если JIT не сможет заоптимизировать...

★★★★

это скалярным произведением делается

Harald ★★★★★ ()

А почему речь идет о векторах, когда по описанию это, вроде-бы, должны быть упорядоченные множества?

asaw ★★★★★ ()

Давай я намекну: «множесто типа short» может быть представлено, как массив из 65536 элементов. set == 0, если элемента «i». Во множестве нету. Далее замечаем, что в роли элемента такого множества может выступать бит, таким образом любой набор short-ов влезет в 8кб.

А как же нам быстро посчитать пересечение? Ну наверное, используя поэлементный «&» + popcnt.

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

kawaii_neko ★★★★ ()
Ответ на: комментарий от kawaii_neko

Давай я намекну: «множесто типа short» может быть представлено, как массив из 65536 элементов

Сам хоть понял, что сморозил? Каждое множество представлено примерно 1000 элементами. Таких множеств 1_000_000. Заданное множество также представлено примерно 1000 элементами.

set == 0, если элемента «i» Во множестве нету.

А когда ты это успел выяснить?

А как же нам быстро посчитать пересечение? Ну наверное, используя поэлементный «&» + popcnt.

Еще один поумничал. А с чего решил, что это будет быстрее подсчета на GPU?

foror ★★★★ ()
Последнее исправление: foror (всего исправлений: 1)
Ответ на: комментарий от foror

Еще один поумничал. А с чего решил, что это будет быстрее подсчета на GPU?

Алгоритм быстрее железа, т.е. пентиум лучше виндовса? Дожили.

mashina ★★★★★ ()

Вопрос собственно в том - на GPU

Гонять память будешь дольше, чем сравнивать.

И нужно ли использовать какие-нибудь интринсики или компилятор GCC сам всё оптимизирует?

Сам всё сделает. Но лучше ему помочь, выровняв данные https://godbolt.org/g/mz9VBn

utf8nowhere ★★ ()
Ответ на: комментарий от foror

Каждое множество представлено примерно 1000 элементами. Таких множеств 1_000_000

При однобитовой кодировке элемента 128Б на множество, 128М на все множества и быстрый поиск пересечения. В качестве бонуса хорошая параллелизация.

Ах да, всё это - при условии, что элементы множества уникальны.

А с чего решил, что это будет быстрее подсчета на GPU?

Данные на GPU еще надо передать. Пока что не выглядит так, что оно того стоит.

tailgunner ★★★★★ ()
Ответ на: комментарий от tailgunner

при условии, что элементы множества уникальны.

Ты знаешь множества с неуникальными элементами?

utf8nowhere ★★ ()
Ответ на: комментарий от foror

Сам хоть понял, что сморозил?

Ты прикидываешься? set == 1, если значение «i» присутствует во множестве и «0» иначе. Если не доходит, почему любое множество из элементов [0..65535] может быть представлено в виде 8-килобайтного битового вектора, самое время записаться на курсы дворников.

А с чего решил, что это будет быстрее подсчета на GPU?

С того, что пересечение неупорядоченных множеств имеет сложность O(n²), пересечение упорядоченных — O(n+m), упорядочивание — O(n·log(n)). Преобразование множества в битовый массив — O(n) и пересечение битовых массивов опять-таки O(n), только в зависимости от используемых расширений, за одну операцию считается пересечение по 8-64 элементам.

kawaii_neko ★★★★ ()
Ответ на: комментарий от tailgunner

1000 элементов типа short
При однобитовой кодировке элемента 128Б на множество

Речь об однобитной кодировке Попова-Бабушкина? В классической схеме размер битовой маски зависит от диапазона допустимых значений элементов множеств.

kawaii_neko ★★★★ ()
Ответ на: комментарий от kawaii_neko

В классической схеме размер битовой маски зависит от диапазона допустимых значений элементов множеств.

Да, господин фельдмаршал.

tailgunner ★★★★★ ()
Ответ на: комментарий от kawaii_neko

Я поддержу этого оратора, разве что на GPU такой алгоритм может работать быстрее при условии параллельной обработки нескольких пар множеств.

hateyoufeel ★★★★★ ()
Последнее исправление: hateyoufeel (всего исправлений: 1)
Ответ на: комментарий от tailgunner

Данные на GPU еще надо передать. Пока что не выглядит так, что оно того стоит.

Ну вообще при таких размерах впихать должно быть не сложно. Да и алгоритм отлично подходит вроде бы для gpu в плане memory coalescence, не?

invy ★★★★★ ()
Ответ на: комментарий от kawaii_neko

Ты прикидываешься? set == 1, если значение «i» присутствует во множестве и «0» иначе. Если не доходит, почему любое множество из элементов [0..65535] может быть представлено в виде 8-килобайтного битового вектора, самое время записаться на курсы дворников.

Теперь понял ) Спасибо за подробное объяснение, извиняюсь за грубость неуча - это всё аура ЛОРа ) Действительно красиво получается. Я как-то и не подумал, что множество можно отсортировать. А затем забить 0-ми отсутствующие элементы в нумерации от 0 до 65535

foror ★★★★ ()
Последнее исправление: foror (всего исправлений: 1)

Если я все правильно понял, можно делать так: перевести все эти множества в упорядоченные последовательности 0 и 1. Тип short обычно 16-битный, так что получается 2^16 бит надо, чтобы хранить такое множество, что равно 65536 бит - 8192 байт. 8192 байта можно представить как массив из 1024 uint64_t. Потом просто берем два массива из 1024 uint64_t и последовательно пробегаем их, делая побитовый and (это векторизуется, в SSE2 bitwise AND на 128 бит, а на AVX2 есть и для 256 бит, интринсик _mm256_and_si256) и считая единичные биты в «пересечении», для этого в gcc есть __builtin_popcount (), кроме того есть SSE4.2 инструкция POPCNT и интринсик int64_t _mm_popcnt_u64(unsigned __int64 a);. Есть и другой вариант, использовать AVX2 инструкции, см http://wm.ite.pl/articles/sse-popcount.html https://news.ycombinator.com/item?id=11277891

SZT ★★★★★ ()
Последнее исправление: SZT (всего исправлений: 1)
Ответ на: комментарий от kawaii_neko

самое время записаться на курсы дворников

Всё таки сообразил использовать шорты, а не инты ) Так что может еще где пригожусь в ИТ ) А если бы это были инты (4 байта)? Для них есть оптимизации по пересечению множеств? Может быть скинешь какую-нибудь ссылку на книгу/сайт, где об этом можно почитать?

foror ★★★★ ()
Ответ на: комментарий от foror

Нет, например в современных интел атомах эти инструкции не поддерживаются

SZT ★★★★★ ()
Ответ на: комментарий от foror

А если бы это были инты (4 байта)?

Иногда применима «атака в лоб», потому как одно множество весит 512M, а оперативка сегодня относительно недорогая. А когда такое неприменимо, приходится проявлять изобретательность.

kawaii_neko ★★★★ ()
Ответ на: комментарий от invy

ПМСМ, алгоритм подходит для CPU не хуже, чем для GPU, но CPU не нужно возиться с передачей памяти на устройство (и с приемом результатов).

tailgunner ★★★★★ ()
Ответ на: комментарий от tailgunner

У gpu распараллеливание намного лучше. Грубо говоря пересечение двух множеств за один такт наверное можно получить.

invy ★★★★★ ()
Ответ на: комментарий от foror

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

Waterlaz ★★★★★ ()
Ответ на: комментарий от kawaii_neko

приходится проявлять изобретательность.

Изобретательность в том, что в байте N бит, с которыми можно работать напрямую :-) Лол :-)

anonymous ()
Ответ на: комментарий от invy

Если руки дойдут попробую реализовать на OpenCL и на AVX2 для сравнения перформанса. Ссылку потом сюда скину.

foror ★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.