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]は1に等しいが、3はに含まれないため、結果には「1」が1つだけ含まれoffsetsます。

数百の範囲についてこれらのビニングされたカウントを計算する必要があり、そのうちのいくつかは配列全体にまたがっています。各ビンと要素の累積合計を格納するためにデータ配列を反復処理することを検討しましたが、メモリ要件は法外なものでした。これが私の実装の簡単なバージョンです：

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番目のビンの内容を単に無視できるため、オフセットを追跡する必要がなくなりました。

各ビンと要素の累積カウントを保存するにはメモリが多すぎると回答で述べましたが、各ビンと範囲のエンドポイントの累積カウントを線形時間で保存することができました。次に、範囲ごとに、範囲の左端でのその要素の累積カウントを右端でのカウントから差し引くことにより、各要素の発生を計算しました。これが私が使用したものです：

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

これは機能しますか。

( 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 に答える
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 に答える