License New BSD license
Lines 34
Keywords
bogosort (5) testing (1)
Permissions
Owner: Theodore Test
Viewable by Everyone
Editable by All Siafoo Users
Hide
Free your code from a slow death on your hard drive Join Siafoo Now or Learn More

Bogosort Implementation Comparison Testing Atom Feed 0

In Brief Test a sequence of bogosort functions on a series of scrambled linear arrays of ascending maximum size. Repeat the tests a given number of times and return a 3-d array of timing information.... more
# 's
 1# Importing some sample bogosort implementations downloaded from around Siafoo  ###
2from vanilla_bogosort import bogo_sort as vanilla_bogosort
3from numpy_bogosort import bogosort as numpy_bogosort
4
5# Regular imports
6import numpy
7from time import time
8from random import shuffle
9from pprint import pprint
10from random import shuffle
11
12def test_bogos(sequence_of_bogosort_functions,number_of_tests,maximum_array_size):
13 ''' Times a sequences of bogosort functions for a series of increasingly large
14 arrays, randomly scrambled, repeated a set number of times.
15
16 Returns a 3d numpy array containing the time-to-run data for all functions
17 Rows are test iterations, columns are array-sizes, and depth corresponds to
18 function used.
19 '''
20
21 num_functions = len(sequence_of_bogosort_functions)
22 times_array = numpy.atleast_3d(numpy.zeros((number_of_tests,maximum_array_size,num_functions)))
23
24 for (t_num,s_num,f_num), x in numpy.ndenumerate(times_array):
25
26 fun = sequence_of_bogosort_functions[f_num]
27 a_list = range(s_num)
28 shuffle(a_list)
29
30 start_time = time()
31 sorted_array = fun(a_list)
32 end_time = time()
33
34 times_array[t_num,s_num,f_num] = end_time - start_time
35
36 return times_array
37
38if __name__ == '__main__':
39
40 fun_seq = [vanilla_bogosort,numpy_bogosort]
41 num_tests = 1000
42 max_size = 9
43 times_arr = test_bogos_02(fun_seq,num_tests,max_size)
44 print 'Average Times',times_arr.mean(axis=0)

Test a sequence of bogosort functions on a series of scrambled linear arrays of ascending maximum size. Repeat the tests a given number of times and return a 3-d array of timing information.

For the main example shown above, I got the following results. They generally demonstrate that the numpy code is faster than the generic python for larger arrays. Surprisingly, the difference was not terribly great. I'd wager that they become more distinct at larger array sizes.

http://charts.siafoo.net/chart?cht=lc&chs=500x200&chd=t:98.1,100.0,90.7,81.5,66.7,53.7,38.9,22.2,3.7|83.3,87.0,83.3,77.8,66.7,53.7,38.9,22.2,5.4&chtt=Bogosort%20Run%20Times&chdl=Normal%20Python|%20NumPy%20Python&chco=ee2000,002EB8&chf=bg,s,fffff8|c,s,ffffff&chxt=x,y,x&chxl=1:|-1%2Alog10%28Avg%20Run%20Time%29|2:|Array%20Size&chxr=0,0,8

Below, the first column is the vanilla python, and the second column is the numpy implementation. The rows correspond to array size, ranging from 0 to 8.

Average Times

[[ 5.05232811e-06 2.64606476e-05]

[ 3.69405746e-06 1.90448761e-05]

[ 1.17156506e-05 3.12585831e-05]

[ 4.38842773e-05 6.61971569e-05]

[ 2.15771198e-04 2.37778425e-04]

[ 1.27175498e-03 1.23753619e-03]

[ 8.11699867e-03 7.92551494e-03]

[ 6.16261077e-02 5.91173282e-02]

[ 5.82711076e-01 5.04583259e-01]]

Comments

over 8 years ago (05 Aug 2008 at 01:30 AM) by David Isaacson
Damn... I'm kind of disappointed there's not too much of a difference. I was hoping for something crazy ; ).... I wonder if the array operations in 'regular' Python have a C-backend anyways?
over 8 years ago (05 Aug 2008 at 05:22 AM) by Theodore Test
I'm guessing the low difference is due to two things. First, one dimensional arrays don't really provide an opportunity for numpy's improved multidimensional indexing and iteration backend to shine.
over 8 years ago (05 Aug 2008 at 05:22 AM) by Theodore Test
Second, the sort-check subalgorithm in my numpy implementation hasn't been properly vectorized. When I get around to that, it'll probably speed up a bit.
over 8 years ago (05 Aug 2008 at 05:45 AM) by Theodore Test
Scratch that second thought. I hadn't considered the major downside to vectorization in micro-algorithm optimization: excess comparison calculations.