バブルソートを使用してリストを反転する次のコードがあり、パフォーマンスが最悪です。
for i in xrange(len(l)):
for j in xrange(len(l)):
if l[i]>l[j]:
l[i], l[j] = l[j], l[i]
場合によっては ( の場合len(l) = 100000)、コードが実行を完了するのに 2 時間以上かかる場合があります。これは非常に奇妙だと思います。コードを修正するか、いくつかの提案をしてください。numpyそしてnumarray解決策は大歓迎です。
バブル ソートは、ソートするのに恐ろしいアルゴリズムです。それが原因である可能性が高いです。速度が必要な場合は、クイック ソートやマージ ソートなどの別のアルゴリズムを試します。
これはバブル ソートとは言えません...些細な間違いを犯さない限り、これは Python のバブル ソートに近いものになります。
swapped = True
while swapped:
swapped = False
for i in xrange(len(l)-1):
if l[i] > l[i+1]:
l[i],l[i+1] = l[i+1],l[i]
swapped = True
全体的な考え方は、「バブル」が配列に沿って移動し、リストを移動するまで隣接する値を交換し、何も交換しないことに注意してください。いくつかの最適化を行うことができます (内側のループのサイズを縮小するなど) が、通常は「宿題を重視する」場合にのみ、気にする価値があります。
編集: 固定長() -> len()
速度を比較するためのベンチマークとしてそれを使用しようとしていたとおっしゃっていたと思います。
一般的に、Python は Ruby よりも少し速いと思いますが、Java/C/C++/C# ほどではありません。Java は C の 2 倍以内ですが、すべてのインタープリター言語は約 100 倍遅くなりました。
アプリ/言語/その他の多くの比較については、「プログラミング言語ゲーム」をグーグルで検索できます。パフォーマンスが向上する可能性がある場合は、Python JIT を確認してください。
Ruby と比較して、より公平なテストを確認することもできます。
編集：楽しみのために（質問とは関係ありません）これをチェックしてください--
public class Test {
public static void main(String[]s) {
int size=Integer.valueOf(s[0]).intValue();
Random r=new Random();
int[] l=new int[size];
for(int i=0;i<size;i++)
l[i]=r.nextInt();
long ms=(new Date()).getTime();
System.out.println("built");
if(fast) {
Arrays.sort(l);
else {
int temp;
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
if(l[i]>l[j]) {
temp=l[i];
l[j]=l[i];
l[j]=temp;
}
}
ms=(new Date()).getTime()-ms;
System.out.println("done in "+ms/1000);
}
}
これの面白いところ: Java の実行時間は次のようになっています。
配列サイズ 遅い時間 速い時間 100k 2s 0s 1M 23s 0s 10分39分2秒 100M NO 23s
この追加が質問と関係があるわけではありませんが、組み込みの実装は高速です。ソートよりも生成に時間がかかったと思います (Random の呼び出しとメモリ割り当てでは意味があると思います)。
最後のものを実行するために、CLI と -Xmx1000M に入る必要がありました。
バブル ソートでは、O(N 2 ) の比較操作 (または反復) が行われます。N = 100,000 の場合、10,000,000,000 回の反復があることを意味します。これに 2 時間かかる場合 (10,000 秒と呼びます)、1 秒あたり 1,000,000 回の反復、つまり反復あたり 1 マイクロ秒を取得することを意味します。それは素晴らしい速度ではありませんが、それほど悪くはありません。そして、私は手を振って、一定の倍率を無視しています。
クイックソートを使用すると、Nlog(N) 回の反復が得られます。これは、約 1,000,000 回の反復を意味し、合計で 1 秒かかります。(log 10 (N) は 5 です。簡単にするために 10 に切り上げました。)
これで、バブル ソートが大規模なデータ セットに適していない理由が十分に示されました。100,000 アイテムは、それを示すのに十分な大きさです。
基本的に、このような大規模なデータセットでバブルを使用して時間を無駄にしていると思います。遅い理由は3つあります。
1）Pythonが遅い2）バブルソートが遅い3）リストされているバブルソートが正しく/非効率的にコーディングされている。
コーディング方法に関係なく、O（N ^ 2）になります。マージ/ツリーソートを使用しないのはなぜですか。または、クイックソート（最悪の場合はO（N ^ 2））を試したい場合は、特定のデータセットの方が高速である可能性があります。データにすでに多くの順序が含まれている場合、クイックソートは経験的に高速であると思います。
一般に、バブルソートは、入力内の要素の数が増えるにつれて、ほとんどの可能な入力にうまくスケーリングしません。（つまり、O（N ^ 2）です。）
サイズNのランダムな入力配列が与えられると、Nが大きくなるにつれて、バブルソートですばやく並べ替えられる配列（たとえば、ほとんど並べ替えられた配列）を取得する可能性ははるかに低くなります。ソートに長い時間がかかる配列を取得する可能性がはるかに高くなります。
ただし、ここでの本当のキッカーは、投稿したコードがバブルソートではないということです。従来、バブルソートは、スワップが行われなかった場合、およびすでにソートされた値をスワップしようとしない場合、早期に終了します。（P回のパスの後、P個の最後のアイテムは正しい順序になるため、それらを処理する必要はありません。）投稿された実際のコードは常に配列内のすべてのペアを検査するため、常に内部ループを実行しますN^2回。100000要素の場合、これは10000000000回の反復です。
ここで、ベースのバブル ソートとより合理化されたバージョン (ベースと変更) を比較するためにまとめたコードをいくつか示します。
from array import *
from random import *
from time import *
def randarray(typecode, numElements, minValue, maxValue):
a = array(typecode)
for i in xrange(0, numElements):
a.append(randint(minValue, maxValue))
return a
def basesort(l):
for i in xrange(len(l)):
for j in xrange(len(l)):
if l[i]<l[j]:
l[i], l[j] = l[j], l[i]
return l
def modifiedsort(l):
NotComplete = True
i = 0
arange = xrange(len(l))
while NotComplete:
NotComplete = False
for j in xrange(len(l) - i):
if l[i]<l[j]:
l[i], l[j] = l[j], l[i]
NotComplete = True
i += 1
Num = 1000
b = randarray('i', Num, 1, 100000)
m = b[:]
print 'perform base bubble sort'
t = time()
basesort(b)
basetime = time() - t
print basetime
#print a
print 'complete'
print 'perform modified bubble sort'
t = time()
modifiedsort(m)
modtime = time() - t
print modtime
#print a
print 'complete'
print 'mod sort is ', basetime / modtime,' fast then base sort'
1 つは、ループが多すぎることです。内側のループは、0 からではなく、i + 1 からリストの最後まで進む必要があります。次に、他の人が指摘したように、バブル ソートには O(N^2) の複雑さがあるため、100000 要素の場合、10,000,000,000 回ループします。これは、インタープリター型言語のパフォーマンスが最も悪い領域の 1 つがループであるという事実によって悪化します。それはすべて、信じられないほどのパフォーマンスの低下につながります。これが、このようなタイトなループを必要とする計算が通常 C/C++ で記述され、Python などの言語で使用できるようにラップされる理由です。
まず第一に、この返信の目的のために、私はあなたがそれを自分で主張しているので、さまざまな言語をベンチマークするためだけにこれを行っていると想定しています. したがって、「バブル ソートは単に遅い」という領域には立ち入らないことにします。本当の問題は、Python ではなぜこれほど遅いのかということです。
その答えは、Python は本質的に C++ や Java よりもはるかに遅いということです。一般的なイベント ドリブンまたは I/O バウンドのアプリケーションでは、ほとんどの時間が入力待機中のアイドリングまたは I/O 呼び出しの完了の待機に費やされるため、これは見られません。ただし、あなたの場合、アルゴリズムは完全に CPU バウンドであるため、Python バイトコード インタープリターのパフォーマンスを直接測定しています。これは、C++ と Java の両方で発生する、対応するネイティブ コードの実行よりも 20 ～ 30 倍遅いと推定されています。
一般に、Python で実行時間の長い CPU バインド ループを作成するときはいつでも、この種のパフォーマンスを期待する必要があります。これを修正する唯一の方法は、ループ全体を C に移動することです。本体だけを (たとえば NumPy を使用して) 移動しても、ループの反復自体は引き続き Python インタープリターによって実行されるため、あまり役に立ちません。
比較やスワップを10万×10万回実行するつもりなので。コンピューターが最も内側のステートメントを毎秒 1,000,000 回実行するのに十分な速さである場合でも、それは 167 分であり、3 時間にはわずかに足りません。
余談ですが、SO に関するこれらのばかげた質問がこれほど多くあるのはなぜですか? 簡単な代数ができることはプログラミングの前提条件ではないでしょうか? ;-)
独自のソートに興味がある場合は、数行のコードでバブル ソートをコーム ソートに変更できます。コーム ソートは、ベスト ソートとほぼ同じくらい優れています。もちろん、独自の並べ替えを行うことは、学習課題として残しておくのが最善です。
コム ソートはバブル ソートよりも優れており、クイック ソートのようなより複雑なアルゴリズムに速度で匹敵します。
それは私にはバブル ソートのようには見えません。もしそうなら、それは非常に非効率的な実装です。
追加するのを忘れていました。データセットのサイズとキーの分布についてある程度わかっている場合は、O(N) になる基数ソートを使用できます。基数ソートの概念を理解するために、0 から 100,000 の間で多かれ少なかれ分布する数値をソートする場合を考えてみましょう。次に、ハッシュ テーブルに似たもの、たとえば 100,000 個のリストの配列を作成し、それぞれの数値をバケットに追加します。これは、いくつかのランダム データを生成し、それを並べ替え、ランダム セグメントを出力する、私が数分で書いた実装です。100,000 個の整数の配列を実行するのにかかる時間は 1 秒未満です。
Option Strict On Option Explicit On
モジュール Module1
Private Const MAX_SIZE As Integer = 100000
Private m_input(MAX_SIZE) As Integer
Private m_table(MAX_SIZE) As List(Of Integer)
Private m_randomGen As New Random()
Private m_operations As Integer = 0
Private Sub generateData()
' fill with random numbers between 0 and MAX_SIZE - 1
For i = 0 To MAX_SIZE - 1
m_input(i) = m_randomGen.Next(0, MAX_SIZE - 1)
Next
End Sub
Private Sub sortData()
For i As Integer = 0 To MAX_SIZE - 1
Dim x = m_input(i)
If m_table(x) Is Nothing Then
m_table(x) = New List(Of Integer)
End If
m_table(x).Add(x)
' clearly this is simply going to be MAX_SIZE -1
m_operations = m_operations + 1
Next
End Sub
Private Sub printData(ByVal start As Integer, ByVal finish As Integer)
If start < 0 Or start > MAX_SIZE - 1 Then
Throw New Exception("printData - start out of range")
End If
If finish < 0 Or finish > MAX_SIZE - 1 Then
Throw New Exception("printData - finish out of range")
End If
For i As Integer = start To finish
If m_table(i) IsNot Nothing Then
For Each x In m_table(i)
Console.WriteLine(x)
Next
End If
Next
End Sub
' run the entire sort, but just print out the first 100 for verification purposes
Private Sub test()
m_operations = 0
generateData()
Console.WriteLine("Time started = " & Now.ToString())
sortData()
Console.WriteLine("Time finished = " & Now.ToString & " Number of operations = " & m_operations.ToString())
' print out a random 100 segment from the sorted array
Dim start As Integer = m_randomGen.Next(0, MAX_SIZE - 101)
printData(start, start + 100)
End Sub
Sub Main()
test()
Console.ReadLine()
End Sub
終了モジュール 開始時間 = 2009 年 6 月 15 日 4:04:08 PM 終了時間 = 2009 年 6 月 15 日 4:04:08 PM 操作数 = 100000 21429 21430 21430 21431 21431 21432 21433 21435 21435 21437 21436 2143 ...
できるよ
l.reverse()
スクリプトee.py :
l = []
for i in xrange(100000):
l.append(i)
l.reverse()
lyrae@localhost:~/Desktop$ time python ee.py
real 0m0.047s
user 0m0.044s
sys 0m0.004s
他の投稿が言うように、バブルソートは恐ろしいです。あなたが経験しているように、パフォーマンスが悪いため、絶対に避けるべきです。幸いなことに、たとえばhttp://en.wikipedia.org/wiki/Sorting_algorithm
など
、他にも多くの並べ替えアルゴリズムがあります。
学校での私の経験では、クイックソートとマージソートは、バブル ソートと一緒に、またはバブル ソートの直後に導入された他の 2 つの基本的なソート アルゴリズムです。したがって、より効果的な並べ替え方法を学ぶために、それらを調べることをお勧めします.