Python: Suche nach dem Index des Elements, das X in der Liste enthält

Question

Ich habe eine riesige Liste von Daten, mehr als 1 Mio. Datensätze in einem Formular, das diesem ähnelt (obwohl es ein viel einfacheres Formular ist):

[
  {'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]} 
  ... 
]

Bei einer ID von 735 möchte ich den Index 2 für Hope Teschner finden, da die angegebene ID in die Liste der IDs für Hope fällt. Wie lässt sich dies am besten bewerkstelligen (in Bezug auf die Leistung)?

Danke für alle Tipps.

EDIT

Wahrscheinlich hätte ich das erwähnen sollen, aber eine id könnte mehr als einmal auftauchen. Für den Fall, dass eine bestimmte id tut mehr als einmal auftauchen, möchte ich den niedrigsten Index für die angegebene ID.

Die Daten in der Liste werden sich häufig ändern, so dass ich zögere, über den Aufbau eines Wörterbuchs zu gehen, da das Wörterbuch bei jeder Aktualisierung der Liste geändert / neu erstellt werden müsste, da die Indizes die Werte im Diktat sind - d.h. die Änderung der Position eines Elements in der Liste würde erfordern, dass jeder Wert im Wörterbuch aktualisiert wird, dessen Index größer ist als der neu geänderte Index.

BEARBEITEN BEARBEITEN

Ich habe gerade ein paar Benchmarks durchgeführt, und es scheint, dass der Wiederaufbau des Wörterbuchs auch bei mehr als 1 Mio. Datensätzen recht schnell geht. Ich denke, ich werde diese Lösung für jetzt verfolgen.

Answer 1

Der einfachste Weg, die erste Index, der die Bedingung erfüllt (in Python 2.6 oder besser:

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

dies ergibt None wenn kein Element die Bedingung erfüllt; allgemeiner könnte man als zweites Argument für den Befehl next einbauen, was auch immer Sie in diesem Fall benötigen, oder das zweite Argument weglassen (und in diesem Fall können Sie einen Satz Klammern entfernen), wenn Sie damit einverstanden sind, eine StopIteration-Ausnahme zu erhalten, wenn kein Element die Bedingung erfüllt (z. B. weil Sie wissen, dass diese Situation unmöglich ist).

Wenn Sie diese Art von Operation mehr als nur ein paar Mal zwischen Änderungen an der hugelist oder dessen Inhalt, dann ist, wie Sie in der zweiten Bearbeitung Ihrer Frage andeuten, die Erstellung eines Hilfsdiktats (von Integer bis zum Index des ersten Diktats, das es enthält) vorzuziehen. Da Sie die erste anwendbaren Index, wollen Sie rückwärts iterieren (also Treffer, die näher am Anfang der hugelist haben Vorrang vor denen, die weiter entfernt liegen) - zum Beispiel:

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

[Sie können nicht verwenden reversed(enumerate(... denn enumerate gibt einen Iterator zurück, keine Liste, und reversed ist so optimiert, dass es nur mit einem Sequenzargument funktioniert - daher die Notwendigkeit für L-i ]].

Sie können bauen auxdict auf andere Weise, zum Beispiel auch ohne Umkehrung:

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

Dies dürfte jedoch aufgrund der großen Anzahl von if die in der inneren Schleife ausgeführt werden. Die direkte dict Konstruktor (der eine Folge von Schlüssel-Wert-Paaren annimmt) ist wahrscheinlich auch langsamer, weil innere Schleifen erforderlich sind:

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

Dies sind jedoch nur qualitative Überlegungen - erwägen Sie, Benchmarks über einige "typische/repräsentative" Beispiele von Werten durchzuführen, die Sie in hugelist (mit timeit an der Eingabeaufforderung, wie ich schon oft empfohlen habe) zu Maßnahme die relativen Geschwindigkeiten dieser Ansätze (sowie deren Laufzeiten im Vergleich zu denen eines ungestützten Lookups, wie ich zu Beginn dieser Antwort gezeigt habe) - dieses Verhältnis sowie die durchschnittliche Anzahl der Lookups, die Sie zwischen aufeinanderfolgenden hugelist Änderungen, hilft Ihnen bei der Auswahl der Gesamtstrategie).

Answer 2

Wenn Sie 1 Mio. Datensätze haben, sollten Sie vielleicht zu einer Datenbank oder einer anderen Datenstruktur wechseln. Mit der gegebenen Datenstruktur ist dies eine Operation mit linearer Zeit. Wenn Sie diese Abfrage jedoch häufig durchführen möchten, können Sie einmalig eine ID to records dict erstellen.

Answer 3

Am besten wäre es wahrscheinlich, ein umgekehrtes dict() von ids zu Namen zu erstellen.

Answer 4

Können zwei oder mehr Dicts dieselbe ID haben? Wenn ja, werden Sie vermutlich eine Liste von Indizes zurückgeben müssen.

Wenn Sie eine einmalige Suche durchführen wollen, können Sie dies mit einem Listenverständnis tun:

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

Wenn Sie dies jedoch häufig tun wollen und sich die Liste nicht oft ändert, ist es viel besser, einen inversen Index zu erstellen:

>>> 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: Der obige Code geht davon aus, dass jede ID eindeutig ist. Wenn es Duplikate gibt, ersetzen Sie das Dict durch ein collections.defaultdict(list).

NNB: Der obige Code gibt den Index in der ursprünglichen Liste zurück, da Sie genau danach gefragt haben. Es ist jedoch wahrscheinlich besser, das eigentliche Diktat anstelle des Indexes zurückzugeben, es sei denn, Sie wollen den Index zum Löschen aus der Liste verwenden.

Answer 5

Wenn die Häufigkeit der Erstellung des Indexes gering ist:

Erstellen Sie ein Nachschlage-Array mit Indexwerten in Ihrer Hauptliste, so dass z.B.

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

...
def addtolookup
...

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

Wenn die Frequenz hoch ist, sollten Sie den Sortieransatz in Betracht ziehen (ich glaube, das ist mit der Antwort "Schwartzsche Transformation" gemeint). Dies könnte gut sein, wenn Sie mehr Probleme mit der Leistung beim Neuaufbau Ihres Baums haben, wenn sich die Quellliste ändert, als mit der Leistung beim Abrufen der Daten aus dem hergestellten Index; da das Einfügen von Daten in eine bestehende Liste (die (entscheidend) die anderen möglichen Übereinstimmungen für eine ID kennt, wenn die vorherige beste Übereinstimmungszeichenfolge nicht mehr mit einer ID verbunden ist) schneller sein wird als das Erstellen einer Liste von Grund auf bei jedem Delta.

エディトリアル

Dabei wird davon ausgegangen, dass Ihre IDs dicht besetzte Ganzzahlen sind.

Um die Leistung beim Zugriff auf die sortierte Liste zu erhöhen, kann sie in Blöcke von z. B. 400-600 Einträgen unterteilt werden, um zu vermeiden, dass die gesamte Liste wiederholt um eine oder mehrere Positionen nach vorne oder hinten verschoben wird, und mit einem binären Algorithmus durchsucht werden.