3

私のリストが1,000,000エントリについて長いとしましょう。アイテムにアクセスするのにかかる時間はO(500,000)、私には非常に長いように思えます。

リストを複数のリストに分割するとどうなりますか? 例を見てみましょう:
リストを 10 の部分に分割すると、次のようなリストになります。

splitted_list = [
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries]
]

アイテムにアクセスする時間O(5) + O(50,000) = O(50,005)は、約 1000% のスピードアップ になります。

元のリストをルート (1000この場合) で分割すると、別の 1000 エントリを持つ 1000 個のリストを含むリストが得られます。

splitted_list = [
    [list with 1000 entries],
    [list with 1000 entries],
    [list with 1000 entries],
    [list with 1000 entries],
    ...
]

次に、アイテムにアクセスする時間を見てみましょう。

O(500) + O(500) = O(1000)
O(1000) < O(50,005) < O(500,000)

これで約1000倍の最適スピードアップ！信じがたいことだと思いますので、私の質問は次のとおりです。

これは実際にも当てはまりますか、それとも単なる理論ですか?

4

3 に答える 3

5

リストからのインデックスによるアイテムの取得は、リストのサイズに関係なくO(1)です。

于 2011-08-11T11:19:55.227 に答える
4

あなたの質問への答えは、各要素が次の要素へのポインターを保持する、リンクされたリストを考えているということです。n 番目の要素を取得する唯一の方法は、リストを最初から順に調べることであるため、これらには O(n) インデックスがあります。

あなたのアイデアはさまざまなデータ構造に関連していますが、最も近いのはおそらくスキップ リストです。これは、リンクされたリストに基づくデータ構造ですが、リストの複数の要素を先にスキップするノードの「ハイウェイ」があります。利点は、高速道路を下ってリストの中央に到達し、個々の要素の精度が必要な場合は「遅い車線」にドロップダウンして、O(log n) のインデックス作成効率を実現できることです。二分木. もちろん、欠点は、ランダム挿入などの他のリンク リスト操作を実行するのがより複雑になる (そして遅くなる) ことです。

ただし、Python のリストは動的に成長する配列として内部で実装されています。これらには O(1) インデックスがあります。これは、3 番目の要素を取得するには、最初の要素のメモリ アドレスに 3 (単位) を追加するだけで、間にあるすべての要素をトラバースする必要がないためです。

データ構造に関するウィキペディアの記事に興味があるかもしれません。

于 2011-08-11T11:52:56.500 に答える
3

リスト内の要素を見つけることについて話していると思います。

並べ替えられたリストを、先頭へのポインターを持つ多くの並べ替えられたリストに分割することについて話している場合は、おめでとう、B ツリーをほぼ発見したことになります。

これらのリストが実際に配列である場合 (つまり、一定時間のランダム アクセスがある場合)、バイナリ検索を実行することもできます。

于 2011-08-11T11:21:38.940 に答える