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()是倒序?有根据吗?

arr
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
sett = set(arr)
sett
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
for i in sett:
    print(i)
    
1
2
3
4
5
6
7
8
9
10

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

冬雪雪冬

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

理论上讲，set是无序的。

当回首遇上转身

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

My mistake, sorry.

冬雪雪冬

这回用时达标了。

def sum_pairs(list1, num):
    list2 = []
    for i in list1:
        if list2.count(i) < 2:
            list2.append(i)
    for i in range(1, len(list2)):
        if num - list2[i] in set(list2[:i]):
            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万长的列表，不好测结果啊，
只好自己随便编个列表了

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

def sum_pairs_1(a,n):
    out = [0,0,len(a)]
    for i in range(len(a)):
        for j in range(i+1,len(a)):
            if a[i]+a[j] == n and j<out[2]:
                out = [a[i],a[j],j]
        if i >= out[2]:
            break
    print(out[:2])

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

def sum_pairs_2(a,n):
    s = set(a)
    length = len(a)
    out = [length,length]
    for i in s:
        for j in s:
            if i+j == n:
                if i==j and a.count(i)==1:
                    continue
                
                num1 = a.index(i)
                num2 = a.index(j)
                if i==j and a.count(i)>1:
                    num2 = a.index(j,num1+1)
                if max(num1,num2) < max(out):
                    out = [num1,num2]
                    
    output = [a[out[0]],a[out[1]]] if sum(out)<(length*2) else None
    print(output)

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

def sum_pairs_3(a,n):
    biggest = max(a)
    smallest = min(a)
    if smallest >=0:
        new_a = [i for i in a if i<=n]
    elif biggest <=0:
        new_a = [i for i in a if i>=n]
    else:
        new_a = [i for i in a if i+biggest >n and i+smallest <n ]
    return sum_pairs_2(new_a, n)

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

import time
import random

t1 = time.time()
# 自己搞个千万级列表，一个随机，一个让答案放在最后（函数1和2的最坏情况）
lst = [random.randint(-100,100) for i in range(10**7)]
lst2 = list(range(10**7,-1,-1))

t2 = time.time()
sum_pairs_1(lst,20)
t3 = time.time()
sum_pairs_2(lst,20)
t4 = time.time()
sum_pairs_3(lst,20)
t5 = time.time()
print("函数1耗时 %s 秒" %(t3-t2))
print("函数2耗时 %s 秒" %(t4-t3))
print("函数3耗时 %s 秒" %(t5-t4))


# 测试3回，答案一致
# 在随机千万级列表情况下，函数1耗时 44.7s\ 95.3s\ 81.9s
#                         函数2耗时 1.49s\ 1.45s\ 1.49s
#                         函数3耗时 6.0s \ 5.9s \ 6.0s

# 在最坏情况1万级列表情况下，函数1耗时 16.5s\ 17.67s\ 17.3s
#                            函数2耗时 15.2s\ 15.64s\ 1.49s
#                            函数3耗时 <0.01s\ <0.01s\ <0.01s

# 在对函数(1、2)最坏情况1千万级列表情况下，函数1、函数2均耗时>10min
#                                          函数3耗时 1.89s

shigure_takimi

def sum_pairs(lst, n):
    lastIndex = len(lst)
    for i in range(lastIndex - 1):
        for j in range(i+1,len(lst)):
            if lst[i]+lst[j] == n and j <= lastIndex:
                lastIndex = j
    if lastIndex != len(lst):
        return [n-lst[lastIndex], lst[lastIndex]]
    else:
        return None

# 按上面大神说的，10000000维度列表会超时，但不知道有什么好方法。

kwty

list = [20,-13,40]
k = 7
if k > 0:
        for i in list:
                if i <= k and (k-i) in list:
                        print(i,k-i)

else:
        for i in list:
                if i >= k and (k-i) in list:
                        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)