在python中制作包含整数的类似列表的对象的最快方法 [英] Fastest way to make a list-like object containing integers in python

问题描述

这意味着我想要一个对象，该对象支持列表的两个(非常)基本操作:在特定索引中获取对象(1)，并更改其值(2).

This means I want to have an object that supports the two (very) basic operations of a list: getting an object in a certain index (1) and changing its value (2).

我遇到了这两个问题: [ 1] [2]

I came across these two: [1] [2]

他们没有解决我的问题，因为所有解决方案都太慢了:在我的PC中array.array('i',(0,)*10 ** 8)导致错误(lol)； [0 for _ in range(10**8)]花费了大约15秒(哇！)； [0] * 10 ** 8用了2.3秒； [None] * 10 ** 8用了1.8秒； (1.8秒可能会更快...)

They didn't solve my problem because all the solutions to them were simply too slow: in my PC array.array('i',(0,)*10 ** 8) resulted in an error (lol); [0 for _ in range(10**8)] took about 15 seconds (wow!); [0] * 10 ** 8 took 2.3 seconds; [None] * 10 ** 8 took 1.8 seconds; (1.8sec could be faster...)

我尝试使用ctypes模块

from ctypes import c_int
array = (c_int * 10 ** 8)()

上面的代码只用了0.7秒...但是有什么方法可以使其更快?除了速度快外，它还有一些缺点:

The code above took only 0.7 seconds ... but is there a way to make it faster? Besides being fast it has some disadvantages:

1. 由于它使用c/c ++变量的骨架，因此其中的整数将处于不像python那样无限"的整数值范围内
2. 列表中不能有多个数据类型
3. 您必须导入一个模块才能使用它

1. As it uses the c/c++ variables' skeleton, the integers in it will be in a "not as unlimited as python" integer value range
2. You can't have more than one datatype in the list
3. You have to import a module to use it

真的可以按照我的要求去做吗?有没有比使用ctypes模块更快的方法?如果是这样，请确保您使用的是内置"/预安装"模块.

Is it really possible to do what I'm asking? Is there a faster way rather than using the ctypes module? If so make sure that you are using a 'built-in' / 'pre-installed' module.

我正在使用python进行竞争性编程，大多数解释器/判断子都不允许使用外部库.

I'm using python for competitive programming and most interpreters/judges just won't allow external libraries.

我可以看到许多答案使用array模块的array功能.它们都使用'i'来指定我们要存储整数.是否可以创建一个类并创建一个包含它的"array.array"?例如:

I can see many of the answers use the array function of the array module. They all use 'i' to specify we want to store integers. Is it possible to make a class and create an `array.array' containing it? For example:

class Point:
 def __init__(self, x, y):
  self.x = x
  self.y = y

# make array.array object with all indexes containing a Point with atributes x and y with value 0
# an example with a list of what I want to do is this:
# l = [Point(0, 0) for _ in range(10**3)]

推荐答案

array.array('i',(0,) * 10**8)导致错误(lol)

array.array('i',(0,) * 10**8) resulted in an error (lol)

您没有指定遇到的错误-对我有用，尽管它不是很快，因为它会建立一个中间元组并立即将其丢弃.使用Python的内置类型，array.array可能会带来最佳性能，前提是您避免使用元组:

You didn't specify what error you got - that works for me, although it's not very fast because it builds an intermediate tuple and immediately discards it. Using Python's built-in types, array.array will probably result in best performance, provided you avoid the tuple:

a = array.array('i', (0,)) * 10**8

上面的代码只用了0.7秒...但是有什么方法可以使其更快?

The code above took only 0.7 seconds ... but is there a way to make it faster?

如果不允许创建或导入C扩展名，将很难击败array.array.在我使用了数年的旧机器上，上述过程需要0.6秒.您可以通过增加初始数组的大小来进一步优化它.例如，这会产生相同的结果，但速度快将将近(！)3倍:

It will be hard to beat array.array if you're not allowed to create or import C extensions. On my several years old machine the above takes 0.6 seconds. You can further optimize it by increasing the size of the initial array. For example, this produces the same result, but is almost 3x faster (!):

# 0.22 s
a = array.array('i', (0,) * 10) * 10**7

在我的计算机上，以下版本最有效:

On my machine the following version works best:

# 0.19 s
a = array.array('i', (0,) * 100) * 10**6

进一步增加初始阵列大小无济于事，并很快开始降低性能.

Further increasing the initial array size doesn't help and soon starts degrading performance.

为获得更好的效率，请考虑其他方法，例如为您的用例量身定制的惰性列表或完全不同的数据结构.在竞争的背景下，这实际上可能是我们所追求的.

To get better efficiency, consider alternative approaches, such as a lazy list or an altogether different data structure tailored for your use case. Given the context of a competition, that might be what is actually being sought.

但是请注意，每种解决方案都会有不同的权衡.例如，像@KonstantinNikitin提供的一个惰性数组将非常有效地进行构造，但是用纯Python实现的__getitem__和__setitem__将比list或array.array慢几个数量级. .哪种方法更适合您，归结为程序中哪些操作更频繁，而这取决于您自己找出答案.

Be aware, however, that each solution will have different tradeoffs. For example, a lazy array such as one provided by @KonstantinNikitin will be extremely efficient to construct, but its __getitem__ and __setitem__, implemented in pure Python, will be several orders of magnitude slower than those of list or array.array. Which is better for you boils down to what operations are more frequent in your program, and that is up to you to find out.

这篇关于在python中制作包含整数的类似列表的对象的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！