Which is fastest dict or list.index() ?

[James T. Dennis]

Shagshag13 <shagshag13 at yahoo.fr> wrote:

> Thanks !!! (i use some tricks i find in seqdict)

>> If you want a skiplist version, let me know and I'll send it.
>> Raymond Hettinger

> I'm sorry, but i don't understand what you mean by a "skiplist version"

> So here is how i do it now, i think i miss to explain that i must keep some
> kind of id (which i use as a key in another table, and i want to keep 
> this other table indexed by integer instead of words to save mermory). 
> <- thoug i don't know if this is a real saving...

 I'd probably use a simple list of tuples in a class.  The class
 would be responsible for maintaining the sorted order of the list
 via the "bisect" module's insort function and it would provide
 a short binary search function to find and return any element 
 of the list.  

 Actually almost any technique is likely to be overkill for this
 particular problem domain.  There are max. a few thousand toons
 and any modern computer could could simply brute force them using
 x=dictionaries.items(); x.sort().

> i'm huge newbie but i feel python really pleasant, great, etc... (even if i
> had lots of trouble
> with memory run out... on a solaris system with  1024mo...)

> i post for comments or advices as i'm not a skilled pythoner...

> thanks in advance for reading and helping

> class IKeys:
>  def __init__(self):
>   self._size = 0
>   self._term = {}  # element -> int key - ex: {a : 0, b : 2, c : 1}
>   self._iKeys = [] # contains elements, int key -> element - ex: [a, c, b]

>  def __str__(self):
>   s = 'iKey (' + "\n"
>   s += str(self._term) + "\n"
>   s += str(self._iKeys) + "\n"
>   s += str(self._size) + " # size)\n"
>   return s

>  def __len__(self):
>   return self._size

>  def __getitem__(self, pos):
>   return self._iKeys[pos]

>  def index(self, element):
>   return self._term[element]

>  def add(self, element):
>   if self._term.has_key(element):
>    return self._term[element]
>   self._iKeys.append(element)
>   self._term[element] = self._size
>   self._size += 1
>   return (self._size - 1)

>  def keys(self):
>   return self._iKeys

>  def get_size(self):
>   return self._size

> which i use like this :

>>>> toons = IKeys()
>>>> for t in ['Bugs', 'Mickey', 'Babs', 'Jerry', 'Tom', 'Babs']:
>  toons.add(t)
> 0
> 1
> 2
> 3
> 4
> 2  # already in toons so we don't had it, we get id
>>>> print toons
> iKey (
> {'Mickey': 1, 'Babs': 2, 'Tom': 4, 'Bugs': 0, 'Jerry': 3}
> ['Babs', 'Bugs', 'Jerry', 'Mickey', 'Tom']
> 5 # size)
>>>> t[2]
> 'b'
>>>> toons[2]
> 'Babs'
>>>> toons.index('Jerry')
> 3
>>>> tmp = toons.keys()
>>>> tmp.sort()
>>>> for t in tmp: # here it's sorted
>  i = toons.index(t)
>  print "Toons [%s] has id [%s]" % (t, i)
> Toons [Babs] has id [2]
> Toons [Bugs] has id [0]
> Toons [Jerry] has id [3]
> Toons [Mickey] has id [1]
> Toons [Tom] has id [4]