最快的算法,以确定数组是否至少有一个重复

Question

我这里有一个非常奇怪的案例.我有一个包含数百万条目的文件,并想知道是否存在至少一个重复项.这里的语言不是很重要,但C似乎是速度的合理选择.现在,我想知道的是采取什么样的方法？速度是这里的主要目标.当然,我们希望一旦找到一个副本就停止查看,这很清楚,但是当数据进入时,我不知道它是如何排序的.我只知道它是一个字符串文件,由换行符分隔.现在请记住,我想知道的是,是否存在重复.现在,我发现了许多关于在数组中查找所有重复项的问题,但是大多数问题都是简单而全面的,而不是最快的.

因此,我想知道:找出一个数组是否包含至少一个副本的最快方法是什么？到目前为止,我能在SO上找到的最接近的是:找出数组中的重复元素.选择的语言并不重要,但是因为它毕竟是编程,所以多线程是可能的(我只是不确定这是否是一种可行的方法).

最后,字符串的格式为XXXNNN(3个字符和3个整数).

请注意,这不是严格的理论.这将一台机器(英特尔i7处理器搭配8GB RAM)上进行测试,所以我必须考虑让字符串比较等等.这就是为什么我也想知道,如果它可能是时间快于分割字符串二,首先比较整数部分,因为int比较会更快,然后是字符串部分？当然,这也需要我拆分字符串并将后半部分转换为int,这可能会更慢......

Answer 1

最后,字符串的格式为XXXNNN(3个字符和3个整数).

了解您的关键域对于此类问题至关重要,因此这使我们能够大规模简化解决方案(以及此答案).

如果X∈{A..Z}和N∈ {0..9},则得到26 ³*10 ³ = 17,576,000个可能的值...一个bitset(基本上是一个普通的,完美的Bloom过滤器,没有误报)将需要〜2Mb为此.

在这里:你可以生成所有可能的1700万个密钥的python脚本:

import itertools
from string import ascii_uppercase

for prefix in itertools.product(ascii_uppercase, repeat=3):
    for numeric in range(1000):
        print "%s%03d" % (''.join(prefix), numeric)   

和一个简单的C位集过滤器:

#include <limits.h>
/* convert number of bits into number of bytes */
int filterByteSize(int max) {
    return (max + CHAR_BIT - 1) / CHAR_BIT;
}
/* set bit #value in the filter, returning non-zero if it was already set */
int filterTestAndSet(unsigned char *filter, int value) {
    int byteIndex = value / CHAR_BIT;
    unsigned char mask = 1 << (value % CHAR_BIT);

    unsigned char byte = filter[byteIndex];
    filter[byteIndex] = byte | mask;

    return byte & mask;
}

为了您的目的,您可以这样使用:

#include <stdlib.h>
/* allocate filter suitable for this question */
unsigned char *allocMyFilter() {
    int maxKey = 26 * 26 * 26 * 10 * 10 * 10;
    return calloc(filterByteSize(maxKey), 1);
}
/* key conversion - yes, it's horrible */
int testAndSetMyKey(unsigned char *filter, char *s) {
    int alpha   = s[0]-'A' + 26*(s[1]-'A' + 26*(s[2]-'A'));
    int numeric = s[3]-'0' + 10*(s[4]-'0' + 10*(s[5]-'0'));
    int key = numeric + 1000 * alpha;
    return filterTestAndSet(filter, key);
}

#include <stdio.h>
int main() {
    unsigned char *filter = allocMyFilter();
    char key[8]; /* 6 chars + newline + nul */
    while (fgets(key, sizeof(key), stdin)) {
        if (testAndSetMyKey(filter, key)) {
            printf("collision: %s\n", key);
            return 1;
        }
    }
    return 0;
}

这是线性的,尽管显然可以优化密钥转换和文件输入.无论如何,样本运行:

useless:~/Source/40044744 $ python filter_test.py > filter_ok.txt
useless:~/Source/40044744 $ time ./filter < filter_ok.txt

real    0m0.474s
user    0m0.436s
sys 0m0.036s

useless:~/Source/40044744 $ cat filter_ok.txt filter_ok.txt > filter_fail.txt
useless:~/Source/40044744 $ time ./filter < filter_fail.txt
collision: AAA000

real    0m0.467s
user    0m0.452s
sys 0m0.016s

诚然,输入文件缓存在内存中以进行这些运行.