Python: szybsze działanie do indeksowania

Question

Mam następujący fragment kodu, który wydobywa indeksy wszystkich unikalnych wartości (hashable) w sekwencji podobny data z indeksów kanonicznych i przechowywać je w słowniku jako list:

from collections import defaultdict 
idx_lists = defaultdict(list) 
for idx, ele in enumerate(data): 
    idx_lists[ele].append(idx) 

ten wygląda na dość powszechny przypadek użycia. I zdarza się, że 90% czasu wykonania mojego kodu jest wydawane w tych kilku liniach. Ta część przechodzi przez ponad 10000 razy podczas wykonywania, a len(data) jest od około 50000 do 100000 za każdym razem, gdy jest uruchamiana. Liczba unikatowych elementów waha się w przybliżeniu od 50 do 150.

Czy jest szybszy sposób, być może wektoryzowany/rozszerzony na c (np. Metody numpy lub pandas), który zapewnia to samo?

Wielkie dzięki.

Answer 1

I znaleziono to pytanie jest bardzo interesująca i chociaż nie mógł uzyskać znaczną poprawę w porównaniu z innymi proponowanymi metodami, w których znalazłem czystą metodę numpy, która była nieco szybsza niż inne proponowane metody.

import numpy as np 
import pandas as pd 
from collections import defaultdict 

data = np.random.randint(0, 10**2, size=10**5) 
series = pd.Series(data) 

def get_values_and_indicies(input_data): 
    input_data = np.asarray(input_data) 
    sorted_indices = input_data.argsort() # Get the sorted indices 
    # Get the sorted data so we can see where the values change 
    sorted_data = input_data[sorted_indices] 
    # Find the locations where the values change and include the first and last values 
    run_endpoints = np.concatenate(([0], np.where(sorted_data[1:] != sorted_data[:-1])[0] + 1, [len(input_data)])) 
    # Get the unique values themselves 
    unique_vals = sorted_data[run_endpoints[:-1]] 
    # Return the unique values along with the indices associated with that value 
    return {unique_vals[i]: sorted_indices[run_endpoints[i]:run_endpoints[i + 1]].tolist() for i in range(num_values)} 


def by_dd(input_data): 
    idx_lists = defaultdict(list) 
    for idx, ele in enumerate(input_data): 
     idx_lists[ele].append(idx) 
    return idx_lists 

def by_pand1(input_data): 
    idx_lists = defaultdict(list) 
    return {k: v.tolist() for k,v in series.groupby(input_data).indices.items()} 

def by_pand2(input_data): 
    return series.groupby(input_data).indices 

def data_to_idxlists(input_data): 
    u, ixs = np.unique(input_data, return_inverse=True) 
    return {u: np.nonzero(ixs==i) for i, u in enumerate(u)} 

def data_to_idxlists_unique(input_data): 
    sorting_ixs = np.argsort(input_data) 
    uniques, unique_indices = np.unique(input_data[sorting_ixs], return_index = True) 
    return {u: sorting_ixs[start:stop] for u, start, stop in zip(uniques, unique_indices, list(unique_indices[1:])+[None])} 

Uzyskane czasy były (od najszybszego do najwolniejszego):

>>> %timeit get_values_and_indicies(data) 
100 loops, best of 3: 4.25 ms per loop 
>>> %timeit by_pand2(series) 
100 loops, best of 3: 5.22 ms per loop 
>>> %timeit data_to_idxlists_unique(data) 
100 loops, best of 3: 6.23 ms per loop 
>>> %timeit by_pand1(series) 
100 loops, best of 3: 10.2 ms per loop 
>>> %timeit data_to_idxlists(data) 
100 loops, best of 3: 15.5 ms per loop 
>>> %timeit by_dd(data) 
10 loops, best of 3: 21.4 ms per loop 

i należy zauważyć, że w przeciwieństwie do by_pand2 wynika dict list, jak podano w przykładzie. Jeśli wolisz zwrócić defaultdict możesz po prostu zmienić ostatni raz na return defaultdict(list, ((unique_vals[i], sorted_indices[run_endpoints[i]:run_endpoints[i + 1]].tolist()) for i in range(num_values))), co zwiększyło ogólny czas w moich testach do 4,4 ms.

Na koniec należy zauważyć, że te terminy są wrażliwe na dane. Gdy stosuje się tylko 10 różnych wartości mam:

1. get_values_and_indicies: 4,34 ms w każdej pętli
2. data_to_idxlists_unique: 4,42 ms na pętli
3. by_pand2: 4,83 ms na pętli
4. data_to_idxlists: 6,09 ms na pętli
5. by_pand1: 9,39 ms na pętlę
6. przez_dd: 22.4 ms w każdej pętli

, a jeśli stosuje się 10,000 różne wartości, że otrzymał:

1. get_values_and_indicies: 7,00 ms w każdej pętli
2. data_to_idxlists_unique: 14,8 ms na pętli
3. by_dd: 29,8 ms na pętli
4. by_pand2: 47,7 ms na pętli
5. by_pand1: 67,3 ms na pętli
6. data_to_idxlists: 869 ms na pętlę

Answer 2

Nie tak imponująca, jak się początkowo spodziewałem (na ścieżce do kodowania grupowego wciąż jest sporo czystego Pythona), ale możesz zmniejszyć czas o 2-4, w zależności od tego, ile dbasz o dokładnych typów końcowych uczestniczących:

import numpy as np, pandas as pd 
from collections import defaultdict 

def by_dd(data): 
    idx_lists = defaultdict(list) 
    for idx, ele in enumerate(data): 
     idx_lists[ele].append(idx) 
    return idx_lists 

def by_pand1(data): 
    return {k: v.tolist() for k,v in data.groupby(data.values).indices.items()} 

def by_pand2(data): 
    return data.groupby(data.values).indices 

data = pd.Series(np.random.randint(0, 100, size=10**5))  

daje mi

>>> %timeit by_dd(data) 
10 loops, best of 3: 42.9 ms per loop 
>>> %timeit by_pand1(data) 
100 loops, best of 3: 18.2 ms per loop 
>>> %timeit by_pand2(data) 
100 loops, best of 3: 11.5 ms per loop 

Answer 3

Choć nie jest to idealne rozwiązanie (to o (NlogN) zamiast o (n)), znacznie szybciej, wektorowy sposób to zrobić:

def data_to_idxlists(data): 
    sorting_ixs = np.argsort(data) 
    uniques, unique_indices = np.unique(data[sorting_ixs], return_index = True) 
    return {u: sorting_ixs[start:stop] for u, start, stop in zip(uniques, unique_indices, list(unique_indices[1:])+[None])} 

Innym rozwiązaniem, które jest O (N * U) (w którym U oznacza liczbę unikalnych grup)

def data_to_idxlists(data): 
    u, ixs = np.unique(data, return_inverse=True) 
    return {u: np.nonzero(ixs==i) for i, u in enumerate(u)}