3

假设我有一个无法放入内存的非常大的数据集,数据集中有数百万条记录,我想删除重复的行(实际上是从重复中保留一行)

就空间和时间复杂度而言,最有效的方法是什么?

我的想法:

1.使用布隆过滤器,我不确定它是如何实现的,但我猜副作用是有误报,在这种情况下,我们如何才能找到它是否真的是重复的?

2.使用哈希值,在这种情况下,如果我们有少量重复值,唯一哈希值的数量会很大,同样我们可能会出现内存问题,

4

2 回答 2

2

您的解决方案 2:使用哈希值不会导致内存问题。您只需要将散列空间划分为适合内存的切片。更确切地说:

考虑一个存储记录集的哈希表,每条记录仅由其在表中的索引表示。例如说这样的哈希表将是 4GB。然后你把你的散列空间分成 k=4 片。根据散列值的最后两位数字,每条记录进入切片之一。所以算法大致如下:

let k = 2^M
for i from 0 to k-1:
    t = new table
    for each record r on the disk:
        h = hashvalue(r)
        if (the M last bit of h == i) {
            insert r into t with respect to hash value h >> M
        }
    search t for duplicate and remove them
    delete t from memory

缺点是您必须对每条记录进行 k 次哈希处理。优点是它可以很容易地分发。

这是 Python 中的原型:

# Fake huge database on the disks
records = ["askdjlsd", "kalsjdld", "alkjdslad", "askdjlsd"]*100

M = 2
mask = 2**(M+1)-1
class HashLink(object):
    def __init__(self, idx):
        self._idx = idx
        self._hash = hash(records[idx]) # file access

    def __hash__(self):
        return self._hash >> M

    # hashlink are equal if they link to equal objects
    def __eq__(self, other):
        return records[self._idx] == records[other._idx] # file access

    def __repr__(self):
        return str(records[self._idx])

to_be_deleted = list()
for i in range(2**M):
    t = set()
    for idx, rec in enumerate(records):
        h = hash(rec)
        if (h & mask == i):
            if HashLink(idx) in t:
                to_be_deleted.append(idx)
            else:
                t.add(HashLink(idx))

结果是:

>>> [records[idx] for idx in range(len(records)) if idx not in to_be_deleted]
['askdjlsd', 'kalsjdld', 'alkjdslad']
于 2013-07-26T19:27:48.443 回答
1

由于您需要删除重复项,而不需要排序或索引,因此您最终可能会扫描整个数据集以进行每次删除,这在性能方面代价高昂。鉴于此,您可能会为此考虑一些外部排序或数据库。如果您不关心输出数据集的排序。根据记录的散列或记录的键创建“n”个文件,这些文件存储输入数据集的子集。获取散列并以“n”取模,并获取正确的输出文件来存储内容。由于现在每个输出文件的大小都很小,因此您的删除操作会非常快;对于输出文件,您可以使用普通文件或 sqlite/berkeley db。不过,我会推荐 sqlite/bdb。为了避免扫描每次写入输出文件,您可以为每个输出文件设置一个前端布隆过滤器。布隆过滤器并不难。有很多图书馆可用。我会说,计算“n”取决于你的主内存。选择“n”的悲观、巨大价值。完成工作后,将所有输出文件连接成一个文件。

于 2013-07-26T20:11:13.477 回答