2

ソートされていない 300k 要素の長いリストがある場合、このリストを最初にソートしてから、リストで「for」ループを実行するとコードが高速化されますか? とにかく「forループ」を実行する必要があり、リスト内包表記を使用できません。

sortedL=[list].sort() 

for i in sortedL:
  (if i is somenumber)
     "do some work"

sortedL がソートされており、リスト全体を読み取っていないことを python に通知するにはどうすればよいですか。リストをソートする利点はありますか? ある場合、どのように実装できますか？

4

3 に答える 3

8

リストを並べ替えて、すぐに検索できるようにすることを検討しているようですsomenumber。

並べ替えが価値があるかどうかは、一度検索するか、繰り返し検索するかによって異なります。

  • 検索が 1 回だけの場合、リストを並べ替えても速度は上がりません。要素を探してリストを反復処理するだけで完了です。

  • 一方、値を繰り返し検索する必要がある場合は、必ずリストを事前に並べ替えてください。これにより、 を使用bisectして値をすばやく検索できます。

3 番目のオプションは、要素を に格納することdictです。これにより、ルックアップが最速になる可能性がありますが、おそらくリストを使用するよりもメモリ効率が低下します。

于 2012-12-18T21:20:45.493 に答える
3

forPython でのループのコストは、入力データがソートされているかどうかに依存しません。

そうは言っても、最初に並べ替えるbreakと、forループを早期に終了したり、アルゴリズムレベルで他の計算を保存したりできる場合があります。

于 2012-12-18T21:14:01.900 に答える
3

sorted 内を検索する場合はlist、ソートを利用するアルゴリズムが必要です。

1 つの可能性は組み込みbisectモジュールです。これを使用するのは少し面倒ですが、その上に単純なソート済みリスト関数を作成するためのレシピがドキュメントに記載されています。

そのレシピを使用すると、次のように記述できます。

i = index(sortedL, somenumber)

もちろん、1 回の検索を高速化するためだけに並べ替えを行う場合、これは少しばかげています。並べ替えには O(N log N) の時間がかかり、検索には O(log N) の時間がかかり、合計で O(N log N) の時間がかかります。線形検索を行うだけでも O(N) 時間かかります。したがって、通常、同じリストに対して log N 回の検索を行う場合を除き、これは行う価値がありません。

実際に並べ替えが必要なく、高速検索だけが必要な場合は、 のset代わりに を使用できますlist。これにより、病理学的ケースを除くすべての O(1) ルックアップが得られます。

また、追加/削除などを続けながらリストをソートしたままにしたい場合blist.sortedlistは、単純なリストの代わりに次のようなものを使用することを検討してください。

于 2012-12-18T21:22:02.920 に答える