1

我们有大量数据，我们想对它们执行一些操作。删除重复项是主要操作之一。

前任。

a,me,123,2631272164
yrw,wq,1237,123712,126128361
yrw,dsfswq,1323237,12xcvcx3712,1sd26128361

这是文件中的三个条目，我们希望根据第一列删除重复项。因此，应删除第 3 行。每行可能有不同数量的列，但我们感兴趣的列将始终存在。

在内存中操作看起来不可行。

另一种选择是将数据存储在数据库中并从那里删除重复项，但这又不是一项简单的任务。我应该遵循什么设计将数据转储到数据库中并删除重复项？

我假设人们一定遇到过这样的问题并解决了它。

我们通常如何解决这个问题？

PS：请将此视为现实生活中的问题，而不是面试问题；）

4

5 回答 5

5

如果键的数量也无法加载到内存中，则必须进行稳定（保留顺序）外部合并排序以对数据进行排序，然后进行线性扫描以进行重复删除。或者您可以修改外部合并排序以在合并排序运行时提供重复消除。

我想因为这不是面试问题，或者效率/优雅似乎不是问题（？）。编写一个 hack python 脚本，以第一个字段作为主键创建 1 个表。解析此文件并将记录插入数据库，将插入包装到 try except 语句中。然后在表上执行一个select *，解析数据并逐行写回文件。

于 2012-04-28T06:04:38.977 回答
2

如果您沿着数据库路线走，您可以将 csv 加载到数据库中并使用“重复密钥更新”

使用 mysql:-

  1. 创建一个包含行以匹配您的数据的表（您可能只需要 2 行 - id 和数据）

  2. 使用类似的东西转储数据

    LOAD DATA LOCAL infile "rs.txt" REPLACE INTO TABLE data_table FIELDS TERMINATED BY ',';

  3. 然后，您应该能够将数据转储回 csv 格式而不会重复。

于 2012-04-28T06:28:47.547 回答
0

如果输入已排序或可以排序，则只需在内存中存储一​​个值即可：

r = read_row()
if r is None:
    os.exit()
last = r[0]
write_row(r)
while True:
    r = read_row()
    if r is None:
        os.exit()
    if r[0] != last:
        write_row(r)
        last = r[0]

除此以外：

我要做的是保留一组我已经看到的第一列值，如果它在该集合中，则删除该行。

S = set()
while True:
    r = read_row()
    if r is None:
       os.exit()
    if r[0] not in S:
       write_row(r)
       S.add(r[0])

这将仅使用与第一列中值集的大小成比例的内存流过输入。

于 2012-04-28T06:00:48.273 回答
0

如果唯一键的数量不是很高，您可以简单地这样做；
（伪代码，因为你没有提到语言）

Set keySet;

while(not end_of_input_file)
    read line from input file
    if first column is not in keySet
        add first column to keySet
        write line to output file
end while
于 2012-04-28T06:00:57.283 回答
0

如果您需要在原始数据中保留顺序，则创建位置和数据元组的新数据可能是明智的，然后对要删除的数据进行排序。一旦您按数据排序，重复数据删除（本质上）就是线性扫描。之后，您可以通过对元组的位置部分进行排序来重新创建原始顺序，然后将其剥离。

假设您有以下数据：a、c、a、b

使用 pos/data 元组，按数据排序，我们最终得到：0/a、2/a、3/b、1/c

然后我们可以进行重复数据删除，可以轻松地选择要保留的第一个或最后一个条目（我们也可以使用更多的内存消耗，保留另一个）并获得：0/a、3/b、1/c。

然后我们按位置排序并去掉：a、c、b

这将涉及对数据集的三个线性扫描和两个排序步骤。

于 2012-04-28T12:19:55.593 回答