4

私はそれに慣れていませんが、Pythonはあまり使用していません。私の知識はかなり広く、言語についてはあまり深くありません。おそらく、ここでより知識のある人が私の質問に答えることができます。リストにアイテムを追加し、追加されたアイテムとして並べ替える必要がある状況に陥っています。これを行う簡単な方法は次のとおりです。

list.append(item)                  // O(1)
list.sort()                        // ??

これがアイテムをリストに追加する唯一の方法であるとしたら、リストは追加ごとに並べ替えられるため、並べ替えがかなり効率的になることを願っています。ただし、これも機能します。

inserted = False
for i in range(len(list)):         // O(N)
    if (item < list[i]): 
        list.insert(i, item)       // ??
        inserted = True
        break
if not inserted: list.append(item)

これらのいずれかが明らかにより効率的であるかどうか誰かに教えてもらえますか？私は2番目のステートメントに傾いていますが、実際にはわかりません。

4

2 に答える 2

7

あなたが探しているのはbisectモジュールであり、おそらくinsort_leftです

したがって、式は次のように同等に記述できます。

から

some_list.append(item)                  // O(1)
some_list.sort()                        // ??

に

bisect.insort_left(some_list, item)
于 2013-02-13T19:21:02.587 に答える
2

挿入ポイントの後に来るすべての要素を移動（コピー）する必要があるため、終了付近を除く任意の場所への挿入にはO（n）時間がかかります。しかし一方で、すべての比較ベースのソートアルゴリズムは、平均してOmega（n log n）の比較を行う必要があります。多くのソート（Pythonが使用するtimsortを含む）は、おそらくあなたの入力（「ほぼソートされた」場合）を含む多くの入力で大幅に改善されます。それでも、少なくともすぐに正しい位置に挿入するのと同じ数の要素を移動する必要があります。また、かなりの追加作業を行う必要があります（すべての要素を検査して、正しい順序になっていることを確認します。さらに、パフォーマンスを向上させる複雑なロジックもありますが、あなたの場合はそうではありません）。これらの理由から、少なくとも大きなリストの場合は、おそらく遅くなります。

Cで記述されているため（CPythonで記述されていますが、他のPythonにも同様の理由が当てはまります）、Pythonで記述された線形スキャンよりも高速である可能性があります。それは、挿入点を見つける方法の問題を残します。二分探索はこの部分をO（log n）時間で実行できるため、ここでは非常に便利です（もちろん、挿入はO（n）のままですが、ソートされたリストが必要な場合はこれを回避する方法はありません）。残念ながら、二分探索は実装がかなり難しいです。幸い、これはすでに標準ライブラリに実装されていますbisect。

于 2013-02-13T19:26:43.877 に答える