使用Single Pass算法将通过for循环从数据帧生成的列表与字典值相交的快速方法

Question

我正在尝试实现Single Pass算法来解决以下问题：

• 对于数据帧中的每个索引，确定哪些列包含该值
• 然后将这些列的名称存储为列表
• 有一个字典，其中键是数据帧中的列名，值是数据帧内的所有其他列名
• 对于该字典中的每个关键字，将其值与上面步骤2)生成的列表相交
• 使用交集的结果更新该字典关键字的值

请参阅下方的我的代码

def sp_algorithm(self, dataframe, col_dict):
# for each cursor value, get all columns that has it
for ind, i in zip(dataframe.index, range(0, len(dataframe.index))):
# vectorised index operation
cols_list = dataframe.columns[dataframe.isin([ind]).any()]
# for each column in col_dict.keys(), intersect its values with cols_list to get the remaining
# if the current column value is null, then do nothing
for key_col in col_dict.keys():
column_val = dataframe.loc[ind, key_col]
if (column_val == column_val) & (column_val != ''):
col_dict[key_col] = list(set(col_dict[key_col]).intersection(cols_list))

包含列名的字典如下所示：

col_dict = {'col_A': ['col_B', 'col_C'], 'col_B' = ['col_A', 'col_C'], 'col_C': ['col_A', 'col_B']}

正如您所看到的，我的代码目前具有O(n^2)时间复杂性，因为其中有2个for loop。

目前，每次迭代(包括2 xfor loops)大约需要0.8秒，这对于小型数据集来说可能不是问题。但是，我正在处理的数据集是300k行和80列。

我的问题是：我如何实现字典交集的单次传递步骤，这样循环就只有1而不是2？

编辑数据帧将包含排序的索引和按升序排列的值，如下所示：

col_A col_B col_C
index
0        nan     0     0
1          1     nan   1
2          2     nan   2
3        nan     3     3

因此，我当前的函数将为每个index、ind循环，以获得列名称cols_list = dataframe.columns[dataframe.isin([ind]).any()]，并将它们与字典值相交。

第一次迭代：cols_list = ['col_B', 'col_C']然后，它将查找col_dict中每个键的值(仅当列有值时，因此对于nan，它将被跳过)，并与它相交并更新它。

col_dict = {'col_A': ['col_B', 'col_C'], 'col_B' = ['col_C'], 'col_C': ['col_B']}

第二次迭代：检查字典值时跳过col_B，因为它是nan，并且它的字典值保持不变cols_list = ['col_A', 'col_C']col_dict = {'col_A': ['col_C'], 'col_B' = ['col_C'], 'col_C': []}

第三次迭代：检查字典值时跳过col_B，因为它是nan，并且它的字典值保持不变cols_list = ['col_A', 'col_C']col_dict = {'col_A': ['col_C'], 'col_B' = ['col_C'], 'col_C': []}

第4次迭代：检查字典值时跳过col_A，因为它是nan，并且它的字典值保持不变cols_list = ['col_B', 'col_C']col_dict = {'col_A': ['col_C'], 'col_B' = ['col_C'], 'col_C': []}

Answer 1

numpy/scpy/panda的优势在于使用C代码为您完成大部分工作。考虑到，用你的话来说，有300k行和80列，我建议你首先尽一切努力确保你用C而不是python处理这些行。因此，应该消除第一个循环：不要使用python处理300k个元素。

按照我阅读您需求的方式，您有一个索引(行标签)，其中包含一些类型的值，这些值可能会出现在其他列的各个单元格中。类似这样的东西：

Index   A  B  C  D
1     0  0  3  0
2     2  0  1  -1
3     0  0  0  0
192   0  0  1  -1

您想知道，对于每个索引，该值是否出现在A列、B列、C列等中的任何列中。如果任何索引值出现在列中，则该列为"ALIVE"。

在该过程结束时，列要么是ALIVE，要么不是，然后您需要过滤其他字典以排除不ALIVE的列。

在我上面的例子中，列A因为｛2｝而被认为是ALIVE，列C因为｛3，1｝而认为是ALIVE，但列B和D不是ALIVE，因为它们不包含Index中存在的任何值。这是对的吗？

尝试使用isin来确定列中的值是否存在于索引中。然后使用any将布尔结果折叠为单个布尔值，以确定列是否活动：

row_labels = df.index
col_is_alive = df.isin(row_labels).any()  # NB: any(index=0) is default

(注意：我不在可以运行此代码的地方。它可能包含语法或其他错误。)

现在，您有一系列80个布尔值，告诉您哪些列是活动的。你可以随心所欲地处理。

alive_col_names = { name for name in df.columns if col_is_alive[name] }  # Set comprehension

然而，您最初的问题语句听起来像是在做一次(而不是迭代更新列名组)。在这种情况下，我建议直接计算值，而不是与字典值相交(除了键之外的每个列名的列表)。也就是说，直接计算键->值对，而不是试图将值列表与所有列名的列表"相交"。

col_dict = { key:alive_col_names - {key} for key in alive_col_names}

另一方面，如果您以某种方式迭代更新这些值，那么我建议您将第二个数据结构设置为string->set的字典，而不是string->list，因为这将使您能够访问标准的set操作和行为。

new_col_dict = {}
for key, other_cols in col_dict.items():
if key not in alive_col_names:
continue
new_col_dict[key] = other_cols.interset(alive_col_names)
col_dict = new_col_dict

(可以使用dict理解来折叠，但为了可读性，可能不应该折叠。)