Python: 每日一题 43,Python交流,编程语言专区,鱼C论坛

badaoqingchen 发表于 2017-5-11 17:15:50

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

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

ooxx7788 发表于 2017-5-11 17:18:11

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

~$ python -m timeit -n 1000 ""

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 17:18:19

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

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

ooxx7788 发表于 2017-5-11 17:21:05

本帖最后由 ooxx7788 于 2017-5-11 17:22 编辑

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

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

arr

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:22:07

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

理论上讲，set是无序的。

当回首遇上转身 发表于 2017-5-11 17:28:47

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

My mistake, sorry.

冬雪雪冬 发表于 2017-5-11 18:00:09

这回用时达标了。
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 in set(list2[:i]):
         return , list2]

ooxx7788 发表于 2017-5-11 18:01:52

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

果然达标了。666

冬雪雪冬 发表于 2017-5-11 18:12:25

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

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

badaoqingchen 发表于 2017-5-11 18:45:24

ooxx7788 发表于 2017-5-11 17:18
~$ python -m timeit -n 1000 ""

1000 loops, bes ...

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

编程新血 发表于 2017-5-11 21:50:11

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

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

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

冬雪雪冬 发表于 2017-5-12 15:46:40

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

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

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

瓦蓝发表于 2017-5-17 15:00:51

学习学习

willLin 发表于 2017-5-18 09:27:53

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

ooxx7788 发表于 2017-5-18 11:55:03

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 发表于 2017-7-1 21:23:43

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

开始就想到直接嵌套循环，暴力破解
def sum_pairs_1(a,n):
out =
for i in range(len(a)):
   for j in range(i+1,len(a)):
         if a+a == n and j<out:
            out = ,a,j]
   if i >= out:
         break
print(out[:2])
然后想到利用集合缩减规模，反正嵌套循环也会产生相同元素
def sum_pairs_2(a,n):
s = set(a)
length = len(a)
out =
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 =

output = ],a]] 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 =
elif biggest <=0:
   new_a =
else:
   new_a =
return sum_pairs_2(new_a, n)
自己编了一个最坏情况，一个随机情况，用time模块算时间
import time
import random

t1 = time.time()
# 自己搞个千万级列表，一个随机，一个让答案放在最后（函数1和2的最坏情况）
lst =
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 发表于 2017-12-5 15:54:52

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

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

kwty 发表于 2018-2-7 22:05:09

list =
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)

大头目 发表于 2018-7-12 10:28:14

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(, 2)
sum_pairs(, 10)
sum_pairs(, -7)

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

小强工作室 发表于 2018-7-22 08:55:07

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

if __name__=="__main__":
list1=
list_add(list1,10)

页: 1 [2] 3

鱼C论坛's Archiver