Python DictionaryTagger class takes too long to initialize
So far all I can see being called is the __init__ method, so I thought I would focus on that. It feels weird, so I wanted to first explain why it felt that way, and then address your questions a little.

Readability first

I think the core reason is that this code feels weird is that it appears to use list comprehensions "just because". It creates a temporary list called files; it creates a temporary list called dictionaries; it closes all the already-opened files, and then it iterates over all the dictionaries. This feels weird because these temporaries serve no obvious purpose. Instead the code could easily set its invariants (initializing self.dictionary and self.max_key_size) and then do a simple for loop over thedictionary_paths:

def __init__(self, dictionary_paths)
    self.dictionary = {}
    self.max_key_size = 0
    for path in dictionary_paths:
        dict_file = open(path, 'r')
        curr_dict = yaml.load(dict_file)
        dict_file.close()
        for key in curr_dict: 
            : : :


This may have some performance benefits, but they are likely to be too small to measure. Namely it puts less file-based pressure on the system as it only opens a single file at a time. Similarly there's somewhat less memory pressure, as only one curr_dict is maintained at a time. One downside is if initialization should fail if it can't open one of the dictionary_paths, that now happens after it does more work. I'm fine with that trade-off.

This change also gives you the opportunity to use modern approaches for closing files. For example, the open/load/close could instead use with to automatically close at the end of the block:

    with open(path, 'r') as dict_file:
        curr_dict = yaml.load(dict_file)


All in all, this advice so far makes things slightly easier to read. There are fewer moving pieces to keep in your head at the same time, and the ones that are there, are ones that we are used to tracking.

Performance concerns

Once the code is easy to read, it becomes easier to consider performance. If you're used to optimizing a compiled language, you'll find that optimizing python can be counter-intuitive. Where in a compiled language it's sometimes helpful to do a larger number of smaller operations (building manual caches, doing shifts and additions to avoid a multiplication), in python it's almost always the reverse: the fewer operations the better, even if they each take longer. What's in common? Always profile. I don't have your data, so I'm going to shoot from the hip here and offer some general ideas. It's up to you to profile them and see if any of the ideas are useful.

Loops are a good first guess, and the loop of __init__ is almost just a conditional. At first it might seem like there's nowhere to go with this, but there are actually three main things I would test to see if they are worth changing. First, the code traverses the internals of curr_dict multiple times; once is in the for loop, and once is in the lookup curr_dict[key]. Do these together by using dict.items (or dict.iteritems in python 2.x if curr_dict might be large):

for key, value in curr_dict.items():         # or .iteritems() in 2.x
    if key in self.dictionary:
        self.dictionary[key].extend(value)
    else:
        self.dictionary[key] = value
        self.max_key_size = max(self.max_key_size, len(key))


Second, to make the if and else case more similar, pull the max_key_size calculation out of the conditional:

for key, value in curr_dict.items():         # or .iteritems() in 2.x
    if key in self.dictionary:
        self.dictionary[key].extend(value)
    else:
        self.dictionary[key] = value
    self.max_key_size = max(self.max_key_size, len(key))


Or better, per what I mentioned above, let's call it once outside of the loop, having it do more work the single time we call it:

for key, value in curr_dict.items():         # or .iteritems() in 2.x
    if key in self.dictionary:
        self.dictionary[key].extend(value)
    else:
        self.dictionary[key] = value
self.max_key_size = max(len(key) for key in self.dictionary)


Third, back to the conditional. Let's examine two ways to collapse this all into a single line of code. One way is to use dict.setdefault. It reads a little funny, but it does exactly the above in one line:

self.dictionary.setdefault(key, []).extend(value)


The upside is that this only traverses the dictionary internals once. What's the downside? Even if you don't need it, this creates an empty list. That's unlikely to be a big performance concern, but if it is, the second way avoids this. A specialized dictionary type, collections.defaultdict lets you choose a "factory" for missing items. So selecting list as that factory will make self.dictionary do something similar to that setdefault line on its own:

self.dictionary = collections.defaultdict(list)
: : :
    self.dictionary[key].extend(value) # creates and extend empty list if key not present


Of course there's a potential downside to this approach too: this dictionary will create empty lists rather than throwing exceptions if someone tries to query a missing key. If that's a problem, you can always convert it back to a regular dictionary later. For convenience, here's all of that together:

def __init__(self, dictionary_paths)
    self.dictionary = collections.defaultdict(list)

    for path in dictionary_paths:
        with open(path, 'r') as dict_file:
            curr_dict = yaml.load(dict_file)
        for key, value in curr_dict.items():
            self.dictionary[key].extend(value)

    # optionally: self.dictionary = dict(self.dictionary)
    self.max_key_size = max(len(key) for key in self.dictionary)


Note also at this point it may be simpler to combine the with and for blocks, as the name curr_dict exists solely to let you close a single dict_file a little earlier. That's much less important now that it's only a single file, and perhaps having one less name and one less line of code is worth keeping the file open a little longer.

What about your other ideas?

First I'd make the loading as fast as it can be without having to resort to ugly tricks. The next steps depend a lot on initialization patterns you don't show here.


Do you instantiate a lot of DictionaryTagger instances with the same set of dictionary_paths? If so, it may be worth caching the dictionary that is created for a set of paths, and just copying (or referencing) that dictionary in later instances.
Do you instantiate a lot of DictionaryTagger instances with different combinations of a few underlying dictionary files? If so, it may be worth caching the dictionary created for each file, and merging them instead of loading the yaml file from scratch.
Do you instantiate just a single DictionaryTagger or not share any dictionary files? If so, there's nothing I can see worth trying to share.
Can you reuse a DictionaryTagger multiple times? If so, and if it's expensive enough to create it, by all means cache and share the instance. If doing so adds more than a tiny bit of complexity to your code, try profiling to be certain that the benefit will be worth it. At the very least, do a simple test with timeit to verify that class initialization is the problem.


Finally, before you even consider a performance rewrite, write some unit tests. That's even a good idea before refactoring like I showed above. I nearly missed the difference between append and extend, and thought your code had a bug in the if/else condition. Had I refactored that while misunderstanding it, I would have introduced a bug. Unit tests can help you avoid such errors, or help you find others.

Other comments

I didn't read your other two functions very closely, but I did notice a comment in tag_sentence that I wanted to call out:


   j = min(i + self.max_key_size, n)  #avoid overflow



Since your code uses j in a slicing operation, this comment suggests a mindset I would expect in a different language. Slicing operations automatically limit to the bounds of the container. For example, the following three slices give the same result:

&gt;&gt;&gt; hello = "world"
&gt;&gt;&gt; hello[3:5]
'ld'
&gt;&gt;&gt; hello[3:10]
'ld'
&gt;&gt;&gt; hello[3:]
'ld'


Then again, your code does math on the value of j, so letting it start too large could result in extra iterations. Thus the min may be necessary. Or there may be a way to start with the expressions built from the whole sentence, then remove the last word each time through the loop until it's empty. When you can find algorithms in python that don't involve index arithmetic, you'll often be happier with the results.

Correspondingly it's usually a good idea to prefer constructs that look like

for i in range(1, n):
    : : :


over ones that look like

while i &lt; n:
    : : :
    i += 1


however your actual case has some extra conditionals in there that might not allow this conversion, so this advice may not apply here.