#!/usr/bin/python import os import time import random import radixsort def append(filename, size, duration): file = open(filename, 'a') file.write('%d %f\n' % (size, duration)) file.close() def shuffle(lst): len_lst = len(lst) for index in xrange(len_lst): # percentage = index * 100.0 / len_lst # if index and percentage % 10 == 0: # print percentage random_index = int(random.random() * len_lst) lst[index], lst[random_index] = lst[random_index], lst[index] def is_sorted(lst): if not lst: return True else: for left, right in zip(lst, lst[1:]): if left > right: return False return True if 0 == 1: #ints = [ 1, 5, 8, 3, 10, 101, 9999, 23, 2000 ] print 'getting consecutive integers' ints = range(10000000) print 'shuffling integers' shuffle(ints) print 'starting int sort', time.ctime(time.time()) # two digits at a time int_c = int_comparator(100) dummy = int_c.radix_sort(ints) print 'done with int sort', time.ctime(time.time()) ints.sort() print 'done with native int sort', time.ctime(time.time()) elif 0 == 2: import random def random_char(): return chr(int(random.random()*26) + ord('a')) def random_string(letters): lst = [] for s_no in xrange(letters): lst.append(random_char()) return ''.join(lst) #strings = [ 'abd', 'abc', 'defg', 'hijkl', 'bongo', 'string value', 'gorilla' ] if 1 == 1: strings = [] for s_no in xrange(1000000): strings.append(random_string(int(random.random() * 20) + 1)) strings_copy = copy.copy(strings) elif 0 == 1: strings = [ 'auoalzkrd', 'aounci' ] #shuffle(strings) print 'radix sorting' str_c = str_comparator(1) result = str_c.radix_sort(strings) print 'done radix sorting' if is_sorted(result): print 'sorted correctly' else: print 'sorted _in_correctly' print 'tim sorting' strings_copy.sort() print 'done tim sorting' if 3 == 3: for x in xrange(9): size = 10**x #ints = [ 1, 5, 8, 3, 10, 101, 9999, 23, 2000 ] print 'starting getting %d (10**%d) consecutive integers, %s' % (size, x, time.ctime(time.time())) ints = range(size) print 'done getting %d consecutive integers, %s' % (size, time.ctime(time.time())) print 'starting shuffling %d consecutive integers, %s' % (size, time.ctime(time.time())) shuffle(ints) print 'done shuffling %d consecutive integers, %s' % (size, time.ctime(time.time())) ints_copy = ints[:] print 'starting int radix_sort', time.ctime(time.time()) t0 = time.time() # two digits at a time dummy = radixsort.radix_sort(ints) t1 = time.time() print 'done with int sort', time.ctime(time.time()) diff_radix_sort = t1 - t0 append('radix_sort.dat', size, diff_radix_sort) print 'radix sort time was', diff_radix_sort print 'starting tim sort', time.ctime(time.time()) t0 = time.time() ints_copy.sort() t1 = time.time() print 'done with tim sort', time.ctime(time.time()) diff_tim_sort = t1 - t0 print 'tim sort time was', diff_tim_sort append('tim_sort.dat', size, diff_tim_sort) print 'radix sort time was %3.2f%% of the tim sort time' % (float(diff_radix_sort - diff_tim_sort) * 100.0 / diff_tim_sort) print