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

Question

Я ищу эффективное по времени решение указанной ниже проблемы, которое использует тот факт, что я хочу выполнить определенную операцию много раз. У меня есть два метода, реализованных ниже, и я заметил, что один из них значительно быстрее. Мне интересно, есть ли более эффективная альтернатива обоим методам.

Входные данные : Матричный мат размерности m * n, заполненный неотрицательными целыми числами (0 <= каждое целое число <= b) Также даны p неотрицательных целых чисел q <sub>1 , q ₂ , ..., q _p (каждый <= b) и векторы v <sub>1 , v ₂ , ..., v _p . Каждая запись в v _j содержит d строковых индексов mat.

Меня интересуют случаи, когда m, p и d большие (~ 10 ⁶ ), n мало (~ 10), а b мало (~ 100).

Выход : для каждой пары (v _j , q _j ), вернуть подсписок строк mat среди v _j [0], v _j [1], ..., v _j [d-1], которые содержат целое число q _j .

Мой подход : Поскольку p может быть большим, я предварительно обработал mat, чтобы определить, содержит ли каждая строка какой-либо из числа между 0 и b. Затем я прошел через векторы v _j , чтобы определить, содержат ли строки mat, определенные их записями, q _j . Я попробовал два разных подхода к хранению, содержит ли каждая строка мата любое целое число от 0 до b. К моему удивлению, я обнаружил, что метод 1 работает значительно быстрее, чем метод 2.

Вопрос : Мне интересно, есть ли лучший (практический) способ предварительной обработки мата, чтобы операции для каждая пара (v _j , q _j ) выполняется максимально быстро.

Редактирование: определение переменной tmp как tmp = isPresent [qs [j]] и итерация элементов tmp дала более быстрое решение, но я надеюсь, что смогу сделать что-то еще быстрее.

Примечание: упорядочение элементов в результате не важно.

# Python code

import random
import numpy
import time

m = 1000000 # number of rows of mat
n = 10 # number of columns of mat
b = 255 # upper bound on entries of mat
d = 10000 # dimension of vec (containing row indices of mat)
p = 100 # number of vecs

# random specification of mat
# mat, vec, and q will be inputs from another part of the project
mat = []
for i in range(m):
    tmp = (numpy.random.permutation(b+1))[0:n]
    mat.append(tmp)

# random specification of vec and q
vecs = []
qs = []
for i in range(p):
    qs.append(random.randrange(0,b+1,1))
    vecs.append((numpy.random.permutation(m))[0:d])


# METHOD 1

# store the rows where each integer occurs
# not too worried about time taken by this step
isPresent = [[False]*m for i in range(b+1)]
for i in range(m):
    for j in mat[i]:
        isPresent[j][i] = True

# mainly care about reducing time from hereon
time1 = 0.0
for j in range(p):
    st1 = time.time()
    result1 = []
    for i in vecs[j]:
        if isPresent[qs[j]][i]:
            result1.append(i)
    time1 += time.time() - st1


# METHOD 2

# store the rows where each integer occurs
# not too worried about time taken by this step
isPresent = [[False]*(b+1) for i in range(m)]
for i in range(m):
    for j in mat[i]:
        isPresent[i][j] = True

# mainly care about reducing time from hereon
time2 = 0.0
for j in range(p):
    st2 = time.time()
    result2 = []
    for i in vecs[j]:
        if isPresent[i][qs[j]]:
            result2.append(i)
    time2 += time.time() - st2


print('time1: ',time1,'  time2: ',time2)

Примечание : Я наблюдаю время1 = 0,46 секунды и время2 = 0,69 секунды на моем ноутбуке

Answer 1

TL; DR: Да, есть гораздо лучший способ вычислить это, используя numpy. Тем не менее, обратите внимание, что существует двумерный шаблон косвенной памяти, который обычно медленный и, как известно, его трудно оптимизировать.

Полезная информация: Случайный доступ к памяти медленный. Действительно, процессору сложно предсказать адрес памяти для извлечения и, таким образом, уменьшить задержку памяти. Это не так уж плохо, если данные помещаются в кеши и используются несколько раз. Случайный доступ к памяти, осуществляемый в огромной области памяти, намного медленнее , и его следует избегать, как чумы (когда это возможно).

Анализ: Оба метода делают случайные косвенные обращения памяти при выполнении выражений isPresent[qs[j]][i] и isPresent[i][qs[j]]. Такие отклонения медленные. Но метод 2 медленнее, так как среднее расстояние между выбранными адресами, как правило, намного больше, чем метод 1, вызывая эффект, называемый кэш-очистка .

Более быстрое решение: Numpy может использоваться для значительного увеличения производительности первого метода (благодаря «векторизованным» нативным методам). Действительно, этот метод использует простые циклы python, которые обычно очень медленные и пересчитывают isPresent[qs[j]] несколько раз. Вот более быстрая реализация:

# Assume vecs is a list of np.arrray rather than a list of list

isPresent = [numpy.array([False]*m) for i in range(b+1)]
for i in range(m):
    for j in mat[i]:
        isPresent[j][i] = True

time3 = 0.0
for j in range(p):
    st3 = time.time()
    tmp = isPresent[qs[j]]
    result3 = numpy.extract(tmp[vecs[j]], vecs[j])
    time3 += time.time() - st3

Результаты производительности:

time1:  0.165357
time2:  0.309095
time3:  0.007201

Новая версия в 23 раза быстрее, чем первый метод, и в 43 раза быстрее, чем секунда.

Обратите внимание, что можно сделать это значительно быстрее, параллельно вычисляя j -l oop, но это немного сложнее.