Эффективная память массив массивных numpy в Python

В настоящий момент каждый вызов np.argsort генерирует (868940742, 1) индексов int64, который сам по себе займет около 7 ГБ. Кроме того, когда вы используете эти индексы для сортировки столбцов full_arr вы генерируете другой (868940742, 1) массив поплавков, так как причудливая индексация всегда возвращает копию, а не представление .

Одним из очевидных улучшений было бы сортировать full_arr на месте с использованием .sort() . К сожалению, .sort() не позволяет вам напрямую указывать строку или столбец для сортировки. Однако вы можете указать поле для сортировки для структурированного массива. Поэтому вы можете принудительно сортировать inplace по одному из трех столбцов, получая view на свой массив в виде структурированного массива с тремя полями поплавка, а затем сортируя по одному из этих полей:

 full_arr.view('f8, f8, f8').sort(order=['f0'], axis=0) 

В этом случае я сортирую full_arr на месте 0-го поля, которое соответствует первому столбцу. Обратите внимание, что я предположил, что есть три столбца float64 ( 'f8' ) – вы должны изменить это соответственно, если ваш тип dtype отличается. Это также требует, чтобы ваш массив был смежным и в основном формате, то есть full_arr.flags.C_CONTIGUOUS == True .

Кредит за этот метод должен пойти к Джо Кингтону за его ответ здесь .

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

  %%timeit -n 1 -r 100 x = np.random.randn(10000, 2); idx = x[:, 0].argsort() x[idx] # 1 loops, best of 100: 148 µs per loop %%timeit -n 1 -r 100 x = np.random.randn(10000, 2); idx = x[:, 0].argsort() np.take(x, idx, axis=0) # 1 loops, best of 100: 42.9 µs per loop 

Однако я бы не ожидал увидеть разницу в использовании памяти, поскольку оба метода будут генерировать копию.

Что касается вашего вопроса о том, почему сортировка второго массива выполняется быстрее – да, вы должны ожидать, что любой разумный алгоритм сортировки будет быстрее, когда в массиве будет меньше уникальных значений, потому что в среднем меньше работы для этого. Предположим, что у меня есть случайная последовательность цифр от 1 до 10:

 5 1 4 8 10 2 6 9 7 3 

Есть 10! = 3628800 возможные способы расположения этих цифр, но только один, в котором они находятся в порядке возрастания. Теперь предположим, что всего 5 уникальных цифр:

 4 4 3 2 3 1 2 5 1 5 

Теперь есть 2⁵ = 32 способа упорядочить эти цифры в порядке возрастания, так как я могу поменять любую пару одинаковых цифр в отсортированном векторе, не нарушая порядок.

По умолчанию np.ndarray.sort() использует Quicksort . qsort вариант этого алгоритма работает рекурсивно выбирая элемент «поворота» в массиве, а затем переназначение массива таким образом, что все элементы меньше , чем значение поворота расположены перед ним, и всеми элементами , больше , чем значение поворота расположены после этого. Значения, равные оси, уже отсортированы. Имея более уникальных значений означает, что, в среднем, больше значения будет равно значению поворота на любой развертки, и, следовательно, меньше метет необходимы для полного сортировки массива.

Например:

 %%timeit -n 1 -r 100 x = np.random.random_integers(0, 10, 100000) x.sort() # 1 loops, best of 100: 2.3 ms per loop %%timeit -n 1 -r 100 x = np.random.random_integers(0, 1000, 100000) x.sort() # 1 loops, best of 100: 4.62 ms per loop 

В этом примере типы двух массивов одинаковы. Если ваш меньший массив имеет меньший размер элемента по сравнению с большим массивом, тогда стоимость его копирования из-за фантазии индексации также будет меньше.

EDIT: Если кто-то новый для программирования и numpy попадает на этот пост, я хочу указать на важность рассмотрения используемого np.dtype . В моем случае я действительно смог уйти с использованием плавающей запятой с половиной точности, то есть np.float16 , которая уменьшила объект на 20 ГБ в памяти до 5 ГБ и сделала сортировку более управляемой. Значение по умолчанию, используемое numpy – np.float64 , что является большой точностью, что вам может и не понадобиться. Ознакомьтесь с документом здесь, где описывается емкость различных типов данных. Спасибо @ali_m за указание на это в комментариях.

Я сделал плохую работу, объясняя этот вопрос, но я обнаружил некоторые полезные обходные пути, которые, по моему мнению, будут полезны для всех, кто должен сортировать по-настоящему массивный массив numpy .

Я строю очень большую матрицу из 22 "поддиапазонов" данных генома человека, содержащих элементы [position, value] . В конечном счете, окончательный массив должен быть численно отсортирован «на месте» на основе значений в конкретном столбце и без перетасовки значений внутри строк.

Размеры подматрицы следуют форме:

 arr1.shape = (N1, 2) ... arr22.shape = (N22, 2) 

sum([N1..N2]) = 868940742 т. е. существует около 1BN позиций для сортировки.

Сначала я обрабатываю 22 под-массива с помощью функции process_sub_arrs , которая возвращает 3-кортеж 1D-массивов той же длины, что и вход. Я складываю 1D массивы в новый (N, 3) массив и вставляю их в массив np.zeros инициализированный для полного набора данных:

  full_arr = np.zeros([868940742, 3]) i, j = 0, 0 for arr in list(arr1..arr22): # indices (i, j) incremented at each loop based on sub-array size j += len(arr) full_arr[i:j, :] = np.column_stack( process_sub_arrs(arr) ) i = j return full_arr 

EDIT: Поскольку я понял, что мой набор данных может быть представлен полуточными поплавками, теперь я инициализирую full_arr следующим образом: full_arr = np.zeros([868940742, 3], dtype=np.float16) , который равен только 1/4 размера и намного проще сортировать.

Результат – массивный массив размером 20 ГБ:

 full_arr.nbytes = 20854577808 

Как отметил @ali_m в своем подробном сообщении, моя ранняя рутина была неэффективной:

 sort_idx = np.argsort(full_arr[:,idx]) full_arr = full_arr[sort_idx] 

массив sort_idx , который составляет 33% от размера full_arr , зависает и full_arr память после сортировки full_arr . Этот тип, предположительно, генерирует копию full_arr из-за «фантазии» индексации, что потенциально увеличивает память до 233% того, что уже используется для хранения массивного массива! Это медленный шаг, который длится около десяти минут и в значительной степени опирается на виртуальную память.

Я не уверен, что «причудливый» вид делает постоянную копию. Наблюдая за использованием памяти на моей машине, кажется, что full_arr = full_arr[sort_idx] удаляет ссылку на несортированный оригинал, потому что примерно через 1 секунду все, что осталось, это память, используемая отсортированным массивом и индексом, даже если есть временная копия.

Более компактным использованием argsort() для сохранения памяти является следующее:

  full_arr = full_arr[full_arr[:,idx].argsort()] 

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

@ali_m указал на хороший трюк (зачисленный Джо Кингтону) за создание де-факто структурированного массива с view о full_arr . Преимущество состоит в том, что они могут быть отсортированы «на месте», поддерживая стабильный порядок строк:

 full_arr.view('f8, f8, f8').sort(order=['f0'], axis=0) 

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

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

Это эскиз конвейера, который я использовал для ускорения массива массива:

 def process_sub_arrs(arr): """process a sub-array and return a 3-tuple of 1D values arrays""" return values1, values2, values3 def build_arr(): """build the initial array by joining processed sub-arrays""" full_arr = np.zeros([868940742, 3]) i, j = 0, 0 for arr in list(arr1..arr22): # indices (i, j) incremented at each loop based on sub-array size j += len(arr) full_arr[i:j, :] = np.column_stack( process_sub_arrs(arr) ) i = j return full_arr def sort_arr(): """return full_arr and sort_idx""" full_arr = build_arr() sort_idx = np.argsort(full_arr[:, index]) return full_arr[sort_idx] def get_sorted_arr(): """call through nested functions to return the sorted array""" sorted_arr = sort_arr() <process sorted_arr> return statistics 

стек вызовов: get_sorted_arr -> sort_arr -> build_arr -> process_sub_arrs

Как только каждая внутренняя функция завершена, get_sorted_arr() наконец, просто удерживает отсортированный массив, а затем возвращает небольшой массив статистики.

EDIT: Здесь также стоит отметить, что даже если вы можете использовать более компактный dtype для представления своего огромного массива, вы захотите использовать более высокую точность для суммарных вычислений. Например, поскольку full_arr.dtype = np.float16 , команда np.mean(full_arr[:,idx]) пытается вычислить среднее значение в точке с плавающей запятой с половинной точностью, но это быстро переполняется при суммировании по массивному массиву. Использование np.mean(full_arr[:,idx], dtype=np.float64) предотвратит переполнение.

Сначала я задал этот вопрос, потому что меня озадачило то, что набор данных одинакового размера внезапно начал забивать мою системную память, хотя была большая разница в пропорции уникальных значений в новом «медленном» наборе. @ali_m отметил, что, действительно, более простые данные с меньшим количеством уникальных значений легче сортировать:

QSort вариант Quicksort работает путем рекурсивного выбор элемента «поворота» в массиве, а затем переназначение массива таким образом, что все элементы меньше, чем значение поворота расположены перед ним, и всеми элементами, больше, чем значение поворота размещены после того, как Это. Значения, которые равны оси вращения, уже отсортированы, поэтому интуитивно, чем меньше уникальных значений в массиве, тем меньше количество свопов, которые необходимо выполнить.

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

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