Skip to main content
 首页 » 编程设计

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

2024年12月31日9jillzhang

我正在尝试实现 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 x for loop s)大约需要 0.8 秒,这对于小型数据集来说可能不是问题。但是,我正在处理的数据集有 300k 行和超过 80 列。

我的问题是:如何实现单次传递到字典交集步骤,以便只有 1 个 for 循环而不是 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获取col名称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': []}

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

请您参考如下方法:

numpy/scipy/pandas 的优势在于使用 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 的列。

在我上面的示例中,A 列因为 { 2 } 而被认为是 ALIVE,C 列因为 { 3, 1 } 而被认为是 ALIVE,但是 B 和 D 列不是 ALIVE,因为它们不包含任何值存在于索引中。这样对吗?

尝试使用 isin 来确定列中的值是否存在于索引中。然后使用 any 将 bool 结果折叠为单个 bool 值,以确定该列是否存在:

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

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

现在您有一系列 80 个 bool 值,告诉您哪些列处于事件状态。您可以随心所欲地进行处理。

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} 

另一方面,如果您以某种方式迭代更新这些值,那么我建议您将第二个数据结构设为字符串字典 -> 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 

(为了可读性,可以使用字典理解来折叠,但也许不应该折叠。)