Как быстро сравнить много массивов?

Есть два списка массивов: первый — 10 млн. массивов, второй 100 массивов. Все массивы одинаковой длины и отсортированы.
Задача:
Для каждого массива из первого списка собрать статистику совпадений с каждым массивом из второго списка.

Т.е. берем первый массив из 1го списка, сравниваем его с каждым массивом из 2го, а результаты (количество совпавших элементов) заносим в словарь. В словаре ключ — результат, а значение — сколько раз этот результат встретился. Такой словарь надо построить для каждого массива из 1го списка

Пример:
Список 1: {1,2,3}
Список 2: {1,2,3}; {1,2,5}; {1,3,4}; {4,5,6}

Сравниваем массив из 1го списка с каждым из 2го:
{1,2,3} и {1,2,3} — 3 совпавших элемента.
{1,2,3} и {1,2,5} — 2 совпавших элемента.
{1,2,3} и {1,3,4} — 2 совпавших элемента.
{1,2,3} и {4,5,6} — 0 совпавших элементов.

Результат:
{0,1}; //0 совпадений — 1 раз
{1,0}; //1 совпадение — 0 раз
{2,2}; //2 совпадения — 2 раза
{3,1}} //3 совпадения — 1 раз

Пишу на c#, в итоге быстрее решения в лоб ничего не нашел. Пытался представить второй список в виде дерева, но работает медленнее(возможно потому что дерево было построено на словарях).
Когда надо было просто проверить есть ли такой массив в списке, то дерево помогало очень сильно, но тут надо именно посчитать количество совпадений.