在有效的数据结构存储号码的铲斗

StackOverflow https://stackoverflow.com/questions/2611244

题

我有号码的水桶例如 - 1至4个，5至15，16至21,22至34，.... 我有大约60万这样的桶。范围落在在每个桶而变化的数字。我需要这些桶存储在合适的数据结构，从而为一些查找是尽可能快。

所以我的问题是什么是适当的数据结构和用于这种类型的问题的分选机构。

在预先感谢

有帮助吗？

解决方案

如果该桶是连续和不相交，如在例中，需要存储在刚刚离开结合每个桶的向量（即1，5，16，22）加，作为最后一个元素，所述第一数目不属于任何桶（35）。 （I假设，当然，你正在谈论的整数的数字。）

请的向量排序。 您可以搜索水桶在O（log n）的，用一种二进制的搜索。要搜索的桶做了数x属于，只是去唯一索引i，使得矢量[I] <= X <矢量第[i + 1]。如果x大于矢量严格更少[0]，或者如果它是大于或等于向量的最后一个元素，则没有桶包含它。

EDIT。这里是我的意思是：

#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）时间（whenere 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分组值的阵列 - MIN分组值=范围的元素，并在这个数组引用的每个元素相应的桶。然后，将得到的查找在保证恒定[O（1）]时，在使用的成本巨大的内存量。

如果A）访问桶的概率并不均匀，B）你知道/可以找出一组给定桶的可能性有多大被访问，你也许可以结合这两种方法制造出一种高速缓存。举例来说，假设桶{0,3}被访问的时候，因为是{7,13}，则可以创建一个数组缓存。 。

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

。 。 。这将允许你寻找在O桶（1）的时间假定值你试图一个值与铲斗cache_low_value和cache_hi_value之间（关联如果Y <= cache_hi_value && Y> = cache_low_value;然后BUCKET = CACHE [ Y]）。在向上的一面，这种方法不会用你所有的计算机上的内存;不利的一面，它会相当于一个额外的操作或者添加到您的bsearch的情况下，你无法在缓存中找到你的电话号码/桶对（因为你必须检查缓存摆在首位）。

让我看看，如果我可以重申你的要求。它类似于有，比方说，在今年的一天，想知道某一天落在哪个月？因此，考虑到每年60万天（一个有趣的星球），你想返回一个字符串，或者“月”，“月”，“月” ...“月”？

让我专注于检索结束第一，我认为你可以弄清楚如何初始化数据结构，给那些已经被张贴以上时，安排数据。

创建的数据结构... 

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];

这里的一般方法是具有“指针”，以附接至600000个条目串的集合。所有的水桶指向同一个字符串的指针。我使用的位的int作为这里下标，而不是600K的4字节指针，因为它需要较少的存储器（4个比特对4个字节），和BUCKET_LIST排序和搜索作为一个物种为int。

使用此方案，您将使用不超过存储简单的INT键更多的内存或存储，得到相同的性能，简单的INT键，并消灭一切对检索范围检查。 IE：没有，如果{}测试。保存这些如果{} S对于初始化BUCKET_LIST数据结构，然后忘记他们上检索。

我指的是这种技术，因为混叠标，因为它由许多的下标转换为一个的下标解决了一个多对一的关系 - 非常有效地我可以补充

。

我的应用程序是使用许多UCHARs的数组索引双浮筒的小得多的阵列。尺寸的减小就足以让所有的热点数据的L1缓存的处理器上。刚刚从这一变化不大，3倍的性能提升。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top