En Sun, 08 Nov 2009 10:08:35 -0300, gil_johnson
<gil_john...@earthlink.net> escribió:
On Nov 6, 8:46 pm, gil_johnson <gil_john...@earthlink.net> wrote:
The problem I was solving was this: I wanted an array of 32-bit
integers to be used as a bit array, and I wanted it initialized with
all bits set, that is, each member of the array had to be set to
4294967295. Of course, you could set your initializer to 0, or any
other 32-bit number.
Originally I found that the doubling method I wrote about before was a
LOT faster than appending the elements one at a time, and tonight I
tried the "list = initializer * N" method. Running the code below, the
doubling method is still fastest, at least on my system.
Of course, as long as you avoid the 'one at a time' method, we're
talking about fractions of a second, even for arrays that I think are
huge, like the 536,870,912 byte beastie below.
I don't get your same results; one_item*N is faster on my tests. Note that
you're comparing disparate things:
# Doubling method, run time = 0.413938045502
newArray = array.array('I') # 32-bit unsigned
integers
Method 1 creates an array object; this takes roughly 2**29 bytes
# One at a time, run time = 28.5479729176
newArray2 = array.array('I')
for i in range(134217728): # the same size as above
newArray2.append(4294967295)
This creates also an array object, *and* 134 million integer objects in
the meantime.
# List with "*", run time = 1.06160402298
newList = [4294967295] * 134217728
And this creates a list object, not an array.
Note that all your 3 methods create global objects and you never delete
them - so the last method is at a disadvantage.
A more fair test would use timeit, and run just one method at a time:
<code>
# Written in Python 3.x
# use xrange everywhere with Python 2.x
import array
INITIAL_VALUE = 4294967295
LOG2SIZE=25
SIZE = 2**LOG2SIZE
def method1a():
newArray = array.array('I')
newArray.append(INITIAL_VALUE)
for i in range(LOG2SIZE):
newArray.extend(newArray)
assert len(newArray)==SIZE
assert newArray[SIZE-1]==INITIAL_VALUE
def method2a():
newArray = array.array('I')
for i in range(SIZE):
newArray.append(INITIAL_VALUE)
assert len(newArray)==SIZE
assert newArray[SIZE-1]==INITIAL_VALUE
def method3a():
newArray = array.array('I', [INITIAL_VALUE]) * SIZE
assert len(newArray)==SIZE
assert newArray[SIZE-1]==INITIAL_VALUE
def method1l():
newList = [INITIAL_VALUE]
for i in range(LOG2SIZE):
newList.extend(newList)
assert len(newList)==SIZE
assert newList[SIZE-1]==INITIAL_VALUE
def method2l():
newList = []
for i in range(SIZE):
newList.append(INITIAL_VALUE)
assert len(newList)==SIZE
assert newList[SIZE-1]==INITIAL_VALUE
def method3l():
newList = [INITIAL_VALUE] * SIZE
assert len(newList)==SIZE
assert newList[SIZE-1]==INITIAL_VALUE
</code>
D:\temp>python31 -m timeit -s "from arraygrow import method1a" "method1a()"
10 loops, best of 3: 411 msec per loop
D:\temp>python31 -m timeit -s "from arraygrow import method2a" "method2a()"
...aborted, too long...
D:\temp>python31 -m timeit -s "from arraygrow import method3a" "method3a()"
10 loops, best of 3: 377 msec per loop
D:\temp>python31 -m timeit -s "from arraygrow import method1l" "method1l()"
10 loops, best of 3: 628 msec per loop
D:\temp>python31 -m timeit -s "from arraygrow import method3l" "method3l()"
10 loops, best of 3: 459 msec per loop
So arrays are faster than lists, and in both cases one_item*N outperforms
your doubling algorithm.
Adding one item at a time is -at least- several hundred times slower; I
was not patient enough to wait.
Finally, I just looked into calling C functions, and found
PyMem_Malloc, PyMem_Realloc, PyMem_Free, etc. in the Memory Management
section of the Python/C API Reference Manual. This gives you
uninitialized memory, and should be really fast, but it's 6:45 AM
here, and I don't have the energy to try it.
No, those are for internal use only, you can't use the resulting pointer
in Python code. An array object is a contiguous memory block, so you don't
miss anything.
--
Gabriel Genellina
--
http://mail.python.org/mailman/listinfo/python-list
