Efficiently building ordered dict

[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])

orderedDict = OrderedDict()
for k in sorted(unorderedDict.keys()):
orderedDict[k] unorderedDict.pop(k)

 

[MRAB]

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?

Why are you building a dict from a list and then an ordered dict from
that? Just build the ordered dict from the list, because it's behaves
like a dict, except for remembering the order in which the keys were
added.

 

[Bryan]

Why are you building a dict from a list and then an ordered dict from
that? Just build the ordered dict from the list, because it's behaves
like a dict, except for remembering the order in which the keys were
added.

Could you write some pseudo-code for that? I'm not sure how I would
add the items to the OrderedDict while looping through the list.
Wouldn't the list need to be sorted first (which in this case isn't
practical)?

 

[MRAB]

Could you write some pseudo-code for that? I'm not sure how I would
add the items to the OrderedDict while looping through the list.
Wouldn't the list need to be sorted first (which in this case isn't
practical)?

ordered != sorted.

If you want the ordered dict to be sorted by key then build a dict first
and then create the ordered dict from the sorted dict. I think the
quickest way to build the sorted dict is:

orderedDict = OrderedDict(sorted(unorderedDict.items()))

although I haven't tried 'sorteddict' (see Daniel Stutzbach's post).

 

[Arnaud Delobelle]

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])

orderedDict = OrderedDict()
for k in sorted(unorderedDict.keys()):
orderedDict[k] unorderedDict.pop(k)

Why don't you sort your unorderedList first then simply create your
orderedDict?

To me your problem is stated in too vague terms anyway and the code you
post could not really work as unorderedDict is bound to remain empty
whatever the values of all the other names.

At any rate, why do you need an ordered dictionary? It seems suspect to
me as you sort the keys before inserting the items.

 

[Mark Lawrence]

Could you write some pseudo-code for that? I'm not sure how I would
add the items to the OrderedDict while looping through the list.
Wouldn't the list need to be sorted first (which in this case isn't
practical)?

Could you please clarify what you are trying to achieve as you appear to
be confusing ordering with sorting.

Mark Lawrence.

 

[Alf P. Steinbach]

* 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

 

[Bryan]

* 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.

self.accTotals = {}
for row in self.rows:
if row.acc.code in self.accTotals:
self.accTotals[row.acc.code].addRow(row)
else:
accSummary = Total()
accSummary.addRow(row)
self.accTotals[row.acc.code] = accSummary
self.accTotals = self._getOrderedDict(self.accTotals)

 

[Arnaud Delobelle]

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.

Why does the dict need to be sorted?
Why is it impractical to sort the list, but practical to sort the
dict?

Whithout knowing this, it is difficult to get an idea of your problem
an a potential solution.

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.

self.accTotals = {}
for row in self.rows:
        if row.acc.code in self.accTotals:
                self.accTotals[row.acc.code].addRow(row)
        else:
                accSummary = Total()
                accSummary.addRow(row)
                self.accTotals[row.acc.code] = accSummary
self.accTotals = self._getOrderedDict(self.accTotals)

This code is a typical example where defaultdict, which was added in
Python 2.5 [1], would be of use:

accTotals = defaultdict(Total)
for row in self.rows:
accTotals[row.acc.code].addRow(row)
self.accTotals = self._getOrderedDict(accTotals)

However, as you don't explain what self._getOrderedDict(...) does, it
is quite difficult to guess how to improve it!

[1] http://docs.python.org/library/collections.html#collections.defaultdict

 

[Diez B. Roggisch]

Am 22.02.10 22:29, schrieb Bryan:

* 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

 

[Bryan]

Am 22.02.10 22:29, schrieb Bryan:

* 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

Here is how I am converting a regular dict to an ordered dict that is
sorted by keys.

def _getOrderedDict(theDict):
ordered = OrderedDict()
for k in sorted(theDict.keys()):
ordered[k] = theDict.pop(k)
return ordered


The list is a bunch of objects that represent hours worked by
employees on particular jobs, and accounts, and client purchase orders
etc. From this list, I am generating these sorted dicts that contain
summarizing information about the list. So one of the sorted dicts
will give a summary of hours worked by job number. Another one will
give summary information by client PO number etc. So instead of
sorting the list a bunch of different ways, I keep the list as is,
generate the summaries I need into dictionaries, and then sort those
dictionaries as appropriate.

 

[Diez B. Roggisch]

Am 22.02.10 23:48, schrieb Bryan:

Am 22.02.10 22:29, schrieb Bryan:

* 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.

(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

Here is how I am converting a regular dict to an ordered dict that is
sorted by keys.

def _getOrderedDict(theDict):
ordered = OrderedDict()
for k in sorted(theDict.keys()):
ordered[k] = theDict.pop(k)
return ordered


The list is a bunch of objects that represent hours worked by
employees on particular jobs, and accounts, and client purchase orders
etc. From this list, I am generating these sorted dicts that contain
summarizing information about the list. So one of the sorted dicts
will give a summary of hours worked by job number. Another one will
give summary information by client PO number etc. So instead of
sorting the list a bunch of different ways, I keep the list as is,
generate the summaries I need into dictionaries, and then sort those
dictionaries as appropriate.

Again - why? Unless there is some filtering going on that reduces the
number of total entries before the sorting when building the
intermediate dict, a simple

ordered = OrderedDict(sorted(the_list, key=lambda v: v['some_key']))

won't cost you a dime more.

I think you believe in building the dict so that ou can have the key for
sorting. As shown abov - you don't need to.

It might even benefitial to really re-sort the original list, because
that spares you the intermediate list.


Diez

 

[MRAB]

Am 22.02.10 22:29, schrieb Bryan:

* 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

Here is how I am converting a regular dict to an ordered dict that is
sorted by keys.

def _getOrderedDict(theDict):
ordered = OrderedDict()
for k in sorted(theDict.keys()):
ordered[k] = theDict.pop(k)
return ordered

As I mentioned in an earlier post, you could do:

def _getOrderedDict(theDict):
return OrderedDict(sorted(theDict.items()))

[snip]

 

[Bryan]

Am 22.02.10 23:48, schrieb Bryan:

Am 22.02.10 22:29, schrieb Bryan:
* 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

Here is how I am converting a regular dict to an ordered dict that is
sorted by keys.

def _getOrderedDict(theDict):
   ordered = OrderedDict()
   for k in sorted(theDict.keys()):
           ordered[k] = theDict.pop(k)
   return ordered

The list is a bunch of objects that represent hours worked by
employees on particular jobs, and accounts, and client purchase orders
etc.  From this list, I am generating these sorted dicts that contain
summarizing information about the list.  So one of the sorted dicts
will give a summary of hours worked by job number.  Another one will
give summary information by client PO number etc.  So instead of
sorting the list a bunch of different ways, I keep the list as is,
generate the summaries I need into dictionaries, and then sort those
dictionaries as appropriate.

Again - why? Unless there is some filtering going on that reduces the
number of total entries before the sorting when building the
intermediate dict, a simple

ordered = OrderedDict(sorted(the_list, key=lambda v: v['some_key']))

won't cost you a dime more.

I think you believe in building the dict so that ou can have the key for
sorting. As shown abov - you don't need to.

It might even benefitial to really re-sort the original list, because
that spares you the intermediate list.

Diez

Lets say my list has 1 million items. If I sort the list before
summarizing it, I will absolutley have to sort 1 million items.

However, if I summarize first, then just sort the keys in the summary
dict, I could wind up only sorting 4 or 5 items, if within that 1
million item list, there were only 4 or 5 job numbers for example.
The list stays as is, and my summary dictionary is sorted so I can
iterate through it and make little reports that humans will like.

 

[John Posner]

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.

Have you looked at this:

http://pypi.python.org/pypi/sorteddict/1.2.1
.... print key, old[key]
....
a 0
c 2
b 5
e 3
d 4
g 9
f 1
i 6
h 8
j 7.... print key, new[key]
....
a 0
b 5
c 2
d 4
e 3
f 1
g 9
h 8
i 6
j 7

-John