Most efficient way to "pre-grow" a list?

In Perl one can assign a value to any element of an array, even to
ones corresponding to indices greater or equal than the length of
the array:

my @arr;
$arr[999] = 42;

perl grows the array as needed to accommodate this assignment. In
fact one common optimization in Perl is to "pre-grow" the array to
its final size, rather than having perl grow it piecemeal as required
by assignments like the one above:

my @arr;
$#arr = 999_999;

After assigning to $#arr (the last index of @arr) as shown above,
@arr has length 1,000,000, and all its elements are initialized to
undef.

In Python the most literal translation of the first code snippet
above triggers an IndexError exception:

>>> arr = list()
>>> arr[999] = 42
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: list assignment index out of range

In fact, one would need to pre-grow the list sufficiently to be
able to make an assignment like this one. I.e. one needs the
equivalent of the second Perl snippet above.

The best I can come up with is this:

arr = [None] * 1000000

Is this the most efficient way to achieve this result?

TIA!

kynn

kj

kj <> writes:
> >>> arr[999] = 42
> ...
> The best I can come up with is this:
> arr = [None] * 1000000
> Is this the most efficient way to achieve this result?

If you're talking about an array of ints, use the array module.
You might also look at numpy.

Paul Rubin

On Nov 6, 12:12*pm, kj <no.em...@please.post> wrote:

[snip]

> In fact, one would need to pre-grow the list sufficiently to be
> able to make an assignment like this one. *I.e. one needs the
> equivalent of the second Perl snippet above.
>
> The best I can come up with is this:
>
> arr = [None] * 1000000
>
> Is this the most efficient way to achieve this result?

That's a good as it gets I think.

If sparsely populated I might be tempted to use a dict (or maybe
defaultdict):

d = {999: 42, 10673: 123}
for idx in xrange(1000000): # Treat it as though it's a list of
1,000,000 items...
print 'index %d has a value of %d' % (idx, d.get(idx, None))

Efficiency completely untested.

Jon.

Jon Clements

On Fri, Nov 6, 2009 at 1:12 PM, kj <> wrote:
>
> In Perl one can assign a value to any element of an array, even to
> ones corresponding to indices greater or equal than the length of
> the array:
>
> Â*my @arr;
> Â*$arr[999] = 42;
>
> perl grows the array as needed to accommodate this assignment. Â*In
> fact one common optimization in Perl is to "pre-grow" the array to
> its final size, rather than having perl grow it piecemeal as required
> by assignments like the one above:
>
> Â*my @arr;
> Â*$#arr = 999_999;
>
> After assigning to $#arr (the last index of @arr) as shown above,
> @arr has length 1,000,000, and all its elements are initialized to
> undef.
>
> In Python the most literal translation of the first code snippet
> above triggers an IndexError exception:
>
>>>> arr = list()
>>>> arr[999] = 42
> Traceback (most recent call last):
> Â*File "<stdin>", line 1, in <module>
> IndexError: list assignment index out of range
>
> In fact, one would need to pre-grow the list sufficiently to be
> able to make an assignment like this one. Â*I.e. one needs the
> equivalent of the second Perl snippet above.
>
> The best I can come up with is this:
>
> arr = [None] * 1000000
>
> Is this the most efficient way to achieve this result?

It depends - what do you want to do with it? My first hunch would be
to use a dictionary instead of a list, then the whole problem
disappears. If there is a reason you don't want to do that, what is
it?


--
André Engels,

Andre Engels

[kj]
> In fact, one would need to pre-grow the list sufficiently to be
> able to make an assignment like this one. *I.e. one needs the
> equivalent of the second Perl snippet above.
>
> The best I can come up with is this:
>
> arr = [None] * 1000000
>
> Is this the most efficient way to achieve this result?

Yes.


Raymond

Raymond Hettinger

"Andre Engels" <> wrote in message
news:mailman.2696.1257520404.2807.python-...
>On Fri, Nov 6, 2009 at 1:12 PM, kj <> wrote:
[snip]
>> arr = [None] * 1000000
>>
>> Is this the most efficient way to achieve this result?
>
> It depends - what do you want to do with it? My first hunch would be
> to use a dictionary instead of a list, then the whole problem
> disappears. If there is a reason you don't want to do that, what is
> it?
>
> --
> André Engels,

I second this. It might seem a sensible thing to do in perl, but I can't
imagine what you would actually want to do it for! Seems like an odd thing
to want to do!

Emily Rodgers

In <hd1os1$aqs$> "Emily Rodgers" <> writes:


>"Andre Engels" <> wrote in message
>news:mailman.2696.1257520404.2807.python-...
>>On Fri, Nov 6, 2009 at 1:12 PM, kj <> wrote:
>[snip]
>>> arr = [None] * 1000000
>>>
>>> Is this the most efficient way to achieve this result?
>>
>> It depends - what do you want to do with it? My first hunch would be
>> to use a dictionary instead of a list, then the whole problem
>> disappears. If there is a reason you don't want to do that, what is
>> it?

>I second this. It might seem a sensible thing to do in perl, but I can't
>imagine what you would actually want to do it for! Seems like an odd thing
>to want to do!

As I said, this is considered an optimization, at least in Perl,
because it lets the interpreter allocate all the required memory
in one fell swoop, instead of having to reallocate it repeatedly
as the array grows. (Of course, like with all optimizations,
whether it's worth the bother is another question.)

Another situation where one may want to do this is if one needs to
initialize a non-sparse array in a non-sequential order, e.g. if
that's the way the data is initially received by the code. Of
course, there are many ways to skin such a cat; pre-allocating the
space and using direct list indexing is just one of them. I happen
to think it is a particularly straighforward one, but I realize that
others (you, Andre, etc.) may not agree.

kynn

kj

On Nov 6, 6:12*am, kj <no.em...@please.post> wrote:
> In Perl one can assign a value to any element of an array, even to
> ones corresponding to indices greater or equal than the length of
> the array:
>
> * my @arr;
> * $arr[999] = 42;
>
> perl grows the array as needed to accommodate this assignment. *In
> fact one common optimization in Perl is to "pre-grow" the array to
> its final size, rather than having perl grow it piecemeal as required
> by assignments like the one above:
>
> * my @arr;
> * $#arr = 999_999;
>
> After assigning to $#arr (the last index of @arr) as shown above,
> @arr has length 1,000,000, and all its elements are initialized to
> undef.
>
> In Python the most literal translation of the first code snippet
> above triggers an IndexError exception:
>
> >>> arr = list()
> >>> arr[999] = 42
>
> Traceback (most recent call last):
> * File "<stdin>", line 1, in <module>
> IndexError: list assignment index out of range
>
> In fact, one would need to pre-grow the list sufficiently to be
> able to make an assignment like this one. *I.e. one needs the
> equivalent of the second Perl snippet above.
>
> The best I can come up with is this:
>
> arr = [None] * 1000000
>
> Is this the most efficient way to achieve this result?
>
> TIA!
>
> kynn

I don't have the code with me, but for huge arrays, I have used
something like:

>>> arr[0] = initializer
>>> for i in range N:
>>> arr.extend(arr)

This doubles the array every time through the loop, and you can add
the powers of 2 to get the desired result.
Gil

gil_johnson

On Nov 6, 6:12*am, kj <no.em...@please.post> wrote:
> In Perl one can assign a value to any element of an array, even to
> ones corresponding to indices greater or equal than the length of
> the array:
>
> * my @arr;
> * $arr[999] = 42;
>
> perl grows the array as needed to accommodate this assignment. *In
> fact one common optimization in Perl is to "pre-grow" the array to
> its final size, rather than having perl grow it piecemeal as required
> by assignments like the one above:
>
> * my @arr;
> * $#arr = 999_999;
>
> After assigning to $#arr (the last index of @arr) as shown above,
> @arr has length 1,000,000, and all its elements are initialized to
> undef.
>
> In Python the most literal translation of the first code snippet
> above triggers an IndexError exception:
>
> >>> arr = list()
> >>> arr[999] = 42
>
> Traceback (most recent call last):
> * File "<stdin>", line 1, in <module>
> IndexError: list assignment index out of range
>
> In fact, one would need to pre-grow the list sufficiently to be
> able to make an assignment like this one. *I.e. one needs the
> equivalent of the second Perl snippet above.
>
> The best I can come up with is this:
>
> arr = [None] * 1000000
>
> Is this the most efficient way to achieve this result?
>
> TIA!
>
> kynn

You mean sum'in like dis?

class PerlishList(list):
'''Hand holding list object for even the most demanding Perl
hacker'''
def __init__(self, dim=0):
list.__init__(self)
if dim:
self.__setitem__(dim, None)

def __setitem__(self, idx, v):
lenkeys = len(self)
sup = super(PerlishList, self)
if idx > lenkeys:
for idx in range(lenkeys, idx):
sup.append(None)
sup.__setitem__(idx, v)

def __getitem__(self, idx):
return self[idx]

l = PerlishList(3)
l.append('a')
l.append('b')
print l
l[10] = 10
print l

r

On Fri, 06 Nov 2009 18:46:33 -0800, gil_johnson wrote:

> I don't have the code with me, but for huge arrays, I have used
> something like:
>
>>>> arr[0] = initializer
>>>> for i in range N:
>>>> arr.extend(arr)
>
> This doubles the array every time through the loop, and you can add the
> powers of 2 to get the desired result. Gil

Why is it better to grow the list piecemeal instead of just allocating a
list the size you want in one go?

arr = [x]*size_wanted



--
Steven

Steven D'Aprano