加快这段代码？ [英] Speed up this code?

问题描述

我正在创建一个程序来计算0到
到n范围内的所有质数数字，其中n是用户想要的数字。我已经计算出了

算法，它运行得非常好并且速度非常快，但是有一件事

严重减慢了程序的速度，代码如下：


def rmlist（原创，删除）：

返回[i for i in original如果我没有删除]


原始将是一个奇数列表，删除将是不是素数的数字

，因此此代码将返回原始

中未删除的所有项目。对于n> 10万左右，该程序需要很长时间才能运行，而对于高达10,000的数字则可以。


有没有人知道更快的方法吗？ （查找列表中的所有

项目不在列表中b）？


谢谢，

Martin

I''m creating a program to calculate all primes numbers in a range of 0
to n, where n is whatever the user wants it to be. I''ve worked out the
algorithm and it works perfectly and is pretty fast, but the one thing
seriously slowing down the program is the following code:

def rmlist(original, deletions):
return [i for i in original if i not in deletions]

original will be a list of odd numbers and deletions will be numbers
that are not prime, thus this code will return all items in original
that are not in deletions. For n > 100,000 or so, the program takes a
very long time to run, whereas it''s fine for numbers up to 10,000.

Does anybody know a faster way to do this? (finding the difference all
items in list a that are not in list b)?

Thanks,
Martin

推荐答案

ao ****** @ gmail.com 写道：

我正在创建一个程序来计算0到n的所有素数，其中n是用户想要的成为。我已经制定了
算法并且它工作得非常好并且速度非常快，但是一件事会严重减慢程序的速度是以下代码：

def rmlist（原创，删除）：
返回[我原来如果我没有删除]

原始将是一个奇数列表和删除将是数字
不是prime，因此此代码将返回原始
中未删除的所有项目。对于n>大约10万左右，程序需要很长时间才能运行，而对于高达10,000的数字则可以。

有人知道更快的方法吗？ （查找列表中所有不在列表中的项目的差异b）？

I''m creating a program to calculate all primes numbers in a range of 0
to n, where n is whatever the user wants it to be. I''ve worked out the
algorithm and it works perfectly and is pretty fast, but the one thing
seriously slowing down the program is the following code:

def rmlist(original, deletions):
return [i for i in original if i not in deletions]

original will be a list of odd numbers and deletions will be numbers
that are not prime, thus this code will return all items in original
that are not in deletions. For n > 100,000 or so, the program takes a
very long time to run, whereas it''s fine for numbers up to 10,000.

Does anybody know a faster way to do this? (finding the difference all
items in list a that are not in list b)?

in运算符对于列表是昂贵的，因为Python必须检查，平均是
，列表中的一半项目。使用更好的数据结构...

在这种情况下，一个集合可以很好地完成。请参阅文档：

http：// docs.python.org/lib/types-set.html
http://docs.python.org/tut/node7.htm...00000000000000


哦，你没有要求它，但我相信你会从其他clpy''ers获得十几个
宠物实施的主要发电机。所以

这里是我的。 :-)


def primes（）：

"""使用Eratosthenes筛子生成素数。""

收益率2

marks = {}

cur = 3

而True：

skip = marks.pop（cur，None）

如果跳过是无：

＃未标记的数字必须是素数

yield cur

＃mark ahead

标记[cur * cur] = 2 * cur

else：

n = cur + skip

而n在标记中：

＃x已被标记为另一个素数的倍数

n + = skip

＃first此素数的无标记

标记[n] =跳过

cur + = 2


--Ben

The "in" operator is expensive for lists because Python has to check,
on average, half the items in the list. Use a better data structure...
in this case, a set will do nicely. See the docs:

http://docs.python.org/lib/types-set.html
http://docs.python.org/tut/node7.htm...00000000000000

Oh, and you didn''t ask for it, but I''m sure you''re going to get a dozen
pet implementations of prime generators from other c.l.py''ers. So
here''s mine. :-)

def primes():
"""Generate prime numbers using the sieve of Eratosthenes."""
yield 2
marks = {}
cur = 3
while True:
skip = marks.pop(cur, None)
if skip is None:
# unmarked number must be prime
yield cur
# mark ahead
marks[cur*cur] = 2*cur
else:
n = cur + skip
while n in marks:
# x already marked as multiple of another prime
n += skip
# first unmarked multiple of this prime
marks[n] = skip
cur += 2

--Ben

> def rmlist（original，deletions）：

> def rmlist(original, deletions):

return [i for i in original如果我没有删除]

原始将是奇数列表，删除将是数字
不是素数，因此这段代码将返回原始
中没有删除的所有项目。对于n>大约10万左右，程序需要很长时间才能运行，而对于高达10,000的数字则可以。

有人知道更快的方法吗？ （查找列表中所有不在列表中的项目的差异b）？

return [i for i in original if i not in deletions]

original will be a list of odd numbers and deletions will be numbers
that are not prime, thus this code will return all items in original
that are not in deletions. For n > 100,000 or so, the program takes a
very long time to run, whereas it''s fine for numbers up to 10,000.

Does anybody know a faster way to do this? (finding the difference all
items in list a that are not in list b)?

测试未排序列表中的成员资格是O（n）操作...... b $ b操作......列表越大，花费的时间越长。


我认为订单无关紧要，或者结果可以事后分类

。如果是这种情况，那么使用提供交集/差异/联合方法的

集非常有效。如果你通过套装而不是清单传递
，你可以简单地


返回original.difference（删除）


这几乎不值得调用函数:)还有一个名为difference_update（）的

就地版本。


一次你找到了你想要的所有结果，并且完成了你想要的所有设置

差异，你可以将结果集传递给

列表并对其进行排序，如果排序结果很重要。


-tkc

Testing for membership in an unsorted list is an O(n) sort of
operation...the larger the list, the longer it takes.

I presume order doesn''t matter, or that the results can be sorted
after the fact. If this is the case, it''s quite efficient to use
sets which provide intersection/difference/union methods. If you
pass in sets rather than lists, you can simply

return original.difference(deletions)

It''s almost not worth calling a function for :) There''s also an
in-place version called difference_update().

Once you''ve found all the results you want, and done all the set
differences you want, you can just pass the resulting set to a
list and sort it, if sorted results matter.

-tkc

ao ****** @ gmail.com 写道：

有人知道更快的方法吗？ （查找列表中不包含在列表中的所有项目的差异b）？

Does anybody know a faster way to do this? (finding the difference all
items in list a that are not in list b)?

a = [3,7,16,1,2,19,13,4,0,8] #random.sample（范围（20），10）
b = [15,11,7 ，2，0,3,9,1,12,16]＃相似
排序（集（a） - 集（b））
[4,8,13,19]

a = [3, 7, 16, 1, 2, 19, 13, 4, 0, 8] # random.sample(range(20),10)
b = [15, 11, 7, 2, 0, 3, 9, 1, 12, 16] # similar
sorted(set(a)-set(b))
[4, 8, 13, 19]

但你可能不想使用那种实现。


这里'' sa版本使用生成器：


def sieve_all（n = 100）：

＃产生所有素数到n

stream = iter（xrange（2，n））

而True：

p = stream.next（）

收益率p

def s1（p，stream）：

＃产生所有非倍数的p

return（如果q％p！= 0，则流为q的q）

stream = s1（p，stream）


＃打印所有素数高达100

打印列表（sieve_all（100））


它很可爱，但一旦你意识到它正在做什么就很可怕;-)

but you probably don''t want to use that kind of implementation.

Here''s a version using generators:

def sieve_all(n = 100):
# yield all primes up to n
stream = iter(xrange(2, n))
while True:
p = stream.next()
yield p
def s1(p, stream):
# yield all non-multiple of p
return (q for q in stream if q%p != 0)
stream = s1(p, stream)

# print all primes up to 100
print list(sieve_all(100))

It''s cute, but horrendous once you realize what it''s doing ;-)

这篇关于加快这段代码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！