大小为 n 的初始化列表的复杂性? [英] Complexity of initialize list of size n?

问题描述

我需要创建一个包含 n 个项都等于 0 的列表，我使用了这个方法:

I need to create a list with n items that all equals to 0, I used this method:

list = [0] * n

时间复杂度是 O(n) 还是 O(1)?

如果是 O(n) 是不是可以用 O(1) 复杂度实现这个列表?

If it is O(n) is it a way to achieve this list with an O(1) complexity?

推荐答案

一种在 O(1) 时间内分配大对象的方法可以是(取决于你的底层操作系统)mmap.mmap，见 https://docs.python.org/2/图书馆/mmap.html.然而，它不是一个具有所有灵活性的 list —— 它的行为更像是一个可变的字符数组.

One way to allocate a large object in O(1) time can be (depending on your underlying operating system) mmap.mmap, see https://docs.python.org/2/library/mmap.html . However, it's not a list with all its flexibility -- it behaves rather like a mutable array of characters.

有时这仍然会有所帮助.在 Python 3 的最新版本中，您可以将 memoryview 放在 mmap 的结果上，然后 eb call .cast('L') 到获得与整数序列相同的内存视图(两种操作都是 O(1)).仍然不是一个列表——你没有list丰富的灵活性和方法的多样性——但是，更有可能是有帮助的......

Sometimes that can still be helpful. In recent versions of Python 3, you can put a memoryview on the result of mmap, and e.b call .cast('L') to obtain a view of the same memory as a sequence of integers (both operations are O(1)). Still not a list -- you don't get a list's rich flexibility and panoply of methods -- but, more likely to be helpful...

补充:然而，这确实让我想起了多年前，当时我正在努力将一个大型 CAD 应用程序移植到当时全新的 AIX 版本和基于 Power 的 IBM 工作站.malloc 本质上是即时的——内核只是在幕后用 CPU 中的内存映射硬件做一些魔术.

Added: this does however remind of a time many years ago when I was working to port a big CAD application to a then-brand-new AIX version and Power-based IBM workstation. malloc was essentially instantaneous -- the kernel was just doing some magic behind the scenes with memory mapping hardware in the CPU.

然而...实际上是第一次访问一个远在malloced区域中的项目(比如N个字节从它的开始)可能需要 O(N) 因为所有需要的页面实际上都已分配 - 如果系统实际上无法找到或释放进程地址空间中的那么多页面(IOW，那甚至可能导致崩溃)malloc 首先是过度使用"内存！).

However... actually accessing an item far into the malloced area (say N bytes form its start) for the first time could take O(N) as all needed pages actually got allocated -- and could even cause a crash if the system couldn't actually find or free that many pages within your process's address space (IOW, that malloc was "overcommitting" memory in the first place!).

正如您想象的那样，这对最初为 malloc 的更传统实现而开发的应用程序造成了严重破坏:该应用程序检查了 malloc 的返回值 -- 如果为 0，则它采取适当的补救措施(最坏的情况，只是让用户知道由于内存不足而无法执行他们想要的操作)；否则，它假设它刚刚分配的内存实际上在那里......有时最终会在路上的随机"点崩溃:-).

As you can imagine this wrecked havoc on an application originally developed for more traditional implementations of malloc: the app checked malloc's return value -- if 0, it took appropriate remedial action (worst case, just letting the user know their desired operation could not be performed due to lack of memory); otherwise, it assumed the memory it just allocated was actually there... and sometimes ended up crashing in "random" spots down the road:-).

解决方案只是中等难度——将 malloc 包装到一个函数中，后缀实际上触及名义分配"页面的正确子集，以确保它们实际上都在那里(它 很难捕捉到在这种时候可能出现的低级错误，但最终我设法找到了一种方法，我记得用一点汇编语言编码).当然，这确实使包装的 malloc O(N) 重来了......似乎没有这样的事情免费的午餐，谁会想到?！-)

The solution was only moderately hard -- wrap malloc into a function with a postfix actually touching the right subset of the "nominally allocated" pages to ensure they were actually all there (it was hard to catch the low-level errors that could come at such times, but eventually I managed to find a way, with a little assembly-language coding as I recall). Of course, this did make the wrapped malloc O(N) all over again... there does appear to be no such thing as a free lunch, who'd have thought?!-)

我不确定 mmap.mmap(-1, lotofbytes) 从这个角度来看，在您感兴趣的所有平台上实际表现如何——我猜除了实际实验之外别无他法！-)(如果它确实提供免费午餐，至少在流行的平台上，那么现在那将值得庆祝:-).

I'm not sure how mmap.mmap(-1, lotsofbytes) actually behaves from this point on view on all platforms of your interest -- nothing for it but actually experiment, I guess!-) (If it does turn out to offer a free lunch, at least on popular platforms, now that would be worth celebrating:-).

这篇关于大小为 n 的初始化列表的复杂性?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！