algorithm - 确定是否从一系列数字中看到了唯一数字

Question

我正在尝试找到最好、最快和最有效的方法来确定某个数字是否在某个范围内。

示例:记录 key :抽奖事件1(数据库 key )

可用门票:1 - 1000000(范围)

4 号票已上交。此事件是否已上交？

票号 865401 已上交。是否已上交此事件？

我考虑过位掩码、将数据存储为桶等。但这些似乎都不是我要寻找的答案。也许它不存在。

我们有 800,000 个事件，每个事件有 100 万张门票。我们目前正在存储上交的最后一个数字，任何更低的数字都会被拒绝。我们想要更精细的粒度，但需要效率并且存储每张票是不切实际的。

使用SQL存储数据

有什么想法吗？

编辑

到目前为止我想出的最好的主意是使用位图。每个事件有 10 列。每列存储 100,000 位。这应该允许快速数据检索，然后只需检查该位是打开还是关闭。这应该是每个事件大约 1mb 的存储空间，或者每列读取 100k。

我仍在寻找其他想法或建议。

Answer 1

如果您预计范围适中，则可以使用位掩码。否则你可以尝试使用集合结构。这些可以使用二叉搜索树来实现。