How to make this code faster?

Question

I'm learning Python. I found this problem from Google Code Jam. And solved it by writing code shown below. It works correctly, but how can I make it faster?

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

Rather than using a list, consider approaching the problem from a graph perspective. Build a tree from the root directory using the existing directories, then traverse it with the new directories, and output a result line each time you have to add a leaf to the graph. This should be a little faster than comparing your two sets.

Answer 2

You can create a tree that you'd update on each iteration (while you calculate also the creation cost). You can do that with a simple nested dictionary. For example:

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

You can use an algorithm with recursion (functional) or loops with inplace modifications (imperative). If you are learning I'd go for the first so you can apply some functional programming concepts (basically, one rule: don't update variables!).