什麼是存儲一組四個（或更多）值的最佳數據結構？

Question

假設我有以下variables及其對應的values，代表record。

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

請注意，value可能是不同types（string，integer，float，參考到任意-其他對象，等）。

會有很多records（至少> 100,000）。當所有這四個variables（實際上它的values）放在一起時，每個record將是unique。換句話說，不存在record與所有4 values是相同的。

我想在Python找到一個有效的數據結構，這將讓我（商店）基於這些variables在log(n)時間複雜度的任何一個檢索records。

例如：

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 

的方式retrieve應該被稱爲如下：

retrieve(name='abc') 

上述應返回[{name:'abc', age:23, wight:50, height=175}, {name:'abc', age:28, wight:55, height=170}, etc]

retrieve(age=23) 

上述應返回[{name:'abc', age:23, wight:50, height=175}, {name:'def', age:23, wight:65, height=180}, etc]

而且，我將來可能需要在此記錄中添加一個或兩個以上的variables。例如，說，sex = 'm'。因此，retrieve函數必須是可擴展的。

因此，在短期：是否有Python的數據結構，這將使storing a record與column在logarithmic的n數columns（姓名，年齡，性別，體重，身高等），retrieving records基於任何（一個） （或理想情況下查找時間）複雜？

Answer 1

沒有內置到Python的一個數據結構，你想要做的一切，但使用它可以實現您的目標並相當有效地完成的組合相當容易。

例如，假設你的輸入是在一個逗號分隔值文件中的以下數據稱爲employees.csv具有被定義爲示出由第一行的字段名稱：

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 

下面是工作的代碼示出了如何讀取這些數據並將其存儲到記錄列表中，並自動創建單獨的查找表，以查找與這些記錄中每個字段中包含的值相關的記錄。

記錄是由namedtuple創建的類的實例，它具有很高的內存效率，因爲每個類缺少類實例通常包含的__dict__屬性。使用它們可以使用點語法按名稱訪問每個字段，如record.fieldname。

該查找表是defaultdict(list)實例，這提供關於平均類字典ø（1）查找時間，並且還允許多個值與每一個相關聯。因此，查找鍵是要查找的字段值的值，並且與其關聯的數據將是Person列表中存儲的Person記錄的整數索引列表，並且具有該值 - 因此它們都是相對的小。

請注意，該類的代碼完全是數據驅動的，因爲它不包含任何硬編碼的字段名，它們在讀入時取自csv數據輸入文件的第一行。使用時，任何實際的retrieve()方法調用當然必須包含有效的字段名稱關鍵字參數。

更新

修改爲各個領域的每一個獨特的價值，當數據文件先讀不創建一個查找表。現在retrieve()方法只根據需要創建它們（並保存/緩存結果以供將來使用）。還修改爲使用Python 2.7+，包括3.x.

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.') 

輸出：

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

鑑於http://wiki.python.org/moin/TimeComplexity這個怎麼樣：

• 有一本字典爲您感興趣的各列 - AGE，NAME等
• 擁有的字典（AGE，NAME）是可能的鑰匙給定列（35或「m」）的值。
• 具有表示一個「集合」的值的列表的列表，例如， VALUES = [ [35, "m"], ...]
• 將列字典的值（AGE，NAME）列爲VALUES列表中的索引列表。
• 有一本詞典，它將列名映射到VALUES的列表中，以便您知道第一列是年齡，第二列是性別（您可以避免這種情況並使用字典，但它會引入大量內存腳本並且有超過100K的對象可能或不會成爲問題）。

然後retrieve功能看起來是這樣的：

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

那麼，這就是你得到

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

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

如果你想要一本字典，你可以做到以下幾點：

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

但是再次，字典有點h在內存方面很有意思，所以如果你可以使用值列表，它可能會更好。

字典和列表檢索平均爲O（1） - 字典的最壞情況是O（n） - 所以這應該是相當快的。保持這一點會有點痛苦，但不是那麼多。要「寫入」，您只需附加到VALUES列表，然後將索引VALUES附加到每個字典。

當然的話，最好將基準您的實際執行情況和尋找潛在的改進，但希望這是有意義的，並讓你去:)

編輯：

請注意，@moooeeeep說，這隻會工作，如果你的值是可散列的，因此可以用作字典鍵。

Answer 3

有沒有在Python的數據結構，這將使存儲紀錄n數列（姓名，年齡，性別，體重，身高等）和檢索列基於任何（一個）記錄在對數（或理想恆定 - O（1）查找時間）複雜度？

不，沒有。但是您可以嘗試在每個值維度的基礎上實現一個字典。只要你的價值當然是可排序的。如果您爲記錄實現自定義類，則每個字典都將包含對相同對象的引用。這會爲你節省一些記憶。

Answer 4

您可以使用索引（​​單列索引）在關係數據庫中實現對數時間複雜度。然後檢索數據只是構建適當的SQL：

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) 

例子：

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

輸出：

174.0 
175.0