main.py 4.9 KB
 Hrishee Shastri committed Feb 23, 2021 1 2 3 4 5 ``````import csv from itertools import permutations from math import factorial import random `````` Eddie Schoute committed Feb 25, 2021 6 7 ``````from reversal_sort import SBR, adaptive_tbs, tripartite_binary_sort `````` Hrishee Shastri committed Feb 23, 2021 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 ``````""" Collects routing time data for the algorithms GDC(TBS), GDC(ATBS), and OES. Spits out the data into csv files in the "/data/" directory. """ def perm_to_str(perm): """ Converts a given list or tuple permutation to a string in the proper format (comma and space separated line without brackets) """ if type(perm) is list: return str(perm).strip('[]') if type(perm) is tuple: return str(perm).strip('()') raise Exception('perm must be a list or a tuple') def str_to_perm(string): """ Converts a string representation of a permutation into a list of ints """ return [int(x) for x in string.split(',')] def new_algs(algs, algnames, nlist): """ Adds a new column to the data files for the values of n given in nlist. The column corresponds to the given algorithm alg. Creates a new file called new_filename with which is a copy of the old data file with the new column added on. """ for n in nlist: with open('data/len_{:.0f}_perms.csv'.format(n), 'r') as readfile, \ open('data/new_len_{:.0f}_perms.csv'.format(n), 'w', newline='') as writefile: reader = csv.reader(readfile) writer = csv.writer(writefile) firstrow = True for row in reader: if firstrow: assert (all(algname not in row for algname in algnames)) firstrow = False row += algnames else: perm = str_to_perm(row[0]) for alg in algs: newcost = alg(perm.copy()) row.append(newcost) writer.writerow(row) print(n, 'complete...') def new_data_file(alglist, algnames, nlist): """ Creates a new data file for the n values given in nlist with columns corresponding to the algorithms given in alglist """ assert (len(alglist) == len(algnames)) for n in nlist: with open('data/len_{:.0f}_perms.csv'.format(n), 'w', newline='') as writefile: writer = csv.writer(writefile) firstrow = ['Permutation'] + algnames writer.writerow(firstrow) ct = 1 ident = [x + 1 for x in range(n)] for perm in permutations(ident): row = [perm_to_str(perm)] for alg in alglist: row.append(alg(list(perm))) writer.writerow(row) ct += 1 if ct % (factorial(n) / n) == 0: print('{:.0f}% complete'.format(ct / factorial(n) * 100)) def new_rand_perms_file(alglist, algnames, nlist, count): """ alglist = list of algorithms as functions that take a single argument L, the list to be sorted algnames = list of algorithm names, as strings nlist = list of permutation lengths count = number of random perms of each length to run algorithms over Runs each algorithm in alglist on the same random perms and spits the data for each permutation length X into a csv file called "data/len_X_random_perms.csv" Note: folder "data/" needs to exist in the top level directory from where this script is running """ assert (len(alglist) == len(algnames)) for n in nlist: with open('data/len_{:.0f}_random_perms.csv'.format(n), 'w', newline='') as writefile: writer = csv.writer(writefile) firstrow = ['Permutation'] + algnames writer.writerow(firstrow) data = [] for i in range(count): perm = [x + 1 for x in range(n)] random.shuffle(perm) row = [perm_to_str(perm)] for alg in alglist: row.append(alg(perm.copy())) data.append(row) # writer.writerow(row) if i % (count // 10) == 0: print('\t{:.0f}% complete'.format(i / count * 100)) writer.writerows(data) print(n, 'complete') def main(NUM_PERMS_PER_LENGTH, LENGTH_FROM, LENGTH_TO): algnames = ['OES', 'GDC(TBS)', 'GDC(ATBS)'] `````` Eddie Schoute committed Feb 25, 2021 120 `````` algs = [SBR.odd_even_sort, tripartite_binary_sort.GDC_TBS, adaptive_tbs.GDC_ATBS] `````` Hrishee Shastri committed Feb 23, 2021 121 `````` new_rand_perms_file(algs, algnames, list(range(LENGTH_FROM,LENGTH_TO + 1)), NUM_PERMS_PER_LENGTH) `````` Eddie Schoute committed Feb 24, 2021 122 123 124 125 126 127 128 `````` # Now you can run `echo "0 1 3 2" | python main.py` if __name__ == "__main__": import sys for line in sys.stdin: perm = [int(el) for el in line.split()] `````` Eddie Schoute committed Feb 25, 2021 129 130 131 132 `````` # Check if is permutation if set(range(0, len(perm))) != set(perm): raise ValueError(f"Given permutation does not contain all elements in [0,{len(perm)-1}].") reversals = tripartite_binary_sort.routing_divideconquer_tbs(perm) `````` Eddie Schoute committed Feb 24, 2021 133 `` print(reversals) # TODO: Implement pretty print``