[SOLVED] Ordering Python structure by dict key

hydrurga · 03-18-2016, 08:49 AM

I'm hoping that Python counts as a proper programming language here.

I'm currently writing a Python program to analyse ext3/4 filesystems and part of my program builds a Python structure called dirent while traversing a directory's data blocks. Sample dirent contents are as follows:

Code:

{223: {'rec_len': 44,
       'name_len': 36,
       'file_type': 1,
       'name': 'c8d653e2b6be79114668c7b9d3c8f37f.png'},
 428: {'rec_len': 4052,
       'name_len': 36,
       'file_type': 1,
       'name': '8d6eaaa5e649889966028dc059831f4e.png'},
 120: {'rec_len': 44,
       'name_len': 36,
       'file_type': 1,
       'name': 'd75e4930a5f82d09111eb1a12c214f7d.png'},
 1193: {'rec_len': 44,
        'name_len': 36,
        'file_type': 1,
        'name': 'c6c41617f1c1bc669fd897dd527136e9.png'},
 278: {'rec_len': 3980,
       'name_len': 36,
       'file_type': 1,
       'name': '45ff55acd424e43983714352b70ae1fa.png'},
 1318: {'rec_len': 44,
        'name_len': 36,
        'file_type': 1,
        'name': 'd57958bbb31272679376b68367aebc7d.png'},
 279: {'rec_len': 4024,
       'name_len': 36,
       'file_type': 1,
       'name': '3530722f4852d3ff971d13770cbd7742.png'},
 1203: {'rec_len': 72,
        'name_len': 36,
        'file_type': 1,
        'name': 'cbe30ff8539c2fc5bff6cd27dd238b8c.png'},
 200: {'rec_len': 4024,
       'name_len': 36,
       'file_type': 1,
       'name': '9590eff28f0a8f57e7997f4032f028ab.png'}}

The first number in each record is the inode number.

What I would like to do is order this structure so that it is ordered by the 'name' field. However I'm having trouble getting my head around how to do this.

Essentially I have a dict with one field which is itself a dict with four fields, and I'd like to order the whole dict using one of the subsidiary dict values as a key.

Is this possible?

dugan · 03-18-2016, 09:30 AM

Depends what you're trying to do.

You can get the list of values with the dict's .values() method and sort that list by name.

There's a collections.OrderedDict class that's sorted by insertion order.

If some combination of the above isn't adequate, then you need to rethink how you're structuring the data.

hydrurga · 03-18-2016, 09:40 AM

Quote:

Originally Posted by dugan

There's a collections.OrderedDict class that's sorted by insertion order.

Thanks dugan. I've used that class before, when I've needed to remember insertion order, but in this case the insertion order is of no consequence.

Edit: Sorry, I understand now. The resulting ordered dict structure can be stored in an OrderedDict structure in order to retain the ordering. I'll do that, but my problem is working out if the original dict can easily be sorted with the sorted() function in the way I'm looking for, without having to manually traverse the data structure, breaking the dict up into its components and doing the sorting on these.

dugan · 03-18-2016, 09:46 AM

See my edit.

dugan · 03-18-2016, 09:55 AM

You can run sorted() on the keys or the values, and doing so gives you a list of either the keys or the values. You can't reorder the dict using a single call to sorted(), especially since dict ordering is technically undefined.

grail · 03-18-2016, 10:00 AM

I do not have much Python experience, so I played with the idea in Ruby.

My process was to create another hash (dict) with the name as the key and your original keys (eg. 223). The I simply sorted that hash and used the sorted order to display the original data in the form needed.

Not sure if that helps at all ... probably best to listen to dugan

hydrurga · 03-18-2016, 10:53 AM

Thanks to both of you. Interesting approach, grail.

Just in case my intentions weren't clear, I was hoping that a one command sort would create (with the target an OrderedDict):

Code:

{279: {'rec_len': 4024,
       'name_len': 36,
       'file_type': 1,
       'name': '3530722f4852d3ff971d13770cbd7742.png'},

 278: {'rec_len': 3980,
       'name_len': 36,
       'file_type': 1,
       'name': '45ff55acd424e43983714352b70ae1fa.png'},

 428: {'rec_len': 4052,
       'name_len': 36,
       'file_type': 1,
       'name': '8d6eaaa5e649889966028dc059831f4e.png'},

 ...

i.e. the exact same structure as the original, but ordered by ascending 'name'.

You're right though, dugan. It was far easier for me, without knowing how to achieve the above programatically, to change my original structure to base the master key on the name rather than the inode.

So I did exactly that, creating the structure, and then following up with a:

Code:

dirent = OrderedDict(sorted(dirent.items())

There's still this niggling thought that my original aim should be achievable, that I should somehow be able to order the whole structure on the values of sub-dict fields, but if it doesn't exist, it doesn't exist.

Marked as "Solved" with my thanks again.

grail · 03-18-2016, 12:12 PM

Well if it helps, here is the ruby I whipped up for the same:

Code:

#!/usr/bin/env ruby

sorted_h = {}

h = {223 => {rec_len: 44,
       name_len: 36,
       file_type: 1,
       name: 'c8d653e2b6be79114668c7b9d3c8f37f.png'},
 428 => {rec_len: 4052,
       name_len: 36,
       file_type: 1,
       name: '8d6eaaa5e649889966028dc059831f4e.png'},
 120 => {rec_len: 44,
       name_len: 36,
       file_type: 1,
       name: 'd75e4930a5f82d09111eb1a12c214f7d.png'},
 1193 => {rec_len: 44,
        name_len: 36,
        file_type: 1,
        name: 'c6c41617f1c1bc669fd897dd527136e9.png'},
 278 => {rec_len: 3980,
       name_len: 36, 
       file_type: 1,
       name: '45ff55acd424e43983714352b70ae1fa.png'},
 1318 => {rec_len: 44, 
        name_len: 36, 
        file_type: 1,
        name: 'd57958bbb31272679376b68367aebc7d.png'},
 279 => {rec_len: 4024,
       name_len: 36, 
       file_type: 1,
       name: '3530722f4852d3ff971d13770cbd7742.png'},
 1203 => {rec_len: 72,
        name_len: 36,
        file_type: 1,
        name: 'cbe30ff8539c2fc5bff6cd27dd238b8c.png'},
 200 => {rec_len: 4024,
       name_len: 36,
       file_type: 1,
       name: '9590eff28f0a8f57e7997f4032f028ab.png'}
}

names = {}

h.each{|k,v| names[v[:name]] = k}

names.keys.sort.each do |key|
  sorted_h[names[key]] = h[names[key]]
end

puts sorted_h

hydrurga · 03-18-2016, 12:31 PM

Maybe I should be changing languages.

dugan · 03-18-2016, 01:13 PM

The Python equivalent of the above would be:

Code:

import collections

h = {} # You know what data goes in here. I'll leave it out for this example.

sorted_h = collections.OrderedDict()

for key, value in sorted(h.iteritems(), key=lambda item: item[1]['name']):
    sorted_h[key] = value

# sorted_h is sorted by name

Quote:

Originally Posted by hydrurga

Maybe I should be changing languages.

Well, I can see that grail's code uses a standard dictionary for both the original and the sorted dictionary. In Python you absolutely need an OrderedDict for the sorted one, because the order of keys and values in standard dictionaries is undefined. Whether that real technical difference is a reason to change languages is up to you.

hydrurga · 03-18-2016, 01:33 PM

Thanks dugan, that is indeed what the doctor ordered (any puns intentional).

I'm too used to Python at the moment anyway. There are just some things I seem to have conceptual difficulties with, and Python dicts and lists are two of them (I know that they should be simple, I use them, but I just haven't got to grips with them yet as regards having a real understanding).

grail · 03-18-2016, 01:44 PM

Mine also has a cheat that is not obvious ... names.keys, this returns an array of the keys which is then sorted.

I did do one with some of the steps combined as well, but it is confusing if you are not familiar with ruby.

As a side note, I did initially start learning python (3+), but was lead to Ruby by kurumi here on LQ