Trình bày một tập hợp các URL trong một danh sách dưới dạng cấu trúc cây

Question

Tôi có một danh sách các dicts lưu trữ URL. Nó chỉ đơn giản là hai trường, title và url. Ví dụ:

[ 
    {'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'}, 
] 

Tuy nhiên, tôi muốn có cấu trúc cây từ danh sách này của dicts. Tôi đang tìm một cái gì đó như thế này:

{ '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'} 
     ] 
    } 
    ] 
} 

nỗ lực đầu tiên của tôi tại đây sẽ là một món súp urlparse trong một loạt các vòng lặp for và tôi tự tin rằng có một cách tốt hơn và nhanh hơn để làm điều này.

Tôi đã nhìn thấy mọi người về phép toán công việc SO với tính năng hiểu danh sách, hàm lambda, v.v. Tôi vẫn đang trong quá trình tìm hiểu.

(Đối với các nhà phát triển Django: Tôi sẽ sử dụng ứng dụng này Django của tôi, tôi đang lưu trữ các URL trong một mô hình gọi là Page trong đó có hai lĩnh vực name và title.)

Answer 1

thời gian thứ ba là sự quyến rũ ... đó là một số cấu trúc đẹp mà bạn có ở đó :). Trong nhận xét của bạn, bạn đề cập đến bạn "chưa thể nghĩ ra định dạng cây tốt hơn để đại diện cho dữ liệu như thế này" ... điều này khiến tôi một lần nữa mất tự do (chỉ hơi) thay đổi định dạng đầu ra. Để tự động thêm các phần tử con, một từ điển phải được tạo để chứa chúng. Nhưng đối với "các nút lá", từ điển này không bao giờ được điền vào. Nếu mong muốn các khóa học này có thể được loại bỏ bởi một vòng lặp khác, nhưng nó không thể xảy ra trong khi lặp lại vì số trống dict phải có mặt cho các nút mới có thể. Một số đi cho các nút mà không có một tập tin trong: này sẽ chứa một trống 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) 

Output:

{'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

Đây là giải pháp của tôi. Dường như nó hoạt động. Một cách tiếp cận rất khác với Jro's:

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

Tôi dường như không hiểu tại sao tôi cần phải sắp xếp vào đầu mỗi lần đệ quy. Tôi cá là nếu tôi làm việc đó, tôi có thể cạo thêm vài giây nữa.