Pythonのソーティングの時間計測

Ο(n log_2 n )で動作する3つのソーティングアルゴリズム(マージソート，ヒープソート，クイックソート) とPythonのsort関数の実行時間を比較しています．比較用インスタンスは，n∈[100, 1000]で100刻み，リストの要素は[0, 10000]の範囲の「実数」とします．要素数ごとに100インスタンス作成します．
インスタンスを用いて，4つのソート手法の実行時間を比較します．
現在のコードは以下の通りです．
[my_sort.py]

Python
1import sys
2import math
3        
4def merge(A,p,q,r):   
5     
6    n1=q-p+1
7    n2=r-q    
8    
9    L=[]
10    R=[]
11    
12    #LにAの左側をコピー
13    for i in range(n1):
14        L.append(A[p+i])
15
16    #RにAの右側をコピー    
17    for j in range(n2):
18        R.append(A[q+j+1])
19        
20    L.append(sys.maxsize)
21    R.append(sys.maxsize)
22        
23    i=0
24    j=0
25        
26    for k in range(p, r+1):
27        if L[i]<=R[j]:
28                A[k]=L[i]
29                i=i+1
30        else:
31                A[k]=R[j]
32                j=j+1
33      
34def merge_sort(A,p,r): 
35    
36    if p<r:
37        
38        q=math.floor((p+r)/2)
39        
40        merge_sort(A,p,q)
41        merge_sort(A, q+1,r)
42        merge(A,p,q,r)
43        
44def left(i):
45    return 2*i+1
46
47def right(i):
48    return 2*i+2          
49        
50def max_heapify(A,i,heapsize):
51    l=left(i)
52    r=right(i) 
53    if (l<=heapsize)and (A[l]>A[i]): 
54        largest=l
55    else:
56        largest=i
57        
58    if(r<=heapsize)and(A[r]>A[largest]):
59        largest=r
60        
61    if largest!=i:
62        temp=A[i] 
63        A[i]=A[largest]
64        A[largest]=temp 
65        max_heapify(A,largest,heapsize)        
66        
67def build_max_heap(A):
68    for i in range(math.floor((len(A))/2)-1,-1,-1):
69        max_heapify(A,i,len(A)-1)        
70        
71def heap_sort(A):
72    build_max_heap(A)
73    heapsize=len(A)-1    
74    for i in range(len(A)-1,0,-1):
75        temp=A[0]
76        A[0]=A[i]
77        A[i]=temp        
78        heapsize=heapsize-1
79        max_heapify(A,0,heapsize)
80        
81def quicksort(A,p,r):
82    
83    if p<r:
84        
85        q=partition(A,p,r)
86        quicksort(A,p,q-1)
87        quicksort(A,q+1,r)
88        
89def partition(A,p,r):
90    x=A[r]
91    i=p-1
92    
93    for j in range(p,r):
94        if A[j]<=x:
95            i=i+1
96            temp=A[i]
97            A[i]=A[j]
98            A[j]=temp
99            
100    temp=A[i+1]
101    A[i+1]=A[r]
102    A[r]=temp
103            
104    return i+1            
105
106A=[incetance]
107A.sort

[instance_generator.py]

Python
1import random
2
3for n in range(100,1001,100):
4    for i in range(100):
5        
6        A=[]
7        
8        for j in range(n):
9            A.append(str(random.uniform(0,10000)))
10        
11        fileobj=open("instances/n"+str(n)+"id"+str(i)+".txt","w")
12        
13        lines=" ".join(A)
14        fileobj.write(lines)
15        
16        fileobj.close()

[evaluation.py]

Python
1import my_sort
2import time
3
4average_computation_time_merge_sort=[]
5average_computation_time_heap_sort=[]
6average_computation_time_quicksort=[]
7average_computation_time_sort=[]
8
9for n in range(100,1001,100):
10    
11    computation_time_merge_sort=[]
12    
13    for id in range(100):
14        
15        fileobj=open("instances/n" +str(n)+"id" +str(id)+".txt","r") 
16               
17        A=fileobj.read().split()
18                
19        fileobj.close()
20        
21        A=[int(s) for s in A]        
22        B=[0]*len(A)
23                
24        start_time=time.perf_counter()
25        
26        my_sort.merge_sort(A,B,10000)
27        
28        end_time=time.perf_counter()
29        
30        computation_time_merge_sort.append(end_time-start_time)
31        
32    total_time=sum(computation_time_merge_sort)
33        
34    average_time=total_time/100
35    
36    text=str(n)+" " +str(average_time)
37        
38    average_computation_time_merge_sort.append(text)
39    
40fileobj=open("merge_sort.txt","w") 
41
42lines="\n".join(average_computation_time_merge_sort) 
43fileobj.write(lines)
44
45fileobj.close()    
46                
47for n in range(100,1001,100):
48    
49    computation_time_heap_sort=[]
50    
51    for id in range(100):
52        
53        fileobj=open("instances/n" +str(n)+"id" +str(id)+".txt","r") 
54               
55        A=fileobj.read().split()
56                
57        fileobj.close()
58        
59        A=[int(s) for s in A]
60        B=[0]*len(A)
61                        
62        start_time=time.perf_counter()
63        
64        my_sort.heap_sort(A,B,10000)
65        
66        end_time=time.perf_counter()
67        
68        computation_time_heap_sort.append(end_time-start_time)
69        
70    total_time=sum(computation_time_heap_sort)
71        
72    average_time=total_time/100
73    
74    text=str(n)+" " +str(average_time)
75        
76    average_computation_time_heap_sort.append(text)
77    
78fileobj=open("heap_sort.txt","w") 
79
80lines="\n".join(average_computation_time_heap_sort) 
81fileobj.write(lines)
82
83fileobj.close() 
84
85for n in range(100,1001,100):
86    
87    computation_time_quicksort=[]
88    
89    for id in range(100):
90        
91        fileobj=open("instances/n" +str(n)+"id" +str(id)+".txt","r") 
92               
93        text=fileobj.read()
94        
95        A=fileobj.read().split()
96        
97        fileobj.close()
98        
99        A=[int(s) for s in A]
100        B=[0]*len(A)
101        
102        start_time=time.perf_counter()
103        
104        my_sort.quicksort(A,B,10000)
105        
106        end_time=time.perf_counter()
107        
108        computation_time_quicksort.append(end_time-start_time)
109        
110    total_time=sum(computation_time_quicksort)
111        
112    average_time=total_time/100
113    
114    text=str(n)+" " +str(average_time)
115        
116    average_computation_time_quicksort.append(text)
117    
118fileobj=open("quicksort.txt","w") 
119
120lines="\n".join(average_computation_time_quicksort) 
121fileobj.write(lines)
122
123fileobj.close()
124
125for n in range(100,1001,100):
126    
127    computation_time_sort=[]
128    
129    for id in range(100):
130        
131        fileobj=open("instances/n" +str(n)+"id" +str(id)+".txt","r") 
132               
133        text=fileobj.read()
134        
135        A=fileobj.read().split()
136        
137        fileobj.close()
138        
139        A=[int(s) for s in A]
140        
141        start_time=time.perf_counter()
142        
143        A.sort(A,0,1000)
144        
145        end_time=time.perf_counter()
146        
147        computation_time_sort.append(end_time-start_time)
148        
149    total_time=sum(computation_time_sort)
150        
151    average_time=total_time/100
152    
153    text=str(n)+" " +str(average_time)
154        
155    average_computation_time_quicksort.append(text)
156    
157fileobj=open("quicksort.txt","w") 
158
159lines="\n".join(average_computation_time_sort) 
160fileobj.write(lines)
161
162fileobj.close()

実行したところ，Traceback (most recent call last):
evaluation.py", line 31, in <module>
my_sort.merge_sort(A,B,10000)
my_sort.py", line 40, in merge_sort
if p<r:
TypeError: '<' not supported between instances of 'list' and 'int'
というエラーが出ます．
エラーを消すにはコードをどのように修正したらよいでしょうか？
わからないので具体的に教えていただきたいです．
他にも間違っている箇所があれば教えてください．よろしくお願いします．

行動規範の内容に同意します

回答1件

ベストアンサー

TypeError: '<' not supported between instances of 'list' and 'int' は訳しますと、「'<' はリストとintの比較はできません」ということです。
my_sort.merge_sort(A,B,10000) の部分でエラーが出ていますが、B=[0]*len(A)はリスト、10000はintとなっています。比べる際は、同じ型同士にしてあげる必要があります。

投稿2020/06/28 15:01

kabayan55

総合スコア389

退会済みユーザー

2020/06/28 15:05

回答ありがとうございます．具体的にどのように修正したらよいでしょうか？わからないので教えてください．よろしくお願いします．

kabayan55

2020/06/28 15:22

def merge_sort の中で何をしようとしているか、簡単に教えていただけますか？ merge_sort の中で merge_sort を呼んだらエラーになりそうだなと思っていて、この部分でしようとしていることがわかりません。 merge_sort()でqを引数として受け取っていないので、この関数内のmerge(A,p,q,r)もエラーになってしまうと思います。 A, p, q, r の意味も教えてください。

退会済みユーザー

2020/06/28 15:50 編集

merge(A,p,q,r)では，２つの既ソート列のマージを行うことが目的です．Aは配列，p,q,rは配列の要素を指す添え字でp≤q<rを満たします．手続きは部分列A[p,..,q]と部分列A[q+1,..,r]が共にソート済みであると仮定します．この２つのソート済み部分列をマージして単一のソート積み部分列を形成し，現在の部分列A[p,..,r]と置き換えようとしています．

kabayan55

2020/06/29 08:53

ご説明ありがとうございます。質問はmerge（）ではなくmerge_sort()の方についてでした。（ですが、ありがとうございます！） merge（）内で置き換えしたAをreturnしてないように見受けられます。 merge_sort() の方でしたいことは整理がついてますでしょうか。 merge_sortのpには現在 B=[0]*len(A) を入力としていらっしゃるので、添字になっていません。pに入っていてほしい値を考えて入れてください。リストの要素は[0, 10000]の範囲の「実数」なのでこの範囲の値が入ると思います。

行動規範の内容に同意します