3
\$\begingroup\$

I have some paths in a list. Here is an example:

a=["/desktop/folderA/fileA","/desktop/folderA/folderX/file1","/diskKH/folderA/fileA","/desktop/folderB/folderC/fileX"]

However I need the output to be in the following form.

[{
    'name': 'desktop',
    'children': [{
        'name': 'folderA',
        'children': [{
            'name': 'fileA'
        }, {
            'name': 'folderX',
            'children': {
                'name': 'file1'
            }
        }]
    }, {
        'name': 'folderB',
        'children': {
            'name': 'folderC',
            'children': {
                'name': 'fileX'
            }
        }
    }]
}, {
    'name': 'diskKH',
    'children': {
        'name': 'folderA',
        'children': {
            'name': 'fileA'
        }
    }
}]

I have programmed the following to do this.

import copy
def ChageArraryInverted(arrary):
    dict_1={}
    for index in range(len(arrary)-1,-1,-1):
        dict_1["name"]= arrary[index]
        dict_2=copy.copy(dict_1)
        dict_1["children"]=dict_2
    return dict_1["children"]

def GetResArrary(arrary):
    list_all=[]
    for item in arrary:
        item=str(item).split("/")[1::]
        item=ChageArraryInverted(item)
        list_all.append(item)
    print(list_all)
    return list_all



import pysnooper
# @pysnooper.snoop()

def Merge(dict1, dict2):
    result = copy.copy(dict1)
    if isinstance(dict1,dict):
        if dict1["name"] == dict2["name"]:
            if 'children' in dict1 and 'children' in dict2:
                if isinstance(dict1["children"], dict):
                    if dict1['children']['name'] == dict2['children']['name']:
                        result['children'] = [Merge(dict1['children'], dict2['children'])]
                    else:
                        result['children'] = [dict1['children'], dict2['children']]
                if isinstance(dict1["children"], list):
                    for index in range(0, len(dict1["children"])):
                        if dict1['children'][index]['name'] == dict2['children']['name']:
                            result['children'] = [Merge(dict1['children'][index], dict2['children'])]
                        else:
                            if dict2['children'] not in result['children']:
                                result['children'].append(dict2['children'])
            elif 'children' in dict1:
                result['children'] = [dict1['children']]
            elif 'children' in dict2:
                result['children'] = [dict2['chidlren']]
            else:
                if "children" in result:
                    del result['children']
            return result
        else:
            result = [result, dict2]
            return result
    elif isinstance(dict1,list):
        for index in range(0,len(dict1)):
            if dict1[index]["name"] == dict2["name"]:
                if 'children' in dict1[index] and 'children' in dict2:
                    if isinstance(dict1[index]["children"], dict):
                        if dict1[index]['children']['name'] == dict2['children']['name']:
                            result['children'] = [Merge(dict1[index]['children'], dict2['children'])]
                        else:
                            result['children'] = [dict1[index]['children'], dict2['children']]
                    if isinstance(dict1[index]["children"], list):
                        for index in range(0, len(dict1[index]["children"])):
                            if dict1[index]['children'][index]['name'] == dict2['children']['name']:
                                result['children'] = [Merge(dict1[index]['children'][index], dict2['children'])]
                            else:
                                if dict2['children'] not in result[index]['children']:
                                    result[index]['children'].append(dict2['children'])
                elif 'children' in dict1[index]:
                    result[index]['children'] = [dict1[index]['children']]
                elif 'children' in dict2:
                    result[index]['children'] = [dict2['chidlren']]
                else:
                    if "children" in result[index]:
                        del result[index]['children']
                return result
            else:
                result = [result, dict2]
                return result

def CirArraryToResult(list):
    re={}
    for index in range(0,len(list)):
        if index<len(list)-1:
            if len(re)==0:
                re=Merge(list[index],list[index+1])
            else:
                if(index==len(list)-1):
                    return re
                re=Merge(re,list[index+1])
    return re
a=["/desktop/folderA/fileA","/desktop/folderA/folderX/file1","/diskKH/folderA/fileA","/desktop/folderB/folderC/fileX"]
res=GetResArrary(a)
res=CirArraryToResult(res)
print("res:",res)

I think this can be done better as the code is rather complex. Can the code be improved by using a more efficient algorithm? Any help or optimization ideas are greatly appreciated. Thank you!

\$\endgroup\$
  • \$\begingroup\$ Should "'name': 'diskC'" be "'name': 'desktop'"? \$\endgroup\$ – Peilonrayz May 21 at 1:51
  • \$\begingroup\$ yes,is desktop 。 。。。 \$\endgroup\$ – Unity May 21 at 2:37
3
\$\begingroup\$

Style

  1. Python has a style guide called PEP 8. Much of your code goes against it.

    • Functions and variables should be lower_snake_case.
    • You should have one space around most operators. Commas and brackets are the common exceptions.
    • You should have two newlines before and after each top level function.
    • All module level Imports should be at the top of the file.
    • You should spell things correctly. array not arrary.
    • You shouldn't shadow builtins.
    • Don't put brackets around if statements.

    You can get many tools to check this for you like pycodestyle, Prospector and flake8. You can also get tools to fix this like Black and YAPF.

import copy

import pysnooper


def change_array_inverted(array)
    dict_1 = {}
    for index in range(len(array) - 1, -1, -1):
        dict_1["name"] = array[index]
        dict_2 = copy.copy(dict_1)
        dict_1["children"] = dict_2
    return dict_1["children"]


def get_res_array(array):
    list_all = []
    for item in array:
        item = str(item).split("/")[1::]
        item = change_array_inverted(item)
        list_all.append(item)
    print(list_all)
    return list_all


# @pysnooper.snoop()
def merge(dict1, dict2):
    result = copy.copy(dict1)
    if isinstance(dict1, dict):
        if dict1["name"] == dict2["name"]:
            if 'children' in dict1 and 'children' in dict2:
                if isinstance(dict1["children"], dict):
                    if dict1['children']['name'] == dict2['children']['name']:
                        result['children'] = [merge(dict1['children'], dict2['children'])]
                    else:
                        result['children'] = [dict1['children'], dict2['children']]
                if isinstance(dict1["children"], list):
                    for index in range(0, len(dict1["children"])):
                        if dict1['children'][index]['name'] == dict2['children']['name']:
                            result['children'] = [merge(dict1['children'][index], dict2['children'])]
                        else:
                            if dict2['children'] not in result['children']:
                                result['children'].append(dict2['children'])
            elif 'children' in dict1:
                result['children'] = [dict1['children']]
            elif 'children' in dict2:
                result['children'] = [dict2['chidlren']]
            else:
                if "children" in result:
                    del result['children']
            return result
        else:
            result = [result, dict2]
            return result
    elif isinstance(dict1, list):
        for index in range(0, len(dict1)):
            if dict1[index]["name"] == dict2["name"]:
                if 'children' in dict1[index] and 'children' in dict2:
                    if isinstance(dict1[index]["children"], dict):
                        if dict1[index]['children']['name'] == dict2['children']['name']:
                            result['children'] = [merge(dict1[index]['children'], dict2['children'])]
                        else:
                            result['children'] = [dict1[index]['children'], dict2['children']]
                    if isinstance(dict1[index]["children"], list):
                        for index in range(0, len(dict1[index]["children"])):
                            if dict1[index]['children'][index]['name'] == dict2['children']['name']:
                                result['children'] = [merge(dict1[index]['children'][index], dict2['children'])]
                            else:
                                if dict2['children'] not in result[index]['children']:
                                    result[index]['children'].append(dict2['children'])
                elif 'children' in dict1[index]:
                    result[index]['children'] = [dict1[index]['children']]
                elif 'children' in dict2:
                    result[index]['children'] = [dict2['chidlren']]
                else:
                    if "children" in result[index]:
                        del result[index]['children']
                return result
            else:
                result = [result, dict2]
                return result


def cir_array_to_result(array):
    re = {}
    for index in range(0, len(array)):
        if index < len(array) - 1:
            if len(re) == 0:
                re = merge(array[index], array[index+1])
            else:
                if index == len(array) - 1:
                    return re
                re = merge(re, array[index+1])
    return re


a = ["/desktop/folderA/fileA", "/desktop/folderA/folderX/file1", "/diskKH/folderA/fileA", "/desktop/folderB/folderC/fileX"]
res = get_res_array(a)
res = cir_array_to_result(res)
print("res:", res)

Improvements

  1. The code in change_array_inverted is really confusing.

    1. Please don't copy objects when you can just create a new one. Copying can add things that are not immediately apparent.
    2. Rather than building from the bottom up we can build from the top down. This makes the code easier to follow.
    3. I would change the name of the argument to names as we are being passed a list of names.
  2. There are some changes I'd make to get_res_array.

    1. Change the name of the argument to paths as we are being passed paths.
    2. Use a list comprehension. This is special syntax to make building lists quicker to read and write.
  3. There are some changes I would make to cir_array_to_result.

    1. We can remove the if index < len(array) - 1: statement by changing the value we pass to range.
    2. Rather than having the if index == len(array) - 1: check we can start by assigning re to array[0].
  4. The function merge really needs some love.

    1. We need to split the function into two. Whenever you think about copying and pasting a block of code you should always think about making a function instead.

      The code to handle lists looks like it has some errors in it.

      1. You use result[index] when there are no children in both dict1 or dict2.
      2. You don't use result[index] when dict1['children'] is a dictionary, or the names are not the same.
      3. You use result[index] when dict1['children'] is a list, but you have another loop that changes the value of index.

      This smaller function will be called _merge take dict1, dict2 and result.

    2. When dict1 is a list, if the first dictionary doesn't have the same name as dict2 then none of the other dictionaries get checked. Move the else: return [result, dict2] outside the loop.
    3. When dict1['children'] is a list you have another issue. If there is more than one child, then dict2 is always appended and potentially merged.
import copy

import pysnooper


def change_array_inverted(names)
    root = item = {}
    for name in names:
        item["children"] = {"name": array[index]}
    return root["children"]


def get_res_array(paths):
    return [
        change_array_inverted(str(path).split("/")[1::])
        for path in paths
    ]


def cir_array_to_result(array):
    re = array[0]
    for index in range(1, len(array)):
        re = merge(re, array[index])
    return re


def _merge(lhs, rhs, result):
    if 'children' in lhs and 'children' in rhs:
        if isinstance(lhs["children"], dict):
            if lhs['children']['name'] == rhs['children']['name']:
                result['children'] = [merge(lhs['children'], rhs['children'])]
            else:
                result['children'] = [lhs['children'], rhs['children']]
        if isinstance(lhs["children"], list):
            for index in range(0, len(lhs["children"])):
                if lhs['children'][index]['name'] == rhs['children']['name']:
                    result['children'] = [merge(lhs['children'][index], rhs['children'])]
                    break
            else:
                if rhs['children'] not in result['children']:
                    result['children'].append(rhs['children'])
    elif 'children' in lhs:
        result['children'] = [lhs['children']]
    elif 'children' in rhs:
        result['children'] = [rhs['chidlren']]
    else:
        if "children" in result:
            del result['children']


# @pysnooper.snoop()
def merge(dict1, dict2):
    result = copy.copy(dict1)
    if isinstance(dict1, dict):
        if dict1["name"] == dict2["name"]:
            _merge(dict1, dict2, result)
            return result
        else:
            return [result, dict2]
    elif isinstance(dict1, list):
        for index in range(len(dict1)):
            if dict1[index]["name"] == dict2["name"]:
                _merge(dict1[index], dict2, result[index])
                return result
        return [result, dict2]


a = ["/desktop/folderA/fileA", "/desktop/folderA/folderX/file1", "/diskKH/folderA/fileA", "/desktop/folderB/folderC/fileX"]
res = get_res_array(a)
res = cir_array_to_result(res)
print("res:", res)

There are still some other ways to improve the code, but they're starting to get challenging to implement.

High Level Review

It's much easier to use dictionaries in a different way. By only taking the folder names as the keys and having them point to child dictionaries we can build a tree.

root = {}
root.setdefault('desktop', {}).setdefault('folderA', {}).setdefault('fileA', {})
print(root)
# {'desktop': {'folderA': {'fileA': {}}}}

root.setdefault('desktop', {}).setdefault('folderA', {}).setdefault('folderX', {}).setdefault('file1', {})
print(root)
# {'desktop': {'folderA': {'fileA': {}, 'folderX': {'file1': {}}}}}

Rather than using .setdefault all the time we can instead subclass dict to make it super simple.

class TreeDict(dict):
    def __missing__(self, key):
        self[key] = value = TreeDict()
        return value


root = TreeDict()
root['desktop']['folderA']['fileA']
print(root)
# {'desktop': {'folderA': {'fileA': {}}}}

root['desktop']['folderA']['folderX']['file1']
print(root)
# {'desktop': {'folderA': {'fileA': {}, 'folderX': {'file1': {}}}}}

root['diskKH']['folderA']['fileA']
root['desktop']['folderB']['folderC']['fileX']

From this we can then just convert to whatever form you want.

import json


def to_desired(node, name=''):
    result = {'name': name}
    if node:
        children = [
            to_desired(value, key)
            for key, value in node.items()
        ]
        if len(children) == 1:
            children = children[0]
        result['children'] = children
    return result


result = to_desired(root)['children']
print(json.dumps(result, indent=4))
[
    {
        "name": "desktop",
        "children": [
            {
                "name": "folderA",
                "children": [
                    {
                        "name": "fileA"
                    },
                    {
                        "name": "folderX",
                        "children": {
                            "name": "file1"
                        }
                    }
                ]
            },
            {
                "name": "folderB",
                "children": {
                    "name": "folderC",
                    "children": {
                        "name": "fileX"
                    }
                }
            }
        ]
    },
    {
        "name": "diskKH",
        "children": {
            "name": "folderA",
            "children": {
                "name": "fileA"
            }
        }
    }
]
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ To make it usable on different OSes, you might want to use pathlib or os.path rather than .split('/'), to get the parts of the path. \$\endgroup\$ – RootTwo May 22 at 0:46
  • \$\begingroup\$ @RootTwo We don't know what type of path it is. It could be a URL path which always uses '/'. Changing to os.sep, or pathlib, can lead to unforeseen problems. \$\endgroup\$ – Peilonrayz May 22 at 0:48
  • \$\begingroup\$ It’s very kind of you,It is very useful。I learned a lot \$\endgroup\$ – Unity May 22 at 3:31
2
\$\begingroup\$

The easy way to generate the output in the given format is to build the dynamic tree structure first, to maintain parent and child mappings as a tree. Then we have the structure we can transform the intermediate output to desired output

from collections import defaultdict

all_folders = ["/desktop/folderA/fileA", "/desktop/folderA/folderX/file1", "/diskKH/folderA/fileA",
     "/desktop/folderB/folderC/fileX"]


def build_dynamic_trees(list_of_folders):
    tree = lambda: defaultdict(tree)
    root = tree()
    for folders in list_of_folders:
        dynamic_keys = ''
        for folder_name in folders.split("/"):
            if not folder_name:
                continue
            dynamic_keys += "['{}']".format(folder_name)
        exec('root' + dynamic_keys + ' = None')
    return root

res = to_desired(build_dynamic_trees(all_folders))['children']

As @Peilonrayz mentioned, you can use to_desired method to recursively transform the output.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ thank you very much,it is very useful to me。 \$\endgroup\$ – Unity May 22 at 3:34
  • \$\begingroup\$ This is really really not good. you can easily change dynamic_keys so you don't you're not building a string to eval, and instead just evaluate the code right there and then. node = node[folder_name] \$\endgroup\$ – Peilonrayz May 22 at 15:24
  • \$\begingroup\$ @Peilonrayz . I'm using 'exec' not 'eval'. Since we have dynamic keys it's also a choice to use for dynamic assignment of the dictionaries. \$\endgroup\$ – Rohith Rangaraju May 22 at 15:30
  • \$\begingroup\$ @RohithRangaraju That's just pedantry, eval is bad 1 2. You can do the exact same thing without it. \$\endgroup\$ – Peilonrayz May 22 at 15:33
  • \$\begingroup\$ @Peilonrayz I agree that it is a not a good practice to use exec or eval but not in the simple dictionary variable assignment, the things you might be talking about is about complex cases. Even though there are security risks involved with exec or eval, I don't see any applicable issues on dictionary assignment. If your saying as a general thumb rule to not use it, then if can you come up with some counter examples to not use for dictionary variable assignment \$\endgroup\$ – Rohith Rangaraju May 22 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.