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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Или даже так https://godbolt.org/g/sl4HES

Но битами лучше, да.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если я все правильно понял, можно делать так: перевести все эти множества в упорядоченные последовательности 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

https://godbolt.org/g/mz9VBn

Ух ты, крутая штука, схоронил )

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

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

Я как понял AVX2 присутствует во всех современных Intel-их ЦПУ? Даже в моём Core M оно есть.

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

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

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

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

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

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

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

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

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