Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email firstname.lastname@example.org
From: ergosum (ergosumneurosecurity.com)
Date: Tue Apr 01 2008 - 09:08:41 CDT
> results in:
> >>> for l in [100000, 1000000, 5000000, 10000000]:
> ... print '%10d %f' % (l, test(l))
> 100000 0.006711
> 1000000 0.764886
> 5000000 28.554786
> 10000000 111.738498
> (wow - so not linear ...)
This is very interesting. I'm not a python ninja but AFAIK (quoting from:
"Chaining two lists of length N1 and N2 is O(N1+N2). Multiplying a list of
length N by the number M is O(N*M). Accessing or rebinding any list item is
O(1) (also known as constant time, meaning that the time taken does not
depend on how many items are in the list). len( ) on a list is also O(1).
Accessing any slice of length M is O(M). Rebinding a slice of length M with
one of identical length is also O(M). Rebinding a slice of length M1 with one
of different length M2 is O(M1+M2+N1), where N1 is the number of items after
the slice in the target list."
So if this is true, slicing data[1024:] should be O(M) where M = 100000,
1000000, 5000000, 10000000 respectively, while slicing data[i:i+1024] should
always be O(N) where N = 1024. There is a huge gain here that accounts for
the more or less homogeneous times of the second algorithm. Nevertheless it
puzzles me why the slicing operation isn't linear. Anyone with a better
python internal knowledge can throw some light?
"We must be the change we wish to see in the world"
Dailydave mailing list