Python-Wörterbuch zu langsam für Kreuzvergleich, Verbesserungen?

Question

Ich kämpfe derzeit mit einem Leistungsproblem bei der Verwendung von Python-Wörterbüchern. Ich habe ein paar riesige dicts (bis zu 30k Einträge), und ich möchte einen Quervergleich über diese Einträge machen. Also, wenn ein Eintrag (Bezeichner ist ein Schlüssel) gegeben ist, wie viele andere Dicts enthalten diesen Eintrag auch mit diesem Schlüssel? Es dauert derzeit bis zu 5 Stunden auf meinem Gerät, aber es sollte in ein paar Minuten funktionieren, um für mein Werkzeug Sinn zu machen. Ich habe bereits versucht, Einträge zu entfernen, um die Suche effizienter zu machen.

all_cached_data ist eine Liste mit diesen Dicts-Listen. ist eine Liste mit Informationen über die Listen in all_cached_data.

appearsin_list = [] 

# first, get all the cached data 
sources = sp.get_sources() 
all_cachedata = [0]*len(sources) 
for source in sources: 
    iscached = source[8] 
    sourceid = int(source[0]) 
    if iscached == "True": 
     cachedata, _ = get_local_storage_info(sourceid) 
    else: 
     cachedata = [] 
    all_cachedata[sourceid-1] = cachedata 

# second, compare cache entries 
# iterate over all cached sources 
for source in sources: 
    sourceid = int(source[0]) 
    datatype = source[3] 
    iscached = source[8] 
    if verbose: 
     print("Started comparing entries from source " + str(sourceid) + 
       " with " + str(len(all_cachedata[sourceid-1])) + " entries.") 

    if iscached == "True": 
     # iterate over all other cache entries 
     for entry in all_cachedata[sourceid-1]: 
      # print("Comparing source " + str(sourceid) + " with source " + str(cmpsourceid) + ".") 
      appearsin = 0 
      for cmpsource in sources: 
       cmpsourceid = int(cmpsource[0]) 
       cmpiscached = cmpsource[8] 
       # find entries for same potential threat 
       if cmpiscached == "True" and len(all_cachedata[cmpsourceid-1]) > 0 and cmpsourceid != sourceid: 
         for cmpentry in all_cachedata[cmpsourceid-1]: 
          if datatype in cmpentry: 
           if entry[datatype] == cmpentry[datatype]: 
            appearsin += 1 
            all_cachedata[cmpsourceid-1].remove(cmpentry) 
            break 

      appearsin_list.append(appearsin) 
      if appearsin > 0: 
       if verbose: 
        print(entry[datatype] + " appears also in " + str(appearsin) + " more source/s.") 
      all_cachedata[sourceid-1].remove(entry) 

avg = float(sum(appearsin_list))/float(len(appearsin_list)) 

print ("Average appearance: " + str(avg)) 
print ("Median: " + str(numpy.median(numpy.array(appearsin_list)))) 
print ("Minimum: " + str(min(appearsin_list))) 
print ("Maximum: " + str(max(appearsin_list))) 

Ich wäre sehr dankbar für einige Tipps zur Beschleunigung dieser.

Answer 1

Ich denke, dass Ihr Algorithmus verbessert werden kann; Nested Loops sind in diesem Fall nicht groß. Ich denke auch, dass Python wahrscheinlich nicht das Beste für dieses spezielle Ziel ist: Verwenden Sie SQL, um zu vergleichen und in einer großen Menge von Daten zu suchen. Sie können etwas wie sqlite_object verwenden, um Ihren Datensatz in einer SQLite-Datenbank zu konvertieren und abzufragen. Wenn Sie mit reinem Python fortfahren möchten, können Sie versuchen, Ihr Skript mit Cython zu kompilieren; Sie können einige vernünftige Verbesserungen in der Geschwindigkeit haben.

http://docs.cython.org/src/tutorial/pure.html

Dann können Sie Ihren Code mit einigem statischen Typ Hinting verbessern:

http://docs.cython.org/src/tutorial/pure.html#static-typing