Python: рекурсивно создайте словарь из путей
У меня есть несколько сотен тысяч URL конечной точки, для которых я хочу генерировать статистику. Например, я имею:
/a/b/c
/a/b/d
/a/c/d
/b/c/d
/b/d/e
/a/b/c
/b/c/d
Я хочу создать словарь, который похож на это
{
{'a':
{'b':
{'c': 2 },
{'d': 1 }
},
{'c':
{'d': 1 }
}
},
{'b':
{'c':
{'d': 2}
},
{'d':
{'e': 1}
}
}
}
Какие-либо умные способы сделать это?
Править
Я должен упомянуть, что пути являются не всегда 3 частями. Мог бы быть /a/b/c/d/e/f/g/h... и т.д., и т.д.
3 ответа
Если бы все пути выглядели как в вашем примере, это бы сработало:
counts = {}
for p in paths:
parts = p.split('/')
branch = counts
for part in parts[1:-1]:
branch = branch.setdefault(part, {})
branch[parts[-1]] = 1 + branch.get(parts[-1], 0)
В этом случае используются словарные методы типа setdefault() и get() , чтобы избежать необходимости писать много if-шаблонов.
Обратите внимание, что это не сработает, если путь, имеющий подкаталоги, может также появиться сам по себе. Тогда неясно, должна ли соответствующая часть countts содержать число или другой словарь. В этом случае, наверное, лучше было бы хранить и счет, и диктат для каждого узла, используя кортеж или пользовательский класс.
Основной алгоритм остается прежним:
class Stats(object):
def __init__(self):
self.count = 0
self.subdirs = {}
counts = Stats()
for p in paths:
parts = p.split('/')
branch = counts
for part in parts[1:]:
branch = branch.subdirs.setdefault(part, Stats())
branch.count += 1
С некоторой красивой печатью вы получаете:
def printstats(stats, indent=''):
print indent + str(stats.count) + ' times'
for (d, s) in stats.subdirs.items():
print indent + d + ':'
printstats(s, indent + ' ')
>>> printstats(counts)
0 times
a:
0 times
c:
0 times
d:
1 times
b:
0 times
c:
2 times
d:
1 times
...
РЕДАКТИРОВАТЬ:
Я изменил свой код, чтобы он соответствовал вашему последнему комментарию выше (сейчас нет сложной структуры данных).
def dictizeString(string, dictionary):
while string.startswith('/'):
string = string[1:]
parts = string.split('/', 1)
if len(parts) > 1:
branch = dictionary.setdefault(parts[0], {})
dictizeString(parts[1], branch)
else:
if dictionary.has_key(parts[0]):
# If there's an addition error here, it's because invalid data was added
dictionary[parts[0]] += 1
else:
dictionary[parts[0]] = 1
Он будет хранить список [частота, словарь] для каждого элемента.
Контрольный пример
>>> d = {}
>>> dictizeString('/a/b/c/d', d)
>>> dictizeString('/a/b/c/d', d)
>>> dictizeString('/a/b/c/d', d)
>>> dictizeString('/a/b/c/d', d)
>>> dictizeString('/a/b/e', d)
>>> dictizeString('/c', d)
>>> d
{'a': {'b': {'c': {'d': 4}, 'e': 1}}, 'c': 1}
Вот моя попытка:
class Result(object):
def __init__(self):
self.count = 0
self._sub_results = {}
def __getitem__(self, key):
if key not in self._sub_results:
self._sub_results[key] = Result()
return self._sub_results[key]
def __str__(self):
return "(%s, %s)" % (self.count, self._sub_results)
def __repr__(self):
return str(self)
def process_paths(paths):
path_result = Result()
for path in paths:
components = path[1:].split("/")
local_result = path_result
for component in components:
local_result = local_result[component]
local_result.count += 1
return path_result
Я заключил часть логики в класс Result , чтобы попытаться сделать сам алгоритм немного понятнее.