Using map() to get number of times list elements exist in a string in Python

Question

I'm trying to get the number of times each item in a list is in a string in Python:

paragraph = "I eat bananas and a banana"

def tester(x): return len(re.findall(x,paragraph))

map(tester, ['banana', 'loganberry', 'passion fruit'])

Returns [2, 0, 0]

What I'd like to do however is extend this so I can feed the paragraph value into the map() function. Right now, the tester() function has paragraph hardcoded. Does anybody have a way to do this (perhaps make an n-length list of paragraph values)? Any other ideas here?

Keep in mind that each of the array values will have a weight at some point in the future - hence the need to keep the values in a list rather than crunching them all together.

UPDATE: The paragraph will often be 20K and the list will often have 200+ members. My thinking is that map operates in parallel - so it will be much more efficient than any serial methods.

Answer 1

A closure would be a quick solution:

paragraph = "I eat bananas and a banana"

def tester(s): 
    def f(x):
        return len(re.findall(x,s))
    return f

print map(tester(paragraph), ['banana', 'loganberry', 'passion fruit'])

Answer 2

I know you didn't ask for list comprehension, but here it is anyway:

paragraph = "I eat bananas and a banana"
words = ['banana', 'loganberry', 'passion fruit']
[len(re.findall(word, paragraph)) for word in words]

This returns [2, 0, 0] as well.

Answer 3

targets = ['banana', 'loganberry', 'passion fruit']
paragraph = "I eat bananas and a banana"

print [paragraph.count(target) for target in targets]

No idea why you would use map() here.

Answer 4

Here's my version.

paragraph = "I eat bananas and a banana"

def tester(paragraph, x): return len(re.findall(x,paragraph))

print lambda paragraph: map(
    lambda x: tester(paragraph, x) , ['banana', 'loganberry', 'passion fruit']
        )(paragraph)

Answer 5

This is basically just going out of your way to avoid a list comprehension, but if you like functional style programming, then you'll like functools.partial.

>>> from functools import partial
>>> def counter(text, paragraph):
    return len(re.findall(text, paragraph))

>>> tester = partial(counter, paragraph="I eat bananas and a banana")
>>> map(tester, ['banana', 'loganberry', 'passion fruit'])
[2, 0, 0]

Answer 6

For Q query words of average length L bytes on large texts of size T bytes, you need something that's NOT O(QLT). You need a DFA-style approach which can give you O(T) ... after setup costs. If your query set is rather static, then the setup cost can be ignored.

E.g. http://en.wikipedia.org/wiki/Aho-Corasick_algorithm
which points to a C-extension for Python:
http://hkn.eecs.berkeley.edu/~dyoo/python/ahocorasick/

Answer 7

Here's a response to the movement of the goalposts ("I probably need the regex because I'll need word delimiters in the near future"):

This method parses the text once to obtain a list of all the "words". Each word is looked up in a dictionary of the target words, and if it is a target word it is counted. The time taken is O(P) + O(T) where P is the size of the paragraph and T is the number of target words. All other solutions to date (including the currently accepted solution) except my Aho-Corasick solution are O(PT).

def counts_all(targets, paragraph, word_regex=r"\w+"):
    tally = dict((target, 0) for target in targets)
    for word in re.findall(word_regex, paragraph):
        if word in tally:
            tally[word] += 1
    return [tally[target] for target in targets]

def counts_iter(targets, paragraph, word_regex=r"\w+"):
    tally = dict((target, 0) for target in targets)
    for matchobj in re.finditer(word_regex, paragraph):
        word = matchobj.group()
        if word in tally:
            tally[word] += 1
    return [tally[target] for target in targets]

The finditer version is a strawman -- it's much slower than the findall version.

Here's the currently accepted solution expressed in a standardised form and augmented with word delimiters:

def currently_accepted_solution_augmented(targets, paragraph):
    def tester(s): 
        def f(x):
            return len(re.findall(r"\b" + x + r"\b", s))
        return f
    return map(tester(paragraph), targets)

which goes overboard on closures and could be reduced to:

# acknowledgement:
# this is structurally the same as one of hughdbrown's benchmark functions
def currently_accepted_solution_augmented_without_extra_closure(targets, paragraph):
    def tester(x):
        return len(re.findall(r"\b" + x + r"\b", paragraph))
    return map(tester, targets)

All variations on the currently accepted solution are O(PT). Unlike the currently accepted solution, the regex search with word delimiters is not equivalent to a simple paragraph.find(target). Because the re engine doesn't use the "fast search" in this case, adding the word delimiters changes it fron slow to very slow.