リスト内の一連のURLをツリー構造として表現する

Question

URLを格納する辞書のリストがあります。単純に2つのフィールド、titleとurlがあります。例：

[ 
    {'title': 'Index Page', 'url': 'http://www.example.com/something/index.htm'}, 
    {'title': 'Other Page', 'url': 'http://www.example.com/something/other.htm'}, 
    {'title': 'About Page', 'url': 'http://www.example.com/thatthing/about.htm'}, 
    {'title': 'Detail Page', 'url': 'http://www.example.com/something/thisthing/detail.htm'}, 
] 

しかし、私はこのdictsのリストからツリー構造を取得したいと思います。私はこのような何かを探しています：この時

{ 'www.example.com': 
    [ 
    { 'something': 
     [ 
     { 'thisthing': 
      [ 
      { 'title': 'Detail Page', 'url': 'detail.htm'} 
      ] 
     }, 
     [ 
      { 'title': 'Index Page', 'url': 'index.htm'}, 
      { 'title': 'Other Page', 'url': 'other.htm'} 
     ] 
     ] 
    }, 
    { 'thatthing': 
     [ 
     { 'title': 'About Page', 'url': 'about.htm'} 
     ] 
    } 
    ] 
} 

私の最初の試みは、forループの束でurlparseスープだろうと私はこれを行うには良いとより高速な方法があることを確信しています。

私はリスト内包、ラムダ関数などでSOの仕事の魔法を知っています。私はまだそれを理解しています。 （Djangoの開発者のために：私は私のDjangoアプリケーションこれを使うことに、私は二つのフィールドnameとtitleありPageというモデル内のURL格納しています。）

Answer 1

第三に時間が魅力ですが...それはあなたがそこにある素敵な構造です:)。あなたのコメントでは、は "このようなデータを表現するためのより良いツリー形式を考えることができませんでした"と言及しています。 ...これにより、出力の書式を自由に（わずかに）変更できました。サブ要素を動的に追加するには、辞書を格納するための辞書を作成する必要があります。しかし、 "リーフノード"の場合、この辞書は決して埋められません。もちろん、これらはもちろん別のループで削除することもできますが、新しいノードのために空のdictが存在する必要があるため、いくつかは、ファイルを持たないノードのためのものです：これらは空のlistを含みます。

ll = [ 
    {'title': 'Index Page', 'url': 'http://www.example.com/something/index.htm'}, 
    {'title': 'Other Page', 'url': 'http://www.example.com/something/other.htm'}, 
    {'title': 'About Page', 'url': 'http://www.example.com/thatthing/about.htm'}, 
    {'title': 'Detail Page', 'url': 'http://www.example.com/something/thisthing/detail.htm'}, 
] 

# First build a list of all url segments: final item is the title/url dict 
paths = [] 
for item in ll: 
    split = item['url'].split('/') 
    paths.append(split[2:-1]) 
    paths[-1].append({'title': item['title'], 'url': split[-1]}) 

# Loop over these paths, building the format as we go along 
root = {} 
for path in paths: 
    branch = root.setdefault(path[0], [{}, []]) 
    for step in path[1:-1]: 
     branch = branch[0].setdefault(step, [{}, []]) 
    branch[1].append(path[-1]) 

# As for the cleanup: because of the alternating lists and 
# dicts it is a bit more complex, but the following works: 
def walker(coll): 
    if isinstance(coll, list): 
     for item in coll: 
      yield item 
    if isinstance(coll, dict): 
     for item in coll.itervalues(): 
      yield item 

def deleter(coll): 
    for data in walker(coll): 
     if data == [] or data == {}: 
      coll.remove(data) 
     deleter(data) 

deleter(root) 

import pprint 
pprint.pprint(root) 

出力：

{'www.example.com': 
    [ 
     {'something': 
      [ 
       {'thisthing': 
        [ 
         [ 
          {'title': 'Detail Page', 'url': 'detail.htm'} 
         ] 
        ] 
       }, 
       [ 
        {'title': 'Index Page', 'url': 'index.htm'}, 
        {'title': 'Other Page', 'url': 'other.htm'} 
       ] 
      ], 
     'thatthing': 
      [ 
       [ 
        {'title': 'About Page', 'url': 'about.htm'} 
       ] 
      ] 
     }, 
    ] 
} 

Answer 2

はここに私のソリューションです。それは動作するようです。 JROの非常に異なったアプローチ：

import itertools 
import pprint 

pages = [ 
    {'title': 'Index Page', 'url': 'http://www.example.com/something/index.htm'}, 
    {'title': 'Other Page', 'url': 'http://www.example.com/something/other.htm'}, 
    {'title': 'About Page', 'url': 'http://www.example.com/thatthing/about.htm'}, 
    {'title': 'dtgtet Page', 'url': 'http://www.example.com/thatthing/'}, 
    {'title': 'Detail Page', 'url': 'http://www.example.com/something/thisthing/detail.htm'}, 
    {'title': 'Detail Page', 'url': 'http://www.example.com/something/thisthing/thisthing/detail.htm'}, 
] 



def group_urls(url_set, depth=0): 
    """ 
    Fetches the actions for a particular domain 
    """ 
    url_set = sorted(url_set, key=lambda x: x['url'][depth]) 

    tree = [] 

    leaves = filter(lambda x: len(x['url']) - 1 == depth, url_set) 
    for cluster, group in itertools.groupby(leaves, lambda x: x['url'][depth]): 
     branch = list(group) 
     tree.append({cluster: branch}) 

    twigs = filter(lambda x: len(x['url']) - 1 > depth, url_set) 
    for cluster, group in itertools.groupby(twigs, lambda x: x['url'][depth]): 
     branch = group_urls(list(group), depth+1) 
     tree.append({cluster: branch}) 

    return tree 

if __name__ == '__main__': 
    for page in pages: 
     page['url'] = page['url'].strip('http://').split('/') 

    pprint.pprint(group_urls(pages)) 

私は、私はすべての再帰の先頭にソートする必要がある理由を見つけ出すように見えることはできません。私は周りにそれを働かせる場合、私は秒の別のカップルをオフに削ることができると思います。