7

私は3つの美しいクイックソートの話を見て、クイックソートをいじっていました。私のPythonでの実装は、cと非常によく似ていました（ピボットを選択し、その周りをパーティション分割して、より小さなパーティションとより大きなパーティションを繰り返します）。私はそれがpythonicではないと思った。

つまり、これはPythonでリスト内包表記を使用した実装です。

def qsort(list):
    if list == []: 
        return []
    pivot = list[0]
    l = qsort([x for x in list[1:] if x < pivot])
    u = qsort([x for x in list[1:] if x >= pivot])
    return l + [pivot] + u

再帰メトqsortRと呼びましょう。ここで、qsortRの実行がlarge（r）リストのqsortよりもはるかに遅いことに気付きました。実際には、再帰法の1000要素でも「最大再帰深度をcmp単位で超えました」。sys.setrecursionlimitでリセットしました。

いくつかの数字：

list-compr 1000 elems 0.491770029068
recursion 1000 elems 2.24620914459
list-compr 2000 elems 0.992327928543
recursion 2000 elems 7.72630095482

すべてのコードはここにあります。

いくつか質問があります。

  • リスト内包表記が非常に速いのはなぜですか？
  • Pythonでの再帰の制限に関するいくつかの啓蒙。最初に100000に設定しましたが、どのような場合に注意する必要がありますか？
    • （「末尾再帰の最適化」とは正確にはどういう意味ですか、どのように実行されますか？）
  • 1000000個の要素を並べ替えようとすると、ラップトップのメモリが占​​有されます（再帰メソッドを使用）。非常に多くの要素を並べ替えたい場合はどうすればよいですか？どのような最適化が可能ですか？
4

3 に答える 3

9

  1. リスト内包表記がなぜこれほど高速なのか?

    forリスト内包表記は、Python のブロックを使用する遅い一般的な方法よりもはるかに高速な C ループを意味するためです。

  2. Python での再帰の制限に関するいくつかの啓発。最初に 100000 に設定しましたが、どのような場合に注意する必要がありますか?

    メモリが不足した場合。

  3. 1000000 個の要素を並べ替えようとすると、ラップトップのメモリが大量に消費されます (再帰法を使用)。非常に多くの要素を並べ替えたい場合はどうすればよいですか? どのような最適化が可能ですか?

    Python の再帰は、すべての関数呼び出しが呼び出しごとに大量のスタック メモリ スペースを割り当てるため、このようなオーバーヘッドをもたらします。

    一般に、反復が答えです (統計的に 99% のユース ケースでパフォーマンスが向上します)。

    メモリ構造について言えば、char、integer、float などの単純なデータ構造がある場合array.arrayは、list.

于 2012-08-24T10:58:59.023 に答える
1

の非再帰的な実装を書いてみましたpartitionか？パフォーマンスの違いは純粋にpartition実装にあると思います。実装内の要素ごとに繰り返します。

アップデート

これが簡単な実装です。それでも超高速でも効率的でもありませんが、元の再帰的なものよりもはるかに優れています。

>>> def partition(data):
...  pivot = data[0]
...  less, equal, greater = [], [], []
...  for elm in data:
...   if elm < pivot:
...    less.append(elm)
...   elif elm > pivot:
...    greater.append(elm)
...   else:
...    equal.append(elm)
...  return less, equal, greater
...
>>> def qsort2(data):
...  if data:
...   less, equal, greater = partition(data)
...   return qsort2(less) + equal + qsort2(greater)
...  return data
...

また、「従来」のバージョンでは、一時的なリストが多く生成されていると思います。

于 2012-08-24T11:10:24.560 に答える
1

メモリが非常に大きくなった場合は、リスト内包表記をインプレース アルゴリズムと比較してみてください。以下のコードは、100K の整数をソートするときにほぼ実行時間を得ますが、1M の整数をソートすると、おそらくリスト内包表記ソリューションでスタックします。4Gb マシンを使用してテストを行いました。完全なコード: http://snipt.org/Aaaje2

class QSort:
def __init__(self, lst):
    self.lst = lst

def sorted(self):
    self.qsort_swap(0, len(self.lst))
    return self.lst

def qsort_swap(self, begin, end):
    if (end - begin) > 1:
       pivot = self.lst[begin]
       l = begin + 1
       r = end
       while l < r:
           if self.lst[l] <= pivot:
               l += 1
           else:
               r -= 1
               self.lst[l], self.lst[r] = self.lst[r], self.lst[l]

       l -= 1
       self.lst[begin], self.lst[l] = self.lst[l], self.lst[begin]    
       # print begin, end, self.lst
       self.qsort_swap(begin, l)
       self.qsort_swap(r, end)
于 2013-05-13T13:40:33.903 に答える