我有一大堆数字，例如 - 1至4,5至15,16至21,22至34，.... 我有大约600,000个这样的桶。每个桶中的数字范围各不相同。我需要将这些存储桶存储在合适的数据结构中，以便尽可能快地查找数字。
所以我的问题是什么是适合这类问题的数据结构和排序机制。
提前致谢
我有一大堆数字，例如 - 1至4,5至15,16至21,22至34，.... 我有大约600,000个这样的桶。每个桶中的数字范围各不相同。我需要将这些存储桶存储在合适的数据结构中，以便尽可能快地查找数字。
所以我的问题是什么是适合这类问题的数据结构和排序机制。
提前致谢
如果桶是连续的和不相交的，如在您的示例中，您需要在向量中存储每个桶的左边界（即1,5,16,22）加上作为最后一个元素的第一个数字。落入任何水桶（35）。 （我当然假设你在谈论 整数 数字。）
保持矢量排序。 您可以使用二进制类型搜索在O（log n）中搜索存储桶。要搜索数字x属于哪个存储桶，只需选择唯一的索引i，使得vector [i] <= x <vector [i + 1]。如果x严格小于vector [0]，或者它大于或等于vector的最后一个元素，则没有bucket包含它。
编辑。这就是我的意思：
#include <stdio.h>
// ~ Binary search. Should be O(log n)
int findBucket(int aNumber, int *leftBounds, int left, int right)
{
int middle;
if(aNumber < leftBounds[left] || leftBounds[right] <= aNumber) // cannot find
return -1;
if(left + 1 == right) // found
return left;
middle = left + (right - left)/2;
if( leftBounds[left] <= aNumber && aNumber < leftBounds[middle] )
return findBucket(aNumber, leftBounds, left, middle);
else
return findBucket(aNumber, leftBounds, middle, right);
}
#define NBUCKETS 12
int main(void)
{
int leftBounds[NBUCKETS+1] = {1, 4, 7, 15, 32, 36, 44, 55, 67, 68, 79, 99, 101};
// The buckets are 1-3, 4-6, 7-14, 15-31, ...
int aNumber;
for(aNumber = -3; aNumber < 103; aNumber++)
{
int index = findBucket(aNumber, leftBounds, 0, NBUCKETS);
if(index < 0)
printf("%d: Bucket not found\n", aNumber);
else
printf("%d belongs to the bucket %d-%d\n", aNumber, leftBounds[index], leftBounds[index+1]-1);
}
return 0;
}
您可能需要某种排序树，如B树，B +树或二叉搜索树。
如果我理解正确，你有一个桶列表，你想要一个任意整数，找出它进入哪个桶。
假设没有任何桶范围重叠，我认为您可以在二叉搜索树中实现它。这将使得O（logn）中的查找成为可能（当n =桶数时）。
这样做很简单，只需将左分支定义为小于桶的低端，将右分支定义为大于右端。所以在你的例子中，我们最终得到的结果如下：
16-21
/ \
5-15 22-34
/
1-4
要搜索，比方说，7，您只需检查根。不到16？是的，向左走。少于5？号码大于15？不，你做完了。
您只需要小心平衡树（或使用自平衡树），以保持最坏情况下的性能。如果您的输入（存储桶列表）已经排序，这非常重要。
在C ++中存储和排序这些数据的简单方法是使用一对排序数组，这些数组表示每个存储桶的下限和上限。然后，你可以使用 int bucket_index= std::distance(lower_bounds.begin(), std::lower_bound(lower_bounds, value)) 找到值匹配的存储桶，和 if (upper_bounds[bucket_index]>=value)， bucket_index 是你想要的水桶。
你可以用一个装有存储桶的结构替换它，但原理是相同的。
+1这种二元搜索的想法。它很简单，可以为600000个桶提供良好的性能。话虽这么说，如果它不够好，你可以用MAX BUCKET VALUE - MIN BUCKET VALUE = RANGE元素创建一个数组，并让这个数组中的每个元素引用相应的桶。然后，你得到一个保证常数[O（1）]时间的查找，代价是使用a 巨大记忆量。
如果A）访问存储桶的概率不统一，并且B）您知道/可以确定访问给定存储桶的可能性，您可以将这两种方法结合起来创建一种缓存。例如，比如说{0,3}一直被访问，就像{7,13}一样，那么你可以创建一个数组CACHE。 。 。
int cache_low_value = 0;
int cache_hi_value = 13;
CACHE [0] = BUCKET_1
CACHE [1] = BUCKET_1
...
CACHE [6] = BUCKET_2
CACHE [7] = BUCKET_3
CACHE [8] = BUCKET_3
...
CACHE [13] = BUCKET_3
。 。 。假设您尝试将值与存储桶关联的值在cache_low_value和cache_hi_value之间（如果Y <= cache_hi_value && Y> = cache_low_value;则BUCKET = CACHE []，这将允许您在O（1）时间内找到存储桶Y]）。从好的方面来说，这种方法不会占用机器上的所有内存;在缺点方面，如果你在缓存中找不到你的数字/存储桶对，它会向你的bsearch添加相当于一两个额外的操作（因为你必须首先检查缓存）。
让我看看我是否可以重申您的要求。这类似于拥有一年中的某一天，并想知道某一天的哪个月落入？所以，给定一年600,000天（一个有趣的星球），你想要返回一个字符串，即“Jan”，“Feb”，“Mar”......“Dec”？
让我首先关注检索结束，并且我认为你可以在初始化数据结构时弄清楚如何安排数据，考虑到上面已经发布的内容。
创建数据结构......
typedef struct {
int DayOfYear :20; // an bit-int donating some bits for other uses
int MonthSS :4; // subscript to select months
int Unused :8; // can be used to make MonthSS 12 bits
} BUCKET_LIST;
char MonthStr[12] = "Jan","Feb","Mar"... "Dec";
.
要初始化，请使用for {}循环将BUCKET_LIST.MonthSS设置为MonthStr中的12个月之一。
在检索时，对BUCKET_LIST.DayOfYear的向量进行二进制搜索（您需要为BUCKET_LIST.DayOfYear编写一个简单的比较函数）。您可以使用bsearch（）作为下标返回MonthStr来获得结果...
pBucket = (BUCKET_LIST *)bsearch( v_bucket_list);
MonthString = MonthStr[pBucket->MonthSS];
这里的一般方法是将附加到600,000个条目的字符串的“指针”集合。存储桶中的所有指针都指向同一个字符串。我在这里使用了一个int作为下标，而不是600k 4字节指针，因为它需要更少的内存（4位对4字节），而BUCKET_LIST作为一种int进行排序和搜索。
使用此方案，您将不会使用比存储简单的int键更多的内存或存储，获得与简单的int键相同的性能， 并取消检索的所有范围检查。 IE：如果{}测试则不。保存那些if {}用于初始化BUCKET_LIST数据结构，然后在检索时忘记它们。
我将此技术称为下标别名，因为它通过将多个下标转换为下标来解决多对一关系 - 我可能会非常有效地添加。
我的应用程序是使用许多UCHAR的数组来索引一个小得多的双浮点数组。尺寸减小足以将所有热点数据保存在处理器的L1缓存中。从这一个小变化中获得3倍的性能提升。