0

プロジェクトに関する要件の一部として、リストのリストでノード (文字列) を検索する必要があります。セットは N 個のリストで構成され、それぞれが L 個のノードで構成されるリストです。ここで、N は大きな値で、通常は >= 5000 で、L は =< 100 です。

  1. 検索がより迅速かつ簡単になるように、各リストの L ノードを変換するのに理想的なデータ構造は何ですか?

    リストのノードは文字列であるため、ある種のツリー構造の形式でリストを変換することについてはわかりません（各ノードに手動でいくつかの番号を割り当てて、検索が実行されるように適切なツリー構造に変換できますかはいの場合、どのツリー構造が理想的か)

これに関してご協力いただきありがとうございます。

4

3 に答える 3

1

私は2つの構造を提案します：

1）文字列のリストを並べ替えて、バイナリ検索を実行できるようにします（複雑さ：挿入と検索の場合はO（n * log（n）））

2）より良い：挿入と検索がO（1）になるように、文字列をハッシュマップに配置します。

Bツリー（http://en.wikipedia.org/wiki/B-tree）を使用することもできますが、これはリストの順序を維持することに似ており、オーバーヘッドが増えると思います。

パフォーマンスが問題になる場合は、間違いなく（2）を選択します。

于 2012-12-24T08:04:30.370 に答える
1

文字列 (都市名) を形式 (index_in_main_list, index_in_sublist) のタプルにマッピングするハッシュ マップまたはソート ツリーをお勧めします。

ハッシュ マップの場合、これにより文字列の一定時間のルックアップが可能になり、元のリストを反復処理できます。

あなたは、都市とサブリストが旅行ルートである文字列について言及しました。都市はおそらくいくつかの移動ルートにあるため、ハッシュごとにいくつかのタプルを保持する必要があります。

たとえば、Java では、型宣言は次のようになります。

public class IndexTuple {
    public final int fst;
    public final int snc;
    public IndexTuple(int fst, int snd) {
        this.fst = fst;
        this.snd = snd;
    }
}

HashMap<String, ArrayList<IndexTuple>> lookupMap;

// The sublists of cities. I've used an ArrayList as example, but
// that's language and context dependent. Use arrays if the size
// won't change.
ArrayList<ArrayList<String>> cities;

リストを実行して追加するだけで、データ構造を埋めるのは非常に簡単になります。

for(int i = 0; i < cities.size(); i++) {
    for(int j = 0; j < cities.get(i).size(); j++) {
        String city = cities.get(i).get(j));
        if(!lookupMap.containsKey(city) {
            lookupMap.put(city, new ArrayList<IndexTuple>());
        }
        lookupMap.get(city).add(new IndexTuple(i, j));
    }
}

編集:元のリストを反復処理する必要がない場合は、ハッシュ マップまたはツリーを構築した後に削除するだけでよいことに注意してください。インデックスが記憶されているため、都市が属するシーケンスを見つけることができます。反復のためにリストを再構築するのは、一種の混乱になります。

于 2012-12-24T16:23:26.363 に答える
0

実際にはデータ構造を変更しません。リストのリストは、次の2つの理由から非常に優れたデータ構造です。

  1. Mainlist（5）（7）のようなインデックスを使用して、基本的にリストを大きな2D配列（列サイズが異なる）として扱うことができます。
  2. 頭の中で「想像」しやすいので、さらなるコーディングが容易になります

したがって、プログラミング言語に応じて、doubleforループを実行します。

for all elements in mainlist:
   for all elements in sublist:
       if element == target:
           break;
       endif
    endfor
endfor

または、foreachループを使用することもできます。

いずれにせよ、foreachは非常に効率的であり、すべてのリストを繰り返して停止します（breakと言ったら）。他のすべての変換では、多くの計算が必要になる可能性があります。

もう1つのオプションは、izaeraがハッシュマップを使用して言ったとおりですが、コードの残りの部分（リストを操作する場合）は少し難しくなるため、単純にしてください。:)

于 2012-12-24T08:20:15.747 に答える