How to use timsort method in hypothesis

Best Python code snippet using hypothesis

performance_compare.py

Source:performance_compare.py

...31            finish_time = time.time() - start_time32            merge_lst.append(finish_time)3334            start_time = time.time()35            timsort(copy)36            finish_time = time.time() - start_time37            timsort_lst.append(finish_time)3839        avg_merge = sum(merge_lst)/len(merge_lst)40        avg_timsort = sum(timsort_lst)/len(timsort_lst)4142        merge_avg.append(avg_merge)43        timsort_avg.append(avg_timsort)4445    # Plot individual graphs for each curve46    plt.plot(merge_avg, color='red', label = 'Traditional merge')47    plt.plot(timsort_avg, color='blue', label = 'TimSort')48    plt.plot(theory_time, color='green', label = 'Theoretical run time O(nlog(n))')49    plt.xlabel("Length of the list")50    plt.ylabel("Averaged run-time")51    plt.legend()52    plt.show()535455# With worst case traditional merge sort - maximum comparisons:56def worstCases(n):57    """Generates the worst case scenario for merge sort58    with maxiimum comparisons possible for every size N"""5960    # Holds base cases of N = 1, N = 261    lst = [[], [1], [2,1]]6263    # Builds worst cases from the bottom up64    for i in range(3, n + 1):65        left = lst[i//2]66        right = lst[i - i//2]67        left = [x*2 for x in left]68        right = [y*2 - 1 for y in right]69        entry = left + right70        lst.append(entry)71    return lst727374def graph_runtimes_worst(length_lst, repeats):75    merge_avg = []76    timsort_avg = []77    theory_time = [0]78    worst_cases = worstCases(length_lst)7980    for i in range(1, length_lst):81        theory_time.append(i*math.log(i)/1000000)8283    for i in worst_cases:84        merge_lst = []85        timsort_lst = []8687        for x in range(repeats):88            mylist = i89            copy = mylist.copy()9091            start_time = time.time()92            mergesort(mylist, 0, len(mylist) - 1)93            finish_time = time.time() - start_time94            merge_lst.append(finish_time)9596            start_time = time.time()97            timsort(copy)98            finish_time = time.time() - start_time99            timsort_lst.append(finish_time)100101        avg_merge = sum(merge_lst)/len(merge_lst)102        avg_timsort = sum(timsort_lst)/len(timsort_lst)103104        merge_avg.append(avg_merge)105        timsort_avg.append(avg_timsort)106107    plt.plot(merge_avg, color='red', label = 'Traditional merge')108    plt.plot(timsort_avg, color='blue', label = 'TimSort')109    plt.plot(theory_time, color='green', label = 'Theoretical run time O(nlog(n))')110    plt.xlabel("Length of the list")111    plt.ylabel("Averaged run-time")112    plt.legend()113    plt.show()114115116# With sorted data - best case Timsort:117def graph_runtimes_best(length_lst, repeats):118    """Identical to graph_runtimes, but with ordered data"""119    merge_avg = []120    timsort_avg = []121    theory_time = [0]122123    for i in range(1, length_lst):124        theory_time.append(i*math.log(i)/1000000)125126    for i in range(length_lst):127        merge_lst = []128        timsort_lst = []129130        for x in range(repeats):131132            # Here is the only change133            mylist = [x for x in range(i)]134            copy = mylist.copy()135136            start_time = time.time()137            mergesort(mylist, 0, len(mylist) - 1)138            finish_time = time.time() - start_time139            merge_lst.append(finish_time)140141            start_time = time.time()142            timsort(copy)143            finish_time = time.time() - start_time144            timsort_lst.append(finish_time)145146        avg_merge = sum(merge_lst)/len(merge_lst)147        avg_timsort = sum(timsort_lst)/len(timsort_lst)148149        merge_avg.append(avg_merge)150        timsort_avg.append(avg_timsort)151152    plt.plot(merge_avg, color='red', label = 'Traditional merge')153    plt.plot(timsort_avg, color='blue', label = 'TimSort')154    plt.plot(theory_time, color='green', label = 'Theoretical run time O(nlog(n))')155    plt.xlabel("Length of the list")156    plt.ylabel("Averaged run-time")
...

hw4_ques2.py

Source:hw4_ques2.py

1import math2import sys3import time4import numpy as np5from matplotlib import pyplot as plt6# https://www.geeksforgeeks.org/insertion-sort/7def insertionSort(arr): 8	for i in range(1, len(arr)): 9		key = arr[i] 10		j = i-111		while j >= 0 and key < arr[j] : 12				arr[j + 1] = arr[j] 13				j -= 114		arr[j + 1] = key15# https://www.geeksforgeeks.org/merge-sort/16def mergeSort(arr):17	if len(arr) >1:18		mid = len(arr)//219		L = arr[:mid]20		R = arr[mid:]21		mergeSort(L)22		mergeSort(R)23		i = j = k = 0		 24		while i < len(L) and j < len(R):25			if L[i] < R[j]:26				arr[k] = L[i]27				i+= 128			else:29				arr[k] = R[j]30				j+= 131			k+= 132		while i < len(L):33			arr[k] = L[i]34			i+= 135			k+= 136		while j < len(R):37			arr[k] = R[j]38			j+= 139			k+= 140def TimSort(array, timsort_constant):41	if(len(array)<=1):42		return43	if(len(array) <= timsort_constant):44		insertionSort(array)45	else:46		mid = len(array)//247		L = array[:mid]48		R = array[mid:]49		TimSort(L, timsort_constant)50		TimSort(R, timsort_constant)51		i = j = k = 0		 52		while i < len(L) and j < len(R):53			if L[i] < R[j]:54				array[k] = L[i]55				i+= 156			else:57				array[k] = R[j]58				j+= 159			k+= 160		while i < len(L):61			array[k] = L[i]62			i+= 163			k+= 164		while j < len(R):65			array[k] = R[j]66			j+= 167			k+= 168time_timsort = np.zeros((11,51))69for n in range(0,51):70	time_timsort_n = []71	for t in range(1000):72		time_timsort_t = []73		array = np.random.randint(1000000, size=n)74		for k in range(0,51,5):75			start_time = time.perf_counter()76			TimSort(np.copy(array),k)77			stop_time = time.perf_counter()78			time_timsort_t.append(stop_time - start_time)79		time_timsort_n.append(time_timsort_t)80	time_timsort_n = np.array(time_timsort_n)81	time_timsort_n = np.mean(time_timsort_n, axis=0)82	time_timsort[:,n] = time_timsort_n83# time_timsort = np.array(time_timsort)84time_timsort = 1000. * time_timsort85for k in range(0,51,5):86	plt.plot(range(0, 51), time_timsort[(k//5)], label='k=' + str(k))87plt.xlabel('Length of Array (N)')88plt.ylabel('Average Run time (ms)')89plt.legend()90plt.show()91optimal_k = 1592time_insertion_sort = []93time_merge_sort = []94time_timsort = []95for n in range(2, 51):96	avg_insertion_sort_time = 0.0097	avg_merge_sort_time = 0.0098	avg_timsort_time = 0.0099	for t in range(1000):100		array = np.random.randint(1000000, size=n)101		start_time = time.perf_counter()102		insertionSort(np.copy(array))103		stop_time = time.perf_counter()104		avg_insertion_sort_time = avg_insertion_sort_time + (stop_time - start_time)105		start_time = time.perf_counter()106		mergeSort(np.copy(array))107		stop_time = time.perf_counter()108		avg_merge_sort_time = avg_merge_sort_time + (stop_time - start_time)109		start_time = time.perf_counter()110		TimSort(np.copy(array), optimal_k)111		stop_time = time.perf_counter()112		avg_timsort_time = avg_timsort_time + (stop_time - start_time)113	time_insertion_sort.append(avg_insertion_sort_time/1000.0)114	time_merge_sort.append(avg_merge_sort_time/1000.0)115	time_timsort.append(avg_timsort_time/1000.0)116time_insertion_sort = np.array(time_insertion_sort)117time_merge_sort = np.array(time_merge_sort)118time_timsort = np.array(time_timsort)119time_insertion_sort = 1000. * time_insertion_sort120time_merge_sort = 1000. * time_merge_sort121time_timsort = 1000. * time_timsort122plt.plot(range(2, 51), time_insertion_sort, label='Insertion Sort', color='#28324b')123plt.plot(range(2, 51), time_merge_sort, label='Merge Sort', color='#f55158')124plt.plot(range(2, 51), time_timsort, label='TimSort', color='#f3c417')125plt.xlabel('Length of Array (N)')126plt.ylabel('Average Run time (ms)')127plt.legend()...

test_timsort.py

Source:test_timsort.py

1import pytest2# import os, sys3# myPath = os.path.dirname(os.path.abspath(__file__))4# sys.path.insert(0, myPath + '/../')5from other_sorts import timsort as ts6def test_timsort_already_sorted():7    nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]8    ts.timSort(nums)9    assert nums == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]10def test_timsort_out_of_order():11    nums = [10, 9, 7, 4, 6, 2, 1, 5, 8, 3]12    ts.timSort(nums)13    assert [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] == nums14def test_timsort_size_more_than_run():15    nums = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,16            21,66,23,24,25,26,27,28,29,30,31,32,33]17    ts.timSort(nums)18    assert [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,19            21,23,24,25,26,27,28,29,30,31,32,33,66] == nums20def test_timsort_empty():21    nothing = []22    ts.timSort(nothing)23    assert [] == nothing24##Helpers##25def test_timsort_insertion_already_sorted():26    nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]27    ts.insertionSort(nums, 0, len(nums) - 1)28    assert nums == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]29def test_timsort_insertion_out_of_order():30    nums = [10, 9, 7, 4, 6, 2, 1, 5, 8, 3]31    ts.insertionSort(nums, 0, len(nums) - 1)32    assert [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] == nums33def test_timsort_insertion_empty():34    nothing = []35    ts.insertionSort(nothing, 0, len(nothing) - 1)36    assert [] == nothing37def test_timsort_merge_nonempty_more_left():38    nums = [2,6,7,1,5]39    ts.merge(nums, 0, 2, 4)40    assert nums == [1,2,5,6,7]41def test_timsort_merge_nonempty_more_right():42    nums = [2,6,7,1,5,8,9]43    ts.merge(nums, 0, 2, 5)44    assert nums == [1,2,5,6,7,8, 9]45def test_timsort_merge_empty():46    nums = []47    ts.merge(nums, 0, 0, 0)...

Automation Testing Tutorials

Learn to execute automation testing from scratch with LambdaTest Learning Hub. Right from setting up the prerequisites to run your first automation test, to following best practices and diving deeper into advanced test scenarios. LambdaTest Learning Hubs compile a list of step-by-step guides to help you be proficient with different test automation frameworks i.e. Selenium, Cypress, TestNG etc.