Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Ok, so given the string:

s = "Born in Honolulu Hawaii Obama is a graduate of Columbia University and Harvard Law School"

I want to retrieve:

[ ["Born"], ["Honolulu", "Hawaii", "Obama"], ["Columbia", "University"] ...]

Assuming that we have successfully tokenised the original string, my first psuedocodish attempt was:

def retrieve(tokens):
    results = []
    i = 0
    while i < len(tokens):
        if tokens[i][0].isupper():
            group = [tokens[i]]
            j = i + 1
            while i + j < len(tokens):
                if tokens[i + j][0].isupper():
                    group.append(tokens[i + j])
                    j += 1
                else:
                    break                
        i += 1
    return results

This is actually quite fast (well compared to some of my trying-to-be-pythonic attempts):

Timeit: 0.0160551071167 (1000 cycles)

Playing around with it, the quickest I can get is:

def retrive(tokens):
    results = []
    group = []
    for i in xrange(len(tokens)):
        if tokens[i][0].isupper():
            group.append(tokens[i])
        else:
            results.append(group)
            group = []
    results.append(group)
    return filter(None, results)

Timeit 0.0116229057312

Are there any more concise, pythonic ways to go about this (with similar execution times)?

share|improve this question
    
What is your question exactly? –  Pedro Romano Nov 24 '12 at 18:47
    
Yea, I forgot the last line ;) Are there any more concise, pythonic ways to go about this (with similar execution times)? –  Timmy O'Mahony Nov 24 '12 at 18:53
    
Your optimized retrive() function doesn't seem to work as expected. I get: [['B'], ['H'], ['H'], ['O'], ['C'], ['U'], ['H'], ['L'], ['S']] when I run it verbatim. –  Austin Marshall Nov 25 '12 at 23:12
add comment

4 Answers

up vote 4 down vote accepted

A trivial optimisation that iterates on the tokens instead of by index (remember that in Python lists are iterables, it's unPythonic to iterate a list by index):

def retrieve(tokens):
    results = []
    group = []
    for token in tokens:
        if token[0].isupper():
            group.append(token)
        else:
            if group:  # group is not empty
                results.append(group)
            group = []  # reset group
    return results

A solution like @JeremyK's with a list comprehension and regular expressions is always going to be more compact. I am only giving this answer to point out how lists should be iterated.

share|improve this answer
    
Thanks - this is an improvement alright. I thought that using xrange would be faster as it doesn't return items, just index values, but thinking about it if you are using the values of what's being iterated it's faster –  Timmy O'Mahony Nov 24 '12 at 19:27
add comment

Here is a solution using regular expressions

import re

def reMethod(pat, s):
    return [m.group().split() for m in re.finditer(pat, s)]

if __name__=='__main__':
    from timeit import Timer
    s = "Born in Honolulu Hawaii Obama is a graduate of Columbia University and Harvard Law School"
    pat = re.compile(r"([A-Z][a-z]*)(\s[A-Z][a-z]*)*")
    t1 = Timer(lambda: reMethod(pat, s))
    print "time:", t1.timeit(number=1000)
    print "returns:", reMethod(pat, s)

Ouptut:

time: 0.0183469604187
returns: [['Born'], ['Honolulu', 'Hawaii', 'Obama'], ['Columbia', 'University'], ['Harvard', 'Law', 'School']]
share|improve this answer
    
I never thought about using regexs actually, this is a good alternative and the performance is around the same –  Timmy O'Mahony Nov 24 '12 at 19:31
    
Yeah, it didn't turn out to be quite as fast, but it felt a waste not to post it once I had it coded up. –  Jeremy K Nov 24 '12 at 19:55
add comment

If you asked me, a pythonic solution would be the most readable solution. However in general, readable solutions are not always going to be the fastest. You can't have both, these are conflicting goals.

Pedro has covered what changes you can do to make it bit more pythonic so I won't repeat that. I can't think of anything else you can do to optimize that any further. However if you want a more purely pythonic solution (IMO), you can do this.

Use itertools.groupby. It groups consecutive items together with a common key into groups. Group them by whether they are capitalized and filter out the non-capitalized words.

This could be done as a one-liner but for readability, I'd write it like this:

from itertools import groupby

input_str = 'Born in Honolulu Hawaii Obama is a graduate of ' +
            'Columbia University and Harvard Law School'
words = input_str.split()
def is_capitalized(word):
    return bool(word) and word[0].isupper()
query = groupby(words, key=is_capitalized)
result = [list(g) for k, g in query if k]

This would run roughly twice as slow as your implementation, based on my tests on 1000 iterations.

0.0130150737235 # my implementation
0.0052368790507 # your implementation

You decide what your goals are.

share|improve this answer
    
I think isCapitalized could be written more simply as word[:1].isupper(). (Although I think is_capitalized would be a more standard name.) –  DSM Nov 25 '12 at 3:57
    
Ah you're right about the name, I've been doing too much Java work lately. ;) –  Jeff Mercado Nov 25 '12 at 4:54
add comment

I get a slight improvement by tweaking your retrive() function:

def retrieve1(tokens):
    results = []
    group = []
    for i in xrange(len(tokens)):
        if tokens[i][0].isupper():
            group.append(tokens[i])
        else:
            results.append(group)
            group = []
    results.append(group)
    return filter(None, results)

def retrieve2(tokens):
    results = []
    group = []
    for token in tokens:
        if token[0].isupper():
            group.append(token)
        elif group:
            results.append(group)
            group = []
    if group:
        results.append(group)
    return results

s = "Born in Honolulu Hawaii Obama is a graduate of Columbia University and Harvard Law School"

if __name__ == "__main__":
    import timeit
    print timeit.timeit('retrieve1(s.split(" "))', setup="from __main__ import (retrieve1, s)", number=100000)
    print timeit.timeit('retrieve2(s.split(" "))', setup="from __main__ import (retrieve2, s)", number=100000)

Results:

1.00138902664 (retrieve1)
0.744722127914 (retrieve2)

It's not necessary to iterate via xrange() as you can iterate tokens directly, and you need only append group to results if group is not an empty list -- no need to filter().

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.