2

我有一个大的、严格递增的数组（1000 万个整数），用于另一个更大的数据数组。没有元素data大于 50。例如，

unsigned char data[70*1000*1000] = {0,2,1,1,0,2,1,4,2, ...};
unsigned int offsets[10*1000*1000] = {0,1,2,4,6,7,8, ...};

然后我想找到一系列范围内每个元素的计数，这些范围直到运行时才知道，仅包括其偏移量包含在offsets数组中的元素。每个范围的端点指的是数据数组的索引，而不是偏移量。例如，范围 [1,4] 的数据将是：

1 zero
1 one
1 two

结果仅包括一个“一”，因为虽然data[3]和data[2]都等于一，但 3 不包括在offsets.

我需要为数百个范围计算这些分箱计数，其中一些跨越整个数组。我考虑遍历数据数组以存储每个 bin 和元素的累积总和，但内存要求会令人望而却步。这是我的实现的简单版本：

for(int i=0; i<range_count; i++){
    unsigned int j=0;
    while(j<range_starts[i]) pi++;
    while(j < 10000000 and data[j]<=range_ends[i]) bins[i][data[offsets[j++]]]++;
}

有没有更有效的方法来计算这些计数？

4

3 回答 3

2

虽然鲁本的回答确实将计数时间缩短了大约一半，但对于我的应用程序来说仍然太慢了。我在这里为好奇的人提供我的解决方案。

data首先，我通过将数组中未索引的元素设置offsets为未使用的值（例如 51）来进行优化。这消除了跟踪偏移量的需要，因为在报告结果时我可以简单地忽略第 51 个 bin 的内容。

虽然我在答案中提到存储每个 bin 和元素的累积计数需要太多内存，但我能够以线性时间存储每个 bin 和范围端点的累积计数。然后，对于每个范围，我通过从右端点的计数中减去该范围左端点的该元素的累积计数来计算每个元素的出现次数。这是我使用的：

struct range{
    unsigned int lowerbound;
    unsigned int upperbound;
    unsigned int bins[52];
};

struct endpoint{
    int n;
    unsigned int counts[50];
};

range ranges[N_RANGES];
endpoint endpoints[N_RANGES*2];
cumulative_counts[52];

// ... < data manipulation > ... 

endpoint* first_ep = &endpoints[0];
endpoint* last_ep = &endpoints[N_RANGES*2-1];
endpoint* next_ep;

for(next_ep=&endpoints[0];next_ep<last_ep;next_ep++){
    unsigned char* i = &data[next_ep->n];
    unsigned char* i_end = &data[(next_ep+1)->n];
    for(int j=0;j<51;j++) next_ep->counts[j] = cumulative_counts[j];
    while(i<i_end) cumulative_counts[*(i++)]++;
}
for(int i=0;i<51;i++) last_ep->sums[i] = cumulative_counts[i];
for(int i=0;i<N_RANGES;i++){
    while(first_ep->n != ranges[i].lowerbound) first_ep++;
    last_ep = first_ep+1;
    while(last_ep->n != ranges[i].upperbound) last_ep++;
    for(int j=0;j<51;j++) tests[i].bins[j] = end_ep->counts[j]-start_ep->counts[j];
    ranges[i].bins[data[last_ep->n]]++;
}
于 2012-11-18T17:56:45.417 回答
1

当您说您的偏移量限制为 50 时，听起来您已经有了答案——它们似乎是正整数。

为每个数据值（从 0 到 50）索引一个向量向量，然后进行其他计算会便宜得多。这将是一种反向索引，从数据到数据库条目。

因此，您将拥有：

data[50][...] = {offsets related to the given data value}

将执行计算，检查每个数组的初始元素，并从一个数组跳到另一个数组，保持最后一个验证元素的位置。

这将与整个数组的元素数量、搜索范围的乘积、数组“数据”（0 到 50）中的元素数量乘以线性关系，考虑到您需要多次执行此操作，不会不是最好的方法。

那么，另一种方法是，对于每个数据条目，从 0 到 50，使用二叉树——甚至是散列结构——，这样您现在就可以知道数据库条目标识符是否属于当前数据元素（从 0 到 50）。在最好的情况下，对于每次迭代，这将与您的搜索范围呈线性关系。

我在分析中将 50 视为常数，因此仅在第一个数据数组或数组“数据”的所有 50 个条目中搜索将是相同的。我不确定这是否是一个有效的假设，所以复杂性是：O(nr)，n 等于您的数据最大范围（0 到 50），r 等于您的搜索范围（条目数您的数据库）。这对于每次计算都是有效的，因此，考虑到 i 作为计算次数，复杂度将被给出为 O(nri)。

于 2012-11-17T21:15:12.910 回答
1

这能行吗。

（演示在http://ideone.com/6rAj7k直播）

#include <algorithm>
#include <iostream>

unsigned char data[/*70*1000*1000*/]   = {0,2,1,1,0,2,1,4,2};
unsigned int offsets[/*10*1000*1000*/] = {0,1,2,4,6,7,8};

using namespace std;

void do_something_for_data_index(unsigned int data_index)
{
    std::cout << "visited: " << (int) data[data_index] << " (at index " << data_index << ")\n";
}

void foo(size_t first_data_index, size_t high_data_index)
{
    const auto low  = lower_bound(begin(offsets), end(offsets), first_data_index);
    const auto high = upper_bound(low           , end(offsets), high_data_index);
    for(auto offset_it = low; offset_it != high; ++offset_it)
    {
        do_something_for_data_index(*offset_it);
    }
}

int main()
{
    foo(1,4);
}

输出：

visited: 2 (at index 1)
visited: 1 (at index 2)
visited: 0 (at index 4)
于 2012-11-17T21:40:06.800 回答