过滤充满列表的字典

Question

我有一个充满列表的字典。该字典包含已解析的“.MDB”表。键是该表的列，每个键列表的元素是该列的行。我需要过滤这些数据。通过过滤，我的意思是获得一个具有所有相同键的新字典，但这些行应该满足我的标准或被删除。例如，新字典应仅包含“index”键值等于“13”的行。

我编写了一个完全满足我需要的函数：

def filter_d(d, key, condition):
    new_d = deepcopy(d)
    for i in range(len(new_d[key]) - 1, -1, -1):
        if new_d[key][i] != condition:
            for k in new_d:
                del new_d[k][i]
    return new_d

我这样称呼它（在这个例子中，我通过 2 个参数过滤字典“extindex”）：

extindex_nu = filter_d(filter_d(extindex, 'idblank', temperature_index), 'index', 13)

这个功能工作正常，但似乎非常慢。我必须对数千行进行数百次过滤。有没有更有效的解决方案？

我只找到了一种叫做“字典理解”的东西，但我不确定它是否能解决我的问题。如果是的话，我想要一些关于它的使用的建议。

Answer 1

您的代码如此缓慢的原因有多种：

• 您需要为要过滤的每一列调用一次

  filter_d

  ，并且每次需要迭代整个数据集；
• 多个for循环；
• 多次使用

  del

  ，速度可能会非常慢。

您将在下面找到改进代码的不同建议。

1. 原代码

from copy import deepcopy
import time

import numpy as np


# Dummy data
data = {
    f"column{idx}": np.random.randint(2, size=(1000000,)).tolist()
    for idx in range(10)
}

def filter_d(d, key, condition):
    new_d = deepcopy(d)
    for i in range(len(new_d[key]) - 1, -1, -1):
        if new_d[key][i] != condition:
            for k in new_d:
                del new_d[k][i]
    return new_d


start = time.time()
filter_d(filter_d(data, "column0", 1), "column3", 0)
print(f"{time.time() - start:.4f}s")

>>> 3.5714s

让我们分析一下代码的复杂性。让我们假设您的数据有

k

列和

n

行。然后，副本位于

O(nk)

中，嵌套循环位于

O(kn²)

中，因为

del

位于

O(n)

中。总的来说，代码在

O(kn²)

中。这忽略了您必须调用此函数两次的事实。

2. 使用相同签名的第一个提议

from collections import defaultdict

def filter_d2(d, key, condition):
    # Convert the dictionnary of lists into an iterator of dictionnaries
    data_iter = (
        {k: v[i] for k, v in d.items()}
        for i in range(len(next(iter(d.values()))))
    )

    # Filter the data
    filtered_iter = filter(lambda row: row[key] == condition, data_iter)

    # Convert to the original structure
    new_d = defaultdict(list)

    for row in filtered_iter:
        for k, v in row.items():
            new_d[k].append(v)

    return new_d

start = time.time()
filter_d2(filter_d2(data, "column0", 1), "column3", 0)
print(f"{time.time() - start:.4f}s")

>>> 0.1278s

此方法将数据更改为另一种更容易迭代的结构（大致是字典列表）。然后，它使用

filter

Python 内置函数执行过滤。最后，它将数据转换回原始结构。

我们来分析一下第二段代码的复杂度。数据结构的转换在

O(nk)

，过滤在

O(n)

，转换到原始结构在

O(nk)

。总的来说，代码在

O(nk)

中。这忽略了这个函数必须被调用两次的事实。

3. 第二个命题使用 lambda 函数来过滤行

def filter_d3(d, cond):
    # Convert the dictionnary of lists into an iterator of dictionnaries
    data_iter = (
        {k: v[i] for k, v in d.items()}
        for i in range(len(next(iter(d.values()))))
    )

    # Filter the data
    filtered_iter = filter(cond, data_iter)

    # Convert to the original structure
    new_d = defaultdict(list)

    for row in filtered_iter:
        for k, v in row.items():
            new_d[k].append(v)

    return new_d

start = time.time()
filter_d3(data, lambda row: row["column0"] == 1 and row["column3"] == 0)
print(f"{time.time() - start:.4f}s")

>>> 0.0633s

这段代码的复杂度也在

O(nk)

，但你只需调用一次，因此时间减少了2倍。