#🔒 Speed of accessing list elements

44 messages · Page 1 of 1 (latest)

tough briar
#

If I have a python list, I assume accessing element [0] is constant time. Is accessing element [-1] - i.e., the last element - O(1)? O(number of list elements)? Something else?

I have a list datapoints = [ [ time, data ], [ time, data ], ..., [ time, data ] ]. I am trying to figure out "what is my most recent data point". Obviously it's most convenient to just do datapoints[-1][0], but if that's slow I'm happy to maintain a separate variable that tracks the most recent time.

sturdy topazBOT
#

@tough briar

Python help channel opened

Remember to:

  • Ask your Python question, not if you can ask or if there's an expert who can help.
  • Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
  • Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.
grim dust
#

accessing list[-1] is constant time

removing elements from the middle of the list can take O(n) time though, e.g. pop(0) will have to move the entire list to the left

tough briar
#

is del l[:N] O(N)?

loud linden
#

It's more O(len(l)-N). The list has to copy the top len(l)-N elements down to the bottom of the list.

jolly jasper
loud linden
#

OTOH, del l[N:] is O(1) because there's no tail-of-the-list to copy.

#

So access to any element is O(1). Modifications depend on how much stuff needs shuffling around.

#

By modification I mean del or insert things. Just setting an element is also O(1): l[9] = foo

tough briar
#

got it

#

that explains why my brilliant optimization did not optimize brilliantly

subtle lintel
#

I think python still needs to decrement all ref count with del l[N:].

loud linden
#

Ain't it the way.

#

YEs it does. So that contributes to the O() number I guess.

#

CPython, anyway.

tough briar
#

Time to move everything to numpy

loud linden
#

That is not the optimisation you might think.

subtle lintel
tough briar
#

😦

loud linden
#

For somethings it is a huge advantage. For a bunch of trite small things it gets you little, possibly negative benefit.

loud linden
tough briar
#

well, I suppose we'll see.

loud linden
#

That is the lesson: measure.

tough briar
#

yeah

#

but apparently the lesson is also to not do
while( len(thing) and thing[0] is bad )
thing.pop(0)

loud linden
#

And speed isn't everything. For plenty of things, the simple stuff is fast enough.

tough briar
#

unfortunately speed matters here :/

loud linden
#

Yeah. Instead, find where thing is not bad, then crop at that point.

#

... or not crop at all, and just work on the good things.

tough briar
#

I have a few hundred objects to detect in a frame and do stuff with before the next frame comes in 16ms later

loud linden
#

Hoo, yes. You may care about speed 🙂

#

Kick to numpy or someother bulk compute engine. If you're talking about images (frames) then they pixel data are usually already an array, very very suitable for numpy or other scipy type libraries.

tough briar
#

the images are alrady numpys

loud linden
#

(Meaning negligible conversion cost to the compact fast form)

#

Better and better.

tough briar
#

I was using a list to maintain a list of boxes to manipulate, but I kept kicking boxes out and putting boxes in

#

and doing it in a Manager() list with multiprocessing

#

so the goal now is shared memory numpy arrays to move the box info arround

loud linden
#

Mutliprocessing brings its own communication costs.

#

Yes.

tough briar
#

so we'll see

vast vault
sturdy topazBOT
#
Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.