"Исправить-это файл" вызов


Я учусь Python и нашел эту проблему с Google код вареньем:

Сколько команды mkdir команды нужно, чтобы построить дано дерево каталогов:

Вход

Первая строка входных данных содержит количество тестовых случаев, Т. Т тестовые случаи следовать. Каждый тест начинается со строки, содержащей два целых числа Н И М, разделенные пробелом.

Следующие П строк дают путь один каталог, который уже существует на вашем компьютере. Этот список будет включать в каждый каталог уже на вашем компьютере корневой каталог. (Корневой каталог находится на каждом компьютере, поэтому нет необходимости указывать в явном виде.)

Следующие м строк дают путь один каталог, который вы хотите создать.

Каждый из путей ввода форматируется как в инструкции выше проблемы. В частности, путь состоит из одного или нескольких строчных буквенно-цифровых строк (т. е. строк, содержащих только символы 'а'-'Z' и '0'-'9'), перед каждым из которых одну косую черту. Эти буквенно-цифровые строки никогда не пустуют.

Выход

Для каждого тестового случая выведите одну строку, содержащую "дело № Х: 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()


Комментарии
2 ответа

Вместо того, чтобы использовать список, считают, подходя к проблеме с точки зрения графика. Построить дерево из корневого каталога, используя существующие каталоги, а затем пройти его с новые каталоги, и вывести результат каждый раз, когда вы должны добавить лист в графе. Это должно быть немного быстрее, чем сравнение двух сетах.

5
ответ дан 14 марта 2011 в 02:03 Источник Поделиться

Вы можете создать дерево, которое надо обновлять на каждой итерации (хотя подсчитать также стоимость создания). Вы можете сделать это с простой вложенный словарь. Например:

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

Вы можете использовать алгоритм с рекурсией (функционального) или петель с работы по месту модификаций (императив). Если вы изучаете я пойду первым, так что вы можете применить некоторые концепции функционального программирования (в основном, одно правило: Не обновлять переменные!).

3
ответ дан 15 марта 2011 в 08:03 Источник Поделиться