搜索数据集的高效算法

Question

给出几组元素,例如:

int set1[5] {5601, 935, 4153, 2195, 422};
int set2[5] {5601, 935, 23, 44, 422};
int set3[5] {4205, 935, 4153, 2195, 15};
int set4[5] {4205, 589, 4015, 44, 422};

在有序的情况下(即1,2,3与2,1,3不同),定位特定集合的有效算法是什么？例如,您想要找到:

int value[5] {5601, 935, 23, 44, 422};

注意事项:

1. 新集的插入成本不是问题,因此可以将它们存储在任何数据结构中,以优化搜索时间.

2. 这些集合将包含每个介于1到1,000,000个元素之间的任何位置(大约,并且将存在1到1000个集合之间的任何位置(再次,大约).但是对于任何给定的集合集合,元素的数量将始终相同(例如,如果一个set有10个元素,那么所有集合都有10个元素).

后续问题,我将用C++实现这一点,所以我有兴趣找出任何推荐的算法,它们是否存在于开源C++库中(最好是STL,Boost或QT,但我会考虑其他人).

Answer 1

如果订单很重要,那么您正在查看序列,而不是集合.术语很重要.

由于您只考虑了大约1,000个序列,因此将它们存储在具有良好性能的哈希表中应该很容易.我会考虑构造一个字符串来表示每个序列,例如,通过连接每个元素的字符串表示形式,加上某种分隔符,以及散列它.