for2gene.py

#coding:utf8
#找出一个随机数列中所有两个数和为100的因子。

import random

def get_random_list(list_len):
    list_range = list_len * 4
    return random.sample(xrange(-list_range, list_range), list_len)

def get_gene0(randome_list, sum_of_gene):
    above_list = []
    below_list = []
    gene_list = []
    for i in randome_list:
        offset_num = i * 2 - sum_of_gene
        if offset_num > 0:
            above_list.append(offset_num)
        else:
            below_list.append(-offset_num)

    intersection_list = set(above_list) & set(below_list)
    for i in intersection_list:
         gene_list.append(((-i+sum_of_gene)/2, (i+sum_of_gene)/2))
        
    print "method get_gene0_0"
    print "sum of the gene pare is:%s"%len(gene_list)
    #print gene_list
    return
  
def get_gene1(random_list, sum_of_gene):
    middle_number = sum_of_gene / 2
    b_index = 0
    above_list = []
    below_list = []
    gene_list = []
    for i in random_list:
        if i > middle_number: 
            above_list.append(i)
        else:
            below_list.append(i)

    above_list.sort()
    below_list.sort()
    below_list.reverse()
    below_list_len = len(below_list)
    for a_num in above_list:
        while True: 
            sum = a_num + below_list[b_index]

            if sum > sum_of_gene:
                if b_index + 1 > below_list_len - 1 or a_num + below_list[b_index+1] < sum_of_gene:
                    break
                b_index += 1

            if sum == sum_of_gene : 
                gene_list.append((below_list[b_index], a_num))
                break

            if sum < sum_of_gene:
                if b_index - 1 < 0 or a_num + below_list[b_index-1] > sum_of_gene:
                    break
                b_index -= 1

    print "method get_gene1"
    print "sum of the gene pare is:%s"%len(gene_list)
    #print  gene_list
    return 

def get_gene2(random_list, sum_of_gene):
    middle_number = sum_of_gene / 2
    above_list = []
    below_list = []
    gene_list = []
    for i in random_list:
        if i > middle_number: 
            above_list.append(i)
        else:
            below_list.append(i)

    above_list.sort()
    below_list.sort()
    below_list.reverse()
    # for test 
    for a_num in above_list:
        for b_num in below_list:
            if sum_of_gene == a_num + b_num:
                gene_list.append((b_num, a_num))

    print "sum of the gene pare is:%s"%len(gene_list)
    #print  gene_list
    return

if __name__ == '__main__':
    #list_len = input("Input length of the random list:")
    #sum_of_gene = input("Input the sum of 2 gene:")
    list_len = 100000 
    sum_of_gene = 99 
    random_list = get_random_list(list_len)
    #import timeit
    #import_stmt = "from __main__ import get_gene1, sum_of_gene, random_list"
    #t = timeit.Timer("get_gene1(random_list, sum_of_gene)", import_stmt) 
    #print t.timeit(100)


    import profile
    profile.run("get_gene0(random_list, sum_of_gene);")
    profile.run("get_gene1(random_list, sum_of_gene);")
    #profile.run("print get_gene2(random_list, sum_of_gene);")