schneller Weg, um Vorkommen in einer Liste in Python zu finden

Question

Ich habe eine Reihe von eindeutigen Worten h_unique genannt. Ich habe auch eine 2D-Liste von Dokumenten h_tokenized_doc genannt, die eine Struktur wie hat:

[ ['hello', 'world', 'i', 'am'], 
    ['hello', 'stackoverflow', 'i', 'am'], 
    ['hello', 'world', 'i', 'am', 'mr'], 
    ['hello', 'stackoverflow', 'i', 'am', 'pycahrm'] ] 

und h_unique als:

('hello', 'world', 'i', 'am', 'stackoverflow', 'mr', 'pycharm') 

, was ich will, ist das Auftreten der einzigartigen Worte in den Token versehen finden Dokumentenliste.
Bis jetzt kam ich mit diesem Code, aber das scheint SEHR langsam zu sein. Gibt es dafür einen effizienten Weg?

term_id = [] 
for term in h_unique: 
    print term 
    for doc_id, doc in enumerate(h_tokenized_doc): 
     term_id.append([doc_id for t in doc if t == term]) 

In meinem Fall habe ich eine Dokumentenliste von 7000 Dokumenten, strukturierte wie:

[ [doc1], [doc2], [doc3], ..... ] 

Answer 1

Es ergibt werde langsam sein, weil du deine gesamte Dokumentenliste einmal durchsuchst f oder jedes einzelne Wort. Warum nicht versuchen, die eindeutigen Wörter in einem Wörterbuch zu speichern und für jedes gefundene Wort anzuhängen?

Dies läuft alle Dokumente nur einmal durch.

Von Ihrem obigen Beispiel unique_dict wäre:

{'pycharm': [], 'i': [(0, 2), (1, 2), (2, 2), (3, 2)], 'stackoverflow': [(1, 1), (3, 1)], 'am': [(0, 3), (1, 3), (2, 3), (3, 3)], 'mr': [(2, 4)], 'world': [(0, 1), (2, 1)], 'hello': [(0, 0), (1, 0), (2, 0), (3, 0)]} 

(Natürlich die Typo 'pycahrm' in Ihrem Beispiel unter der Annahme, absichtlich war)

Answer 2

term_id.append([doc_id for t in doc if t == term])

Das wird man nicht doc_id für jeden passenden Begriff hängen; es wird eine vollständige Liste von möglicherweise vielen identischen Werten von doc_id anhängen. Sicher hast du das nicht gewollt.

Basierend auf Ihrem Beispielcode endet term_id als auf den Punkt:

[[0], [1], [2], [3], [0], [], [2], [], [0], [1], [2], [3], [0], [1], [2], [3], [], [1], [], [3], [], [], [2], [], [], [], [], []]

Ist das wirklich das, was Sie gedacht?

Answer 3

Wenn ich das richtig verstanden, und basierend auf Ihrem Kommentar auf die Frage, wo man

ja sagen, weil ein einzelner Begriff in mehreren docs wie im obigen Fall für hallo das Ergebnis erscheinen kann, ist [0,1 , 2, 3] und für Welt ist es [0, 2]

es sieht aus wie das, was Sie tun möchten ist: für jedes der Wörter in der h_unique Liste (die, wie erwähnt, sollte ein set sein, oder Tasten in einem dict, die beide einen Suchzugriff von O(1) haben), gehen Sie durch alle Listen co In der Variablen h_tokenized_doc finden Sie die Indizes, in denen das Wort erscheint.

IF, die tatsächlich ist, was Sie tun möchten, können Sie so etwas wie das folgende tun könnte:

#!/usr/bin/env python 

h_tokenized_doc = [['hello', 'world', 'i', 'am'], 
        ['hello', 'stackoverflow', 'i', 'am'], 
        ['hello', 'world', 'i', 'am', 'mr'], 
        ['hello', 'stackoverflow', 'i', 'am', 'pycahrm']] 

h_unique = ['hello', 'world', 'i', 'am', 'stackoverflow', 'mr', 'pycharm'] 

# Initialize a dict with empty lists as the value and the items 
# in h_unique the keys 
results = {k: [] for k in h_unique} 

for i, line in enumerate(h_tokenized_doc): 
    for k in results: 
     if k in line: 
      results[k].append(i) 
print results 

Welche Ausgänge:

{'pycharm': [], 'i': [0, 1, 2, 3], 'stackoverflow': [1, 3], 'am': [0, 1, 2, 3], 'mr': [2], 'world': [0, 2], 'hello': [0, 1, 2, 3]}

Die Idee, die h_unique Liste verwendet als Schlüssel in einem Wörterbuch (der results = {k: [] for k in h_unique} Teil).

Keys in Wörterbücher haben den Vorteil einer konstanten Lookup-Zeit, die für die if k in line: Teil groß ist (wenn es sich um eine Liste waren, dass inO(n) nehmen würde) und dann prüfen, ob das Wort (der Schlüssel k) in das erscheint Liste.Wenn dies der Fall ist, fügen Sie den Index der list innerhalb der matrix an das Wörterbuch der Ergebnisse.

Obwohl ich nicht sicher bin, ist das, was Sie erreichen möchten, obwohl.

Answer 4

Sie können den Code zu tun, den Trick mit

1. Mit nur einem einzigen for-Schleife

2. Generatoren Wörterbücher für konstante Lookup-Zeit optimieren, wie zuvor vorgeschlagen. Generatoren sind schneller als für Schleifen, weil die Werte erzeugen on the fly

   In [75]: h_tokenized_doc = [ ['hello', 'world', 'i', 'am'], 
       ...: ['hello', 'stackoverflow', 'i', 'am'], 
       ...: ['hello', 'world', 'i', 'am', 'mr'], 
       ...: ['hello', 'stackoverflow', 'i', 'am', 'pycahrm'] ] 
   
   In [76]: h_unique = ('hello', 'world', 'i', 'am', 'stackoverflow', 'mr', 'pycharm') 
   
   In [77]: term_id = {k: [] for k in h_unique} 
   
   In [78]: for term in h_unique: 
       ...:  term_id[term].extend(i for i in range(len(h_tokenized_doc)) if term in h_tokenized_doc[i]) 
   

   , die die Ausgabe

   {'am': [0, 1, 2, 3], 
   'hello': [0, 1, 2, 3], 
   'i': [0, 1, 2, 3], 
   'mr': [2], 
   'pycharm': [], 
   'stackoverflow': [1, 3], 
   'world': [0, 2]} 
   

Eine beschreibende Lösung wäre

In [79]: for term in h_unique: 
    ...:  term_id[term].extend([(i,h_tokenized_doc[i].index(term)) for i in range(len(h_tokenized_doc)) if term in h_tokenized_doc[i]]) 


In [80]: term_id 
Out[80]: 
{'am': [(0, 3), (1, 3), (2, 3), (3, 3)], 
'hello': [(0, 0), (1, 0), (2, 0), (3, 0)], 
'i': [(0, 2), (1, 2), (2, 2), (3, 2)], 
'mr': [(2, 4)], 
'pycharm': [], 
'stackoverflow': [(1, 1), (3, 1)], 
'world': [(0, 1), (2, 1)]}