假设我有一张单子
l = [1, 1 , 1, 2, 3, 4, 5, 5]
以及两个长度相等的不相交的集合
a = (1, 3)
和b = (2, 5)
我想分别得到l
中的元素,也就是a
和b
中的元素
[1, 1, 1, 3]
和[2, 5, 5]
我尝试了列表理解,比如[x for x in l if x in a]
,但是如果l
、a
和b
的长度是10^5,那就需要很长时间
编辑:集合是长度相等的不相交集合。你知道吗
编辑:我需要做的是计算l
中的元素,这在a
中是常见的(有重复项),减去b
中l
的元素(也有重复项)。所以上面的例子应该输出1
。问题是列表和集合的长度是否与10E5一样长。使用filter和itertools仍然需要很长时间。你知道吗
编辑:我现在明白了!显然,我必须用set()
包装输入集!一开始我没有(我只是通过input().split()
得到的),因为输入已经是唯一的,但不知道列表和集合非常不同,集合更快!好吧,直到我。你知道吗
快点?你知道吗
由于Kasramvd提出了一种聪明的方法,Wesley的马力框架也被提出了,所以让我来设定一个定量的尺度,使之能够处理单个的解决方案。你知道吗
让我们既公平又量化:
更多的,一旦10E+5项目在游戏中。处理的效率和速度、内存处理、矢量化潜在的和(可能)隐藏的不良副作用、CPU缓存延迟掩蔽较差或较好的非CPU数据访问时间(以及更多的troll)-这些都是敌人,我们必须在生产中生活:
总结:
Nathan基于
set
的方法对于所有被测试的量表来说都要快得多。你知道吗Nathan的方法处理小的,
1E+4
和1E+6
缩放集的速度要快得多,它利用了隐藏在set
-s中独特元素的python哈希集合中的有利搜索能力(正如set
类型正是为其引入的)。你知道吗然而,
O( m*n )
/O( n^2 )
不能被证明。你知道吗这些假定的复杂度模型应该意味着,随着
m
、n
规模的增长,基于numpy
的方法与基于相同list
/set
数据集的基于set
的方法相比,对更大的m
、n
数据集的不利性能惩罚将增长并加速随着
set
尺度的增大,初始边缘在更大尺度上变得更小。你知道吗1:3速度优势在
1E+4
尺度上有所下降,但部分1:2速度优势在
1E+6
尺度上较小。你知道吗实际的代码执行使得任务O(m*n)/O(n^2)-复杂性的先验假设无法在体内得到证实。
如何测试?你知道吗
提示:
是的,没有免费的晚餐。
如您所见,一旦我们不得不为JIT编译付出代价。 然而,多亏了Travis OLIPHANT伟大的
numba
工具,没有人能阻止我们进行“pre mini call”(让JIT编译器完成它的职责)下一步用已经编译好的
与
Nathan Davis
交流想法引发的事后讨论计时:请参考实际代码执行工件出现时计时结果的差异(缓存脏度的差异,)
对于缩放到
1E+4
和1E+6
大小的对象:在
numba
的帮助下:最后,几乎-
1E+6
缩放:您可以使用来自
itertools
模块的chain
和repeat
函数:注意:作为一种更有效的方法,您可以为
a
使用一个set
容器,该容器对于成员身份检查具有O(1)复杂性,并且您不需要调用list
如果您不需要结果作为列表,chain.from_iterable
返回一个iterator。你知道吗或者,作为一种非常优化的方法,您可以使用
numpy
,它在处理大量列表时特别强大:根本的问题是您没有为作业使用适当的数据结构。 在这种情况下,使用元组表示集合可能是ok对于small集合, 但是对于大型集合,您可以期望搜索平均值 列表中每个元素的集合总大小的一半 这实际上是其中一组。 对于列表中不是的每个元素, 我们必须搜索两个集合的所有元素来确定这一点。你知道吗
所以任何基于这些数据结构的算法 (即,用元组表示集合) 充其量是
O(m*n)
,其中m
是列表的大小n
是集合的大小。你知道吗我们真的没有办法减少
m
组件 -我们必须检查列表中的每一个元素以确定哪一组 (如果有的话)它属于。你知道吗但是,我们可以减少
n
分量。 怎样?通过对我们的集合使用更有效的数据结构。你知道吗幸运的是,这并不难,因为Python包含一个内置的
set
类型。 所以第一步是构造两个集合:现在,我们可以轻松(有效地)确定元素
e
是否在其中一个集合中:现在,我们只需要循环输入列表并累积结果:
相关问题 更多 >
编程相关推荐