Быстрый доступ к индексу элемента

Question

Есть лист состоящий из диктов, пример:

testList
[
    {'el1':{'x': 0, 'y': 0, 'z': 0}},
    {'el2':{'x': 1, 'y': 1, 'z': 1}},
    {'el3':{'x': 2, 'y': 2, 'z': 3}}
 ]

Диктов в таком листе 400к+ шт. Необходим быстрый способ, который позволяет получить номер индекса элемента листа. Например: нужен номер индекса элемента листа, в котором 'x' равен 0. Первое, что бросилось в голову, это поиск рекурсивный по типу "половинного деления", сейчас не вспомню как точно этот алгоритм называется. Собственно этот способ был реализован и результат устроил. Но задался вопросом, о том, что я придумал велосипед. Может есть готовая функция в list, которая позволяет искать быстро индекс в листе из диктов или вовсе можно воспользоваться "срезом" и результат по скорости будет тем же?

Answer 1

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

import pandas as pd

testList = [
    {'el1':{'x': 0, 'y': 0, 'z': 0}},
    {'el2':{'x': 1, 'y': 1, 'z': 1}},
    {'el3':{'x': 2, 'y': 2, 'z': 3}},
    {'el4':{'x': 0, 'y': 1, 'z': 3}}]  # <--- добавлен

df = pd.concat(map(pd.Series,testList)).apply(pd.Series).reset_index()

def get_idxs(col,val,df=df):
    return df.loc[df[col]==val].index.tolist()

get_idxs('z',3)  # [2, 3]
get_idxs('x',0)  # [0, 3]
get_idxs('y',1)  # [1, 3]

если эту строчку заменить на такую:

df = pd.concat(map(pd.Series,testList)).apply(pd.Series)

получим такой результат:

get_idxs('x',0)  # ['el1', 'el4']
get_idxs('y',1)  # ['el2', 'el4']

Answer 2

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

testList =\
[
    {'el1':{'x': 0, 'y': 0, 'z': 0}},
    {'el2':{'x': 1, 'y': 1, 'z': 1}},
    {'el3':{'x': 2, 'y': 2, 'z': 3}}
]

testListX = {next(iter(x.values()))['x']: x for x in testList}
print(testListX[1])

Вывод:

{'el2': {'x': 1, 'y': 1, 'z': 1}}

Если x могут повторяться, то код будет немного сложнее - нужно будет хранить не элементы, а списки элементов, но всё же словарь в любом случае это самое быстрое решение со временем доступа O(1).

Answer 3

Постройте индекс - словарь, которые сопоставляет значение и список индексов. Индекс имеет смысл построить один раз и использовать его многократно. В сравнении с исходным списком он не займёт много памяти:

def makeIndex(list_, key):
    d = {}
    for i, item in enumerate(list_):
        for v in item.values():
            d.setdefault(v.get(key), []).append(i)
    return d


testList = [
    {'el1':{'x': 0, 'y': 0, 'z': 0}},
    {'el2':{'x': 1, 'y': 1, 'z': 1}},
    {'el3':{'x': 2, 'y': 2, 'z': 3}}
]


import pprint


for key in 'axyz':
    pprint.pprint((key, makeIndex(testList, key)))

$ python indices.py
('a', {None: [0, 1, 2]})
('x', {0: [0], 1: [1], 2: [2]})
('y', {0: [0], 1: [1], 2: [2]})
('z', {0: [0], 1: [1], 3: [2]})

БЛОГ НА HUSL

Быстрый доступ к индексу элемента

Ответы (3 шт):