12

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

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

提前致谢

4

6 回答 6

8

如果存储桶是连续且不相交的，如您的示例所示，您需要将每个存储桶的左边界（即 1、5、16、22）加上作为最后一个元素的第一个数字存储在一个向量中。 t 落入任何桶 (35)。（当然，我假设您在谈论整数。）

保持向量排序。您可以使用二进制搜索来搜索 O(log n) 中的存储桶。要搜索数字 x 属于哪个存储桶，只需查找唯一的索引 i，使得 vector[i] <= x < vector[i+1]。如果 x 严格小于 vector[0]，或者如果它大于或等于 vector 的最后一个元素，则没有桶包含它。

编辑。这就是我的意思：

#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;
}
于 2010-04-09T22:26:17.533 回答
2

您可能需要某种排序树，例如 B-Tree、B+ 树或二叉搜索树。

于 2010-04-09T22:08:26.447 回答
2

如果我理解正确，您有一个存储桶列表，并且您希望给定一个任意整数，找出它进入哪个存储桶。

假设没有一个桶范围重叠，我认为您可以在二叉搜索树中实现这一点。这将使在 O(logn) 中的查找成为可能（当 n=桶数时）。

这样做很简单，只需定义左分支小于桶的低端，右分支大于右端。因此，在您的示例中，我们最终会得到一棵树，例如：

    16-21
    /    \
  5-15  22-34
  /
1-4

例如，要搜索 7，您只需检查根目录。小于16？是的，向左走。少于5个？不，大于 15？不，你已经完成了。

你只需要小心平衡你的树（或使用自平衡树），以降低最坏情况下的性能。如果您的输入（桶列表）已经排序，这非常重要。

于 2010-04-09T22:12:50.260 回答
0

在 C++ 中存储和排序它们的一种简单方法是使用一对排序数组，它们表示每个桶的下限和上限。然后，您可以使用int bucket_index= std::distance(lower_bounds.begin(), std::lower_bound(lower_bounds, value))找到该值将匹配的存储桶，并且if (upper_bounds[bucket_index]>=value),bucket_index是您想要的存储桶。

您可以将其替换为一个包含存储桶的结构，但原理是相同的。

于 2010-04-09T22:26:57.877 回答
0

+1 对二分搜索的想法。它很简单，并且为 600000 个存储桶提供了良好的性能。话虽如此，如果还不够好，您可以创建一个包含 MAX BUCKET VALUE - MIN BUCKET VALUE = RANGE 元素的数组，并让该数组中的每个元素引用适当的存储桶。然后，您可以在保证恒定的 [O(1)] 时间内进行查找，但代价是使用大量内存。

如果 A) 访问存储桶的概率不均匀，并且 B) 您知道/可以计算出访问给定存储桶集的可能性，您可能可以结合这两种方法来创建一种缓存。例如，假设桶 {0, 3} 一直被访问，{7, 13} 也是如此，那么您可以创建一个数组 CACHE。. .

int cache_low_value = 0;

int cache_hi_value = 13;

缓存[0] = BUCKET_1

缓存[1] = BUCKET_1

...

缓存[6] = BUCKET_2

缓存[7] = BUCKET_3

缓存[8] = BUCKET_3

...

缓存[13] = BUCKET_3

. . . 假设您尝试将值与存储桶关联的值介于 cache_low_value 和 cache_hi_value 之间（如果 Y <= cache_hi_value && Y >= cache_low_value; 那么 BUCKET = CACHE[是]）。从好的方面来说，这种方法不会使用您机器上的所有内存。不利的一面是，如果您在缓存中找不到您的号码/存储桶对（因为您必须首先检查缓存），它会在您的 bsearch 中添加相当于一两个额外操作的操作。

于 2010-04-09T23:42:42.460 回答
0

让我看看我是否可以重申您的要求。这类似于拥有一年中的某一天，并想知道某一天在哪一个月？因此，假设一年有 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 位 vs 4 字节），并且 BUCKET_LIST 作为 int 的一种进行排序和搜索。

使用此方案，您将只使用存储一个简单 int 键的内存或存储空间，获得与简单 int 键相同的性能，并取消检索时的所有范围检查。IE：没有 if{ } 测试。保存那些 if{ } 用于初始化 BUCKET_LIST 数据结构，然后在检索时忘记它们。

我将这种技术称为下标别名，因为它通过将多个的下标转换为一个的下标来解决多对一的关系——我可以非常有效地添加。

我的应用程序是使用一个包含许多 UCHAR 的数组来索引一个小得多的双浮点数组。尺寸减小足以将所有热点数据保留在处理器的 L1 高速缓存中。仅此一点点更改即可获得 3 倍的性能提升。

于 2013-01-15T00:52:15.730 回答