Python: hoạt động nhanh hơn cho chỉ mục

Question

Tôi có đoạn sau đây trích xuất các chỉ số của tất cả các giá trị duy nhất (hashable) trong một chuỗi như data với các chỉ số kinh điển và lưu trữ chúng trong một cuốn từ điển như danh sách:

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

này trông giống như tôi một trường hợp sử dụng khá phổ biến. Và điều đó xảy ra là 90% thời gian thực thi mã của tôi được chi tiêu trong vài dòng này. Phần này được chuyển qua hơn 10000 lần trong quá trình thực hiện và len(data) là khoảng 50000 đến 100000 mỗi lần chạy. Số lượng các phần tử độc đáo dao động từ 50 đến 150.

Có cách nào nhanh hơn, có thể được vector hóa/c-mở rộng (ví dụ: numpy hoặc pandas phương pháp), có đạt được điều tương tự không?

Rất cám ơn nhiều người.

Answer 1

Tôi tìm thấy câu hỏi này được khá thú vị và trong khi tôi đã không thể có được một cải tiến lớn so với các phương pháp được đề xuất khác mà tôi đã tìm thấy một phương pháp thô lỗ tinh khiết nhanh hơn một chút so với các phương pháp được đề xuất khác.

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])} 

Các timings kết quả là (từ nhanh nhất để chậm nhất):

>>> %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 

và cần lưu ý rằng không giống như by_pand2 nó kết quả một dict danh sách như được đưa ra trong ví dụ. Nếu bạn muốn trả lại số defaultdict, bạn có thể chỉ cần thay đổi thời gian qua thành return defaultdict(list, ((unique_vals[i], sorted_indices[run_endpoints[i]:run_endpoints[i + 1]].tolist()) for i in range(num_values))) để tăng thời gian tổng thể trong các thử nghiệm của tôi lên 4,4 ms.

Cuối cùng, tôi nên lưu ý rằng thời gian này nhạy cảm với dữ liệu. Khi tôi sử dụng chỉ có 10 giá trị khác nhau tôi nhận:

1. get_values_and_indicies: 4,34 ms mỗi vòng lặp
2. data_to_idxlists_unique: 4,42 ms mỗi vòng lặp
3. by_pand2: 4,83 ms mỗi vòng lặp
4. data_to_idxlists: 6,09 ms mỗi vòng lặp
5. by_pand1: 9,39 ms mỗi vòng lặp
6. by_dd: 22.4 ms mỗi vòng lặp

trong khi nếu tôi sử dụng 10.000 giá trị khác nhau tôi nhận:

1. get_values_and_indicies: 7,00 ms mỗi vòng lặp
2. data_to_idxlists_unique: 14,8 ms mỗi vòng lặp
3. by_dd: 29,8 ms mỗi vòng lặp
4. by_pand2: 47,7 ms trên mỗi vòng
5. by_pand1: 67,3 ms mỗi vòng
6. data_to_idxlists: 869 ms trên mỗi vòng

Answer 2

Không ấn tượng như tôi hy vọng ban đầu (vẫn có một chút tinh khiết của Python thuần túy trong đường dẫn mã nhóm), nhưng bạn có thể giảm thời gian xuống theo hệ số 2-4, tùy thuộc vào bao nhiêu bạn quan tâm đến các loại thức chính xác liên quan đến:

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))  

mang lại cho tôi

>>> %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

Mặc dù nó không phải là giải pháp hoàn hảo (nó O (NlogN) thay vì O (N)), nhanh hơn nhiều, vectorized cách thực hiện:

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])} 

Một giải pháp mà là O (N * U), (trong đó U là số lượng các nhóm duy nhất):

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)}