3

配列があるとしましょう：

bool eleme[1000000] = {false};

コードのある時点で、nこの配列の最初の要素のいくつかを に変更しtrueます。その後、配列のすべての要素がfalse. 私もです：

for (int i =0; i < n; ++i)     
       eleme[i] = false;

費用がかかりますΘ(n)。

これを一定時間で行う方法はありますか？たとえば、次のようなもの make_false(eleme, n);

4

4 に答える 4

3

一般的な回答メモリ内の N 個の要素を変更する場合、または
のような単一のコマンドで表現できるかどうかに関係なく、最終的には O(N) 操作になります。memsetstd::fill

できるだけ多くの配列がキャッシュにあるようにアルゴリズムを設計すると、操作はかなり高速になります。のような最適化された組み込みコマンドを使用するとmemset、高速化にも役立ちます。

提案 1
ただし、一定時間の配列初期化には古いアルゴリズムのトリックがあり、これはあなたのケース (一定時間の配列のリセット) でも機能しますが、メモリの使用量が大幅に増加します。

次のようになります: メインの array に加えて、同じ長さのA12 番目の arrayと、これもサイズ N の stack を割り当てます。これらの構造体はどれも初期化する必要はありません (そして、単にそれらを割り当てるだけで間違いなく O(1 ） 手術）。スタック ポインタも必要です。A2SSP

最初、スタック ポインターは 0 (スタックの一番下を指しています) です。

A1たとえば、にエントリを作成するたびにA1[i]=j、 を設定A2[i]=SPし、S[SP]=iをインクリメントしますSP。

特定のエントリが設定されているかどうかを確認したい場合はA1[i]、 を検索しA2[i]ます。の場合、つまりスタック ポインタの現在の値よりも小さい場合、対応するスタック エントリが以前に設定されている必要がA2[i]<SPあることがわかります。SP[A2[i]]そのスタック エントリの値が である場合i、A1[i]有効なエントリです。それ以外の場合は、初期化されませんでした。

ここで、 のすべてのエントリをリセットするにはA1、スタック ポインタを 0 に戻すだけです。これは一定時間の操作です。

私は、このトリックが実際に役立つと感じた状況に遭遇したことがないことを認めなければなりません。通常memset、一定時間ではありませんが、単純に十分に高速です。

Gonzalo Navarro は最近、余分な配列を圧縮して、O(1) の時間制限を維持しながら使用するスペースを減らすための一連のトリックについて説明したノートを公開しました。

提案 2
別の可能性は、必要な場合にのみ、怠惰な方法で値をリセットすることです。これは、リセット時に、最初のいくつかの要素の一部のみが実際に使用されるという事実を利用しています。

これには、初期化されていない (または最新のリセット時にリセットされた) 一番左の要素のインデックスを変数に保持し、要素をA[i]設定するときに、左端の間のすべての要素を初期化 (またはリセット) する必要があります。 -最も初期化されていないものとi.

index の要素にアクセスするには、 が初期化されていない左端の要素よりも小さいiかどうかを確認します。それ以外の場合は初期化 (またはリセット) されていないため、初期化値 (おそらく 0) をリテラルとして返します。iA[i]

配列をリセットするには、左端の初期化されていない要素のインデックスを 0 に戻すだけです。これは一定時間の操作です。

もちろん、これはエントリの変更が O(N) 操作であることを意味しますが、通常、配列の最初のいくつかの要素のみを設定する場合、実際に高価になることはありません。また、各要素が 1 回しかリセットされないため、2 つのリセット間のすべての操作の総コストも O(N) であることに注意してください。

もう 1 つの重要な利点は、キャッシュ フレンドリーです。要素が設定されるたびに、初期化が必要な要素の範囲が小さくなり、すべての要素を一度にリセットする場合よりも完全にキャッシュ内に収まる可能性が高くなります。

C++ では、次のようになります。

template <typename T, std::size_t N, T init_val>
class FastResetArray
{
  std::array<T,N> _data;                // the array
  unsigned        _min_uninitialised;   // the left-most non-initialised element
public:
  FastResetArray()
    :_data(),_min_uninitialised(0)
  {}

  T at(const unsigned index) {
    return (index < _min_uninitialised ? _data[index] : init_val);
  }

  void set(const unsigned index, const T val) {
    if (index > _min_uninitialised)
      std::fill_n(begin(_data) + _min_uninitialised,
          index - _min_uninitialised,
          init_val);
    _data[index] = val;
    _min_uninitialised = index + 1;
  }

  void reset() {
    _min_uninitialised = 0;
  }
};

_min_uninitialised(コンストラクターで、 (左端の初期化されていない要素のインデックス) を 0に設定したことに注意してください。既定のコンストラクターはstd::array配列全体をゼロに初期化するため、Nifinit_valをゼロに設定することもできます。したがって、上記の実装は最初の O(N) の初期化を回避するのに役立ちません – で O(N) を回避するだけreset()です。)

于 2012-10-13T03:30:30.667 に答える
1

nこれを一定時間で行う方法はありますか[要素以上を訪問しないでください]？

いいえ。n要素を設定する必要がありnます。これにより、手順が実行されます。つまり、O（n）になります。

手作業でループを作成しないことで、処理速度を上げることができます。私はあなたがそれを発見すると思います：

std::fill(eleme, eleme+n, false);

より速くなります

for (int i =0; i < n; ++i)     
   eleme[i] = false;

それらは同じbig-Oの複雑さを持っていますが。

于 2012-10-13T03:16:10.057 に答える
1

によると

http://en.wikipedia.org/wiki/Time_complexity#Constant_time

あなたのコードはすでに定数時間です

要素数が事前に分かっていて変わらない場合

これは宣言から正しいようです

bool eleme[1000000] = {false};

于 2012-10-13T03:30:49.573 に答える
0

配列の要素数が n (定数ではない) の場合、その配列のすべての値を false に初期化すると、常に線形時間になります。ただし、考えてみると、この配列がより大きなアルゴリズムの一部である場合、通常は一定時間内に問題を解決する別の方法を見つけることができます (この仮定を行っているのは、配列を「false」に設定した場合、現在そこに格納されているデータを気にする必要はないので、この時点で何かを行う必要はありません)。

于 2012-10-13T07:03:32.840 に答える