C++を使用して2つのソートされた配列の一致するインデックスのインデックスを見つける最も効率的な方法

Question

私は現在解決策を持っていますが、この問題になるほど効率的ではないと感じています。この。

私は2つの配列（例：std :: vectors）を持っています。両方の配列には、ソートされているが値が疎な固有の整数値しか含まれていません。つまり、1,4,12,13 ...私が求めているのは、同じだ。たとえば、array1の値は1,4,12,13で、array2の値は2,12,14,16です。最初の照合値インデックスは配列2で1です。配列内のインデックスは、このインデックスを使用して "一致する"データを含む他の配列を持つため、重要です。

私は配列を使用することに限定されず、マップも可能です。私は2つの配列を1回だけ比較しています。彼らは最初のマッチの後に再利用されません。いずれかの配列では、値が小さいものから多いもの（30万以上）がありますが、必ずしも同じ数の値を持つとは限りません（これにより、はるかに簡単になります）。

ひどい場合はO ）。マップを使用すると、より良いO（ログN）が得られますが、私はまだ値のマップ、インデックスのペアに配列を変換しているでしょう。

私は現在コンテナのタイプ変換を行わない必要があります。 2つの配列のうちの小さいほうにループします。小配列（array1）の現在の要素と大配列（array2）の現在の要素を比較します。 array1要素の値がarray2要素の値より大きい場合は、array1の要素の値（whileループ）を超えないように、array2のインデックスを増やします。次に、array1要素の値がarray2要素よりも小さい場合は、次のループ反復に進み、再び開始します。さもなければ、それらは等しくなければならず、私は、一致する値のいずれかの配列にインデックスを持ちます。

このループでは、すべての値が一致する場合はO（N）、一致しない場合はさらに悪いO（2N）になります。だから、もっと速いものがあるのだろうか？ 2つの配列がどれくらいの頻度で一致するかを知るのは難しいですが、ほとんどの配列がより多くのものにマッチします。

私は問題を十分に説明していただき、これを改善するためのフィードバックやヒントをいただければ幸いです。

コード例は：

std::vector<int> array1 = {4,6,12,34}; 
std::vector<int> array2 = {1,3,6,34,40}; 

for(unsigned int i=0, z=0; i < array1.size(); i++) 
{ 
    int value1 = array1[i]; 
    while(value1 > array2[z] && z < array2.size()) 
     z++; 

    if (z >= array2.size()) 
     break; // reached end of array2 

    if (value1 < array2[z]) 
     continue; 

    // we have a match, i and z indices have same value 

} 

結果は、配列が既にソートされているので、あなただけ使用することができる配列1 = [1,3]および配列2 = [2,3]

Answer 1

私は、些細な線形マージよりもスパース分布で優れたアルゴリズムを使ってこの関数の実装を書いています。

^†の場合、複雑さはO（n）ですが、分布が大きく異なる範囲で最適な場合はO（log n）に近づくはずです。しかし、私は最悪の場合がO（n log n）よりも良くないことを証明できませんでした。一方、私はその最悪の事態を見つけることができませんでした。

サブレンジや生の配列など、あらゆるタイプの範囲を使用できるようにテンプレート化しました。技術的には、非ランダムアクセスイテレータでも動作しますが、複雑さははるかに大きいので推奨しません。その場合には線形探索にフォールバックするアルゴリズムを変更することは可能だと思いますが、私は気にしませんでした。 類似分布によって†

^{、Iは、配列のペアが多く交差を有することを意味します。交差するは、2つの配列をソート順にマージすると、ある配列から別の配列に切り替えることを意味します。}

#include <algorithm> 
#include <iterator> 
#include <utility> 

// helper structure for the search 
template<class Range, class Out> 
struct search_data { 
    // is any there clearer way to get iterator that might be either 
    // a Range::const_iterator or const T*? 
    using iterator = decltype(std::cbegin(std::declval<Range&>())); 
    iterator curr; 
    const iterator begin, end; 
    Out out; 
}; 

template<class Range, class Out> 
auto init_search_data(const Range& range, Out out) { 
    return search_data<Range, Out>{ 
     std::begin(range), 
     std::begin(range), 
     std::end(range), 
     out, 
    }; 
} 

template<class Range, class Out1, class Out2> 
void match_indices(const Range& in1, const Range& in2, Out1 out1, Out2 out2) { 
    auto search_data1 = init_search_data(in1, out1); 
    auto search_data2 = init_search_data(in2, out2); 

    // initial order is arbitrary 
    auto lesser = &search_data1; 
    auto greater = &search_data2; 

    // if either range is exhausted, we are finished 
    while(lesser->curr != lesser->end 
      && greater->curr != greater->end) { 
     // difference of first values in each range 
     auto delta = *greater->curr - *lesser->curr; 

     if(!delta) { // matching value was found 
      // store both results and increment the iterators 
      *lesser->out++ = std::distance(lesser->begin, lesser->curr++); 
      *greater->out++ = std::distance(greater->begin, greater->curr++); 
      continue; // then start a new iteraton 
     } 

     if(delta < 0) { // set the order of ranges by their first value 
      std::swap(lesser, greater); 
      delta = -delta; // delta is always positive after this 
     } 

     // next crossing cannot be farther than the delta 
     // this assumption has following pre-requisites: 
     // range is sorted, values are integers, values in the range are unique 
     auto range_left = std::distance(lesser->curr, lesser->end); 
     auto upper_limit = 
      std::min(range_left, static_cast<decltype(range_left)>(delta)); 

     // exponential search for a sub range where the value at upper bound 
     // is greater than target, and value at lower bound is lesser 
     auto target = *greater->curr; 
     auto lower = lesser->curr; 
     auto upper = std::next(lower, upper_limit); 
     for(int i = 1; i < upper_limit; i *= 2) { 
      auto guess = std::next(lower, i); 
      if(*guess >= target) { 
       upper = guess; 
       break; 
      } 
      lower = guess; 
     } 

     // skip all values in lesser, 
     // that are less than the least value in greater 
     lesser->curr = std::lower_bound(lower, upper, target); 
    } 
} 

#include <iostream> 
#include <vector> 

int main() { 
    std::vector<int> array1 = {4,6,12,34}; 
    std::vector<int> array2 = {1,3,6,34}; 

    std::vector<std::size_t> indices1; 
    std::vector<std::size_t> indices2; 

    match_indices(array1, array2, 
        std::back_inserter(indices1), 
        std::back_inserter(indices2)); 

    std::cout << "indices in array1: "; 
    for(std::vector<int>::size_type i : indices1) 
     std::cout << i << ' '; 

    std::cout << "\nindices in array2: "; 
    for(std::vector<int>::size_type i : indices2) 
     std::cout << i << ' '; 
    std::cout << std::endl; 
} 

Answer 2

のインデックスに一致するであろうmergesortのマージステップに非常によく似たものです。これは、各配列のhead要素を調べ、下の要素を破棄します（次の要素が先頭になります）。一致が見つかったとき（またはいずれかの配列が使い尽くされたとき、一致しないことを示す）に停止します。

これはO（n）であり、任意のdistubtionsに対して最も速く実行できます。特定のクラスタ化されたディストリビューションでは、常に次の要素を見るのではなく、「スキップ・アヘッド」アプローチを使用できます。これにより、特定のディストリビューションの実行時間よりもO（n）時間が長くなる可能性があります。例えば、配列1,2,3,4,5と10,11,12,13,14が与えられたアルゴリズムでは、わずか1回の比較（5 < 10）に一致するものがないと判断することができます。

Answer 3

保存されている数字の範囲は何ですか？

数字は整数で、ソートされ、疎である（つまり非連続的である）と、30万を超える可能性がありますが、実際の範囲は何ですか？

私が尋ねる理由は適度に小さい上限がある場合に、ということで、uは、（たとえば、U =50万）、最速かつ最も好都合ソリューションは、単なる指標として値を使用するかもしれません。はい、あなたはメモリを浪費しているかもしれませんが、実際には4 * uのメモリがありますか？これはアプリケーションとターゲットプラットフォームによって異なります（つまり、メモリに制約のある組み込みシステムの場合は、32GiB RAMのラップトップをお持ちの場合よりも良い考えになる可能性は低いです）。

値が多かれ少なかれ0-2^31-1に広がっている場合、この粗い考え方は魅力的ではありませんが、他のものを単純に活用できる入力値のプロパティがあるかもしれませんその範囲よりも。かなりシンプルなハッシュ関数を手書きで書くことができます。

また、実際にインデックスをすばやく取得できる必要があるかどうか、またはインデックスがすぐに他のアレイに存在するかどうかを判断できるようにする必要があるかどうかを検討する必要があります。特定のインデックスに値が存在するかどうかは1ビットだけで済みますので、入力値の範囲のビットマップを32倍少ないメモリで使用することができます（つまり、5LSBをマスクしてビット位置として使用し、 27ビット右5桁とそれを配列インデックスとして使用）。

最後に、使用する準備ができているメモリ量（64Kiの4バイト整数に対応する256KiBを決定する）を決定した場合は、ハイブリッド手法を検討する価値があります。はるかに小さなサブ問題に陥る。 LSBがかなり均等に分布している300,000の値があるとします。次に、平均して4または5の長さのリストのルックアップテーブルにインデックスとして16のLSBを使用して、他の方法で検索することができます。数年前、私は細胞のIDを持っている〜200,000,000の細胞を持っていたいくつかのシミュレーションソフトウェアに取り組みました。いくつかのユーティリティ機能は、idでセルを識別するためにバイナリ検索を使用しました。我々は、この戦略により、大幅に、かつ非侵略的にそれをスピードアップすることができました。完璧な解決策ではありませんが、大きな改善です。 （LSBが均等に分散されていない場合は、おそらくそれが悪用できるプロパティか、多分ハッシュのビットを選択するか、または少しハッシングを行うことができます）

私は、 「ハッシュ」、「アイデンティティハッシュ」や単純なマスキング/モジュロでさえ、「あなたのソリューションは完全に一般的である必要はありません」と、「あなたのソリューションは完全にスペース効率が良い」必要はありません。上。