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)

Something about recursion

Here is something recursion to print every file path in the root dir, from here.


import os

def printpath(rootDir):

    for lists in os.listdir(rootDir):

    path = os.path.join(rootDir, lists)

    print(path)

    if os.path.isdir(path):

        Test2(path)

And here is some 'formula' for recursion, from Eric Lippert:

Result M(Problem prob) { 

     if (<problem can be solved easily>) 

     return <easy solution>; 

     // The problem cannot be solved easily. 

     Problem smaller1 = <reduce problem to smaller problem> 

     Result result1 = M(smaller1); 

     Problem smaller2 = <reduce problem to smaller problem> 

     Result result2 = M(smaller2); 

     ... 

     Result finalResult = <combine all results of smaller problem to solve large      problem> 

     return finalResult; }

Four stool TOAHModel

It seems that I got some luck for the best i in the four stool TOAHModel.After the programming, I read a little about the algorithm for the solution of the program, which is called Frame–Stewart algorithm.
This and this article is kind of helpful.

OOP between Python and Objective-C

The basic idea of OOP, object and method is same in Python and Objective-C. But there is some difference between them.

Similar to Java, Obj-c divided a class into public and private part strictly. Other functions can use only public method and property of the class, while in Python, everything in fact is public. 

In obj-c method and property are called in different syntax. [object message] is used for a method, and object.property is for a property. However, in python it seems that the only difference is that properties do not have the brackets behind it. 

But I assume that for my knowledge about the both language is far from enough, there are much more difference within them. By Why Objective-C is “weird” for the contemporary programmers, Python is more c++-like while obj-c learns more from small talk. 

Aloha World!

So this is my blog of programming. I may not go further into programming, which means I may not maintain this nice little web page, however, I can guarantee you at least three essays, for it is required by my course. Also, if you can find it, I also have a abandoned blog at blogger.com, written in Chinese, and it's funny to read those articles where I tried hard to make simple things sophisticated. I hope I will not do that again here.
And that's it.