2

私は整数の配列を持っていますが、それは数十万（またはそれ以上）に達する可能性があり、元々積み重ねられていた方法であるため、数値的に昇順で並べ替えられています。

配列をクエリして、>=入力された数値の最初の出現のインデックスをできるだけ効率的に取得できるようにする必要があります。考えもせずにこれを行う方法を知る唯一の方法は、条件がtrueになるまで配列テストを繰り返し、その時点で繰り返しを停止することです。ただし、これはこの問題に対する最も費用のかかる解決策であり、私はそれを解決するための最良のアルゴリズムを探しています。

私はObjective-Cでコーディングしていますが、応答できる人々の聴衆を広げるためにJavaScriptで例を示します。

// Sample set
var numbers = [1, 7, 23, 23, 23, 89, 1002, 1003];

var indexAfter100 = getIndexOfValueGreaterThan(100);
var indexAfter7 = getIndexOfValueGreaterThan(7);

// (indexAfter100 == 6) == true
// (indexAfter7 == 2) == true

この検索を実行するためにこのデータをDBに入れることは、メモリ内でこれにすばやく取り組むためのある種のアルゴリズムを見たいと思っているので、最後の手段にすぎません。

私のプログラムはすでに各番号をこのスタックに1つずつプッシュしているので、データ構造を変更したり、配列を構築するときに追加のデータ構造を保存したりすることができます。そのため、次のコードを変更するだけです。それらをスタックに追加します。スタックに追加されているインデックスを検索することはできません。これは、検索操作が事後に異なる値で頻繁に繰り返されるためです。

今は「B-Tree」を考えていますが、正直なところ、どうやって実装すればいいのかわからないので、それを理解する前に、この単一のユースケースに合う素晴らしいアルゴリズムがあるのではないかと思います。より良い？

4

5 に答える 5

7

二分探索を使用する必要があります。Objective Cには、そのための組み込みメソッドを含めることもできます（私が知っている多くの言語にはあります）。データをディスクに保存する場合を除いて、Bツリーはおそらくあまり役​​に立ちません。

于 2010-10-24T13:44:14.147 に答える
2

Objective-Cについてはわかりませんが、C（プレーン'ol C）には次の関数が付属していますbsearch（AFAIK以外に、Obj-CはC関数を問題なく呼び出すことができます）。

http://www.cplusplus.com/reference/clibrary/cstdlib/bsearch/

それは基本的にあなたが必要としているもののように聞こえる二分探索を行います。

于 2010-10-24T13:49:51.753 に答える
1

高速検索アルゴリズムは、それほど長くはかからずにそのサイズのintの配列を処理できるはずです（そして配列はソートされているので、おそらくバイナリ検索が最適です）。

私はbtreeがおそらくやり過ぎだと思います...

于 2010-10-24T13:47:58.150 に答える
0

それらは特定の昇順でソートされ、大きいものだけが必要なので、その配列をシリアル化し、INTで分解し、大きいINTを保持するシリアル化された文字列の一部を保持してから、シリアル化を解除してボイラーします。

于 2010-10-24T15:02:17.467 に答える
0

線形検索は、順次検索とも呼ばれ、各要素を最初から順番に調べて、目的の要素がデータ構造に存在するかどうかを確認します。データ量が少ない場合、この検索は高速です。簡単ですが、必要な作業は検索するデータ量に比例します。要素数を2倍にすると、目的の要素が存在しない場合に検索にかかる時間が2倍になります。

二分探索は、より大きな配列に対して効率的です。ここでは、真ん中の要素をチェックします。値が探している値よりも大きい場合は、前半を確認します。それ以外の場合は、後半を確認します。目的のアイテムが見つかるまでこれを繰り返します。テーブルは、バイナリ検索のためにソートする必要があります。各反復でデータの半分を削除します。対数

于 2014-09-17T10:33:11.050 に答える