“文件修复-它”挑战

Question

我正在学习Python，并从Google中找到了这个问题：

构造给定的目录树需要多少mkdir命令:输入输入的第一行给出测试用例的数量，T.T测试用例如下。每一种情况都以一条包含两个整数N和M的线开始，用一个空格隔开。下一个N行分别给出了计算机上已经存在的一个目录的路径。此列表将包括除根目录以外的计算机上的每个目录。(根目录位于每台计算机上，因此不需要显式列出它。)下一个M行分别给出要创建的一个目录的路径。输入中的每个路径都被格式化，如上面的问题陈述所示。具体来说，路径由一个或多个小写字母数字字符串(即仅包含符号'a'-'z‘和'0'-'9')组成，每个字符串前面都有一个斜杠。这些字母-数字字符串从不是空的。输出每个测试用例，输出一行包含“case #x: y"，其中x是用例号(从1开始)，y是您需要的mkdir数。

我已经通过编写下面所示的代码来解决这个问题，它正确地工作，但是如何使它更快呢？

import sys

def split_path(path_file,line_count_to_be_read):
    for i in range(line_count_to_be_read):
        # Get the Path line
        line = path_file.readline()
        # Skip the first slash
        line = line[1:]
        line = line.strip()
        splited = line.split('/')
        # make each subpaths from the source path
        for j in range(1,len(splited)+1):
            joined = "/".join(splited[:j])
            yield joined

def main():

    file_name = ""

    try:
        file_name = sys.argv[1]
    except IndexError:
        file_name = "A-small-practice.in"
        
    with open(file_name) as path_file:

        # skip the first line
        line = path_file.readline()
        total_testcases = int(line) # Number of Test Cases - Unused

        case_no = 0

        while True:
            line = path_file.readline()

            if not line:
                break

            # Get Existing path and New path count
            existing_count,new_count = line.split()
            existing_count = int(existing_count)
            new_count = int(new_count)        
            
            # Split Every Path and Make all Subpaths
            existing_paths = list(split_path(path_file,existing_count)) # Existing Subpaths                
            new_paths = list(split_path(path_file,new_count)) # New Subpaths

            # Remove all paths that is in Existing list from the New list
            new_mkdir_set = set(new_paths) - set(existing_paths)        

            case_no += 1
            
            # length of new_set contains number of needed mkdir(s)
            print "Case #{0}: {1}".format(case_no,len(new_mkdir_set))

if __name__ == '__main__':
    main()

Answer 1

与其使用列表，不如考虑从图的角度来处理问题。使用现有目录从根目录构建树，然后使用新目录遍历树，并在每次向图表中添加叶时输出结果行。这应该比比较你的两组快一点。

Answer 2

您可以在每次迭代中创建一个更新的树(同时计算创建成本)。您可以使用一个简单的嵌套字典来实现这一点。例如：

start with empty filesystem -> fs = {}, cost 0
"/1/2/3" -> fs = {1: {2: 3: {}}}, cost 3
"/1/2/4" -> fs = {1: {2: 3: {}, 4: {}}}, cost 1
"/5" -> fs = {1: {2: 3: {}, 4: {}}, 5: {}}, cost 1

= cost 5

您可以使用带有递归(函数式)或带内置修改的循环(命令式)的算法。如果您正在学习，我会选择第一个，这样您就可以应用一些函数式编程概念(基本上，有一个规则:不要更新变量！)