1

私の JSP ページには、60k 以上のオブジェクトを含む可能性のある選択オブジェクトがあります。これらの 60,000 以上のオブジェクトを「masterList」と呼ばれる JavaScript 配列に格納しています。リストをフィルタリングするための入力ボックスをユーザーに提供しました。フィルタリングは、「で始まる」アプローチに基づいています。これを行うより速い方法はありますか？ユーザーが入力ボックスにゼロまたは 1 文字を入力すると、パフォーマンスの問題が発生します。

これが私のコードの外観です。

    var numShown = 0;
    var listLength = masterList.length;     

    for(i = 0; i < listLength; i++){
        if(masterList[i].search(re) != -1){
            selectBox[numShown] = new Option(masterList[i], masterList[i]);
            numShown++;
        }

        // Stop when the number to show is reached and input present
        if(input.value != "" && numShown == maxToShow){
            break;
        }
    }
4

7 に答える 7

2

ループのたびに作成される Option() オブジェクトは何ですか? それ自体がパフォーマンスの問題の原因になる可能性があります。常に新しいオブジェクトを作成する必要があるとは考えにくいため、そのコードを追加できれば、コードの最適化に役立ちます。

検索時間の最適化を開始する非常に基本的な方法は、masterList 内の各文字の開始インデックスを含む 2 番目のオブジェクトを作成することです。ユーザーが作業中に masterList データが変更された場合は、インデックス オブジェクトを再計算する必要があることに注意してください。

例えば

var masterList = [aardvark, apple, balloon, blue, cat, dog];
var indexes = {'a':0, 'b':2, 'c':4, 'd':5};

ユーザーが入力するたびに、入力した最初の文字を取得し、'indexes' オブジェクトでその開始インデックスを参照します。次に、そのインデックスから for ループを開始します。また、一致が見つからない場合、または文字一致の範囲を超えて検索を拡張した場合は、for ループを停止する必要があることにも注意してください。基本的に、最初の検索基準が満たされない場合、masterList の最後まで検索しても意味がありません。

その他の注意事項: for ループで var を使用して i を宣言する必要があります。知っているかどうかにかかわらず、listLength を使用して長さをキャッシュすることで、うまくいきました。そうしないと、Javascript は反復ごとに masterList.length を再計算します。

于 2012-07-13T19:52:37.260 に答える
1

主な問題は、リスト全体を毎回スキャンしていることです。これは避けることができるものです、

1つのアプローチは、リストをソートすることです。これにより、一致の最後に到達したときに、検索でスキャンを停止できるタイミングを判断できます。

また、スキャンではなく、バイナリ検索を実行する必要があります。これは、ソートされたリストで比較的簡単に実行できます。

それができない場合は、代わりにオブジェクトのディレクトリを作成する必要があります。何かのようなもの：

{
   aa: ['aardvark', 'aardwolf' ],
   ab: ['abstain'.....
   ...
}

これにより、本当に必要なスキャンの量が減ります

于 2012-07-13T19:56:46.550 に答える
1

[編集] 100.000 要素の初期配列を使用した例については、この jsfiddleを参照してください。

他の多かれ少なかれ有用な提案は別として：

最初の最適化は、配列をソートすることです。次に、その値を既製Optionのオブジェクトに変換することで、大きな配列を準備できます。第三に、新しい配列mapとfilterメソッドを適用することを考えましたか? test第 4 に、代わりにRegEx を使用しsearchます。これらを使用すると、フィルタリング コードを次のように減らすことができます。

//once, on page load
masterlist = masterlist
             .sort()
             .map(function(item){return new Option(item,item);});

//filtering
var optsfiltered = masterlist.filter(function(item){
     re.lastIndex = 0;
     return re.test(item.value);
    }).slice(0,maxToShow);

//replace selectBox options
selectBox.options.length = 0;
for (var i=0;i<optsfiltered.length;i++){
  selectBox[i] = optsfiltered[i];
}

ブラウザーの互換性のために、マップとフィルターにシムを使用することをお勧めします

于 2012-07-13T21:07:01.497 に答える
1

JQuery UI は優れたオートコンプリート コンポーネントを提供します。60k 要素をクライアントにプッシュすると、設計上の欠陥があると見なされる可能性があります。

このコンポーネントにより、次のことが可能になります。

  • すべての要素をサーバー側にプッシュしたい場合は、配列から単純にオートコンプリートします。
  • Web サービスを使用して表示する要素を提供する、より複雑なオートコンプリート スキーマを構築します (以下のコメントで示唆されているように、サーバー側のキャッシュを検討することをお勧めします)。
于 2012-07-13T19:53:02.057 に答える
0

パフォーマンスの最良のオプションは、入力後にデータをロードすることです。つまり、ユーザーが「tes」と入力すると、サーバーは。のようなJSON文字列を送り返します["test", ...]。

次善の策は、@ Dancrumbが提案したように、物事を木に分割することです。

これらのいずれも実行できない場合、次善のアプローチは、配列が正常であることを確認し、開始点の二分探索を実行することです。Nicholas C. Zakasの良い例がここにあります：http ：//www.nczonline.net/blog/2009/09/01/computer-science-in-javascript-binary-search/

それはあなたをからに連れて行くでしょO(N)うO(lg(N))

値と同じではなくで始まる文字列を検索するように少し変更してから、最初のインスタンスを逆方向に検索する必要があります。

アップデート

使用しているのを見ただけです.search。つまり、これらのアプローチはいずれも使用できず、サーバーでの高額な検索またはクライアントでの高額な検索のいずれかで立ち往生しています。検索を高速化するために、代わりに値で始まることを確認することを検討してください。文字列が別の文字列「StartsWith」であるかどうかを確認するにはどうすればよいですか。

于 2012-07-13T20:00:03.493 に答える
0

配列をループするには、最善の方法で for ループを実行します...

for(var z =listLength;--z;) { do what ever }

これにより、ループごとに評価が保存されるため (たとえば、

私があなただったら、Trieのような高速検索のために別の形式を使用して保持します

配列を使用する必要がある場合は、少なくともそれらをa、b、cなどの配列に分割します...

于 2012-07-13T20:10:32.720 に答える
0

さて、これがあなたが抱えている最大の問題であり、他の解決策（私の他の解決策を含む）がうまくいかない理由です：

if(masterList[i].search(re) != -1)

リストに入力するまで、すべてのエントリに対して正規表現検索を実行しています! これはコストのかかる操作であるだけでなく、単語の途中での一致に関心がある可能性が高いことを意味します。つまり、誰もが提案している接頭辞ベースの最適化に頼ることはできません。

以下は、(A) ヒット率が高く、(B) 本当にやりたいと思っている場合に、かなりうまく機能するアプローチですsearch。

  1. ユーザーが「a」などの文字を入力すると、検索が開始されます。一致するすべてのアイテムを制限 (たとえば 5) まで検索します。エントリをキャッシュに保存します。例えば：

    myCache['a'] = {
    entries: ['aaaa', 'aaab', 'aaac', 'aaad', 'aaae'],
    lastIndex: 5
};

  2. ユーザーが次の文字を入力すると、文字列は「ab」になり、文字列から 1 文字を引いた文字列を取得すると、「a」がmyCache["a"]得られます。値を調べて確認すると、「aaab」と一致しますが、他のすべてが失敗します。まだあと4つ必要です。

  3. から開始しmyCache["a"].lastIndex + 1ます。一致するまで検索を続けます。結果をキャッシュに保存すると、次のようになります。

    myCache['ab'] = {
    entries: ['aaab', 'aaba', 'aabb', 'aabc', 'aabd'],
    lastIndex: 29
};

  4. 弦の長さが長くなるにつれて、手順 2 と 3 を繰り返します。

于 2012-07-13T22:06:47.413 に答える