[poll] anyone else needs fast random element access off a dictionary?

[Michal Vitecek]

 hello Skip,

 this is not possible because the data in the dictionary are very often
 changed -> in the worst case scenario the cached keys would have to be
 regenerated each time a distinct data is generated. here's a code
 snippet to illustrate what i'm doing:

 class MemeticAlgorithm(...):
     GENERATION_SIZE      = 15
     ADD_DISTINCT_MEMBERS = 5

     def __init__(...):
         self.distinctMembers = {}
 
     def getInitialGeneration(...):
         generation = []
         membersToGenerate = max(self.GENERATION_SIZE - self.ADD_DISTINCT_MEMBERS,
                                 self.GENERATION_SIZE - len(self.distinctMembers))
         # part I. - generate members
         for i in xrange(membersToGenerate):
             member = somehowGenerateMember()
             cost = self.computeCost(member)
             self.distinctMembers.setdefault(cost, member)
             # using setdefault() to minimalize look-ups
             generation.append(member)

         # part II. - add distinct members
         for i in xrange(membersToGenerate, self.GENERATION_SIZE):
             cost = self.distinctMembers.randkey()
             member = self.distinctMembers[cost]
             del self.distinctMembers[cost]
             # get a random member from the dictionary and delete it
             # Note: if popitem() worked better it could be used, but
             # its counter is reset everytime a new item is added to the
             # dictionary and returns items in too sequential order
             generation.append(member)
        return generation

    ...

 [i'm using a memetic algorithm for a combinatorial optimalization
 problem which is NP-hard]
        
 part I. is used to generate members from scratch. because it's possible
 that it can generate members that are alike, part II. is used to add
 distinct members to the generation as to increase diversity of the
 population and thus improve the performance of the memetic algorithm.

 however it's also probable that it can generate very diversive members
 (in terms of cost) and in such a case regenerating the cached keys
 would happen very often (always in the worst case).

 i'm removing the members from the distinctMembers dictionary because i
 don't want them to be used more than once (need as different results
 from the generator as possible). i can't use popitem() because 1) its
 internal counter is reset everytime a new item is added to the
 dictionary 2) it accesses the items almost in sequential order (hash
 function problem).

    thank you,

>Why not wrap your code in a class, then cache dict.keys()?  Only update the
>cached copy if the dictionary is modified.  Something like this untested
>code:
[Skip's example code]

-- 
		fuf		(fuf at mageo.cz)