Python: 每日一题 43

badaoqingchen

冬雪雪冬 发表于 2017-5-11 17:10
我不是很能理解其中的原因，一般教科书上说，集合是hash散列，查找的速度原快于列表元组，特别是数据量大 ...

哦哦，那估计可能和内存有关系了

ooxx7788

badaoqingchen 发表于 2017-5-11 17:06
水土都不服，就服你
明白了，这个是判断count( )的返回值。
我感觉for循环已经挺快的了啊， ...

~$ python -m timeit -n 1000 "[x for x in range(1000) if x in range(500, 1500)]"

1000 loops, best of 3: 28.2 msec per loop

~$ python -m timeit -n 1000 "set(range(1000)).intersection(range(500, 1500))"

1000 loops, best of 3: 120 usec per loop

List 大概用了Set的225倍的时间。List转Set基本用不了什么时间，所以如果有需要求（集合，列表等）的并集和交集的时候，最好使用Set。

提供一个人家测试的数据,就可以看出差距了.
我在一个爬虫教学视频里面,那个人也推荐使用集合.尤其是你不太需要用切片来取出值的情况下.

当回首遇上转身

冬雪雪冬 发表于 2017-5-11 16:37
没有更好的想法，用set是否快点。

set()在Python3里面是倒序
请问set()在Python2.7里面排序规律是什么？

ooxx7788

当回首遇上转身 发表于 2017-5-11 17:18
set()在Python3里面是倒序
请问set()在Python2.7里面排序规律是什么？

set()是倒序?有根据吗?

1. arr
   
2. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
   
3. sett = set(arr)
   
4. sett
   
5. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
   
6. for i in sett:
   
7.     print(i)
   
8.    
   
9. 1
   
10. 2
    
11. 3
    
12. 4
    
13. 5
    
14. 6
    
15. 7
    
16. 8
    
17. 9
    
18. 10
    

复制代码

好像取出的顺序也没有倒过来啊.

冬雪雪冬

当回首遇上转身 发表于 2017-5-11 17:18
set()在Python3里面是倒序
请问set()在Python2.7里面排序规律是什么？

理论上讲，set是无序的。

当回首遇上转身

ooxx7788 发表于 2017-5-11 17:21
set()是倒序?有根据吗?

My mistake, sorry.

冬雪雪冬

这回用时达标了。

1. def sum_pairs(list1, num):
   
2.     list2 = []
   
3.     for i in list1:
   
4.         if list2.count(i) < 2:
   
5.             list2.append(i)
   
6.     for i in range(1, len(list2)):
   
7.         if num - list2[i] in set(list2[:i]):
   
8.             return [num - list2[i], list2[i]]

复制代码

ooxx7788

冬雪雪冬 发表于 2017-5-11 18:00
这回用时达标了。

果然达标了。666

冬雪雪冬

ooxx7788 发表于 2017-5-11 18:01
果然达标了。666

还是标准答案厉害，我的程序有些投机取巧了，假定列表有大量重复数据，否则用时比优化前更多。

badaoqingchen

ooxx7788 发表于 2017-5-11 17:18
~$ python -m timeit -n 1000 "[x for x in range(1000) if x in range(500, 1500)]"

1000 loops, bes ...

学习了。
这种题好，不但可以练习基本知识，还要追求精益求精。很锻炼水平。

编程新血

类似的题目：有一个长度为1000w个数组，每个元素互不重复，找出其中top n元素。

我没得到允许，就不贴内容了，原微博：

http://blog.csdn.net/echoutopia/article/details/51731269

冬雪雪冬

编程新血 发表于 2017-5-11 21:50
类似的题目：有一个长度为1000w个数组，每个元素互不重复，找出其中top n元素。

我没得到允许，就不贴内 ...

没太理解这个题目，把列表从大到小排序，取前n个数，不就行了？

瓦蓝

学习学习

willLin

def find_num(list1, num):
    for i in range(len(list1)):
        for j in range(i+1, len(list1)):
            if list1[i] + list1[j] == num:
                print("{}+{}={},index:{}, {}".format(list1[i], list1[j], num, i, j))
    else:
        print("none")

ooxx7788

willLin 发表于 2017-5-18 09:27
def find_num(list1, num):
    for i in range(len(list1)):
        for j in range(i+1, len(list1)): ...

方法可行，效率不可行

solomonxian

楼主没有给出1000万长的列表，不好测结果啊，
只好自己随便编个列表了

开始就想到直接嵌套循环，暴力破解

1. def sum_pairs_1(a,n):
   
2.     out = [0,0,len(a)]
   
3.     for i in range(len(a)):
   
4.         for j in range(i+1,len(a)):
   
5.             if a[i]+a[j] == n and j<out[2]:
   
6.                 out = [a[i],a[j],j]
   
7.         if i >= out[2]:
   
8.             break
   
9.     print(out[:2])

复制代码

然后想到利用集合缩减规模，反正嵌套循环也会产生相同元素

1. def sum_pairs_2(a,n):
   
2.     s = set(a)
   
3.     length = len(a)
   
4.     out = [length,length]
   
5.     for i in s:
   
6.         for j in s:
   
7.             if i+j == n:
   
8.                 if i==j and a.count(i)==1:
   
9.                     continue
   
10.                
    
11.                 num1 = a.index(i)
    
12.                 num2 = a.index(j)
    
13.                 if i==j and a.count(i)>1:
    
14.                     num2 = a.index(j,num1+1)
    
15.                 if max(num1,num2) < max(out):
    
16.                     out = [num1,num2]
    
17.                     
    
18.     output = [a[out[0]],a[out[1]]] if sum(out)<(length*2) else None
    
19.     print(output)

复制代码

在函数2的基础上把不可能的元素排除，继续缩减规模

1. def sum_pairs_3(a,n):
   
2.     biggest = max(a)
   
3.     smallest = min(a)
   
4.     if smallest >=0:
   
5.         new_a = [i for i in a if i<=n]
   
6.     elif biggest <=0:
   
7.         new_a = [i for i in a if i>=n]
   
8.     else:
   
9.         new_a = [i for i in a if i+biggest >n and i+smallest <n ]
   
10.     return sum_pairs_2(new_a, n)

复制代码

自己编了一个最坏情况，一个随机情况，用time模块算时间

1. import time
   
2. import random
   
3. 
   
4. t1 = time.time()
   
5. # 自己搞个千万级列表，一个随机，一个让答案放在最后（函数1和2的最坏情况）
   
6. lst = [random.randint(-100,100) for i in range(10**7)]
   
7. lst2 = list(range(10**7,-1,-1))
   
8. 
   
9. t2 = time.time()
   
10. sum_pairs_1(lst,20)
    
11. t3 = time.time()
    
12. sum_pairs_2(lst,20)
    
13. t4 = time.time()
    
14. sum_pairs_3(lst,20)
    
15. t5 = time.time()
    
16. print("函数1耗时 %s 秒" %(t3-t2))
    
17. print("函数2耗时 %s 秒" %(t4-t3))
    
18. print("函数3耗时 %s 秒" %(t5-t4))
    
19. 
    
20. 
    
21. # 测试3回，答案一致
    
22. # 在随机千万级列表情况下，函数1耗时 44.7s\ 95.3s\ 81.9s
    
23. #                         函数2耗时 1.49s\ 1.45s\ 1.49s
    
24. #                         函数3耗时 6.0s \ 5.9s \ 6.0s
    
25. 
    
26. # 在最坏情况1万级列表情况下，函数1耗时 16.5s\ 17.67s\ 17.3s
    
27. #                            函数2耗时 15.2s\ 15.64s\ 1.49s
    
28. #                            函数3耗时 <0.01s\ <0.01s\ <0.01s
    
29. 
    
30. # 在对函数(1、2)最坏情况1千万级列表情况下，函数1、函数2均耗时>10min
    
31. #                                          函数3耗时 1.89s
    
32. 
    
33. 
    

复制代码

shigure_takimi

1. def sum_pairs(lst, n):
   
2.     lastIndex = len(lst)
   
3.     for i in range(lastIndex - 1):
   
4.         for j in range(i+1,len(lst)):
   
5.             if lst[i]+lst[j] == n and j <= lastIndex:
   
6.                 lastIndex = j
   
7.     if lastIndex != len(lst):
   
8.         return [n-lst[lastIndex], lst[lastIndex]]
   
9.     else:
   
10.         return None
    
11. 
    
12. # 按上面大神说的，10000000维度列表会超时，但不知道有什么好方法。

复制代码

kwty

1. list = [20,-13,40]
   
2. k = 7
   
3. if k > 0:
   
4.         for i in list:
   
5.                 if i <= k and (k-i) in list:
   
6.                         print(i,k-i)
   
7. 
   
8. else:
   
9.         for i in list:
   
10.                 if i >= k and (k-i) in list:
    
11.                         print(i,k-i)

复制代码

大头目

import itertools
import time

t1 = time.clock()
def sum_pairs(listx,sumx):
        if len(listx)>100:
                print('list out of range 100')
        else:
                for i,j in itertools.combinations(listx, 2):
                        if i + j == sumx:
                                print(i,'+',j,'=',sumx)
                                return 'End'
                               
                else:
                        print('没有可以相加成',sumx,'的组合')

sum_pairs([0, 0, -2, 3], 2)
sum_pairs([10, 5, 2, 3, 7, 5],         10)
sum_pairs([20, -13, 40], -7)

t2 = time.clock()
print(t2-t1)

小强工作室

import itertools
def list_add(x,y):
    for i in itertools.combinations(x,2):
        if sum(i)==y:
            print(i)

if __name__=="__main__":
    list1=[10, 5, 2, 3, 7, 5]
    list_add(list1,10)