История изменений

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

Если я все правильно понял, можно делать так: перевести все эти множества в упорядоченные последовательности 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);. Есть и другой вариант, использовать PSHUFB, см http://wm.ite.pl/articles/sse-popcount.html https://news.ycombinator.com/item?id=11277891