Speeding up a Cython program

Question

I wrote the following piece of Python as a part of a larger system. Profiling reveals that a large amount of time is spent in DocumentFeature.from_string. So far I've tried compiling the unmodified code with Cython and got a 33% improvement in running time. Any suggestions as to how this code can be improved further are greatly appreciated.

Here's the code and the unit tests I've been using.

import logging
from operator import itemgetter
from functools import total_ordering
from unittest import TestCase
import nose

class DocumentFeature(object):
    def __init__(self, type, tokens):
        self.type = type
        self.tokens = tokens

    @classmethod
    def from_string(cls, string):
        """
        Takes a string representing a DocumentFeature and creates and object out of it. String format is
        "word/POS" or "word1/PoS1 word2/PoS2",... The type of the feature will be inferred from the length and
        PoS tags of the input string. 

        :type string: str
        """
        try:
            token_count = string.count('_') + 1
            pos_count = string.count('/')
            if token_count != pos_count:
                return DocumentFeature('EMPTY', tuple())

            tokens = string.strip().split('_')
            if len(tokens) > 3:
                raise ValueError('Document feature %s is too long' % string)
            bits = [x.split('/') for x in tokens]
            if not all(map(itemgetter(0), bits)):
                # ignore tokens with no text
                return DocumentFeature('EMPTY', tuple())
            tokens = tuple(Token(word, pos) for (word, pos) in bits)

            if len(tokens) == 1:
                t = '1-GRAM'
            elif ''.join([t.pos for t in tokens]) == 'NVN':
                t = 'SVO'
            elif ''.join([t.pos for t in tokens]) == 'JN':
                t = 'AN'
            elif ''.join([t.pos for t in tokens]) == 'VN':
                t = 'VO'
            elif ''.join([t.pos for t in tokens]) == 'NN':
                t = 'NN'
            elif len(tokens) == 2:
                t = '2-GRAM'
            elif len(tokens) == 3:
                t = '3-GRAM'
            else:
                t = 'EMPTY'
        except:
            logging.error('Cannot create token out of string %s', string)
            raise

        return DocumentFeature(t, tokens)

    def __eq__(self, other):
        return (isinstance(other, self.__class__)
                and self.__dict__ == other.__dict__)
    # other irrelevant methods removed

@total_ordering
class Token(object):
    def __init__(self, text, pos, index=0):
        self.text = text
        self.pos = pos
        self.index = index

    def __str__(self):
        return '{}/{}'.format(self.text, self.pos) if self.pos else self.text

    def __repr__(self):
        return self.__str__()

    def __eq__(self, other):
        return (not self < other) and (not other < self)

    def __lt__(self, other):
        return (self.text, self.pos) < (other.text, other.pos)

    def __hash__(self):
        return hash((self.text, self.pos))

class Test_tokenizer(TestCase):
    def test_document_feature_from_string(self):
        x = DocumentFeature.from_string('big/J_cat/N')
        y = DocumentFeature('AN', (Token('big', 'J'), Token('cat', 'N')))
        self.assertEqual(y, x)

        self.assertEqual(
            DocumentFeature('1-GRAM', (Token('cat', 'N'), )),
            DocumentFeature.from_string(' cat/N ')
        )

        self.assertEqual(
            DocumentFeature('VO', (Token('chase', 'V'), Token('cat', 'N'))),
            DocumentFeature.from_string('chase/V_cat/N')
        )

        self.assertEqual(
            DocumentFeature('NN', (Token('dog', 'N'), Token('cat', 'N'))),
            DocumentFeature.from_string('dog/N_cat/N')
        )

        self.assertEqual(
            DocumentFeature('3-GRAM', (Token('dog', 'V'), Token('chase', 'V'), Token('cat', 'V'))),
            DocumentFeature.from_string('dog/V_chase/V_cat/V')
        )

        self.assertEqual(
            DocumentFeature('2-GRAM', (Token('chase', 'V'), Token('cat', 'V'))),
            DocumentFeature.from_string('chase/V_cat/V')
        )

        self.assertEqual(
            DocumentFeature('SVO', (Token('dog', 'N'), Token('chase', 'V'), Token('cat', 'N'))),
            DocumentFeature.from_string('dog/N_chase/V_cat/N')
        )

        for invalid_string in ['a\/s/N', 'l\/h/N_clinton\/south/N', 'l\/h//N_clinton\/south/N',
                               'l//fasdlj/fasd/dfs/sdf', 'l//fasdlj/fasd/dfs\_/sdf', 'dfs\_/sdf',
                               'dfs\_/fadslk_/sdf', '/_dfs\_/sdf', '_/_/', '_///f_/', 'drop_bomb',
                               'drop/V_bomb', '/V_/N', 'cat']:
            self.assertEqual(
                DocumentFeature('EMPTY', tuple()),
                DocumentFeature.from_string(invalid_string)
            )

if __name__ == '__main__':
    nose.core.runmodule()

Answer 1

By parsing the string using a regular expression, I get a 20% performance increase over your original code.

from itertools import izip_longest
import re

class DocumentFeature(object):
    def __init__(self, type, tokens):
        self.type = type
        self.tokens = tokens

    _TYPES = dict([
        ('NVN', 'SVO'), ('JN', 'AN'), ('VN', 'VO'), ('NN', 'NN')
    ])
    _TOKEN_RE = re.compile(r'([^/_]+)/([NVJ])(?:_|$)')

    @classmethod
    def from_string(cls, string):
        try:
            match = cls._TOKEN_RE.split(string, 3)
            type = ''.join(match[2::3])
            match = iter(match)
            tokens = []
            for (junk, word, pos) in izip_longest(match, match, match):
                if junk:        # Either too many tokens, or invalid token
                    raise ValueError(junk)
                if not word:
                    break
                tokens.append(Token(word, pos))
            type = cls._TYPES.get(type,
                ('EMPTY', '1-GRAM', '2-GRAM', '3-GRAM')[len(tokens)])
            return DocumentFeature(type, tuple(tokens))
        except:
            raise

Answer 2

I find your error handling is a bit counterintuitive: if the input string is invalid, you return an "empty" DocumentFeature, but if there are too many tokens, it raises an exception. I would raise exceptions in both cases, and let the caller decide what to do.

I think that you're being too pessimistic in validating your inputs: the validation repeats some of the real work that would be done anyway. Furthermore, counting slashes and underscores is insufficient validation — for example, "word1_word2//" passes the initial validation, only to fail at tuple(Token(word, pos) for (word, pos) in bits). Instead, I would suggest validating as you perform the transformations.

_TYPES = dict([
    ('NVN', 'SVO'), ('JN', 'AN'), ('VN', 'VO'), ('NN', 'NN')
])

@classmethod
def from_string(cls, string):
    """
    Takes a string representing a DocumentFeature and creates and object out of it. String format is
    "word/PoS" or "word1/PoS1_word2/PoS2",... The type of the feature will be inferred from the length and
    PoS tags of the input string. 

    :type string: str
    """
    try:
        tokens = string.strip().split('_')
        if len(tokens) > 3:
            raise ValueError('Document feature %s is too long' % string)

        tokens = [token.split('/') for token in tokens]

        # Check for too many slashes, too few slashes, or empty words
        if not all(map(lambda token: len(token) == 2 and token[0], tokens)):
            raise ValueError('Invalid document feature %s' % string)

        tokens = tuple(Token(word, pos) for (word, pos) in tokens)

        type = cls._TYPES.get(''.join([t.pos for t in tokens]),
            ('EMPTY', '1-GRAM', '2-GRAM', '3-GRAM')[len(tokens)])
    except:
        logging.error('Cannot create token out of string %s', string)
        raise

    return DocumentFeature(type, tokens)