what this python code trying to do

Question

Hi,

The following python code is to traverse a 2D grid of (c, g) in some special order, which is stored in "jobs" and "job_queue". But I am not sure which kind of order it is after trying to understand the code. Is someone able to tell about the order and give some explanation for the purpose of each function? Thanks and regards!

import Queue

c_begin, c_end, c_step = -5,  15, 2  
g_begin, g_end, g_step =  3, -15, -2  

def range_f(begin,end,step):  
    # like range, but works on non-integer too  
    seq = []  
    while True:  
        if step > 0 and begin > end: break  
        if step < 0 and begin < end: break  
        seq.append(begin)  
        begin = begin + step  
    return seq  

def permute_sequence(seq):  
    n = len(seq)  
    if n <= 1: return seq  

    mid = int(n/2)  
    left = permute_sequence(seq[:mid])  
    right = permute_sequence(seq[mid+1:])  

    ret = [seq[mid]]  
    while left or right:  
        if left: ret.append(left.pop(0))  
        if right: ret.append(right.pop(0))  

    return ret  

def calculate_jobs():  
    c_seq = permute_sequence(range_f(c_begin,c_end,c_step))  
    g_seq = permute_sequence(range_f(g_begin,g_end,g_step))  
    nr_c = float(len(c_seq))  
    nr_g = float(len(g_seq))  
    i = 0  
    j = 0  
    jobs = []  

    while i < nr_c or j < nr_g:  
        if i/nr_c < j/nr_g:  
            # increase C resolution  
            line = []  
            for k in range(0,j):  
                line.append((c_seq[i],g_seq[k]))  
            i = i + 1  
            jobs.append(line)  
        else:  
            # increase g resolution  
            line = []  
            for k in range(0,i):  
                line.append((c_seq[k],g_seq[j]))  
            j = j + 1  
            jobs.append(line)  
    return jobs  

def main():  

    jobs = calculate_jobs()  
    job_queue = Queue.Queue(0)  

    for line in jobs:  
        for (c,g) in line:  
            job_queue.put((c,g))  

main()

---

EDIT:

There is a value for each (c,g). The code actually is to search in the 2D grid of (c,g) to find a grid point where the value is the smallest. I guess the code is using some kind of heuristic search algorithm? The original code is here http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/gridsvr/gridregression.py, which is a script to search for svm algorithm the best values for two parameters c and g with minimum validation error.

Answer 1

Here is an example of permute_sequence in action:

print permute_sequence(range(8))
# prints [4, 2, 6, 1, 5, 3, 7, 0]
print permute_sequence(range(12))
# prints [6, 3, 9, 1, 8, 5, 11, 0, 7, 4, 10, 2]

I'm not sure why it uses this order, because in main, it appears that all candidate pairs of (c,g) are still evaluated, I think.

Answer 2

permute_sequence reorders a list of values so that the middle value is first, then the midpoint of each half, then the midpoints of the four remaining quarters, and so on. So permute_sequence(range(1000)) starts out like this:

    [500, 250, 750, 125, 625, 375, ...]

calculate_jobs alternately fills in rows and columns using the sequences of 1D coordinates provided by permute_sequence.

If you're going to search the entire 2D space eventually anyway, this does not help you finish sooner. You might as well just scan all the points in order. But I think the idea was to find a decent approximation of the minimum as early as possible in the search. I suspect you could do about as well by shuffling the list randomly.

xkcd readers will note that the urinal protocol would give only slightly different (and probably better) results:

    [0, 1000, 500, 250, 750, 125, 625, 375, ...]