Skip to content

Instantly share code, notes, and snippets.

@silegon
Created August 7, 2012 08:15
Show Gist options
  • Save silegon/3283062 to your computer and use it in GitHub Desktop.
Save silegon/3283062 to your computer and use it in GitHub Desktop.
找出一个随机数列中所有两个数和为100的因子,3种方法。
#coding:utf8
#找出一个随机数列中所有两个数和为100的因子。
from __future__ import division
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):
middle_number = sum_of_gene / 2
above_list = []
below_list = []
gene_list = []
for i in randome_list:
offset_num = i - middle_number
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+middle_number, i+middle_number))
#return 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
#return 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))
#return 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 = 100
random_list = get_random_list(list_len)
#print get_gene0(random_list, sum_of_gene)
#print get_gene1(random_list, sum_of_gene)
#print get_gene2(random_list, sum_of_gene)
#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("print get_gene0(random_list, sum_of_gene);")
profile.run("print get_gene1(random_list, sum_of_gene);")
profile.run("print get_gene2(random_list, sum_of_gene);")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment