лучше, чем функция numpy in1d mask: упорядоченные массивы?

Question

Эта операция должна применяться как можно быстрее, как фактические массивы, содержащие миллионы элементов. Это простая версия проблемы.

Итак, у меня есть случайный массив из уникальных целых чисел (обычно миллионы элементов).

totalIDs = [5,4,3,1,2,9,7,6,8 ...]

У меня есть еще один массив (обычно десятки тысяч) уникальных целых чисел который я могу создать маску.

subsampleIDs1 = [5,1,9] 
subsampleIDs2 = [3,7,8] 
subsampleIDs3 = [2,6,9] 
... 

я могу использовать NumPy сделать

маска = np.in1d ​​(totalIDs, subsampleIDs, assume_unique = True)

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

переменная = allvariables [маска] [:, 0]

Теперь, учитывая, что идентификаторы являются уникальными в обоих массивах, есть ли способ, чтобы значительно ускорить этот процесс. Требуется много времени, чтобы создать маску для нескольких тысяч точек (subsampleID), соответствующих миллионам идентификаторов (totalID).

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

for i in range(0,3): 
    mask = np.in1d(totalIDs,subsampleIDs,assume_unique=True) 
    index[mask] = i 

где X находится в subsampleIDsX. Тогда я могу просто сделать:

for i in range(0,3): 
    if index[i] == i: 
     rowmatch = i 
     break 

variable = allvariables[rowmatch:len(subsampleIDs),0] 

правый? Но это также медленно, потому что в цикле есть условие, чтобы найти, когда оно сначала совпадает. Есть ли более быстрый способ найти, когда число сначала появляется в упорядоченном массиве, поэтому условие не замедляет цикл?

Answer 1

Я предлагаю вам использовать DataFrame в панд. индекс DataFrame является идентификатором totalID, и вы можете выбрать subsampleIDs: df.ix[subsampleIDs].

Создать тестовые данные первым:

import numpy as np 
N = 2000000 
M = 5000 
totalIDs = np.random.randint(0, 10000000, N) 
totalIDs = np.unique(totalIDs) 
np.random.shuffle(totalIDs) 
v1 = np.random.rand(len(totalIDs)) 
v2 = np.random.rand(len(totalIDs)) 

subsampleIDs = np.random.choice(totalIDs, M) 
subsampleIDs = np.unique(subsampleIDs) 
np.random.shuffle(subsampleIDs) 

Затем конвертировать вам данные в DataFrame:

import pandas as pd 
df = pd.DataFrame(data = {"v1":v1, "v2":v2}, index=totalIDs) 
df.ix[subsampleIDs] 

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

Answer 2

Часто такой тип индексации лучше всего выполнять с использованием БД (с надлежащим индексированием столбцов).

Еще одна идея состоит в том, чтобы сортировать totalIDs один раз, как этап предварительной обработки, и реализовать собственную версию in1d, которая позволяет избежать сортировки всего. Реализация numpy in1d (по крайней мере, в версии, которую я установил) довольно проста и должна быть легко скопирована и изменена.

EDIT:

Или, еще лучше, использовать ведро сортировки (или Radix сортировка). Это должно дать вам O (N + M), N - размер totalIDs, а M - размер sampleIDs (время, в которое вы можете играть, изменяя количество ковшей). Здесь вы также можете разделить totalIDs на ведра только один раз, что дает вам отличный O (N + M1 + M2 + ...).

К сожалению, я не знаю о реализации Numpy, но я нашел это: http://en.wikipedia.org/wiki/Radix_sort#Example_in_Python