Was ist die beste Datenstruktur zum Speichern eines Satzes von vier (oder mehr) Werten?

Question

Angenommen, ich habe die folgenden variables und ihre entsprechenden values, die eine record darstellt.

name = 'abc' 
age = 23 
weight = 60 
height = 174 

Bitte beachten Sie, dass die value von types anders sein könnte (string, integer, float, Referenz-to-any-other-Objekt, etc).

Es wird viele records (mindestens> 100.000) geben. Jeder record wird unique sein, wenn all diese vier variables (eigentlich seine values) zusammengefügt werden. Mit anderen Worten, gibt es keine record mit allen 4 values sind die gleichen.

Ich versuche, eine effiziente Datenstruktur in Python zu finden, die mir erlauben wird (Speicher und) records Komplexität basierend auf einem dieser variables in log(n) Zeit abgerufen werden.

Zum Beispiel:

def retrieve(name=None,age=None,weight=None,height=None) 
    if name is not None and age is None and weight is None and height is None: 
     /* get all records with the given name */ 
    if name is None and age is not None and weight is None and height is None: 
     /* get all records with the given age */ 
    .... 
    return records 

Die Art und Weise der retrieve aufgerufen werden soll wie folgt:

retrieve(name='abc') 

Die oben sollte zurückkehren [{name:'abc', age:23, wight:50, height=175}, {name:'abc', age:28, wight:55, height=170}, etc]

retrieve(age=23) 

Die oben zurückkehren sollte [{name:'abc', age:23, wight:50, height=175}, {name:'def', age:23, wight:65, height=180}, etc]

Und ich muss möglicherweise zu diesem Datensatz in Zukunft ein oder zwei weitere variables hinzufügen. Sagen wir zum Beispiel: sex = 'm'. Also muss die retrieve Funktion skalierbar sein.

Also kurz gesagt: Gibt es eine Datenstruktur in Python die storing a record mit n Anzahl von columns ermöglichen (Name, Alter, Geschlecht, wiegen, Höhe, etc.) und retrieving records basierend auf einer beliebigen (einer) der column in logarithmic (oder idealerweise constant - O(1) Nachschlagezeit) Komplexität?

Answer 1

Es gibt nicht eine einzige Datenstruktur in Python gebaut, der alles tut, die Sie wollen , aber es ist ziemlich einfach, eine Kombination von den zu verwenden, die es hat, um Ihre Ziele zu erreichen, und zwar ziemlich effizient.

Zum Beispiel, sagen Sie Ihre Eingabe die folgenden Daten in einer kommagetrennten Wertdatei ist von der ersten Zeile genannt employees.csv mit Feldnamen wie dargestellt definiert:

name,age,weight,height 
Bob Barker,25,175,6ft 2in 
Ted Kingston,28,163,5ft 10in 
Mary Manson,27,140,5ft 6in 
Sue Sommers,27,132,5ft 8in 
Alice Toklas,24,124,5ft 6in 

Der folgenden arbeiten Code, der zeigt, wie um diese Daten in einer Liste von Datensätzen zu lesen und zu speichern, und automatisch separate Nachschlagetabellen zum Auffinden von Datensätzen zu erzeugen, die den Werten der in jedem dieser Datensätze enthaltenen Felder zugeordnet sind.

Die Datensätze sind Instanzen einer Klasse, die von namedtuple erstellt wurde. Dies ist sehr speichereffizient, da jedem ein __dict__ Attribut fehlt, das Klasseninstanzen normalerweise enthalten. Wenn Sie sie verwenden, können Sie auf die einzelnen Felder mit dem Namen mithilfe der Punktsyntax wie record.fieldname zugreifen.

Die Look-up-Tabellen sind defaultdict(list) Instanzen, die im Durchschnitt Wörterbuch ähnlichen O (1) Look-up-Zeiten liefern und erlauben auch mehr Werte mit jedem verbunden sein. Also ist der Nachschlageschlüssel der Wert des gesuchten Feldwertes, und die damit verbundenen Daten sind eine Liste der ganzzahligen Indizes der Person Datensätze, die in der employees Liste mit diesem Wert gespeichert sind - also werden sie alle relativ sein klein.

Beachten Sie, dass der Code für die Klasse vollständig datengesteuert ist, da er keine fest codierten Feldnamen enthält, die alle aus der ersten Zeile der csv-Dateneingabedatei stammen, wenn sie eingelesen wird verwendet werden, müssen alle tatsächlichen retrieve() Methodenaufrufe natürlich gültige Feldnamen-Schlüsselwortargumente enthalten.

aktualisieren

Modified nicht eine Lookup-Tabelle für jeden eindeutigen Wert jedes Feld zu erzeugen, wenn die Datendatei zuerst gelesen wird. Jetzt erstellt die Methode retrieve() sie nur bei Bedarf (und speichert/speichert das Ergebnis für die zukünftige Verwendung). Auch geändert, um in Python 2.7+ einschließlich 3.x zu arbeiten.

from collections import defaultdict, namedtuple 
import csv 

class DataBase(object): 
    def __init__(self, csv_filename, recordname): 
     # Read data from csv format file into a list of namedtuples. 
     with open(csv_filename, 'r') as inputfile: 
      csv_reader = csv.reader(inputfile, delimiter=',') 
      self.fields = next(csv_reader) # Read header row. 
      self.Record = namedtuple(recordname, self.fields) 
      self.records = [self.Record(*row) for row in csv_reader] 
      self.valid_fieldnames = set(self.fields) 

     # Create an empty table of lookup tables for each field name that maps 
     # each unique field value to a list of record-list indices of the ones 
     # that contain it. 
     self.lookup_tables = defaultdict(lambda: defaultdict(list)) 

    def retrieve(self, **kwargs): 
     """ Fetch a list of records with a field name with the value supplied 
      as a keyword arg (or return None if there aren't any). """ 
     if len(kwargs) != 1: raise ValueError(
      'Exactly one fieldname/keyword argument required for function ' 
      '(%s specified)' % ', '.join([repr(k) for k in kwargs.keys()])) 
     field, value = list(kwargs.items())[0] # Get only keyword arg and value. 
     if field not in self.valid_fieldnames: 
      raise ValueError('keyword arg "%s" isn\'t a valid field name' % field) 
     if field not in self.lookup_tables: # Must create field look up table. 
      for index, record in enumerate(self.records): 
       value = getattr(record, field) 
       self.lookup_tables[field][value].append(index) 
     matches = [self.records[index] 
        for index in self.lookup_tables[field].get(value, [])] 
     return matches if matches else None 

if __name__ == '__main__': 
    empdb = DataBase('employees.csv', 'Person') 
    print("retrieve(name='Ted Kingston'): {}".format(empdb.retrieve(name='Ted Kingston'))) 
    print("retrieve(age='27'): {}".format(empdb.retrieve(age='27'))) 
    print("retrieve(weight='150'):".format(empdb.retrieve(weight='150'))) 
    try: 
     print("retrieve(hight='5ft 6in'):".format(empdb.retrieve(hight='5ft 6in'))) 
    except ValueError as e: 
     print("ValueError('{}') raised as expected".format(e)) 
    else: 
     raise type('NoExceptionError', (Exception,), {})(
      'No exception raised from "retrieve(hight=\'5ft\')" call.') 

Ausgang:

retrieve(name='Ted Kingston'): [Person(name='Ted Kingston', age='28', weight='163', height='5ft 10in')] 
retrieve(age='27'): [Person(name='Mary Manson', age='27', weight='140', height='5ft 6in'), 
        Person(name='Sue Sommers', age='27', weight='132', height='5ft 8in')] 
retrieve(weight='150'): None 
retrieve(hight='5ft 6in'): ValueError('keyword arg "hight" is an invalid fieldname') 
          raised as expected 

Answer 2

Da http://wiki.python.org/moin/TimeComplexity wie über dieses:

• Haben Sie ein Wörterbuch für jede Spalte, die Sie interessiert sind - AGE, NAME usw.
• haben die Schlüssel, dass Wörterbücher (AGE, NAME) möglich sein, Werte für gegebene Spalte (35 oder "m").
• Haben Sie eine Liste von Listen, die Werte für eine "Sammlung" darstellen, z. VALUES = [ [35, "m"], ...]
• Lassen Sie den Wert der Spaltenwörterbücher (AGE, NAME) Listen von Indizes aus der VALUES Liste sein.
• Haben Sie ein Wörterbuch, das den Spaltennamen in Listen in VALUES indexiert, so dass Sie wissen, dass die erste Spalte Alter und Sekunde ist Sex (Sie könnten dies vermeiden und Wörterbücher verwenden, aber sie führen große Speicher foerrpint und mit über 100K Objekte dies kann oder nicht ein Problem sein).

Dann wird die retrieve Funktion könnte wie folgt aussehen:

def retrieve(column_name, column_value): 
    if column_name == "age": 
     return [VALUES[index] for index in AGE[column_value]]  
    elif ...: # repeat for other "columns" 

Dann, das ist, was Sie

VALUES = [[35, "m"], [20, "f"]] 
AGE = {35:[0], 20:[1]} 
SEX = {"m":[0], "f":[1]} 
KEYS = ["age", "sex"] 

retrieve("age", 35) 
# [[35, 'm']] 

bekommen Wenn Sie ein Wörterbuch möchten, können Sie folgendes tun:

[dict(zip(KEYS, values)) for values in retrieve("age", 35)] 
# [{'age': 35, 'sex': 'm'}] 

aber wieder, Wörterbücher sind ein wenig h eavy auf der Speicherseite, also wenn Sie mit Wertelisten gehen können, könnte es besser sein.

Sowohl Wörterbuch und Listenabruf sind im Durchschnitt O (1) - Worst Case für Wörterbuch ist O (n) - so sollte dies ziemlich schnell sein. Das zu erhalten wird ein bisschen Schmerz sein, aber nicht so viel. Um zu "schreiben", müssen Sie nur an die VALUES Liste anhängen und dann den Index in VALUES an jedes der Wörterbücher anhängen.

Natürlich dann würde am besten Ihre tatsächliche Umsetzung zu Benchmark und für mögliche Verbesserungen aussehen, aber hoffentlich dieser Sinn machen und loslegen Sie :)

EDIT:

Bitte beachten Sie, dass als @moooeeeep sagte, das wird nur funktionieren, wenn Ihre Werte hashbar sind und daher als Wörterbuchschlüssel verwendet werden können.

Answer 3

Gibt es eine Datenstruktur in Python, die einen Datensatz mit n Anzahl der Spalten zu speichern, die (Name, Alter, Geschlecht, wiegen, Höhe, usw.) und Abrufen von Datensätzen basierend auf einer beliebigen (einer) der Säule in logarithmischer (oder idealerweise konstanter - O (1) Nachschlagzeit) Komplexität?

Nein, es gibt keine. Aber Sie könnten versuchen, eines auf der Grundlage eines Wörterbuchs pro Wertdimension zu implementieren. Solange deine Werte natürlich hashbar sind. Wenn Sie eine benutzerdefinierte Klasse für Ihre Datensätze implementieren, enthält jedes Wörterbuch Verweise auf dieselben Objekte. Dies wird Ihnen etwas Speicher sparen.

Answer 4

Sie könnten logarithmische Zeitkomplexität in einer relationalen Datenbank mit Indizes (O(log(n)**k) mit einzelnen Spaltenindizes) erreichen. Dann können Sie Daten abrufen nur entsprechende SQL-Konstrukt:

names = {'name', 'age', 'weight', 'height'} 

def retrieve(c, **params): 
    if not (params and names.issuperset(params)): 
     raise ValueError(params) 
    where = ' and '.join(map('{0}=:{0}'.format, params)) 
    return c.execute('select * from records where ' + where, params) 

Beispiel:

import sqlite3 

c = sqlite3.connect(':memory:') 
c.row_factory = sqlite3.Row # to provide key access 

# create table 
c.execute("""create table records 
      (name text, age integer, weight real, height real)""") 

# insert data 
records = (('abc', 23, 60, 174+i) for i in range(2)) 
c.executemany('insert into records VALUES (?,?,?,?)', records) 

# create indexes 
for name in names: 
    c.execute("create index idx_{0} on records ({0})".format(name)) 

try: 
    retrieve(c, naame='abc') 
except ValueError: 
    pass 
else: 
    assert 0 

for record in retrieve(c, name='abc', weight=60): 
    print(record['height']) 

Ausgang:

174.0 
175.0