Python: найти индекс элемента, содержащего X в списке

Question

У меня есть огромный список данных, более 1M записей в форме, аналогичной (хотя это гораздо более простая форма) к этому:

[ 
    {'name': 'Colby Karnopp', 'ids': [441, 231, 822]}, 
    {'name': 'Wilmer Lummus', 'ids': [438, 548, 469]}, 
    {'name': 'Hope Teschner', 'ids': [735, 747, 488]}, 
    {'name': 'Adolfo Fenrich', 'ids': [515, 213, 120]} 
    ... 
] 

Учитывая id 735, я хочу найти индекс 2 для Hope Teschner, так как данный идентификатор попадает в список идентификаторов для Hope. Каков наилучший (по производительности) способ сделать это?

Спасибо за любые советы.

EDIT

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

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

EDIT EDIT

Я просто сделал некоторые бенчмаркинг, и кажется, что восстановление словаря довольно быстро, даже для 1M + записей. Я думаю, что я продолжу это решение на данный момент.

Answer 1

Простейший способ получить первый индекс, удовлетворяющий условию (в Python 2.6 или лучше:

next((i for i, d in enumerate(hugelist) if 735 in d['ids']), None) 

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

Если вам нужно выполнить этот вид операции более чем несколько раз между изменениями в hugelist или его содержимом, то, как вы укажете во втором редактировании на свой вопрос, построение вспомогательного dict (от целого до индекса первого dict, содержащего это). Так как вы хотите, применимый индекс первого, вы хотите, чтобы перебирать в обратном направлении (так хитами, которые находятся ближе к началу hugelist перекроет те, которые в дальнейшем) - например:

auxdict = {} 
L = len(hugelist) - 1 
for i, d in enumerate(reversed(hugelist)): 
    auxdict.update(dict.fromkeys(d['ids'], L-i)) 

[[Вы не можете используйте reversed(enumerate(..., потому что enumerate возвращает итератор, а не список, а reversed оптимизирован для работы только с аргументом последовательности - откуда требуется L-i]].

Вы можете построить auxdict другими способами, в том числе и без обращения, например:

auxdict = {} 
for i, d in enumerate(hugelist): 
    for item in d['ids']: 
    if item not in auxdict: auxdict[item] =i 

, но это, вероятно, будет существенно медленнее из-за огромного количества if, что выполнить во внутреннем цикле.Прямой dict конструктор (с последовательностью ключа, значение пара), вероятно, также будет медленнее из-за необходимость внутренних петель:

L = len(hugelist) - 1 
auxdict = dict((item, L-i) for i, d in enumerate(reversed(hugelist)) for item in d['ids']) 

Однако, это лишь качественные соображения - рассмотреть возможность запуска тестов в течение нескольких «типичные/представительные» примеры значений, которые вы могли бы иметь в hugelist (используя timeit в командной строке, как я часто рекомендовал) до измеряют относительные скорости этих подходов (а также то, как их время выполнения сравнивается с этим невооруженного поиска, как я показал в начале этого ответа - это соотношение, а также среднее число поисков, которые вы ожидаете выполнять между последовательными изменениями hugelist, wi вы сможете выбрать общую стратегию).

Answer 2

Производительность, если у вас есть записи 1M, вы можете переключиться на базу данных или другую структуру данных. С данной структурой данных это будет линейная операция времени. Вы могли бы создать идентификатор для записей dict, но если вы планируете часто выполнять этот запрос.

Answer 3

Лучшим способом, вероятно, будет установка обратного dict() от идентификаторов к именам.

Answer 4

Может ли два или более диктофона использовать один и тот же идентификатор? Если это так, я полагаю, вам нужно будет вернуть список индексов.

Если вы хотите, чтобы сделать поиск одноразового, то вы можете сделать это с помощью списка понимания:

>>> x = [ 
... {'name': 'Colby Karnopp', 'ids': [441, 231, 822]}, 
... {'name': 'Wilmer Lummus', 'ids': [438, 548, 469]}, 
... {'name': 'Hope Teschner', 'ids': [735, 747, 488]}, 
... {'name': 'Adolfo Fenrich', 'ids': [515, 213, 120]}, 
     ... 
... ] 

>>> print [idx for (idx, d) in enumerate(x) if 735 in d['ids']] 
[2] 

Однако, если вы хотите сделать это много, и список не изменится, то это намного лучше создать обратный индекс:

>>> indexes = dict((id, idx) for (idx,d) in enumerate(x) for id in d['ids']) 
>>> indexes 
{213: 3, 515: 3, 548: 1, 822: 0, 231: 0, 488: 2, 747: 2, 469: 1, 438: 1, 120: 3, 441: 0, 735: 2} 
>>> indexes[735] 
2 

NB: приведенный выше код предполагает, что каждый идентификатор уникален. Если есть дубликаты, замените dict с помощью файла collection.defaultdict (list).

NNB: приведенный выше код возвращает индекс в исходный список, поскольку это то, о чем вы просили. Однако, вероятно, лучше вернуть фактический dict вместо индекса, если вы не хотите использовать индекс для его удаления из списка.

Answer 5

Если частота создания индекса низок:

Создать подстановки массив значений индекса в основной список, таким образом, что, например,

lookup = [-1,-1,-1...] 

... 
def addtolookup 
... 

mainlistindex =lookup[myvalue] 
if mainlistindex!=-1: 
name=mainlist[mainlistindex].name 

Если frwquency высок, считает сортировочный подход (I думайте, что это то, что подразумевается под ответом Шварцского преобразования). Это может быть полезно, если у вас возникли проблемы с производительностью при восстановлении вашего дерева всякий раз, когда изменяется исходный список, чем вы с производительностью, получая данные из произведенного индекса; как данные о слотах в существующий список (который (в решающей степени) знает о других возможных совпадениях для идентификатора, когда предыдущая строка наилучшего соответствия перестает ассоциироваться с идентификатором) будет быстрее, чем строить список с нуля на каждой дельта.

EDIT

Это предполагает, что ваши идентификаторы плотно заселены целые числа.

Чтобы увеличить производительность при доступе к отсортированному списку, его можно разделить на блоки, скажем, 400-600 записей, чтобы избежать повторного перемещения всего списка вперед или назад на одну или несколько позиций и поиска с помощью двоичного алгоритма.

Answer 6

Похоже, что структура данных плохо подходит для ее использования. Изменение списка является дорогостоящим - как самим изменением (если вы делаете какие-либо вставки/деления), так и в результате необходимо перестроить dict или выполнять линейное сканирование каждый раз.

Вопрос: как Ваш список меняется?

Возможно, вместо использования индексов (которые часто меняются) вы можете использовать объекты и использовать указатели для самих объектов, а не беспокоиться об индексах?