在Python中聚合满足特定条件的表格数据的最有效方法是O(1)时间？
假设我有一个表，其中包含一堆长格式的数据(每行都有一个数据点)。例如，假设我们有一个包含人们的SAT分数的表，其中包含州、城市、学校、性别、种族和个人的列。我的目标是找到一种方法，轻松地提取并平均与某些数据分组相对应的数据点。
例如，如果我想要计算得克萨斯州男性的SAT平均分数，或者纽约市的白人女性的平均分数。在Python语言中做这件事的最好方法是什么(我认为它类似于R中的tapply )？对Pandas数据结构进行布尔索引？这是在O(1)时间完成的吗？显然，最愚蠢的可能方法是逐行爬行，检查每一行是否满足条件，并收集符合条件的数字，但我忍不住认为还有比这更好的方法；我不认为随着我的数据集变得更大，这会变得不必要地变慢。
回答 1
Stack Overflow用户
发布于 2016-06-02 01:33:44
你不能在O(1)时间内做到这一点。
这个问题有多个与之相关的复杂性。我可以想到三个:前置、插入和查找。
您可以在O(nlog(n))预处理+ O(log(n))查找时间和O(log(n))插入时间内完成此操作，如下所示：
from collections import deque
datatable = collections.deque(your_data_table)
column_names = ['col1', 'col2'...etc]保持额外的数据结构更新，它总是有一个指针列表，指向按每列排序的主表的行。也就是说，如果你有一个有6列的数据表，你将需要6个有序数组，这些数组的值指向主表的行号。这个额外的结构应该占用与原始数据表相同的内存量。
overhead_structure = {}
for column, column_name in zip( column_names, table):
row_indexes, sorted_column_values = sort(column)
overhead_structure[column_name] = (sorted_column_values, row_indexes)有了排序的元数据->的新的额外开销，您可以在您有条件的每一行上使用二进制搜索来搜索满足您的条件的行。
from bisect import bisect_left
overhead_index = bisect_left(overhead_structure[column_name], 1, lo,hi)
real_index = overhead_structure[column_name][overhead_index][1]此外，由于排序后的元数据带来了新的开销，每次向主表添加新的行时，都必须在新的元数据排序中填入指向该行的指针。因此，您必须确定该行在每个列排序中所属位置。
for column_name in column_names:
overhead_index = bisect_left(overhead_structure[column_name],1, lo,hi)
real_index = overhead_structure[column_name][overhead_index]
overhead_structure[column_name].insert(overhead_index, (new_item, real_index))
datatable.append(new_item)这是我能想到的最快的方法..我怀疑有一种更健壮、更好的方法可以做到这一点，因为这正是SQL数据库必须通过SELECT语句在幕后处理的问题，而且经过多年的努力，聪明的人已经使这些查询得到了相当优化。
编辑：
使用任意数据类型会给插入带来麻烦，因为本机数组的长度是固定的。使用双向链表数据类型可能会缩短插入时间，并产生更多的内存开销，但会使其他复杂性保持在我估计的水平。我用python‘’deque‘’写了一些sudo代码
https://stackoverflow.com/questions/37577965
复制
腾讯云开发者
