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

Question

В этом фрагменте кода Python

fun перебирает массив arr и подсчитывает количество идентичных целых чисел в двух разделах массива для каждой пары разделов.(Он имитирует матрицу.) Это делает n*(n-1)/2*m сравнений в общей сложности, давая сложность по времени O(n^2).

Существуют ли программные решения или способы переформулирования этой проблемы, которые дали бы эквивалентные результаты, но сократили бы времясложность?

# n > 500000, 0 < i < n, m = 100
# dim(arr) = n*m, 0 < arr[x] < 4294967311

arr = mp.RawArray(ctypes.c_uint, n*m)

def fun(i):
    for j in range(i-1,0,-1):
        count = 0
        for k in range(0,m):
            count += (arr[i*m+k] == arr[j*m+k])
        if count/m > 0.7:
            return (i,j)
    return ()

• arr - это массив совместно используемой памяти, поэтому его лучше хранить только для чтения из соображений простоты и производительности.

• arr реализован как 1D RawArray от multiprocessing.Причиной этого является самая быстрая производительность по моим тестам.Например, использование двумерного массива numpy, например, такого:

  arr = np.ctypeslib.as_array(mp.RawArray(ctypes.c_uint, n*m)).reshape(n,m)
  

  обеспечит возможности векторизации, но увеличит общее время выполнения на порядок - 250 с против 30 с для n = 1500, что составляетдо 733% .

Answer 1

Так что, немного поиграв, я смог значительно сократить время работы с помощью векторизации NumPy и JIT-компилятора Numba.Возвращаясь к исходному коду:

arr = mp.RawArray(ctypes.c_uint, n*m)

def fun(i):
    for j in range(i-1,0,-1):
        count = 0
        for k in range(0,m):
            count += (arr[i*m+k] == arr[j*m+k])
        if count/m > 0.7:
            return (i,j)
return ()

Мы можем опустить нижнее утверждение return, а также отказаться от идеи использования count полностью, оставив нам:

def fun(i):
    for j in range(i-1,0,-1):
        if sum(arr[i*m+k] == arr[j*m+k] for k in range(m)) > 0.7*m:
            return (i,j)

Затем мы изменяем массив arr на формат NumPy:

np_arr = np.frombuffer(arr,dtype='int32').reshape(m,n)

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

Наконец, мы применяем декоратор Numba и переписываем функцию sum в векторной форме, чтобы она работала с новым массивом:

import numba as nb
@nb.njit(fastmath=True,parallel=True)
def fun(i):
    for j in range(i-1, 0, -1):
        if np.sum(np_arr[i] == np_arr[j]) > 0.7*m:
            return (i,j)

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

Answer 2

Поскольку вы не можете изменить характеристики массива вообще, я думаю, что вы застряли с O (n ^ 2) .numpy получит некоторую векторизацию, но изменит доступ для других, разделяющих массив.Начните с самой внутренней операции:

    for k in range(0,m):
        count += (arr[i][k] == arr[j][k])

Измените это на однострочное назначение:

    count = sum(arr[i][k] == arr[j][k] for k in range(m))

Теперь, если это истинно массив, а несписок списков, используйте векторизацию пакета массива для упрощения циклов, по одному:

    count = sum(arr[i] == arr[j])   # results in a vector of counts

Теперь вы можете вернуть индексы j, где count[j] / m > 0.7.Обратите внимание, что нет реальной необходимости возвращать i для каждого из них: оно является постоянным внутри функции, и вызывающая программа уже имеет значение.В вашем массиве, скорее всего, есть пара векторизованных операций индексирования, которые могут возвращать эти индексы.Если вы используете numpy, их достаточно легко найти на этом сайте.