Nachschlagen große Mengen von Schlüsseln: Wörterbuch vs. NumPy Array

Question

Ich habe eine sehr große (200k +) Satz von Schlüssel/Wert-Paaren, für die ich sehr große (manchmal alle) der Werte abrufen müssen. Der offensichtliche Weg, dies zu tun, ist mit einem Wörterbuch, so dass

values = {lookup.get(key) for key in key_set} 

Dies ist sehr zeit immer in meinem Code aufwendig, und ich frage mich, ob es ein schnellerer Weg, dies mit einem Array NumPy zu implementieren. Ich habe experimentiert mit einem Array mit zwei Spalten mit und n Reihen, so dass für jeden einzelnen Schlüssel:

value = lookup_array[lookup_array[:,0] == key, 1] 

Aber ich bin nicht sicher, wie dies ohne aufwendige Iteration bis zu vielen Schlüssel zu skalieren. Ich habe mir angeschaut:

values = lookup_array[np.in1d(lookup_array[:,0], key_set), 1] 

aber das scheint auch zeitaufwendig.

Gibt es eine andere Möglichkeit, eine massive Suche nach nicht konsekutiven Werten schnell ohne Iteration durchzuführen?

Answer 1

Hier ein Ansatz mit np.searchsorted -

row_idx = np.searchsorted(lookup_array[:,0],key_set)[key_set.argsort()] 
values = lookup_array[row_idx,1] 

Dies setzt voraus, dass lookup_array die Schlüssel in seiner ersten Spalte sortiert hat. Wenn das nicht der Fall ist, können Sie das optionale Sortierer-Argument mit np.searchsorted verwenden.

Answer 2

Das Laden eines Wörterbuchs dieser riesigen Speicher ist irgendwie nicht gut und dann der zusätzliche Overhead von Nachschlagen. Wenn es sich um eine Datenstruktur handelt, verwenden Sie relativ häufig eine Datenbank-Engine. Es gibt KEY/VALUE-Datenbanken, wenn Sie SQL nicht mögen. Sie sind für Lookups optimiert.

Answer 3

Wenn bestimmte Sonderbedingungen gelten, können Sie die NumPy-Indizierung als sehr schnelle Alternative zu Dictionary-Lookups verwenden.

• Die Tasten müssen ganze Zahlen sein

• Sie haben genug Speicher eine NumPy Array, dessen Größe so groß wie die maximale Schlüsselwert, den Sie sehen möchten, erstellen (so dass alle Schlüssel zu einem korrespondieren gültige Index in das Array.)

die Idee ist, verwenden

lookup_array = np.empty((M,), dtype=values.dtype) 
lookup_array[keys] = values 
result = lookup_array[key_set] 

statt

result = {lookup_dict.get(key) for key in key_set} 

---

Zum Beispiel

import numpy as np 
import pandas as pd 

def using_dict(lookup_dict, key_set): 
    return {lookup_dict.get(key) for key in key_set} 

def using_array(lookup_array, key_set): 
    return lookup_array[key_set] 

def using_pandas(df, key_set): 
    return df.loc[df['a'].isin(key_set)] 

M = 10**6 
N = 2*10**5 
K = 10**4 
keys = np.random.randint(M, size=(N,)) 
values = np.random.random((N,)) 
lookup_dict = dict(zip(keys, values)) 
lookup_array = np.empty((M,), dtype=values.dtype) 
lookup_array[keys] = values 
df = pd.DataFrame(np.column_stack([keys, values]), columns=list('ab')) 
key_set = np.random.choice(keys, size=(K,)) 

---

Und hier ist ein timeit Benchmark (mit IPython) für die oben genannten Methoden:

In [25]: %timeit using_array(lookup_array, key_set) 
10000 loops, best of 3: 22.4 µs per loop 

In [26]: %timeit using_dict(lookup_dict, key_set) 
100 loops, best of 3: 3.73 ms per loop 

In [24]: %timeit using_pandas(df, key_set) 
10 loops, best of 3: 38.9 ms per loop