Complexity of initialize list of size n?

Question

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

list = [0] * n

Is the time-complexity O(n) or O(1)?

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

Answer 1

you can roll your own methods for generators too:

def foo(num, times):
    for a in range(0, times):
        yield num

After profiling in my machine :

import timeit

code = """
def foo(num, times):
    for a in range(0, times):
        yield num
"""
print timeit.timeit("foo(0,1)", setup=code)
print timeit.timeit("foo(0,2**8)", setup=code)

# 0.310677051544
# 0.32208776474

Answer 2

Creating a (dense) list of n zeros can't be done in O(1). The only option you have is to look at some sparse or lazy data structures. Depending on what you want to use this for, one option might be itertools.repeat().

a = itertools.repeat(0, n)

will be executed in O(1). Iterating over it will, of course, still be O(n).

Answer 3

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.

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...

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.

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!).

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:-).

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?!-)

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:-).