A programming beginner tried to find out the execution time of sorting etc.
Overview
Read Math Girl Randomized Algorithm Last time (http://qiita.com/RyuSA/items/0be781f38fa7fc38f69d) Timed some sorts → I want a more solid distribution → Do you want to measure it?
Execution environment
DELL venue 11pro 5300 OS : Windows10 CPU : Atom Z3770 1.46GHz Memory : 2GB Language : Python 2.7
Search algorithm
Measurement method
Repeat the following procedure 10000 times and compare the times.
- Randomly generate 100,000 numbers from 1 to 100000 with numpy.random.randint (1,100000,100000)
- Generate one search target with random.randint (1,100000)
- Run each search algorithm (start measurement from here)
- When True / False returns, the measurement ends and the measured time is saved in a file.
- Return to 1.
Linear search
The simplest search algorithm. Just check in order from the front. The source code is below
import numpy as np
def LINER_SERCH(A,n,v):
k = 1
while k < n:
if A[k] == v:
return True
k += 1
return False
Measurement result
Below is the frequency distribution of the measurement results
There are many around 0.09sec to 0.10sec. It seems that False is returned here.
Linear search with sentinel
Just add the search target to the end of the given sequence. It's faster than just a linear search because it reduces the number of decisions in the While Loop. The source code is below
import numpy as np
def SENTINEL_LINER_SERCH(A,n,v):
A = np.append(A,v)
k = 0
while A[k] != v:
k += 1
if k < n:
return True
return False
Measurement result
Below is the frequency distribution of the measurement results
There are many around 0.08sec to 0.085sec. It seems that False is returned here.
In the previous linear search and linear search with sentinel, you can see that the latter is a little faster.
Binary search method
How to compare the element in the middle of a given sequence (sorted) with the search target and reduce the search range according to the size. Only in this case, the operation of sorting the given sequence A is performed in advance. The source code is below
import numpy as np
import math
def BINARY_SEARCH(A,n,v):
a = 0
b = n-1
A.sorted()
while a <= b :
k = int(math.floor(b + (a-b)/2))
if A[k] == v:
return True
elif A[k] < v:
a = k+1
else:
b = k-1
return False
Measurement result
Below is the frequency distribution of the measurement results
There are many around 0.015sec to 0.017sec. Compared to the previous two searches, you can see that the algorithm is overwhelmingly faster even though it includes sorting first.
Sort algorithm
Measurement method
Repeat the following procedure 10000 times and compare the times.
- Randomly generate 1000 numbers from 1 to 1000 with numpy.random.randint (1,1000,1000)
- Run each sort algorithm (measurement starts from here)
- When the sequence is returned, the measurement is completed and the measured time is saved in a file.
- Return to 1.
Bubble sort
A method of repeating comparison and exchange with the neighbor in order from the first one of the given sequence. The source code is below
import numpy as np
def BUBBLE_SORT(A):
n = np.size(A)
m = n-1
while m > 1:
k = 0
while k < m :
if A[k] > A[k+1]:
A[k],A[k+1] = A[k+1],A[k]
k += 1
m -= 1
return A
Measurement result
Below is the frequency distribution of the measurement results
0.7sec is the mode. Very slow ...
Quick sort
The first sequence of a given sequence is taken as the pivot, and it is divided into two sequences that are larger / smaller than the pivot. All you have to do is repeat the same operation. However, if you pass a sorted sequence or a similar sequence, it will be very slow. The source code is below
import numpy as np
def QUICK_SORT(A,L,R):
if L < R:
p = L
k = L+1
while k <= R:
if A[k] < A[L]:
A[p+1], A[k] = A[k], A[p+1]
p += 1
k += 1
A[L], A[p] = A[p], A[L]
A = QUICK_SORT(A,L,p-1)
A = QUICK_SORT(A,p+1,R)
return A
Measurement result
Below is the frequency distribution of the measurement results
0.17sec is the mode. Compared to bubble sort, the speed was about 75% faster.
Especially this time, since the sequence to be passed is generated by pseudo-random numbers, I wondered if the execution time was relatively stable thanks to the moderate randomness in the sequence. .. ..
Randomized quicksort
Randomly get the pivoting method instead of fixing it to the left side of the sequence. This way you can (should) perform quicksort without depending on the randomness of the sequence (probability distribution of each element). The source code is below
import numpy as np
def RANDOMIZED_QUICK_SORT(A,L,R):
if L < R:
r = np.random.randint(L,R)
A[L], A[r] = A[r], A[L]
p = L
k = L+1
while k <= R:
if A[k] < A[L]:
A[p+1], A[k] = A[k], A[p+1]
p += 1
k += 1
A[L], A[p] = A[p], A[L]
A = RANDOMIZED_QUICK_SORT(A,L,p-1)
A = RANDOMIZED_QUICK_SORT(A,p+1,R)
return A
Measurement result
Below is the frequency distribution of the measurement results
…… (ﾟ Д ﾟ) Poker
Well, for some reason it became very slow when I made it random. .. .. And so I put np.random.randint (L, R) into the original Quick Sort in vain and remeasured it.
This is also late! (ﾟ Д ﾟ)
Apparently, np.random.randint is a very heavy process compared to other processes. .. ..
It seems that it can be used as a quicksort that does not depend on a given sequence while maintaining the same execution speed (except for random number generation) even if it is randomized.
in conclusion
When the execution time of the search / sort algorithm was actually measured and aggregated, the results were almost as theoretical. On the other hand, if you make random numbers, it will take time to generate random numbers, and you can also know interesting facts such as the original algorithm is faster (laugh)
References
Mathematics Girl Random Algorithm Author: Hiroshi Yuki Programming beginners compared sort times
Recommended Posts