假设我有下面的variables
及其对应的values
,它表示一个record
。
name = 'abc'
age = 23
weight = 60
height = 174
请注意,value
可以是不同的types
(string
,integer
,float
,对任何其他对象的引用等)。
将会有很多records
(至少100000)。当这四个variables
(实际上是它的values
)放在一起时,每个record
都将是unique
。换句话说,不存在record
,所有4values
都是相同的。
我试图在Python
中找到一个有效的数据结构,它将允许我(存储和)检索records
基于log(n)
时间复杂性中的任何一个variables
。
例如:
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
基于logarithmic
(或理想情况下的constant - O(1)
查找时间)复杂性中的任何一个?
Python中没有一个单独的数据结构可以实现您想要的所有功能,但是使用这些数据结构的组合来实现您的目标并相当有效地做到这一点是相当容易的。
例如,假设您的输入是名为
employees.csv
的逗号分隔值文件中的以下数据,其中的字段名由第一行定义:以下是工作代码,说明如何将此数据读取并存储到记录列表中,并自动创建单独的查找表,以查找与每个记录的字段中包含的值相关联的记录。
记录是由
namedtuple
创建的类的实例,这非常节省内存,因为每个类都缺少类实例通常包含的__dict__
属性。使用它们可以使用点语法(如record.fieldname
)按名称访问每个字段。查找表是
defaultdict(list)
实例,它提供类似字典的O(1)平均查找时间,并且允许每个值关联多个值。因此,查找键是要查找的字段值的值,与之关联的数据将是存储在具有该值的employees
列表中的Person
记录的整数索引列表,因此它们都相对较小。请注意,类的代码完全是数据驱动的,因为它不包含任何硬编码字段名,而这些字段名都是从csv数据输入文件的第一行读取的。当然,在使用实例时,所有的
retrieve()
方法调用都必须提供有效的字段名。更新
修改为在第一次读取数据文件时不为每个字段的每个唯一值创建查找表。现在,
retrieve()
方法“惰性地”只在需要时创建它们(并保存/缓存结果以供将来使用)。也被修改为在Python2.7+中工作,包括3.x输出:
给定http://wiki.python.org/moin/TimeComplexity这个如何:
AGE
,NAME
,等等AGE
,NAME
)成为给定列(35或“m”)的可能值。VALUES = [ [35, "m"], ...]
AGE
,NAME
)的值成为VALUES
列表中的索引列表。VALUES
中有一个字典,它将列名映射到列表中的索引,这样您就知道第一列是年龄,第二列是性别(您可以避免这一点,并使用字典,但它们引入了大内存footrpint,并且有超过100K个对象,这可能是问题,也可能不是问题)。然后
retrieve
函数可以如下所示:那么,这就是你得到的
如果需要词典,可以执行以下操作:
不过,字典在内存方面还是有点重,所以如果你能列出一些值,可能会更好。
字典和列表检索平均都是O(1)-字典的最坏情况是O(n)-所以这应该相当快。保持这一点会有点痛苦,但不会太痛苦。要“写”,您只需附加到
VALUES
列表,然后将VALUES
中的索引附加到每个字典。当然,最好的方法是对实际的实现进行基准测试,并寻找潜在的改进,但希望这是有意义的,并能让您继续:)
编辑:
请注意,正如@moooeeep所说,只有当您的值是可散列的,因此可以用作字典键时,这才起作用。
不,没有。但是您可以尝试在每个值维度一个字典的基础上实现一个。当然,只要你的值是散列的。如果为记录实现自定义类,则每个字典都将包含对相同对象的引用。这会帮你省点内存。
相关问题 更多 >
编程相关推荐