什么是存储一组的四个（或更多）值的最佳数据结构？(What is the best data str

说我有以下variables及其对应的values它代表一个record 。

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

请注意，该value可以是不同的types （ string ， integer ， float ，参考到任意-其他对象，等）。

会有很多records （至少> 100,000）。 每个record将是unique ，当所有这四个variables （实际上其values ）放在一起。 换句话说，不存在record与所有4个values是相同的。

我试图找到一个高效的数据结构Python ，这将让我（商店）检索records基于这些中的任何一个variables中log(n)的时间复杂度。

例如：

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与n的数columns （姓名，年龄，性别，体重，身高等）， retrieving records的基于任何（一个） column在logarithmic （或理想constant - O(1)查找时间）的复杂性？

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)的情况下，它们提供关于平均类似于字典的O（1）查找时间，并且还允许多个值与每一个相关联。 因此，查找关键是受到追捧的字段值的价值，并与它相关的数据将是整数索引列表Person保存在记录employees与值列表-所以他们都会比较小。

注意，对于类的代码完全是数据驱动的，因为它不包含其中，而不是当它在读过都是从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 = {}

    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 retrieve function '
            '(%s specified)' % ', '.join([repr(k) for k in kwargs.keys()]))
        field, value = kwargs.popitem()  # Keyword arg's name 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:  # Need to create a lookup table?
            lookup_table = self.lookup_tables[field] = defaultdict(list)
            for index, record in enumerate(self.records):
                field_value = getattr(record, field)
                lookup_table[field_value].append(index)
        # Return (possibly empty) sequence of matching records.
        return tuple(self.records[index]
                        for index in self.lookup_tables[field].get(value, []))

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:

有没有在Python的数据结构，这将使与存储记录n对数（或理想常数列数（姓名，年龄，性别，体重，身高等），并基于任何（一个）列的检索记录- O（1）查找时间）的复杂性？

不，是没有的。 但是你可以尝试实施每一个价值维度一个词典的基础上。 只要你的值是哈希的课程。 如果您实现自定义类的记录，每个字典将包含相同的对象引用。 这将节省您的一些记忆。

Answer 3:

鉴于http://wiki.python.org/moin/TimeComplexity这个怎么样：

• 有一本字典为您感兴趣的各列- AGE ， NAME等。
• 具有词典（的键AGE ， NAME ）对给定列（35或“M”）的可能值。
• 有代表的一个“收藏”值列表的列表，如VALUES = [ [35, "m"], ...]
• 有列词典的值（ AGE ， NAME ）是从指数的名单VALUES列表。
• 有这列名映射到索引列表中的一本词典VALUES ，让你知道，第一列是年龄，其次是性别（你能避免和使用字典，但是他们引入了大内存footrpint，并与超过10万的对象这可能会或不会是一个问题）。

然后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'}]

但同样，词典都在内存方面有点重，所以如果你能值列表走它可能会更好。

无论字典和列表检索为O（1）平均 - 为词典最坏的情况是O（n） - 所以这应该是相当快的。 维护，这将是痛苦的一点点，但没有这么多。 “写”，你就必须要追加到VALUES列表，然后在索引中添加VALUES到每个字典。

当然，话，最好将基准您的实际执行情况和寻找潜在的改进，但希望这是有意义的，并让你去:)

编辑：

请注意，@moooeeeep说，这将只有当你的价值观是可哈希可以作为字典键的作用，因此。

Answer 4:

你可以使用索引在关系数据库中实现数时间复杂度（ O(log(n)**k)单列索引）。 然后检索数据只是构建适当的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

文章来源: What is the best data structure for storing a set of four (or more) values?