在DataFrame中将每个记录与列表进行比较

Question

我有一个使用场景，其中我正在将同一列中的列表与其自身进行比较，代码如下：

for i in range(0,len(counts95)):
    for j in range(i+1,len(counts95)):
        for x in counts95['links'][i]:
            for y in counts95['links'][j]:
                if x == y and counts95['linkoflinks'][j] is None:
                    counts95['linkoflinks'][j] = counts95['index'][i]

代码本身可行，但不够符合Python习惯（使用了4个循环），且运行该操作需要很长时间。 其主要思路是将列表counts95['links']中的元素与后续行中的任何一个元素进行比较，若相同，则更新列linksoflinks的值为第一列的索引，前提是linksoflinks列为空（不覆盖）。

参考表格如下：

counts95 = pd.DataFrame({'index': [616351, 616352, 616353,6457754], 
                   'level0': [25,30,35,100],
                   'links' : [[1,2,3,4,5],[23,45,2],[1,19,67],[14,15,16]],
                   'linksoflinks' : [None,None,None,None]})

编辑： 新的数据框

counts95 = pd.DataFrame({'index': [616351, 616352, 616353,6457754,6566666,464664683], 
                   'level0': [25,30,35,100,200,556],
                   'links' : [[1,2,3,4,5],[23,45,2],[1,19,67],[14,15,16],[1,14],[14,1]],
                   'linksoflinks' : [None,None,None,None,None,None]})

期望的输出结果：

     index  level0            links  linksoflinks
0   616351      25  [1, 2, 3, 4, 5]         NaN
1   616352      30      [23, 45, 2]    616351.0
2   616353      35      [1, 19, 67]    616351.0
3  6457754     100     [14, 15, 16]         NaN
4  6566666     200           [1,14]    616351.0
5  6457754     556           [14,1]    616351.0

- Rishi

---

请分享数据而不是图片。https://dev59.com/O2Ij5IYBdhLWcg3wk182 - sammywemmy

编辑了问题，包括参考表格示例。 - Rishi

Answer 1

您的期望输出与示例数据框构造函数使用不同的值和列名。 我使用您的期望输出数据框进行测试。

逻辑:
对于links的每个子列表，我们需要找到第一个重叠子列表的行索引（我的意思是数据帧的索引，而不是列index）。 我们将使用这些行索引通过.loc在counts95上进行切片，以获取列index的相应值。 为了实现这个目标，我们需要执行几个步骤：

• 将每个子列表与link中的所有子列表进行比较。 列表推导式对于此任务快速高效。 我们需要编写一个列表推导式来创建布尔2D掩码数组，其中每个子数组包含重叠行的True值和非重叠的False值（请查看这个2D掩码的逐步过程并检查与列links一起使用，您将更清楚）
• 我们想要从顶部向当前子列表进行比较。 即，从当前行开始，我们只想向后与顶部进行比较。 因此，我们需要将任何向前比较设置为False。 这是np.tril的功能
• 在此2D掩码的每个子数组中，True的位置/索引是当前子列表重叠的行的行索引。 我们需要找到这些True的位置。 这是np.argmax的功能。 np.argmax返回数组的第一个最大元素的位置/索引。 将True视为1，将False视为0。 因此，在任何包含True的子数组上，它正确地返回第一个重叠的行索引。 但是，在所有False子数组上，它返回0。 我们将使用where处理所有False子数组
• 经过np.argmax后，2D掩码被缩减为1D掩码。 此1D掩码的每个元素都是重叠子列表的行索引号码。 将其传递给.loc以获取列index的相应值。 但是，结果还错误地包括了子数组的所有False行。 我们希望这些行变成NaN。 这是.where的功能

方法一：
使用列表理解来构建每个links列表和所有links列表之间的布尔2D掩码m。我们只需要进行向后比较，因此使用np.tril将掩码的右上三角形压缩为全是False，表示向前比较。最后，调用np.argmax来获取每行中第一个True的位置，并链接where将m的所有False行转换为NaN。

c95_list = counts95.links.tolist()
m = np.tril([[any(x in l2 for x in l1) for l2 in c95_list] for l1 in c95_list],-1)
counts95['linkoflist'] = (counts95.loc[np.argmax(m, axis=1), 'index']
                                  .where(m.any(1)).to_numpy())

 Out[351]:
     index  level0            links  linkoflist
0   616351      25  [1, 2, 3, 4, 5]         NaN
1   616352      30      [23, 45, 2]    616351.0
2   616353      35      [1, 19, 67]    616351.0
3  6457754     100     [14, 15, 16]         NaN
4  6566666     200          [1, 14]    616351.0
5  6457754     556          [14, 1]    616351.0

---

方法二:
如果您的数据框很大，将每个子列表与 links 的顶部部分进行比较可以加快速度。在大型数据框上，这种方法可能比方法一快2倍。

c95_list = counts95.links.tolist()
m = [[any(x in l2 for x in l1) for l2 in c95_list[:i]] for i,l1 in enumerate(c95_list)]
counts95['linkoflist'] = counts95.reindex([np.argmax(y) if any(y) else np.nan 
                                                   for y in m])['index'].to_numpy()

---

步骤(method 1)

m = np.tril([[any(x in l2 for x in l1) for l2 in c95_list] for l1 in c95_list],-1)

Out[353]:
array([[False, False, False, False, False, False],
       [ True, False, False, False, False, False],
       [ True, False, False, False, False, False],
       [False, False, False, False, False, False],
       [ True, False,  True,  True, False, False],
       [ True, False,  True,  True,  True, False]])

argmax 返回所有-False行中第一个 True 和第一个 False 的位置。

In [354]: np.argmax(m, axis=1)
Out[354]: array([0, 0, 0, 0, 0, 0], dtype=int64)

使用 argmax 的结果进行切片

counts95.loc[np.argmax(m, axis=1), 'index']

Out[355]:
0    616351
0    616351
0    616351
0    616351
0    616351
0    616351
Name: index, dtype: int64

使用where关键字，将与m中所有False对应的行转换为NaN。

counts95.loc[np.argmax(m, axis=1), 'index'].where(m.any(1))

Out[356]:
0         NaN
0    616351.0
0    616351.0
0         NaN
0    616351.0
0    616351.0
Name: index, dtype: float64

最后，输出的索引与counts95的索引不同，因此只需调用to_numpy来获取ndarray并将其赋值给counts95的linkoflist列即可。

- Andy L.

---

这将我的循环时间从3小时缩短到了6分钟，总共处理了15000行数据。我知道你已经给出了很好的解释，能否请您添加一下整体逻辑以更好地理解代码，我会非常感激并将答案标记为正确的。 - Rishi

@Rishi：我在回答中添加了详细的逻辑，希望可以帮到你 :) - Andy L.

Answer 2

好的编程模式应该是为您的任务使用适当的数据结构。回答“元素X是否存在于Y序列中”的最佳选择是内置的set。当您的集合是不可变的时，考虑使用frozenset。

解决方案

以下是我如何以Pythonic方式解决问题：

# necessary imports
from collections import defaultdict
from typing import Tuple, FrozenSet, DefaultDict

# initialise the links "mapping": for every index save frozenset of its links
links: Tuple[Tuple[int, FrozenSet[int]]] = (
    # tuple of tuples is like a dict but will let you iterate by index
    (616351, frozenset((1, 2, 3, 4, 5))),
    (616352, frozenset((23, 45, 2))),
    (616353, frozenset((1, 19, 67))),
    (6457754, frozenset((14, 15, 16))),
)

# defaultdict automatically creates new lists
#   as you access its keys which are not yet present
links_of_links: DefaultDict[int, List[int]] = defaultdict(list)

for i, item in enumerate(links):
    key, values = item  # split tuple into individual elements
    next_rows = links[i+1:]  # we will iterate over succeeding rows
    for next_key, next_values in next_rows:
        # here we check sets intersection:
        #   it is non-empty if any common elements are present
        if values & next_values:
            # though key might not be present in links_of_links,
            #   defaultdict will autocreate a new empty list
            links_of_links[key].append(next_key)

链接的内容如下：defaultdict(<class 'list'>, {616351: [616352, 616353]})

复杂度

现在让我们比较一下你的解决方案和我的复杂度，以证明后者更有效率。假设N是行数，L是链接列表的长度（平均值或最大值，实际上并不重要）。你的解决方案大致比较了所有行对，这给我们带来了O(N * N)。然后再乘以两个列表之间的朴素比较的复杂度——O(L * L)。总共给我们O(N * L)²。

所提出的解决方案仍然交叉连接所有行，因此N * N仍然存在。但现在我们以更有效的方式比较集合本身：O(min(L, L)) === O(L)，正如Python时间复杂度所说。因此，总体复杂度被单个L除，总共为O(N² * L)。

- Anton Bryzgalov

---

这会产生所需的输出，但我如何更改我的现有数据框以使用frozensets？ - Rishi

@Rishi，在我看来使用frozensets没有问题，pandas会保留其类型：pd.DataFrame({'x': frozenset([1, 2])}).iloc[0]['x']是frozenset({1, 2})。 - Anton Bryzgalov

由于问题中的数据集已更新，当前代码无法产生期望的输出。为参考，我已添加了一个期望输出到问题中。 - Rishi

Answer 3

使用 explode 和 duplicated 以及 .map 将重复链接值分配给后面的项目。

df = counts95.explode('links')


m = df[df.duplicated(subset=['links'],keep=False)].groupby('links')['index'].first()


df['link_above'] = df['links'].loc[df.duplicated(subset='links',keep='first')].map(m)



re_made_df = df.groupby(["index", "level0"]).agg(
    links=("links", list), linkoflist=("link_above", "first")).reset_index()


print(re_made_df)


     index  level0            links  linkoflist
0   616351      25  [1, 2, 3, 4, 5]         NaN
1   616352      30      [23, 45, 2]    616351.0
2   616353      35      [1, 19, 67]    616351.0
3  6457754     100     [14, 15, 16]         NaN

- Umar.H

---

这里的link_above是什么？ - Rishi

这是你的列，我只是在重新创建之前使用了一个不同的名称 @rishi - Umar.H

你能否解释一下这段代码，比如逐步说明你在这里做什么，这会对我很有帮助。我看到它在工作，但我必须理解它，而不是只是复制粘贴它。 - Rishi

@Rishi，我正在进行一个项目，但是我会做的。你的解决方案可行吗？现在只需逐行打印以查看发生了什么，并阅读“explode”和“map”的文档，我很快会回复你。 - Umar.H

谢谢你的帮助，但是有一个问题，如果有两个不同索引的重复列表，它会出现错误：无法从重复的轴重新索引，我正在编辑问题以添加2行，以便可以重新创建错误。 - Rishi

Answer 4

只是另一种选择，您可以在其中更多地操纵数据；

代码

import pandas as pd

counts95 = pd.DataFrame({'index': [616351, 616352, 616353,6457754,6566666,464664683], 
                   'level0': [25,30,35,100,200,556],
                   'links' : [[1,2,3,4,5],[23,45,2],[1,19,67],[14,15,16],[1,14],[14,1]],
                   'linksoflinks' : [None,None,None,None,None,None]})

def has_match(ar1, ar2):
    return bool(set(ar1).intersection(ar2))

def set_linksoflinks(df):
    for i, row in df.iterrows():
        j = i+1
        while j<df.shape[0]:
            check = has_match(row['links'], df.loc[j, 'links'])
            if check and not df.loc[j, 'linksoflinks']:
                df.loc[j, 'linksoflinks'] = row['index']
            j+=1
    return df.copy()

df = set_linksoflinks(counts95)

print(df)

输出

       index  level0            links linksoflinks
0     616351      25  [1, 2, 3, 4, 5]         None
1     616352      30      [23, 45, 2]       616351
2     616353      35      [1, 19, 67]       616351
3    6457754     100     [14, 15, 16]         None
4    6566666     200          [1, 14]       616351
5  464664683     556          [14, 1]       616351

- null

---

这不是预期的输出，第4行和第5行应该有616351，这是我们仅使用一个值标记重复项的位置。 - Rishi

抱歉，忘记加上空值检查 :)。请查看已编辑的答案。 - null