convert a list of delimited strings to a tree/nested dict, using python

Question

I am trying to convert a list of dot-separated strings, e.g.

['one.two.three.four', 'one.six.seven.eight', 'five.nine.ten', 'twelve.zero']

into a tree (nested lists or dicts - anything that is easy to walk through). The real data happens to have 1 to 4 dot-separated parts of different length and has 2200 records in total. My actual goal is to fill in the set of 4 QComboBox'es with this data, in manner that the 1st QComboBox is filled with first set items ['one', 'five', 'twelve'] (no duplicates). Then depending on the chosen item, the 2nd QComboBox is filled with its related items: for 'one' it would be: ['two', 'six'], and so on, if there's another nested level.

So far I've got a working list -> nested dicts solution, but it's horribly slow, since I use regular dict(). And I seem to have a trouble to redesign it to a defaultdict in a way to easily work out filling the ComboBoxes properly.

My current code:

def list2tree(m):
    tmp = {}
    for i in range(len(m)):
        if m.count('.') == 0:
            return m
        a = m.split('.', 1)
        try:
            tmp[a[0]].append(list2tree(a[1]))
        except (KeyError, AttributeError):
            tmp[a[0]] = list2tree(a[1])
    return tmp

main_dict = {}
i = 0
for m in methods:
    main_dict = list2tree(m)
    i += 1
    if (i % 100) == 0: print i, len(methods)
print main_dict, i, len(methods)

score 28 · Accepted Answer · answered May 14 '13 at 15:55

28

ls = ['one.two.three.four', 'one.six.seven.eight', 'five.nine.ten', 'twelve.zero']
tree = {}

for item in ls:
    t = tree
    for part in item.split('.'):
        t = t.setdefault(part, {})

Result:

{
 "twelve": {
  "zero": {}
 }, 
 "five": {
  "nine": {
   "ten": {}
  }
 }, 
 "one": {
  "six": {
   "seven": {
    "eight": {}
   }
  }, 
  "two": {
   "three": {
    "four": {}
   }
  }
 }
}

answered May 14 '13 at 15:55

georg

211,518
52
313
390

Yay, that's gorgeous! Thanks for your quick response.Now I just gotta teach it to slice the dict of dicts. – python_head May 14 '13 at 16:06
Could you advice the slicing code (getting a set of keys depending on a chosen higher level key) as easy? It seems I tend to put the recursion in odd places, while your code has just shocked me with its simplicity. – python_head May 14 '13 at 16:18
@python_head: I'm not entirely sure what you mean... Given the above struct the and key `one` - what should the slicing code return? – georg May 14 '13 at 16:21
kind of getting the levels of the dict: level1 = [one,five,twelve]; if chosen level1=one, then level2 = [two,six]; if level2=two, then level3=[three], and so on. If empty, return empty list/dict. – python_head May 14 '13 at 16:26
@python_head: looks like you need `dict.keys()`: `tree['one'].keys()` returns `['six', 'two']` (the order is not guaranteed though). – georg May 14 '13 at 16:57
The expected result should be a list [two, six]. But my problem is to go further, e.g. for the level tree['one']['two'] the result is ['three']. And keep going deeper as long as there're non-empty keys, I believe. As I've mentioned, I wonder if recursive calls are adequate here, or I am gonna overkill it again :) Thanks for your attention. – python_head May 15 '13 at 08:49
After running this code, "tree" is totally empty. I don't understand how this is supposed to work. – Alkanshel Nov 24 '14 at 05:29
@Amalgovinus: make sure you run the code exactly as is, without any changes. – georg Nov 24 '14 at 08:40
I find it hard to understand this code, could you explain? How should I change this so that the end are strings instead of empty dicts? – ConanG Aug 22 '17 at 20:42
@ConanG: this code basically creates a "key-only" structure. if we bring values in play, it will be more complicated. – georg Aug 22 '17 at 23:54
@georg: Thanks. I will look into other ways of doing that. – ConanG Aug 23 '17 at 07:31

score 2 · Answer 2 · answered Jun 15 '21 at 19:25

While this is beyond the reach of the original question, some comments mentioned a form of this algorithm that incorporates values. I came up with this to that end:

def dictionaryafy(self, in_dict):
    tree = {}
    for key, value in in_dict.items():
        t = tree
        parts = key.split(".")
        for part in parts[:-1]:
            t = t.setdefault(part, {})
        t[parts[-1]] = value
    return tree

convert a list of delimited strings to a tree/nested dict, using python

2 Answers2

Linked