c++ - O(1) でソートされた配列を維持しますか?

Question

ソートされた配列があり、結果の配列がソートされたままになるように、1 つのインデックスの値を 1 単位 (array[i]++) だけ増やしたいと考えています。これは O(1) で可能ですか? STL および C++ で可能な任意のデータ構造を使用しても問題ありません。

より具体的なケースでは、配列がすべて 0 の値で初期化され、インデックスの値を 1 だけ増やすことによって常にインクリメンタルに構築される場合、O(1) ソリューションはありますか?

Answer 1

私はこれを完全には解決していませんが、一般的な考え方は少なくとも整数には役立つと思います。より多くのメモリを犠牲にして、繰り返し値の実行の終了インデックスを維持する別のデータ構造を維持できます (インクリメントされた値を繰り返し値の終了インデックスと交換したいため)。これは、最悪のケースO(n)のランタイムに遭遇する値が繰り返されるためです。たとえば[0, 0, 0, 0]、 location で値をインクリメントするとします0。次にO(n)、最後の場所を見つけることです（3）。

しかし、私が言及したデータ構造を維持しているとしましょう (O(1)ルックアップがあるため、マップは機能します)。その場合、次のようなものがあります。

0 -> 3

したがって0、 location で終わる一連の値があります3。値をインクリメントするとき、たとえば でi、新しい値が での値より大きいかどうかを確認しますi + 1。そうでない場合は、問題ありません。しかし、そうである場合は、二次データ構造にこの値のエントリがあるかどうかを確認します。ない場合は、簡単に交換できます。エントリがある場合は、終了インデックスを調べて、その場所の値と交換します。次に、二次データ構造に必要な変更を加えて、配列の新しい状態を反映させます。

より完全な例:

[0, 2, 3, 3, 3, 4, 4, 5, 5, 5, 7]

二次データ構造は次のとおりです。

3 -> 4
4 -> 6
5 -> 9

location の値をインクリメントするとします2。したがって3、 を に増やしました4。配列は次のようになります。

[0, 2, 4, 3, 3, 4, 4, 5, 5, 5, 7]

次の要素は です3。次に、二次データ構造でその要素のエントリを検索します。エントリは です。これは、で終わる一連の4があることを意味します。これは、現在の場所の値を index の値と交換できることを意味します。344

[0, 2, 3, 3, 4, 4, 4, 5, 5, 5, 7]

ここで、セカンダリ データ構造も更新する必要があります。具体的には、 の実行が31 インデックス早く終了するため、その値を減らす必要があります。

3 -> 3
4 -> 6
5 -> 9

必要なもう 1 つのチェックは、値が繰り返されているかどうかを確認することです。i - 1th とi + 1th の場所を調べて、問題の値と同じかどうかを確認できます。どちらも等しくない場合は、この値のエントリをマップから削除できます。

繰り返しますが、これは単なる一般的な考え方です。私が考えたようにうまくいくかどうかを確認するために、コードを作成する必要があります。

気軽に穴をあけてください。

アップデート

ここでは、JavaScriptでこのアルゴリズムを実装しています。JavaScriptを使用したのは、すばやく実行できるようにするためです。また、かなり迅速にコーディングしたため、おそらくクリーンアップできます。コメントはあるけど。私も難解なことはしていないので、これは C++ に簡単に移植できるはずです。

アルゴリズムには基本的に 2 つの部分があります。インクリメントとスワッピング (必要な場合)、および繰り返される値の実行の終了インデックスを追跡するマップ上で行われるブックキーピングです。

コードには、ゼロの配列で始まり、ランダムな位置をインクリメントするテスト ハーネスが含まれています。すべての反復の最後に、配列がソートされていることを確認するテストがあります。

var array = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
var endingIndices = {0: 9};

var increments = 10000;

for(var i = 0; i < increments; i++) {
    var index = Math.floor(Math.random() * array.length);    

    var oldValue = array[index];
    var newValue = ++array[index];

    if(index == (array.length - 1)) {
        //Incremented element is the last element.
        //We don't need to swap, but we need to see if we modified a run (if one exists)
        if(endingIndices[oldValue]) {
            endingIndices[oldValue]--;
        }
    } else if(index >= 0) {
        //Incremented element is not the last element; it is in the middle of
        //the array, possibly even the first element

        var nextIndexValue = array[index + 1];
        if(newValue === nextIndexValue) {
            //If the new value is the same as the next value, we don't need to swap anything. But
            //we are doing some book-keeping later with the endingIndices map. That code requires
            //the ending index (i.e., where we moved the incremented value to). Since we didn't
            //move it anywhere, the endingIndex is simply the index of the incremented element.
            endingIndex = index;
        } else if(newValue > nextIndexValue) {
            //If the new value is greater than the next value, we will have to swap it

            var swapIndex = -1;
            if(!endingIndices[nextIndexValue]) {
                //If the next value doesn't have a run, then location we have to swap with
                //is just the next index
                swapIndex = index + 1;
            } else {
                //If the next value has a run, we get the swap index from the map
                swapIndex = endingIndices[nextIndexValue];
            }

            array[index] = nextIndexValue;
            array[swapIndex] = newValue;

            endingIndex = swapIndex;

        } else {
        //If the next value is already greater, there is nothing we need to swap but we do
        //need to do some book-keeping with the endingIndices map later, because it is
        //possible that we modified a run (the value might be the same as the value that
        //came before it). Since we don't have anything to swap, the endingIndex is 
        //effectively the index that we are incrementing.
            endingIndex = index;
        }

        //Moving the new value to its new position may have created a new run, so we need to
        //check for that. This will only happen if the new position is not at the end of
        //the array, and the new value does not have an entry in the map, and the value
        //at the position after the new position is the same as the new value
        if(endingIndex < (array.length - 1) &&
           !endingIndices[newValue] &&
           array[endingIndex + 1] == newValue) {
            endingIndices[newValue] = endingIndex + 1;
        }

        //We also need to check to see if the old value had an entry in the
        //map because now that run has been shortened by one.
        if(endingIndices[oldValue]) {
            var newEndingIndex = --endingIndices[oldValue];

            if(newEndingIndex == 0 ||
               (newEndingIndex > 0 && array[newEndingIndex - 1] != oldValue)) {
                //In this case we check to see if the old value only has one entry, in
                //which case there is no run of values and so we will need to remove
                //its entry from the map. This happens when the new ending-index for this
                //value is the first location (0) or if the location before the new
                //ending-index doesn't contain the old value.
                delete endingIndices[oldValue];
            }
        }
    }

    //Make sure that the array is sorted   
    for(var j = 0; j < array.length - 1; j++) {
        if(array[j] > array[j + 1]) {        
            throw "Array not sorted; Value at location " + j + "(" + array[j] + ") is greater than value at location " + (j + 1) + "(" + array[j + 1] + ")";
        }
    }
}

Answer 2

したがって、ソートされた配列とハッシュテーブルを使用します。配列を調べて、要素が同じ値である「フラット」領域を見つけます。すべての平坦な領域について、1) どこで開始するか (最初の要素のインデックス) 2) その値は何か 3) 次の要素の値 (次に大きい要素) は何かを把握する必要があります。次に、このタプルをハッシュテーブルに入れます。キーは要素の値になります。これは前提条件であり、その複雑さは実際には問題ではありません。

次に、いくつかの要素 (インデックス i) を増やすと、次の大きな要素 (j と呼びます) のインデックスのテーブルを検索し、 と交換iしi - 1ます。次に、1) ハッシュテーブルに新しいエントリを追加します。2) 既存のエントリを以前の値に更新します。

完全なハッシュテーブル (または可能な値の限られた範囲) では、ほぼ O(1) になります。欠点：安定しない。

ここにいくつかのコードがあります：

#include <iostream>
#include <unordered_map>
#include <vector>

struct Range {
    int start, value, next;
};

void print_ht(std::unordered_map<int, Range>& ht)
{
    for (auto i = ht.begin(); i != ht.end(); i++) {
        Range& r = (*i).second;
        std::cout << '(' << r.start << ", "<< r.value << ", "<< r.next << ") ";
    }
    std::cout << std::endl;
}

void increment_el(int i, std::vector<int>& array, std::unordered_map<int, Range>& ht)
{
    int val = array[i];
    array[i]++;
    //Pick next bigger element
    Range& r = ht[val];
    //Do the swapping, so last element of that range will be first
    std::swap(array[i], array[ht[r.next].start - 1]);
    //Update hashtable
    ht[r.next].start--;
}

int main(int argc, const char * argv[])
{
    std::vector<int> array = {1, 1, 1, 2, 2, 3};
    std::unordered_map<int, Range> ht;

    int start = 0;
    int value = array[0];

    //Build indexing hashtable
    for (int i = 0; i <= array.size(); i++) {
        int cur_value = i < array.size() ? array[i] : -1;
        if (cur_value > value || i == array.size()) {
            ht[value] = {start, value, cur_value};
            start = i;
            value = cur_value;
        }
    }

    print_ht(ht);

    //Now let's increment first element
    increment_el(0, array, ht);
    print_ht(ht);
    increment_el(3, array, ht);
    print_ht(ht);

    for (auto i = array.begin(); i != array.end(); i++)
        std::cout << *i << " ";


    return 0;
}

Answer 3

同じ値を持つことができるアイテムの数によって異なります。より多くのアイテムが同じ値を持つことができる場合、通常の配列で O(1) を持つことはできません。

例を見てみましょう: array[5] = 21 で、array[5]++ を実行したいとします。

• アイテムを増やします:

  array[5]++
  

  (これは配列なので O(1) です)。

  したがって、今は配列 [5] = 22 です。

• 次の項目 (つまり、array[6]) を確認します。

  array[6] == 21の場合、 21 より大きい値が見つかるまで、新しいアイテム (つまり、array[7] など) をチェックし続ける必要があります。その時点で、値を交換できます。配列全体をスキャンする必要がある可能性があるため、この検索はO(1)ではありません。

代わりに、アイテムが同じ値を持つことができない場合は、次のようになります。

• アイテムを増やします:

  array[5]++
  

  (これは配列なので O(1) です)。

  したがって、今は配列 [5] = 22 です。

• 次の項目を 21 にすることはできません (2 つの項目が同じ値を持つことはできないため)。そのため、値が 21 より大きい必要があり、配列は既に並べ替えられています。

Answer 4

要件を明確にすることが重要です。最も簡単な方法は、問題を ADT (Abstract Datatype) として表現し、必要な操作と複雑さをリストすることです。

これがあなたが探していると私が思うものです：次の操作を提供するデータ型：

• Construct(n)n:すべての値が であるサイズの新しいオブジェクトを作成します0。

• Value(i): index の値を返しますi。

• Increment(i): index の値をインクリメントしますi。

• Least(): 値が最小の要素 (複数ある場合はそのような要素の 1 つ) のインデックスを返します。

• Next(i)i: トラバーサルがすべての要素を返すように、から始まるソートされたトラバーサルの要素の次の要素のインデックスを返しLeast()ます。

コンストラクターは別として、上記のすべての操作に複雑さを持たせたいと考えていますO(1)。オブジェクトがO(n)スペースを占有することも必要です。

実装ではバケットのリストを使用します。各バケットにはvalueと 要素のリストがあります。各要素には、それが属するバケットへのポインタであるインデックスがあります。最後に、要素へのポインタの配列があります。(C++ では、おそらくポインターではなく反復子を使用します。別の言語では、おそらく侵入リストを使用します。) 不変条件は、バケットが空になることはなくvalue、バケットの は厳密に単調に増加することです。

n要素のリストを持つ値 0 の単一のバケットから始めます。

Value(i)配列の要素iでイテレータによって参照される要素のバケットの値を返すことによって実装されます。Least()最初のバケットの最初の要素のインデックスです。Next(i)element のイテレータによって参照される次の要素のインデックスですi。ただし、そのイテレータがすでにリストの最後を指している場合を除きます。この場合、要素のバケットが最後でない限り、次のバケットの最初の要素です。この場合、要素リストの最後にいます。

関心のある唯一のインターフェイスはIncrement(i)、次のとおりです。

• 要素iがそのバケット内の唯一の要素である場合 (つまり、バケット リストに次の要素がなく、要素iがバケット リストの最初の要素である場合):

  • 関連するバケットの値を増やします。
  • 次のバケットの値が同じ場合は、次のバケットの要素リストをこのバケットの要素リストに追加し (これはO(1)リストのサイズに関係なく、単なるポインタ スワップであるため)、次のバケットを削除します。

• i要素がそのバケット内の唯一の要素ではない場合:

  • バケット リストから削除します。
  • 次のバケットに次の連続値がある場合、要素iを次のバケットのリストにプッシュします。
  • それ以外の場合は、次のバケットの値の方が大きいため、次の連続する値と要素のみで新しいバケットを作成し、iこのバケットと次のバケットの間に挿入します。

Answer 5

はいといいえ。

はい、リストに一意の整数のみが含まれている場合は、次の値のみを確認する必要があることを意味します。いいえ、他の状況ではありません。値が一意でない場合、N 個の重複値の最初の値をインクリメントすることは、N 個の位置を移動する必要があることを意味します。値が浮動小数点の場合、x と x+1 の間に数千の値がある可能性があります

Answer 6

正しい場所が見つかるまで、変更された要素から配列に沿って反復し、次に交換します。平均的なケースの複雑さは O(N) で、N は重複の平均数です。最悪のケースは O(n) で、n は配列の長さです。N が大きくなく、n のスケーリングが悪くない限り、問題はなく、実際には O(1) のふりをすることができます。

重複が標準であり、および/または n で強くスケーリングされる場合、より良い解決策があります。他の回答を参照してください。