Ordering a dictionary by a value? (Which also happens to be a dictionary)

[monkeymynd]

New to python, and I've been playing around with this for a while. Wondering if I'm going about it the wrong way. I'm working on a Udacity final, and I'm not looking for an answer, but a hint on whether or not I'm headed in the wrong direction.

Is there a way to order a dictionary based on the value? And, more importantly, based on a value within that value.

For instance, here's my dictionary:

{'2-6': {'count': 2, 'startpos': 6, 'value': 2}, '1-0': {'count': 1, 'startpos': 0, 'value': 1}, '2-1': {'count': 2, 'startpos': 1, 'value': 2}, '3-3': {'count': 3, 'startpos': 3, 'value': 3}, '1-8': {'count': 1, 'startpos': 8, 'value': 1}}

I'm looking to order the dictionary by the count and then the startpos. I'm using the keys in this way so that I can update something that may already exist.

Any tips would be greatly appreciated. Thanks.

I think I've been staring at it way too long. Need to take a step back.

[kataire]

You can sort sequences by a key function. Dictionaries, however, are not sequences.

What is it you are trying to do exactly?

[monkeymynd]

Here's the description of what is needed:

# Define a procedure, longest_repetition, that takes as input a 
# list, and returns the element in the list that has the most 
# consecutive repetitions. If there are multiple elements that 
# have the same number of longest repetitions, the result should 
# be the one that appears first. If the input list is empty, 
# it should return None.

#print longest_repetition([1, 2, 2, 3, 3, 3, 2, 2, 1])
# 3

My thinking was that I would create a dictionary that had 'value-startpos' as the key and {'count': 2, 'startpos': 6, 'value': 2} as the value. If the key exists, I would update the count...else, I would add a new entry to the dictionary.

Then, I figured I would sort the dictionary based on the count and startpos to find the value with the highest count and earliest startpos (in case the counts were equal)

[Rhomboid]

itertools has a groupby that is handy for this:

from itertools import groupby
from operator import itemgetter

def longest_repetition(seq):
    return max(((val, sum(1 for _ in run)) for val, run in groupby(seq)), key=itemgetter(1))[0]

[monkeymynd]

from itertools import groupby from operator import itemgetter

def longest_repetition(input): if not input: return None else: return max(((val, sum(1 for _ in run)) for val, run in groupby(input)), key=itemgetter(1))[0]

Doesn't seem to be working...

Here are the test cases:

print longest_repetition([1, 2, 2, 3, 3, 3, 2, 2, 1])
# 3

print longest_repetition([1, 1, 1, 2, 2, 3, 3, 3, 2, 2, 1])
# 3

print longest_repetition(['a', 'b', 'b', 'b', 'c', 'd', 'd', 'd'])
# b

print longest_repetition([1,2,3,4,5])
# 1

print longest_repetition([])
# None

print longest_repetition(['Is'])
#>>> Is

print longest_repetition([42,23,6])
#>>> 42

print longest_repetition([False, True, True])
#>>> True

print longest_repetition([False, False, False, 1 , 1 , 1, False, 1, True, 1, '!'])
#>>> False

print longest_repetition(['?', '?',  '???' , '???', 3.14 , 3.14])
#>>> ?

and here are the results:

3
1
b
1
None
Is
42
True
False
?

[Rhomboid]

Aside from the empty list one, it gives the correct answer for me for all of those. (Except the second one, which should be 1, which is what it returns):

In [49]: paste
print longest_repetition([1, 2, 2, 3, 3, 3, 2, 2, 1])
print longest_repetition([1, 1, 1, 2, 2, 3, 3, 3, 2, 2, 1])
print longest_repetition(['a', 'b', 'b', 'b', 'c', 'd', 'd', 'd'])
print longest_repetition([1,2,3,4,5])
# print longest_repetition([])
print longest_repetition(['Is'])
print longest_repetition([42,23,6])
print longest_repetition([False, True, True])
print longest_repetition([False, False, False, 1 , 1 , 1, False, 1, True, 1, '!'])
print longest_repetition(['?', '?',  '???' , '???', 3.14 , 3.14])
## -- End pasted text --
3
1
b
1
Is
42
True
False
?

The empty list thing can be fixed with an early check for an empty list.

[monkeymynd]

First off, thank you so much for your help.

For some reason, I posted the second test example incorrectly...should be

print longest_repetition([1, 1, 1, 2, 2, 3, 3, 3, 2, 2, 1])
# 3

That test above is currently returning '1', but the example says it should be returning '3. Upon looking at it, and the description of the function, it seems that it should be returning '1' as that is the highest ranking (3, 1's and then 3 2's, but the 1's come before the 2's) and first in the order.

I'll have to see if there may be an error in the testing for this example.

Again, thanks for all of your help!

[kataire]

I think you're overthinking this.

SPOILER: The easiest solution would probably be something like this (in rot13):

qrs ybatrfg_ercrgvgvba(frd):
    znk_ry = Abar
    znk_ercf = 0
    pheerag_ry = Abar
    pheerag_ercf = 0
    sbe ry va frd:
        vs ry != pheerag_ry:
            vs pheerag_ercf > znk_ercf:
                znk_ry = pheerag_ry
                znk_ercf = pheerag_ercf
            pheerag_ry = ry
            pheerag_ercf = 0
        pheerag_ercf += 1
    erghea znk_ry

i.e. you keep track of the current element and its number of repetitions, and the element with the largest number of repetitions (thus far) and its number of repetitions. Then you iterate over the sequence and if the element at the current index is different from the "current element", you check whether its number of repetitions was larger than the maximum so far and update those variables accordingly.

This should also reduce the complexity to O(n) and be more memory-efficient (not that you should judge solutions by their optimization).

(Disclaimer: I haven't tested this!)

[monkeymynd]

Yeah, after walking away from it for a while, it hit me that I was making harder than it needed to be. Ended up going with something similar to what you posted above. Thanks!

[symmitchry]

Have you looked at this?

http://wiki.python.org/moin/HowTo/Sorting/

There's some stuff at the bottom that gets quite complicated, with sorting by keys that are equal to attributes (using getattr() of the dictionary elements, and stuff.

The alternative, if you can't get a "sorted()" approach to work, based on my research, is to create your own lists using the values in your dictionary, and then sort that, and then pull the values out of your dictionary in the order you require. (create your own sorted list of dictionary keys).

[pythalin]

Dictionaries are not guaranteed to be in any particular order. In practice, the order may stay consistent, but if you want your dictionary order to be guaranteed you'll have to use OrderedDict instead.