Какой алгоритм использует больше памяти?

Question

Какой алгоритм использует больше памяти?

Рейтинг: 0Ответов: 1Опубликовано: 22.08.2023

Есть два двумерных массива numpy (заведомо огромных). Необходимо вывести двумерный массив (два столбца и N строк) пар индексов строк, значения в первых 5ти элементов которых совпадают в обоих массивах. Например:

array1 = np.array([
    [1, 4, 3, 6, 2, 6, 2, 5],
    [7, 3, 5, 2, 4, 6, 7, 2],
    [3, 3, 6, 2, 1, 6, 8, 4],
    [1, 6, 3, 8, 6, 8, 4, 2],
])

array2 = np.array([
    [6, 2, 4, 1, 6, 4, 2, 2],
    [1, 4, 3, 6, 2, 6, 2, 5],
    [1, 6, 3, 8, 6, 8, 4, 2],
    [5, 3, 1, 5, 2, 6, 3, 2],
])

result = np.array([
    [0, 1],
    [3, 2],
])

Есть два варианта реализации

который жрет много памяти:

matches = np.array(np.all((np.round(array1[:,:6], decimals=4)[:, None, :] == np.round(array2[:,:6], decimals=4)[None, :, :]), axis=-1).nonzero()).T

который долгий:

matches = np.array([])
for i in range(array1.shape[0]):
    correspond_map = np.all((np.round(array1[i, :6], decimals=4) == np.round(array2[:,:6], decimals=4)), axis=-1)
    idx = np.where(correspond_map)[0]
    if idx.shape[0] != 0:
        if matches.shape[0] != 0:
            matches = np.vstack((matches, np.array([i, idx[0]])))
        else:
            matches = np.array([i, idx[0]])

я хочу получить количественно (чтоб графики построить) сколько памяти потребляет каждый алгоритм, но пока не нашел решения, как именно. Memory profiler дает какую то дичь, либо я не понял как им пользоваться правильно.

python numpy memory-management profile profiler

Источник: Stack Overflow на русском

Answer 1

▲ 5

Чтобы померять расход памяти в NumPy инструментально используйте numpy.ndarray.nbytes. Чтобы измерения были честными, нужно измерять потребление памяти для всех временных массивов, которые создаются при вычислении выражений.

Оценим расход памяти "вручную". Поставим эксперимент над массивами из 20 и 30 строчек:

@>>> a = np.arange(120).reshape((-1, 6))
@>>> a.shape
(20, 6)
@>>> b = np.arange(180).reshape((-1, 6))
@>>> b.shape
(30, 6)

Преобразуем размерности:

@>>> a2 = a[:, None, :]
@>>> a2.shape
(20, 1, 6)
@>>> b2 = b[None, :, :]
@>>> b2.shape
(1, 30, 6)

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

@>>> c = a2 == b2
@>>> c.shape
(20, 30, 6)

Новый массив стал значительно больше. Сворачиваем последнее измерение:

@>>> c2 = np.all(c, axis=-1)
@>>> c2.shape
(20, 30)

Строим пары:

@>>> c3 = np.array(c2.nonzero()).T
@>>> c3.shape
(20, 2)

В конце массив снова стал небольшим.

Обобщаем:

Имя    Размер           Пример

a      N * 6            20 * 6
b      M * 6            30 * 6

a2     N * 1 * 6        20 * 1 * 6
b2     1 * M * 6        1 * 30 * 6

c      N * M * 6        20 * 30 * 6

c2     N * M            20 * 30

c3     min(M, N) * 2    20 * 2

Максимальное потребление памяти составляет 6NM. В терминах O-большого - O(NM). Если простыми словами, алгоритм потребляет квадратичную память. И поэтому работает за квадрат.

Аналогичный анализ для второго алгоритма даст максимальную память в итерации 6M. Это линейный по памяти алгоритм. К сожалению, из-за ошибки в накоплении результатов (повторяющиеся вызовы np.vstack) он тоже будет работать за квадратичное время.

Выводы: первый алгоритм требует квадратичную память, второй - линейную. Оба алгоритма работают за квадратичное время. Первый кажется быстрее, так как у него меньше константа. На больших массивах тормозить будут оба.

P.S. Линейный алгоритм с линейной памятью:

import numpy as np


array1 = np.array([
    [1, 4, 3, 6, 2, 6, 2, 5],
    [7, 3, 5, 2, 4, 6, 7, 2],
    [3, 3, 6, 2, 1, 6, 8, 4],
    [1, 6, 3, 8, 6, 8, 4, 2],
])

array2 = np.array([
    [6, 2, 4, 1, 6, 4, 2, 2],
    [1, 4, 3, 6, 2, 6, 2, 5],
    [1, 6, 3, 8, 6, 8, 4, 2],
    [5, 3, 1, 5, 2, 6, 3, 2],
])


relation = {}
for i, r in enumerate(np.round(array1[:,:6], decimals=4)):
    relation.setdefault(tuple(r), ([], []))[0].append(i)
for i, r in enumerate(np.round(array2[:,:6], decimals=4)):
    relation.setdefault(tuple(r), ([], []))[1].append(i)

result = []
for i1, i2 in relation.values():
    if i1 and i2:
        result.append((i1, i2))
print(result)

$ python temp.py
[([0], [1]), ([3], [2])]

Какой алгоритм использует больше памяти?

Ответы