9
\$\begingroup\$

From the question and since I'm currently learning functional programming I was inspired to write the following (curried) function:

def map_starts_with(pat_map):
    def map_string(t):
        pats = [pat for pat in pat_map.keys() if t.startswith(pat)]
        return pat_map.get(pats[0]) if len(pats) > 0 else 0 
    # get only value of "first" pattern if at least one pattern is found
    return map_string

Summary of what the code does:

For a given mapping of patterns to ints, it maps a string to (positive) ints if it starts with one of the patterns and it maps to 0 if no pattern is found (in fact one could and should pass startswith also as a function parameter).

So currently, if you have a DataFrame, you would use the apply method:

df = pd.DataFrame({'col':[ 'xx', 'aaaaaa', 'c']})
      col
0      xx
1  aaaaaa
2       c

mapping = { 'aaa':4 ,'c':3}
df.col.apply(lambda x: map_starts_with(mapping)(x))

0    0
1    4
2    3

However, when acting in the Pandas/NumPy world, this approach will typically be too slow. Are there any suggestions on how to speed up this function using NumPy or Pandas vectorization capabilities?

\$\endgroup\$
  • 1
    \$\begingroup\$ Not an answer to the performance, but you don't need to wrap the result of map_starts_with(mapping) in a lambda, it is already applyable \$\endgroup\$ – Caleth Feb 15 '17 at 14:21
5
\$\begingroup\$

I'm not completely sure about the specifics of optimizing from the numpy or pandas side (here are some things documented), but, we can optimize the function itself:

  • you are calling .keys() making an extra list of keys in memory (in Python 2; in Python 3 though keys() returns a "view")
  • you can use an iterative approach switching to iteritems() (or items() in Python 3) and using next() built-in function allowing you to take an early exit once you encounter a key that t starts with

Changes applied:

def map_starts_with(pat_map):
    def map_string(t):
        return next((value for key, value in pat_map.items() if t.startswith(key)), 0)
    return map_string

You can also refactor it to use functools.partial instead of nested functions:

from functools import partial

import pandas as pd


def map_starts_with(pat_map, t):
    return next((value for key, value in pat_map.items() if t.startswith(key)), 0)

mapping = {'aaa': 4 ,'c': 3}

df = pd.DataFrame({'col':[ 'xx', 'aaaaaa', 'c']})
print(df.col.apply(partial(map_starts_with, mapping)))
\$\endgroup\$
3
\$\begingroup\$

Looks like your function works with a dictionary mapping and any string. The string could come from a pandas apply. Here I use a list comprehension to apply it to a list of strings:

In [2]: mapping = { 'aaa':4 ,'c':3}
In [3]: alist = ['xx','aaaaaa','c']
In [4]: [map_starts_with(mapping)(i) for i in alist]
Out[4]: [0, 4, 3]

'Vectorization' is an ambiguous term when dealing with numpy arrays.

There is a vectorize function that makes iteration over an array (or list) easy (but not faster):

In [5]: f = np.vectorize(map_starts_with(mapping), otypes=[int])
In [6]: f(alist)
Out[6]: array([0, 4, 3])

True 'vectorization' requires rewriting the function so that it takes a numpy array, and acts on all of the elements at once (or at least does the iteration in compiled code). In your case that requires testing all 3 strings at once. For numbers there are actions like addition and summing that are fast compiled. But there are few string operations that are truly vectorized. np.char.... defines a lot of functions that apply various string methods to elements of any array. They can be handy, but are still basically iterative.

Using char, I can test all elements of the list or array for startswith, and from the resulting boolean arrays, I can imagine building your [0,4,3] array from these arrays, but haven't worked out the logic.

In [7]: np.char.startswith(alist, 'aaa')
Out[7]: array([False,  True, False], dtype=bool)
In [8]: np.char.startswith(alist, 'c')
Out[8]: array([False, False,  True], dtype=bool)

Preliminary time testing to see if the np.char.startswith is a time saver:

In [9]: def foo(pat_map, arr):
   ...:     return [np.char.startswith(arr, pat) for pat in pat_map.keys()]
   ...: 
In [10]: foo(mapping,alist)
Out[10]: 
[array([False,  True, False], dtype=bool),
 array([False, False,  True], dtype=bool)]
In [11]: timeit foo(mapping,alist)
10000 loops, best of 3: 29.2 µs per loop
In [12]: timeit f(alist)
10000 loops, best of 3: 26.9 µs per loop

Off hand it doesn't appear to help.


Another way to test startswith is to truncate the string array entries and do an == test:

In [13]: arr=np.array(alist)
In [14]: arr
Out[14]: 
array(['xx', 'aaaaaa', 'c'], 
      dtype='<U6')
In [16]: arr.astype('U3')    # clip to 3 char
Out[16]: 
array(['xx', 'aaa', 'c'], 
      dtype='<U3')
In [17]: arr.astype('U3')=='aaa'
Out[17]: array([False,  True, False], dtype=bool)

In [18]: arr.astype('U1')=='c'
Out[18]: array([False, False,  True], dtype=bool)

Same arrays that I got before

In [21]: def bar(pat_map, arr):
    ...:     return [arr.astype('U%s'%len(pat))==pat for pat in pat_map.keys()]
    ...: 
In [22]: bar(mapping, arr)
Out[22]: 
[array([False,  True, False], dtype=bool),
 array([False, False,  True], dtype=bool)]
In [23]: timeit bar(mapping, arr)
The slowest run took 4.05 times longer... cached.
100000 loops, best of 3: 13.5 µs per loop

This shows some promise.


If the pat were all the same length, I could apply this == test to all elements at once:

In [25]: arr.astype('U1')==np.array(['x','a','c'])[:,None]
Out[25]: 
array([[ True, False, False],
       [False,  True, False],
       [False, False,  True]], dtype=bool)

That kind of action is the ideal array vectorization.


Notice that my attempts to vectorize work in a different direction than your curry. You create a function that applies the whole mapping to an individual string, and then iterate over the strings. I instead found functions that applied a single pattern string to all elements of an array or list, and then iterates over the mapping dictionary.


Here's a function that uses on my array startswith expressions, and tries to recreate your mapping logic. It would be nice to evaluate this from a 2d boolean array (size mappings by size arr), but that gets too complicated with your logic.

def map_starts_with1(arr, pat_map):
    b = np.zeros_like(arr, int)
    for pat in pat_map:
        c=arr.astype('U%s'%len(pat))==pat
        b = np.where(c, mapping[pat], b)
    return b

In [102]: map_starts_with1(arr, mapping)
Out[102]: array([0, 4, 3])

With this small test case, it times the same as f(arr) above (the np.vectorized version of your mapping. But I suspect that if the array arr is much larger than mapping dictionary, its performance will improve. In general if you must iterate, it is best to do so on the smallest dimension.

The last 'pat' that matches will overwrite any others, whereas you claimed to use the first match. To achieve that I could iterate on pat_map in the reverse order. But since the keys of a dictionary are (technically) unordered, it doesn't matter, does it?

\$\endgroup\$
  • \$\begingroup\$ thanks for the exhaustive answer. I expected something like your last function and was looking for an implementation that acts on a array of strings. Of course it's the natural way to iterate over the keys of the mapping (we expect fewer patterns than strings). Btw. is there a small typo on the 5th line? mapping should be pat_map. Shouldn't it be possible to get same sized patterns by appending wildcard regexes (but probably the equality match will fail there)? Thanks also for emphasiszing, that string operations are generally slower than operations on numbers. \$\endgroup\$ – Quickbeam2k1 Feb 16 '17 at 6:47
  • \$\begingroup\$ What do you mean with my logic? I'm open to different approaches, or if you have a suggestion for a better logic, just communicate it. \$\endgroup\$ – Quickbeam2k1 Feb 16 '17 at 6:54
  • 1
    \$\begingroup\$ I really like the final algorithm, but it could use some better variable naming to be easier to understand. And also some whitespace around the operators :) \$\endgroup\$ – Graipher Feb 16 '17 at 7:47
  • \$\begingroup\$ Sorry, I'm used to writing the quick-n-dirty SO solutions, not the refined CR ones. :) \$\endgroup\$ – hpaulj Feb 16 '17 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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