Как быстро заполнить матрицу 100000x100000 в Python с помощью NumPy?

Question

Мне очень нравится структура данных и алгоритмы.

Я работаю с матрицей 80000 X 80000 для вставки данных. Я использую NumPy. И мой код выглядит так:

n = 80000
similarity = np.zeros((n, n), dtype='int8')
for i, photo_i in enumerate(photos):
    for j, photo_j in enumerate(photos[i:]):
       similarity[i, j] = score(photo_i, photo_j)
    if i % 100 == 0:
        print(i)

Этот кусок кода занимает слишком много времени. score функция - O (1). Мне было интересно, может ли быть лучший способ сделать это. Я хочу построить данные этой матрицы в «короткие сроки» возможно. Но, кстати, я делаю это со сложностью O (n ^ 2).

Есть ли "что-нибудь", с чем это можно "оптимизировать" или, возможно, с использованием другой структуры данных?

Я уже читал подобные вопросы по SO, и они упомянули pytables. Я обязательно попробую, но пока не знаю как. Любое предложение приветствуется.

Заранее спасибо.

Answer 1

Есть множество разных вещей, которые вы могли бы сделать, все они вращаются вокруг того, чтобы избежать явных циклов for, которые медленны в Python, и делегировать коду C-уровня (либо используя базовую среду выполнения C Python, либо встроенные методы создания массива numpy). ).

Использование fromfunction

Numpy имеет встроенную функцию для заполнения матрицы из функции, принимающей координаты: numpy.fromfunction . Это может быть быстрее, так как он выполняет все итерации и присваивания в C вместо Python.

Вы должны предоставить ей функцию оценки по координатам, например ::

def similarity_value(i, j, photos=photos):
  return score(photos[i], photos[j])

similarity = numpy.fromfunction(similarity_value, (n, n), dtype='int8')

photos=photos в определении функции делает массив фотографий локальным для функции и экономит некоторое время, обращаясь к ней при каждом вызове; это распространенный метод микрооптимизации Python.

Обратите внимание, что это вычисляет сходство для всей матрицы, а не только треугольника. Чтобы это исправить, вы можете сделать:

def similarity_value(i, j, photos=photos):
  return score(photos[i], photos[j]) if i < j else 0

similarity = numpy.fromfunction(similarity_value, (n, n), dtype='int8')
similarity += similarity.T  # fill in other triangle from transposed matrix

Использование пониманий

Вы также можете попытаться создать матрицу сходства из понимания генератора (или даже из списка), снова избегая явных циклов for в пользу понимания, которое быстрее, но жертвуя оптимизацией треугольника:

similarity = numpy.fromiter((score(photo_i, photo_j) 
                             for photo_i in photos 
                             for photo_j in photos),
                            shape=(n,n), dtype='int8')

# or:
similarity = numpy.array([score(photo_i, photo_j) 
                          for photo_i in photos 
                          for photo_j in photos],
                         shape=(n,n), dtype='int8')

Чтобы заново ввести оптимизацию треугольника, вы можете сделать что-то вроде:

similarity = numpy.array([score(photo_i, photo_j) if i < j else 0
                          for i, photo_i in enumerate(photos)
                          for j, photo_j in enumerate(photos)],
                         shape=(n,n), dtype='int8')
similarity += similarity.T

Использование triu_indices для непосредственного заполнения треугольника

Наконец, вы можете использовать numpy.triu_indices, чтобы назначить непосредственно в верхний (и затем нижний) треугольник матрицы:

similarity_values = (score(photo_i, photo_j
                     for photo_i in photos
                     for photo_j in photos[:i])  # only computing values for the triangle
similarity = np.zeroes((n,n), dtype='int8')
xs, ys = np.triu_indices(n, 1)
similarity[xs, ys] = similarity_values
similarity[ys, xs] = similarity_values
similarity[np.diag_indices(n)] = 1  # assuming score(x, x) == 1

Этот подход основан на следующем вопросе: https://codereview.stackexchange.com/questions/107094/create-symmetrical-matrix-from-list-of-values

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