Skip to main content
gamedev.net
🔒 Locked

Efficient random access object array in python?

Started by Tylon Aug 28, 2006 at 1:45 PM 4 replies 7.7k views
Original Post
Tylon
Tylon
I need to create an array of my python objects which has a good random access speed, but I cannot really see what a good way of doing it is; - Lists I assume are implemented as linked lists, so random access is slow. - Dictionaries are implemented as hash tables, which are again unnecessarliy slow for a sequential list of homogeneous objects. - array modules such as the built-in array and third party ones like Numeric, numpy can not contain objects, only basic types. Are some of my above statements incorrect, or are there any alternatives? The arrays that I will have will be quite large and always randomly accessed, so I require a fairly efficient solution.
Gorg
Gorg
Lists are implemented similar to a C++ std::deque. The only difference is inserting in front is O(n).

They are not linked list. That would give obscenely slow performance when using random access.

So no worries, python's list are O(1) for random access.

FYI, Python 2.4 introduces deque that acts just like the C++ version. Check collections.deque.

Tylon
Tylon
Ok, thanks.
Fruny
Fruny
Quote:
Original post by Tylon
- array modules such as the built-in array and third party ones like Numeric, numpy can not contain objects, only basic types.


Numpy arrays can contain objects if you create them with dtype=object, although for most common uses, you'll certainly want to just use a list, as Gorg pointed out.
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
Kylotan
Kylotan
Quote:
Original post by Gorg
Lists are implemented similar to a C++ std::deque. The only difference is inserting in front is O(n).


In other words, they're pretty much an std::vector. ;)

Gorg
Gorg
Quote:
Original post by Kylotan
Quote:
Original post by Gorg
Lists are implemented similar to a C++ std::deque. The only difference is inserting in front is O(n).


In other words, they're pretty much an std::vector. ;)


hmm. I just looked through the source. You are right. Somehow, I thought they were using something with buckets. Oh well, good to know.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.