Блог

Главная - Вопросы по программированию - Как эффективно вычислить количество совпадений во многих списках?

Как эффективно вычислить количество совпадений во многих списках?

#python #numpy

#python #numpy

Вопрос:

Я использую Python 3.8, и мне нужно эффективно вычислять количество совпадений чисел в списке списков.

У меня есть следующий массив:

 x = [[1, 3, 4], [5, 11, 4, 4], ...]

Я хочу вычислить матрицу совпадений следующим образом:

 C[i][j] = # freq(i) * freq(j) summed over all lists k in x

В настоящее время я векторизовал вычисления для каждого списка в x следующим образом:

 for l in x:
  freqs = np.bincount(l, minlength=SIZE)
  C[freqs > 0]  = np.outer(freqs[freqs != 0], freqs)

Проблема в том, что я не вижу способа векторизовать этот внешний цикл. Я также не вижу способа легко ускорить его с помощью параллелизма. C может содержать ~ 1B записей, поэтому параллелизм типа слияния будет сложным для памяти.

Есть ли способ ускорить это?

Примечание: x может иметь ~ 2,5 Млн списков, а C может иметь стороны 75 тыс. (уникальные элементы)

Комментарии:

1. У вас есть массив NxM (который вы можете представить с помощью numpy ndarray), или, как в вашем примере, предлагается просто список списков разной длины?

2. просто список списков с разной длиной. x может содержать более 2 элементов, поэтому массив NxM будет слишком большим

3. Таким образом, вы, вероятно, не сможете легко векторизовать его, используя numpy , тогда. Вы можете попробовать numba , если хотите придерживаться Python.

4. Поскольку каждая итерация внешнего цикла несет значительную полезную нагрузку, векторизация не сильно сэкономит вам, потому что отношение накладных расходов к работе уже невелико.