問題タブ [prefix-sum]

cub::scan でサポートされている最大サイズを知っている人はいますか? 5 億を超える入力サイズのコア ダンプを取得しました。自分が悪いことをしていないことを確認したかったのです...

これが私のコードです：

私は計算シェーダーを実行しようとしています - プレフィックスサムのデモは次の場所で提供されています:

https://github.com/openglsuperbible/sb7code/blob/master/src/prefixsum/prefixsum.cpp

私は正確なコードを使用しました：

そして、これはシェーダーです:

問題は、出力が 4 つの場所のうちの 1 つに書き込まれることです。

これは入力です：

ここで、Codility による Prefix Sum レッスンで示されている例を参照して、Prefix Sum の概念の背後にあるアイデアを把握しようとしています(マッシュルーム ピッカーの問題) 。

私の理解では、概念全体が単純なプロパティに基づいており、配列 A の 2 つの位置 A(pos_left, pos_right) 間のすべての要素の合計を見つけるために、すべての要素が連続して合計され、検索された場所で 2 番目の配列 P が使用されます。合計は
value(P(pos_right + 1)) - value(P(pos_left)) として計算されます。

問題
空でないベクトルで表されるすべての場所にキノコのある通りがあります。ピッカーの初期位置とその移動範囲を考慮して、収集できる最大数のキノコを探します。

例を見ると、ループの構築の背後にあるロジックがわかりません。このアルゴリズムの仕組みを説明できる人はいますか?

第 2 に、この例のポジショインのインデックス付けが非常にわかりにくく、扱いにくいことがわかりました。接頭辞の合計でベクトルを最初にゼロで「シフト」するのは一般的な方法ですか? (ベクター内の要素のカウントは、python ではデフォルトで 0 から始まるという事実は、すでにいくつかの混乱を引き起こしています)。

ソリューション

小さな配列の例をいくつか実行しA= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]、位置 k=5 と範囲 m = 3 を選択しました。2 つのループでチェックする範囲を作成するロジックがわかりません。

ループの次のパラメーターを取得します

範囲はさまざまです。なんで？

デバッグ用のバージョン

次の疑似コードを考えると、時間の計算量を決定しようとするときの私の思考プロセスが正しいかどうか疑問に思っています。

アルゴリズムは n 回ループし、最後の反復で最も多くの計算 (n 回の計算) が必要になるため、アルゴリズムは合計でn^2 + f(n)計算を行います。ここで、 は次数以下f(n)の多項式です。したがって、このアルゴリズムは二次です。n^2 O(n^2)