Sort and efficiency

I think the most interesting for me is to find out how fast the python built-in sort is.I know that it may be unfair to compare it, which is written in c, with other sorts that written in python, but it actually runs ten time faster than the other sorts tested in this week's sort. So I did some wiki and find out that the built-in sort is actually Tim sort, which is used not only in python but also Java and Android platform.

Here is a good explain about Tim sort, and I found this 'sound of sorts' quite amazing:

Although in the worst case, the time would be O(nlogn), just like the other sorts, but because this sort can take advantage of the sorted part of the original list, in real world near-sorted cases it can be much better.

But compare to Quicksort, it occupies more memory space(O(logn) to O(n))and may be slower on average. What's more, Quicksort is really simple to write and understand, while Timsort, which is a hybrid sorting algorithm, is not that easy and clear.

An auto tester for Assignment 2

I write this auto tester to test the correctness for my assignment 2 part 2. It uses multi-process and python re class to test all the regexes for all the possible cases.

import regex_functions
# import pep8
# pep8.Checker('regex_functions.py').check_all()
import time
import re
from multiprocessing import Pool, Queue, Value
from concurrent.futures import ThreadPoolExecutor, ProcessPoolExecutor
def generate_case(n):
    raw = set()
    for i in range(n):
        for j in range(n - i):
            s = '1' * i + '2' * j + '0' * (n - i - j)
            raw.add(s)
    result = set()
    for i in raw:
        arranged = regex_functions.perm(i)
        result.update(arranged)
    return result
def regex_change(s):
    result = ''
    for i in s:
        if i == 'e':
            j = '()'
        elif i == '.':
            j = ''
        else:
            j = i
        if result and result[-1] == '*' and j == '*':
            result = '(' +result + ')' + j
        else:
            result = result + j
#     print (result)
    return result if result else '.*'
def process(s, case):
    string = case
    try:
        tree = regex_functions.build_regex_tree(s)
    except Exception:
        tree = -1
    if not tree == -1:
#         regex_value.put(s)
#         print(s)
        if regex_functions.regex_match(regex_functions.build_regex_tree(s), string):
            s_re = regex_change(s)
            try:
                match = re.match(s_re, string)
            except Exception:
                print(s, '   ', s_re)
                match = True
            if not match:
                file = open('output.txt', 'a')
                file.write(s + ' ' + string +'\n')
                file.close()
                return 1
    return 0

def build_queue2(a, case):
    lst = ['*', '1', '2', '0', 'e', '|', '.', '(', ')', '']
    count = 0
    for i1 in lst[a: a+1]:
        for i2 in lst:
            for i3 in lst:
                for i4 in lst:
                    for i5 in lst:
                        for i6 in lst:
#                            for i7 in lst:
#                                for i8 in lst:
#                                    for i9 in lst:
#                                        for i10 in lst:
#                                            for i11 in lst:
                                                        s = i1 + i2 + i3 + i4 + i5 + i6 #+ i7 + i8 + i9 + i10 + i11
#                                         executor.submit(process, s)
                                                        count += process(s, case)
    return count
def testb(a):
    print(0)
    return 0

def f(x):
    return x*x
if __name__ == '__main__':
    test = True
    CASE_LENTH = 4
    with Pool(processes=8) as pool:
        log = open('output.txt', 'w')
        log.write(str(time.localtime())+ '\n')
        log.close()
        case_set = generate_case(CASE_LENTH)
        if test:
            all_start = time.time()
            total_erroes = 0
            for case in case_set:
                print('Testing case ', case)
                start = time.time()         # start 4 worker processes
                regex_value = Value('i', 0)
                count = Value('i', 0)
                argument_list = []
                for i in range(10):
                    argument_list.append((i, case))
                errors = sum(pool.starmap(build_queue2, argument_list))
                total_errors = total_erroes + errors
                print('number of errors:', '\t', errors, 'Total errors: \t', total_errors)
                end = time.time()
                print('time of processing:')
                print(end - start)
            all_end = time.time()
            print(all_end - all_start)