4

実際、これは真珠のプログラミングからの興味深いトピックであり、効率的なアルゴリズムを使用して限られたメモリ内で 10 桁の電話番号を並べ替えます。全編はこちらからご覧いただけます

私が興味を持っているのは、実装が Python でどれだけ高速になるかということです。モジュール bitvector を使用して素朴な実装を行いました。コードは次のとおりです。

from BitVector import BitVector
import timeit
import random
import time
import sys

def sort(input_li):
        return sorted(input_li)

def vec_sort(input_li):
        bv = BitVector( size = len(input_li) )
        for i in input_li:
                bv[i] = 1

        res_li = []
        for i in range(len(bv)):
                if bv[i]:
                        res_li.append(i)

        return res_li

if __name__ == "__main__":
        test_data = range(int(sys.argv[1]))
        print 'test_data size is:', sys.argv[1]
        random.shuffle(test_data)

        start = time.time()
        sort(test_data)
        elapsed = (time.time() - start)
        print "sort function takes " + str(elapsed)
        start = time.time()
        vec_sort(test_data)
        elapsed = (time.time() - start)
        print "sort function takes " + str(elapsed)
        start = time.time()
        vec_sort(test_data)
        elapsed = (time.time() - start)
        print "vec_sort function takes " + str(elapsed)

私の macbook (2GHz Intel Core 2 Duo 2GB SDRAM) で配列サイズ 100 から 10,000,000 までをテストしました。結果は次のとおりです。

  • test_data のサイズ: 1000
  • ソート関数は 0.000274896621704 かかります

  • vec_sort 関数は 0.00383687019348 かかります

  • test_data のサイズ: 10000

  • ソート関数は 0.00380706787109 かかります

  • vec_sort 関数は 0.0371489524841 かかります

  • test_data のサイズ: 100000

  • ソート関数は 0.05205​​60741425 かかります

  • vec_sort 関数は 0.374383926392 かかります

  • test_data のサイズ: 1000000

  • ソート関数は 0.867373943329 かかります

  • vec_sort 関数は 3.80475401878 かかります

  • test_data のサイズ: 10000000

  • ソート機能は 12.9204008579 かかります
  • vec_sort 関数は 38.8053860664 かかります

がっかりしたのは、test_data のサイズが 100,000,000 の場合でも、sort 関数は vec_sort よりも高速であることです。vec_sort 関数を高速化する方法はありますか?

4

2 に答える 2

3

Niki が指摘したように、あなたは非常に高速な C ルーチンと Python ルーチンを比較しています。psycoを使用すると少し高速化されますが、C で記述されたビット ベクトル モジュールを使用すると、実際に高速化できます。サイコを使用。

使用した関数は次のとおりです。

def vec_sort2(input_li):
    bv = bitarray(len(input_li))
    bv.setall(0)
    for i in input_li:
        bv[i] = 1

    return [i for i in xrange(len(bv)) if bv[i]]

また、リスト内包表記を使用してソートされたリストを作成したことにも注意してください。これは少し役立ちます。psyco と上記の関数を関数で使用すると、次の結果が得られます。

test_data size is: 1000000
sort function takes 1.29699993134
vec_sort function takes 3.5150001049
vec_sort2 function takes 0.953999996185

補足として、BitVector は Python に対しても特に最適化されていません。bitarray を見つける前に、モジュールにさまざまな微調整を行い、微調整を含むモジュールを使用すると、このサイズの配列で vec_sort の時間が 1 秒以上短縮されました。ただし、bitarray の方がはるかに高速であるため、変更を送信していません。

于 2010-06-07T18:33:16.043 に答える
1

私の Python は最高ではありませんが、コードにバグがあるようです:

bv = BitVector( size = len(input_li) )

ビットベクトルのサイズは、入力配列のサイズと同じです。ビットベクトルをドメインのサイズ - 10^10 にしたいとします。Python のビットベクトルがオーバーフローをどのように処理するかはわかりませんが、ビットベクトルのサイズが自動的に変更されると、2 次動作が発生します。

さらに、Python のソート機能は C で実装されており、純粋に Python で実装されたソートのオーバーヘッドは発生しないと思います。ただし、それによって O(nlogn) アルゴリズムが O(n) アルゴリズムより大幅に高速に実行されることはおそらくないでしょう。

編集：また、このソートは大きなデータセットでのみ機能します。あなたのアルゴリズムは O(n + 10^10) 時間で実行されます (テストに基づいて、これを知っていると仮定します)。これは、小さな入力の場合は O(nlogn) よりも悪くなります。

于 2010-06-07T17:38:46.333 に答える