3

特定の状況で組み込みの timsort を打ち負かすために、python でカウントソートを記述しようとしています。現在、組み込みの sorted 関数よりも優れていますが、非常に大きな配列 (長さが 100 万以上の整数、1000 万以上は試していません) および 10,000 を超えない範囲に対してのみです。さらに、勝利は狭く、特にそれに合わせて調整されたランダムリストでは、カウントソートはかなりの差でしか勝てません.

Pythonコードをベクトル化することで得られる驚異的なパフォーマンスの向上について読んだことがありますが、その方法やここでの使用方法については特に理解していません。このコードをベクトル化して高速化する方法を知りたいです。その他のパフォーマンスに関する提案は大歓迎です。

Python と stdlibs のみの現在の最速バージョン:

from itertools import chain, repeat

def untimed_countsort(unsorted_list):
    counts = {}
    for num in unsorted_list:
        try:
            counts[num] += 1
        except KeyError:
            counts[num] = 1

    sorted_list = list(
        chain.from_iterable(
            repeat(num, counts[num])
            for num in xrange(min(counts), max(counts) + 1)))
    return sorted_list

  • ここで重要なのは生の速度だけなので、速度を上げるためにさらに多くのスペースを犠牲にすることは完全に公正なゲームです.

  • コードはすでにかなり短く明確であることを認識しているため、速度を改善する余地がどれだけあるかはわかりません。

  • 誰かがコードを短くするためにコードを変更した場合、遅くならない限り、それも素晴らしいことです。

  • 実行時間はほぼ 80% 短縮されました! 現在のテストでは、Timsort の 3 倍の速度になりました。

ロングショットでこれを行う絶対最速の方法は、numpy でこのワンライナーを使用することです。

def np_sort(unsorted_np_array):
    return numpy.repeat(numpy.arange(1+unsorted_np_array.max()), numpy.bincount(unsorted_np_array))

これは、純粋な python バージョンよりも約 10 ～ 15 倍速く、Timsort よりも約 40 倍速く実行されます。numpy 配列を受け取り、numpy 配列を出力します。

4

2 に答える 2

1

アルゴリズムについて考えなくても、これはほとんどの純粋な python ループ (非常に遅い) を取り除き、それらを内包表記またはジェネレーターに変換するのに役立ちます (常に通常のforブロックよりも高速です)。また、すべて同じ要素で構成されるリストを作成する必要がある場合は、[x]*n構文がおそらく最速の方法です。はsum、リストのリストを平坦化するために使用されます。

from collections import defaultdict

def countsort(unsorted_list):
    lmin, lmax = min(unsorted_list), max(unsorted_list) + 1
    counts = defaultdict(int)
    for j in unsorted_list:
        counts[j] += 1
    return sum([[num]*counts[num] for num in xrange(lmin, lmax) if num in counts])

これはベクトル化されておらず、numpy も使用していないことに注意してください。

于 2013-08-29T04:21:35.370 に答える