在高效的数据结构中存储一桶数字

Question

我有一堆数字,例如 - 1到4,5到15,16到21,22到34 ......我有大约600,000个这样的桶.每个桶中的数字范围各不相同.我需要将这些存储桶存储在合适的数据结构中,以便尽可能快地查找数字.

所以我的问题是什么是适合这类问题的数据结构和排序机制.

提前致谢

Answer 1

如果桶是连续的和不相交的,如在您的示例中,您需要在向量中存储每个桶的左边界(即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;
}