8

時間の複雑さ O(1) で配列をゼロにする方法はありますか? これは、for ループ、memset によって実行できることは明らかです。しかし、それらの時間計算量は O(1) ではありません。

4

9 に答える 9

20

はい

ただし、配列ではありません。これが機能するには、作成された配列が必要です。

template <typename T, size_t N>
class Array {
public:
    Array(): generation(0) {}

    void clear() {
        // FIXME: deal with overflow
        ++generation;
    }

    T get(std::size_t i) const {
        if (i >= N) { throw std::runtime_error("out of range"); }

        TimedT const& t = data[i];
        return t.second == generation ? t.first : T{};
    }

    void set(std::size_t i, T t) {
        if (i >= N) { throw std::runtime_error("out of range"); }

        data[i] = std::make_pair(t, generation);
    }


private:
    typedef std::pair<T, unsigned> TimedT;

    TimedT data[N];
    unsigned generation;
};

原理は簡単です:

  • generation属性を使用してエポックを定義します
  • アイテムが設定されると、それが設定されたエポックが記録されます
  • 現在のエポックのアイテムのみが表示されます
  • したがって、クリアはエポックカウンターをインクリメントすることと同じです

この方法には次の 2 つの問題があります。

  • ストレージの増加: アイテムごとにエポックを保存します
  • 世代カウンターのオーバーフロー: エポックの最大数として何かがあります

後者は、実際の大きな整数を使用して阻止できます (uint64_tより多くのストレージを犠牲にして)。

前者は自然な結果です。考えられる解決策の 1 つは、バケットを使用して問題を軽視することです。たとえば、単一のカウンターに最大 64 個のアイテムを関連付け、このカウンター内で有効なものを識別するビットマスクを設定します。

編集：バケツのアイデアに戻りたかっただけです。

元のソリューションには、要素ごとに 8 バイト (64 ビット) のオーバーヘッドがあります (既に 8 バイトにアラインされている場合)。保存されている要素によっては、大したことではない場合があります。

大事な場合は、バケットを使用することをお勧めします。もちろん、すべてのトレードオフと同様に、アクセスがさらに遅くなります。

template <typename T>
class BucketArray {
public:
     BucketArray(): generation(0), mask(0) {}
     
     T get(std::size_t index, std::size_t gen) const {
         assert(index < 64);

         return gen == generation and (mask & (1 << index)) ?
                data[index] : T{};
     }

     void set(std::size_t index, T t, std::size_t gen) {
         assert(index < 64);

         if (generation < gen) { mask = 0; generation = gen; }

         mask |= (1 << index);
         data[index] = t;
     }

private:
     std::uint64_t generation;
     std::uint64_t mask;
     T data[64];
};

この固定数の要素の小さな配列 (実際にこれをテンプレート化し、静的に 64 以下であることを確認できます) のオーバーヘッドは 16 バイトのみであることに注意してください。これは、要素ごとに 2 ビットのオーバーヘッドがあることを意味します。

template <typename T, size_t N>
class Array {
    typedef BucketArray<T> Bucket;
public:
    Array(): generation(0) {}
    
    void clear() { ++generation; }

    T get(std::size_t i) const {
        if (i >= N) { throw ... }

        Bucket const& bucket = data[i / 64];
        return bucket.get(i % 64, generation);
    }

    void set(std::size_t i, T t) {
        if (i >= N) { throw ... }

        Bucket& bucket = data[i / 64];
        bucket.set(i % 64, t, generation);
    }

private:
    std::uint64_t generation;
    Bucket data[N / 64 + 1];
};

スペースのオーバーヘッドを 32 分の 1 に削減しました。charたとえば、配列を使用して格納することもできますが、以前は法外でした。コストは、除算とモジュロを取得するため、アクセスが遅くなることです (両方の結果を 1 回で返す標準化された操作を取得するときは?)。

于 2012-05-29T11:02:29.183 に答える
12

nメモリ内の場所を短時間で変更することはできませんO(n)（ハードウェアが十分に小さい場合でも、nたとえばフラッシュメモリのように、メモリの適切に配置された特定のブロックをゼロにする一定時間の操作が可能になる場合があります）。

ただし、演​​習の目的が横方向の思考である場合は、「まばらな」配列を表すクラスを作成できます。スパース配列の一般的な考え方は、コレクションを保持し (おそらく 、map使用法によってはそれだけではない可能性があります)、インデックスを検索するときに、基になるコレクションにない場合は返すことです。0.

O(1) で基になるコレクションをクリアできる場合は、O(1) でスパース配列をゼロにすることができます。std::mapこれらのノードをすべて解放する必要があるため、通常、マップのサイズをクリアするのは一定時間ではありません。O(1)ただし、ツリー全体を「マップのコンテンツ」から「将来の使用のために予約したノードのツリー」に移動することで、クリアできるコレクションを設計できます。欠点は、この「予約済み」スペースがまだ割り当てられていることvectorです。

于 2012-05-29T10:51:11.843 に答える
9

非常に大きな定数係数を受け入れる限り、O(1) で配列をゼロにすることは確かに可能です。

void zero_out_array_in_constant_time(void* a, size_t n)
{
    char* p = (char*) a;
    for (size_t i = 0; i < std::numeric_limits<size_t>::max(); ++i)
    {
        p[i % n] = 0;
    }
}

これは、配列のサイズに関係なく、常に同じ数のステップを取るため、O(1) です。

于 2012-05-29T10:40:56.920 に答える
4

いいえ。

N 要素コレクションのすべてのメンバーを O(N) 時間以内にアクセスすることはできません。

Mike Kwan が観察したように、コストを実行時からコンパイル時に変更することもできますが、それによって操作の計算の複雑さが変わることはありません。

于 2012-05-29T10:33:25.870 に答える
2

一定の時間内に任意のサイズの配列を初期化することは明らかに不可能です。ただし、配列の初期化のコストをその使用全体にわたって償却する、配列のような ADT を作成することは完全に可能です。ただし、このための通常の構成では、3 倍以上のストレージが必要です。具体的には:

template <typename T, size_t arr_size>
class NoInitArray
{
    std::vector<T> storage;

    // Note that 'lookup' and 'check' are not initialized, and may contain
    // arbitrary garbage.
    size_t lookup[arr_size];
    size_t check[arr_size];
public:
    T& operator[](size_t pos)
    {
        // find out where we actually stored the entry for (*this)[pos].
        // This could be garbage.
        size_t storage_loc=lookup[pos];

        // Check to see that the storage_loc we found is valid
        if (storage_loc < storage.size() && check[storage_loc] == pos)
        {
            // everything checks, return the reference.
            return storage[storage_loc];
        }
        else
        {
            // storage hasn't yet been allocated/initialized for (*this)[pos].
            // allocate storage:
            storage_loc=storage.size();
            storage.push_back(T());

            // put entries in lookup and check so we can find 
            // the proper spot later:
            lookup[pos]=storage_loc;
            check[storage_loc]=pos;

            // everything's set up, return appropriate reference:
            return storage.back();
        }
    }
};

少なくとも概念上、破壊を必要としないタイプの場合、メンバーを追加して、clear()そのような配列の内容をかなり簡単に空にすることができます。T

于 2012-05-29T11:02:25.680 に答える
1

の配列を実行時にゼロにすることはできませんO(1)。これは、固定時間内に任意のサイズのメモリ ブロックの値を設定できる言語メカニズムがないことを考えると、直感的です。あなたができる最も近いものは次のとおりです。

int blah[100] = {0};

これにより、コンパイル時に初期化を行うことができます。実行時memsetは、一般的に最速ですが、O(N). ただし、特定の配列タイプでの使用に関連する問題があります。memset

于 2012-05-29T10:28:15.760 に答える
0

まだ O(N) ですが、キャッシュ ライン全体やメモリ ページのクリアなどのハードウェア支援操作にマップする実装は、1 ワードあたり 1 サイクル未満で実行できます。

実際、Steve Jessop のアイデアをリフすると...

大量のメモリを同時にクリアするためのハードウェア サポートがあれば、それを行うことができます。任意に大きな配列を指定する場合は、ハードウェア並列処理を使用して任意に大きなメモリを指定して、1 つのリセット ピンですべてのレジスタを一度に同時にクリアすることもできます。そのラインは任意に大きな論理ゲート (任意に大きな電力を消費する) によって駆動される必要があり、回路トレースは任意に短くする必要があります (R/C 遅延を克服するため) (または超伝導)、しかしこれらのことは非常に一般的です。異次元空間で。

于 2012-05-29T10:51:27.633 に答える