Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > creating really big lists

Reply
Thread Tools

creating really big lists

 
 
Dr Mephesto
Guest
Posts: n/a
 
      09-05-2007
Hi!

I would like to create a pretty big list of lists; a list 3,000,000
long, each entry containing 5 empty lists. My application will append
data each of the 5 sublists, so they will be of varying lengths (so no
arrays!).

Does anyone know the most efficient way to do this? I have tried:

list = [[[],[],[],[],[]] for _ in xrange(3000000)]

but its not soooo fast. Is there a way to do this without looping?

David.

 
Reply With Quote
 
 
 
 
Paul Rudin
Guest
Posts: n/a
 
      09-05-2007
Dr Mephesto <(E-Mail Removed)> writes:

> Hi!
>
> I would like to create a pretty big list of lists; a list 3,000,000
> long, each entry containing 5 empty lists. My application will append
> data each of the 5 sublists, so they will be of varying lengths (so no
> arrays!).
>
> Does anyone know the most efficient way to do this? I have tried:
>
> list = [[[],[],[],[],[]] for _ in xrange(3000000)]
>
> but its not soooo fast. Is there a way to do this without looping?


You can do:

[[[],[],[],[],[]]] * 3000000

although I don't know if it performs any better than what you already
have.
 
Reply With Quote
 
 
 
 
Diez B. Roggisch
Guest
Posts: n/a
 
      09-05-2007
Paul Rudin wrote:

> Dr Mephesto <(E-Mail Removed)> writes:
>
>> Hi!
>>
>> I would like to create a pretty big list of lists; a list 3,000,000
>> long, each entry containing 5 empty lists. My application will append
>> data each of the 5 sublists, so they will be of varying lengths (so no
>> arrays!).
>>
>> Does anyone know the most efficient way to do this? I have tried:
>>
>> list = [[[],[],[],[],[]] for _ in xrange(3000000)]
>>
>> but its not soooo fast. Is there a way to do this without looping?

>
> You can do:
>
> [[[],[],[],[],[]]] * 3000000
>
> although I don't know if it performs any better than what you already
> have.


You are aware that this is hugely different, because the nested lists are
references, not new instances? Thus the outcome is most probably (given the
gazillion of times people stumbled over this) not the desired one...

Diez
 
Reply With Quote
 
Bryan Olson
Guest
Posts: n/a
 
      09-05-2007
Paul Rudin wrote:
> Dr writes:
>> I would like to create a pretty big list of lists; a list 3,000,000
>> long, each entry containing 5 empty lists. My application will append
>> data each of the 5 sublists, so they will be of varying lengths (so no
>> arrays!).
>>
>> Does anyone know the most efficient way to do this? I have tried:
>>
>> list = [[[],[],[],[],[]] for _ in xrange(3000000)]
>>
>> but its not soooo fast. Is there a way to do this without looping?

>
> You can do:
>
> [[[],[],[],[],[]]] * 3000000
>
> although I don't know if it performs any better than what you already
> have.


Actually, that produces list of 3000000 references to the same
5-element list. A reduced example:

>>> lst = [[[],[],[],[],[]]] * 3
>>> lst[1][1].append(42)
>>> print lst

[[[], [42], [], [], []], [[], [42], [], [], []], [[], [42], [], [], []]]


--
--Bryan
 
Reply With Quote
 
Paul Rudin
Guest
Posts: n/a
 
      09-05-2007
"Diez B. Roggisch" <(E-Mail Removed)> writes:

> Paul Rudin wrote:
>
>> Dr Mephesto <(E-Mail Removed)> writes:
>>
>>> Hi!
>>>
>>> I would like to create a pretty big list of lists; a list 3,000,000
>>> long, each entry containing 5 empty lists. My application will append
>>> data each of the 5 sublists, so they will be of varying lengths (so no
>>> arrays!).
>>>
>>> Does anyone know the most efficient way to do this? I have tried:
>>>
>>> list = [[[],[],[],[],[]] for _ in xrange(3000000)]
>>>
>>> but its not soooo fast. Is there a way to do this without looping?

>>
>> You can do:
>>
>> [[[],[],[],[],[]]] * 3000000
>>
>> although I don't know if it performs any better than what you already
>> have.

>
> You are aware that this is hugely different, because the nested lists are
> references, not new instances? Thus the outcome is most probably (given the
> gazillion of times people stumbled over this) not the desired one...


Err, yes sorry. I should try to avoid posting before having coffee in
the mornings.
 
Reply With Quote
 
Dr Mephesto
Guest
Posts: n/a
 
      09-05-2007
yep, thats why I'm asking

On Sep 5, 12:22 pm, "Diez B. Roggisch" <(E-Mail Removed)> wrote:
> Paul Rudin wrote:
> > Dr Mephesto <(E-Mail Removed)> writes:

>
> >> Hi!

>
> >> I would like to create a pretty big list of lists; a list 3,000,000
> >> long, each entry containing 5 empty lists. My application will append
> >> data each of the 5 sublists, so they will be of varying lengths (so no
> >> arrays!).

>
> >> Does anyone know the most efficient way to do this? I have tried:

>
> >> list = [[[],[],[],[],[]] for _ in xrange(3000000)]

>
> >> but its not soooo fast. Is there a way to do this without looping?

>
> > You can do:

>
> > [[[],[],[],[],[]]] * 3000000

>
> > although I don't know if it performs any better than what you already
> > have.

>
> You are aware that this is hugely different, because the nested lists are
> references, not new instances? Thus the outcome is most probably (given the
> gazillion of times people stumbled over this) not the desired one...
>
> Diez



 
Reply With Quote
 
Hrvoje Niksic
Guest
Posts: n/a
 
      09-05-2007
Dr Mephesto <(E-Mail Removed)> writes:

> I would like to create a pretty big list of lists; a list 3,000,000
> long, each entry containing 5 empty lists. My application will
> append data each of the 5 sublists, so they will be of varying
> lengths (so no arrays!).
>
> Does anyone know the most efficient way to do this? I have tried:
>
> list = [[[],[],[],[],[]] for _ in xrange(3000000)]


You might want to use a tuple as the container for the lower-level
lists -- it's more compact and costs less allocation-wise.

But the real problem is not list allocation vs tuple allocation, nor
is it looping in Python; surprisingly, it's the GC. Notice this:

$ python
Python 2.5.1 (r251:54863, May 2 2007, 16:56:35)
[GCC 4.1.2 (Ubuntu 4.1.2-0ubuntu4)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import time
>>> t0=time.time(); l=[([],[],[],[],[]) for _ in xrange(3000000)];
>>> t1=time.time()
>>> t1-t0

143.89971613883972

Now, with the GC disabled:
$ python
Python 2.5.1 (r251:54863, May 2 2007, 16:56:35)
[GCC 4.1.2 (Ubuntu 4.1.2-0ubuntu4)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import gc
>>> gc.disable()
>>> import time
>>> t0=time.time(); l=[([],[],[],[],[]) for _ in xrange(3000000)];
>>> t1=time.time()
>>> t1-t0

2.9048631191253662

The speed difference is staggering, almost 50-fold. I suspect GC
degrades the (amortized) linear-time list building into quadratic
time. Since you allocate all the small lists, the GC gets invoked
every 700 or so allocations, and has to visit more and more objects in
each pass. I'm not sure if this can be fixed (shouldn't the
generational GC only have to visit the freshly created objects rather
than all of them?), but it has been noticed on this group before.

If you're building large data structures and don't need to reclaim
cyclical references, I suggest turning GC off, at least during
construction.
 
Reply With Quote
 
Aahz
Guest
Posts: n/a
 
      09-05-2007
In article <(E-Mail Removed). com>,
Dr Mephesto <(E-Mail Removed)> wrote:
>
>I would like to create a pretty big list of lists; a list 3,000,000
>long, each entry containing 5 empty lists. My application will append
>data each of the 5 sublists, so they will be of varying lengths (so no
>arrays!).


Why do you want to pre-create this? Why not just create the big list and
sublists as you append data to the sublists?
--
Aahz ((E-Mail Removed)) <*> http://www.pythoncraft.com/

"Many customs in this life persist because they ease friction and promote
productivity as a result of universal agreement, and whether they are
precisely the optimal choices is much less important." --Henry Spencer
http://www.lysator.liu.se/c/ten-commandments.html
 
Reply With Quote
 
John Machin
Guest
Posts: n/a
 
      09-05-2007
On Sep 5, 7:50 pm, Dr Mephesto <(E-Mail Removed)> wrote:
> Hi!
>
> I would like to create a pretty big list of lists; a list 3,000,000
> long, each entry containing 5 empty lists. My application will append
> data each of the 5 sublists, so they will be of varying lengths (so no
> arrays!).


Will each and every of the 3,000,000 slots be used? If not, you may be
much better off storagewise if you used a dictionary instead of a
list, at the cost of slower access.

Cheers,
John

 
Reply With Quote
 
Dr Mephesto
Guest
Posts: n/a
 
      09-06-2007
On 6 Sep., 01:34, "Delaney, Timothy (Tim)" <(E-Mail Removed)> wrote:
> Hrvoje Niksic wrote:
> > Dr Mephesto <(E-Mail Removed)> writes:

>
> >> I would like to create a pretty big list of lists; a list 3,000,000
> >> long, each entry containing 5 empty lists. My application will
> >> append data each of the 5 sublists, so they will be of varying
> >> lengths (so no arrays!).

>
> >> Does anyone know the most efficient way to do this? I have tried:

>
> >> list = [[[],[],[],[],[]] for _ in xrange(3000000)]

> > If you're building large data structures and don't need to reclaim
> > cyclical references, I suggest turning GC off, at least during
> > construction.

>
> This is good advice, but another question is whether you really want
> such a list. You may well be better off with a database of some kind -
> they're designed for manipulating large amounts of data.
>
> Tim Delaney


I need some real speed! a database is waaay to slow for the algorithm
im using. and because the sublists are of varying size, i dont think I
can use an array...

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
GIDS 2009 .Net:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf ASP .Net 0 12-26-2008 09:29 AM
GIDS 2009 .Net:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf ASP .Net Web Controls 0 12-26-2008 06:11 AM
GIDS 2009 Java:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf Python 0 12-24-2008 07:35 AM
GIDS 2009 Java:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf Ruby 0 12-24-2008 05:07 AM
List of lists of lists of lists... =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==?= Python 5 05-15-2006 11:47 AM



Advertisments