像这样的代码经常发生:
l = []
while foo:
#baz
l.append(bar)
#qux
如果您要将数千个元素追加到列表中,这非常慢,因为必须不断调整列表大小以适应新元素.
在Java中,您可以创建具有初始容量的ArrayList.如果您对列表的大小有所了解,那么效率会更高.
我知道像这样的代码通常可以重新考虑到列表理解中.但是,如果for/while循环非常复杂,那么这是不可行的.我们的Python程序员有没有相同的东西？
在内存使用和CPU消耗方面,Python的效率更高 - 词典还是对象？
背景: 我必须将大量数据加载到Python中.我创建了一个只是一个字段容器的对象.创建4M实例并将它们放入字典大约需要10分钟和大约6GB的内存.字典准备好后,访问它是一眨眼.
示例: 为了检查性能,我编写了两个执行相同操作的简单程序 - 一个是使用对象,另一个是字典:
对象(执行时间~18秒):
class Obj(object):
def __init__(self, i):
self.i = i
self.l = []
all = {}
for i in range(1000000):
all[i] = Obj(i)
字典(执行时间~12秒):
all = {}
for i in range(1000000):
o = {}
o['i'] = i
o['l'] = []
all[i] = o
问题: 我做错了什么或字典比对象更快？如果确实字典表现更好,有人可以解释为什么吗？
我正在填写一个包含大约10,000,000个项目的python dict.我对dict(或hashtables)的理解是,当有太多的元素进入它们时,需要调整大小,这个操作花费了相当长的时间.
有没有办法对python dict说你将至少存储n个项目,以便它可以从一开始就分配内存？或者这种优化对我的跑步速度没有任何好处？
(不,我没有检查过我的小脚本的缓慢是因为这个,我实际上现在不会怎么做.但是我会用Java做的,设置HashSet的初始容量吧)
我应该以尽可能低的时间复杂度来解决这个问题，但让我更具体一些。
给您一个包含重复项的排序整数数组。
唯一四元组是四个索引的集合。这些索引下的数组中的元素之和必须为给定值 X。例如：
给定一个数组 [10, 20, 30, 40] 且 X = 100，则只有一个四元组：(0, 1, 2, 3)。
给定一个数组 [0, 0, 0, 0, 0] 且 X = 0，则有 5 个四元组： (0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 3 , 4), (0, 2, 3, 4), (1, 2, 3, 4)。
互联网上有很多 N^3 解决方案，但这些解决方案是针对值而不是索引的唯一四元组。在这些解决方案中，示例 1 仍仅给出一个四元组：(10, 20, 30, 40)，但示例 2 只给出一个四元组 (0, 0, 0, 0)，而不是其中的五个。
我找不到一个 O(N^3) 解决方案来代替另一个解决我的问题。我可以轻松地编写一个在 O(N^3logN) 时间内解决该问题的程序。我还听说这个问题的复杂度下限据称是未知的。是否有已知的 O(N^3) 解决方案？
我所知道的解决方案：
明显朴素的方法 O(N^4)：
int solution(int arr[], int arrSize, int X){ …