Construct a tree from list os file paths (Python) - Performance dependent

Now that you clarified the question a bit more, I guess the following is what you want:

from collections import defaultdict

input_ = '''dir/file
dir/dir2/file2
dir/file3
dir2/alpha/beta/gamma/delta
dir2/alpha/beta/gamma/delta/
dir3/file4
dir3/file5'''

FILE_MARKER = '<files>'

def attach(branch, trunk):
    '''
    Insert a branch of directories on its trunk.
    '''
    parts = branch.split('/', 1)
    if len(parts) == 1:  # branch is a file
        trunk[FILE_MARKER].append(parts[0])
    else:
        node, others = parts
        if node not in trunk:
            trunk[node] = defaultdict(dict, ((FILE_MARKER, []),))
        attach(others, trunk[node])

def prettify(d, indent=0):
    '''
    Print the file tree structure with proper indentation.
    '''
    for key, value in d.iteritems():
        if key == FILE_MARKER:
            if value:
                print '  ' * indent + str(value)
        else:
            print '  ' * indent + str(key)
            if isinstance(value, dict):
                prettify(value, indent+1)
            else:
                print '  ' * (indent+1) + str(value)



main_dict = defaultdict(dict, ((FILE_MARKER, []),))
for line in input_.split('\n'):
    attach(line, main_dict)

prettify(main_dict)

It outputs:

dir3
  ['file4', 'file5']
dir2
  alpha
    beta
      gamma
        ['delta']
        delta
          ['']
dir
  dir2
    ['file2']
  ['file', 'file3']

A few thing to note:

• The script make heavy use of defaultdicts, basically this allows to skip checking for the existence of a key and its initialisation if it is not there
• Directory names are mapped to dictionary keys, I thought this might be a good feature for you, as key are hashed and you will able to retrieve information much faster this way than with lists. You can access the hierarchy in th

I'm not fully clear on what you have vs what you need (it'd probably help to provide some of the code you have that's too slow), but you probably should just break up your pathnames into dirnames and basenames, then build a tree from that using a purpose-made class, or at least a hierarchy of lists or dictionaries. Then various traversals should allow you to serialize in almost any way you require.

As to the performance issues, have you considered using Pypy, Cython or Shedskin? I have a deduplicating backup system I've been working on for fun, that can run the same code on Pypy or Cython; running it on Pypy actually outperforms the Cython-augmented version (by a lot on 32 bit, by a little bit on 64 bit). I'd love to compare shedskin as well, but it apparently can't yield across the shedskin/cpython boundary.

Also, profiling is de rigueur when you have performance issues - at least, if you've already selected an appropriate algorithm.