python - 在 CSV 文件中查找主键候选人的最快方法？

Question

在CSV文件中查找候选主键，测试要求列数<= 4且这些列的任何子集都不能是主键。 有一些例子:

• key1:[column18] ==>正确
• key2: [column15,column18] ==>错误，包含key1
• key3: [column1,column2,column3,column5,column6] ==> 错误，超过 4

这是对我的考验!我在 35 秒 内完成了它，但没有达到高效要求:在大约 10000 行的 csv 文件中在大约 1 秒 内找到主键。

测试数据:

• you can get the example csv file here .

• 该文件的正确答案是: [['column8', 'column11', 'column15', 'column18']]

所以，我的问题是“有没有更有效的方法来查找主键？”

这是我的代码:

# coding: utf-8
import pandas as pd
import numpy as np
import os
import itertools
import time

def is_subkey(newkey,keys):
#     test wheather newkey is sub set of any keys
    for key in keys:
        if set(key).issubset(newkey):
            return True
    return False

def primarykey_recognition(file,max_num=4):
#     file is an file object, returnd by function open()
#   doc is a pandas DF
    doc = pd.read_csv(file,sep=',')
    num = 1
    result = []
    table_length = len(doc.values)
    while num <= max_num:
        keys = list(itertools.combinations(doc.columns,num))
#         print(keys)
        for key in keys:
            if is_subkey(key,result):
#           if key belong to any sub set of keys in result ,continue
                continue
#           
            bools = np.array(doc.duplicated(subset=list(key)))
            if np.sum(bools) > 0:
#           sum(bools) means bools has duplicated lines 
                continue
            else:
                result.append(list(key))
        num += 1
    return result

if __name__=="__main__":

    with open(r"..\data\Table_C.csv") as file:
        tic = time.clock()
        keys = primarykey_recognition(file)
        toc = time.clock()

        print("File {} has primary keys: ".format(filename))
        print(keys)
        print("Elapsed: {} s".format(round(toc - tic,4)))

我发现有一个类似的问题，How to find a columns set for a primary key candidate in CSV file? ，但代码效率不高并且会找到错误的键，例如示例 key2。

这是该问题的代码:

# coding: utf-8
import pandas
from itertools import chain, combinations
import time

def key_options(items):
    return chain.from_iterable(combinations(items, r) for r in range(1, len(items)+1) )

tic = time.clock()    
df = pandas.read_csv(r"..\data\Table_C.csv");

# iterate over all combos of headings, excluding ID for brevity
for candidate in key_options(list(df)[1:]):
    deduped = df.drop_duplicates(candidate)

    if len(deduped.index) == len(df.index):
        print(','.join(candidate))

toc = time.clock()
print("Elapsed: {} s".format(round(toc - tic,4)))

Answer 1

这里有一些想法:

• 计算每一列的唯一值的数量。将这些数字称为 u_1、u_2、... 删除/跳过组合，其中将这些数字相乘导致乘积 < 文件中的行数。在您的示例文件中，这将有效地删除几乎所有组合，因为只有 bool 列最多可以识别 2*2*2*2 = 16 个不同的值。
• 不要将您的候选人转换成集合。您只需要检查子序列，而不是子集。在不创建新数据结构的情况下线性执行此操作。复制内存是昂贵的。集合交集操作也很昂贵。
• 使用 cProfile 分析您的代码。像这样:python3 -m cProfile -s cumtime key-extractifyer.py < lotsadata.csv
• 重新考虑你是否真的需要 numpy 来解决这个问题。对于大多数操作，Python 列表已经具有恒定时间或分摊的恒定时间运行时间。

---

澄清第一点:

让我们从抽象层面开始。您正在尝试查找满足某些约束的列组合。在这类问题中，我们称所有候选对象为“search space”，每个候选对象都是candidate that satisfy the constraints。被称为“问题的解决方案”。现在您的搜索空间是“itertools.combinations 生成的所有组合”。您正在检查每个候选人的约束条件。

现在让我们假设检查约束是昂贵的。在你的情况下是 pandas.duplicated() call，代表95%的执行时间。显然，如果我们可以最小化搜索空间，我们可以节省很多时间!

可以通过三种方式最小化搜索空间:

1. 找到一种算法来生成误报较少的候选人。如果您确实需要，我会把它留作练习。
2. 寻找更快的方法来排除不满足限制条件的候选人。这就是我的第一个要点。
3. 找到问题的一些隐藏结构，使您可以同时排除大部分搜索空间。示例:如果列 A、B、C、D 不是主键，您还可以排除这些列的所有较短组合。您或许能够找到一种数据结构，使您能够进行这种“彻底删除”。

我专注于“方式 2”，但如果需要，也可以随意探索其他方式。

搜索空间的很大一部分是具有二进制值的列。除此之外，您还有一些列只有一个值。由于数学原因，仅涉及这些列的组合永远无法满足您的约束(此类组合永远不会解决您的问题)。可以有 2 个值的一列最多能够唯一标识 2 行。如果您有 3 行或更多行，则必须至少有两行在列中共享相同的值。这称为 pigeonhole principle .

我们可以将其扩展到更多列。两个二进制列最多可以识别 2*2 = 4 行，具有这些组合:(0, 0), (0, 1), (1, 0), (1, 1) .并且它扩展到具有多于(或少于)两个值的列。每列有 3 个唯一值的两列最多可以标识 3*3 = 9 行。

这是我们要利用来减少搜索空间的原理。通过在开始时计算每列中的unique/distinct 值的数量，并将结果保存到一个数组中，这样您就不必在每次循环迭代时都这样做，您可以给出一个上限该列最多可以识别多少行。所以在你做昂贵的事情之前 pandas.duplicated()调用，您检查更便宜的乘法以查看此列组合是否有可能满足约束。如果不是，我们可以避免昂贵的调用。请注意，我们并不是要证明您的候选人是一个解决方案，我们是要证明它不是。在您确定之前，您仍然需要进行昂贵的通话，但候选人数量要少得多。