Efficiently building ordered dict

[Diez B. Roggisch]

Am 22.02.10 22:29, schrieb Bryan:
> On Feb 22, 10:57 am, "Alf P. Steinbach"<al... at start.no>  wrote:
>> * Bryan:
>>
>>
>>
>>> I am looping through a list and creating a regular dictionary.  From
>>> that dict, I create an ordered dict.  I can't think of a way to build
>>> the ordered dict while going through the original loop.  Is there a
>>> way I can avoid creating the first unordered dict just to get the
>>> ordered dict?  Also, I am using pop(k) to retrieve the values from the
>>> unordered dict while building the ordered one because I figure that as
>>> the values are removed from the unordered dict, the lookups will
>>> become faster.  Is there a better idiom that the code below to create
>>> an ordered dict from an unordered list?
>>
>>> unorderedDict = {}
>>> for thing in unorderedList:
>>>     if thing.id in unorderedDict:
>>>             UpdateExistingValue(unorderedDict[thing.id])
>>>     else:
>>>             CreateNewValue(unorderedDict[thing.id])
>>
>> If this were real code the last statement would generate an exception.
>>
>>> orderedDict = OrderedDict()
>>> for k in sorted(unorderedDict.keys()):
>>>     orderedDict[k]  unorderedDict.pop(k)
>>
>> This is not even valid syntax.
>>
>> Please
>>
>>     (1) explain the problem that you're trying to solve, not how you
>>         imagine the solution, and
>>
>>     (2) if you have any code, please post real code (copy and paste).
>>
>> The above code is not real.
>>
>> Cheers&  hth.,
>>
>> - Alf
>
> Sorry about the sorted != ordered mix up.  I want to end up with a
> *sorted* dict from an unordered list.  *Sorting the list is not
> practical in this case.*  I am using python 2.5, with an ActiveState
> recipe for an OrderedDict.
>
> Given these requirements/limitations, how would you do it?
>
> My solution is to create a regular dict from the list.  Then sort the
> keys, and add the keys+values to an OrderedDict.  Since the keys are
> being added to the OrderedDict in the correctly sorted order, at the
> end I end up with a OrderedDict that is in the correctly *sorted*
> order.

If that works for you, I don't understand your assertion that you can't 
sort the list. If you have the space & time to sort the intermediate 
dict, then it's as easy to create the list & sort & then the ordered 
dict from it. It should be faster, because you sort the keys anyway.

Diez