How can I optimise the ordinal encoding of a 2D array of strings in Python?

user_2739654 0
Viewed 725

I have a Pandas series that holds an array of strings per row:

0                                           []
1                                           []
2                                           []
3                                           []
4         [0007969760, 0007910220, 0007910309]
                          ...                 
243223                                      []
243224                            [0009403370]
243225                [0009403370, 0007190939]
243226                                      []
243227                                      []
Name: Item History, Length: 243228, dtype: object

My goal is to do some straightforward Ordinal Encoding here, but as efficiently (in terms of both time and memory) as possible, with the following caveats:

  1. Empty lists need to have an integer denoting "Empty list" inserted that is also unique. (for example if there are 100 unique strings, empty lists might be encoded as [101]).
  2. The encoding must be saved somehow such that I can identically encode other lists in the future
  3. Where those future lists contain a string that is not present in the initial input data, it must encode its own separate integer to denote "Never seen that before mate".

The obvious question is "Why are you not just using OrdinalEncoder from sklearn". Well, apart from not having an unknown item handler, it's also actually horrendously slow to apply rowwise in this fashion (we'd have to fit it on a combined single array of all the distinct strings, then use Series.apply(lambda x: oe.transform(x)) to transform each row), because it has to do some dict-comprehension to build the mapping table for each row and that takes time. Not very much time per call, only about 0.01 seconds, but that's still far too slow for the amount of data that I have.

One solution is to take that dict comprehension out of the each-row part, and build a mapping table before looping over the rows, as in this function:

def encode_labels(X, table, noHistory, unknownItem):

    res = np.empty(len(X), dtype=np.ndarray)

    for i in range(len(X)):
        if len(X[i]) == 0:
            res[i] = np.array([noHistory])
        else:
            res[i] = np.empty(len(X[i]), dtype=np.ndarray)
            for j in range(len(X[i])):
                try:
                    res[i][j] = table[X[i][j]]
                except KeyError:
                    res[i][j] = unknownItem

    return res

That's significantly better than row-wise .apply() but still not the fastest piece of code. I can cythonize it and do a bunch of other optimisations to get some more speedup, but it's not orders-of-magnitude better:

%%cython

cimport numpy as cnp
import numpy as np
from cpython cimport array
import array

cpdef list encode_labels_cy(cnp.ndarray X, dict table, int noHistory, int unknownItem, array.array rowLengths):

    cdef int[:] crc = rowLengths

    cdef list flattenedX = []    
    cdef Py_ssize_t i, j
    cdef list row = []

    for row in X:
        if len(row)==0:
            flattenedX.append('ZZ')
        else:
            flattenedX.extend(row)

    cdef Py_ssize_t lenX = len(flattenedX)

    cdef array.array res = array.array('i', [0]*lenX)
    cdef int[:] cres = res

    i=0
    while i < lenX:
        try:
            cres[i] = table[flattenedX[i]]
        except KeyError:
            cres[i] = unknownItem
        i += 1

    cdef list pyres = []
    cdef Py_ssize_t s = 0

    for k in crc:
        pyres.append(res[s:s+k])
        s+= k

    return pyres

# classes is a dict of {string:int} mappings. noHistory and unknownItem are ints encoding those values

%timeit encode_labels(X.values, classes, noHistory, unknownItem)
%timeit encode_labels_cy(X.values, classes, noHistory, unknownItem, array.array('i', [1 if x == 0 else x for x in [len(j) for j in X]]))

50.4 ms ± 2.76 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
11.2 ms ± 1.11 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)

(that's for a 5000 row sample, not the whole dataset).

UPDATE: I managed to get an implementation working in ctypes and that is faster than both the row-wise .apply() and my original native python, but it's still slower than Cython (which really ought not be the case in my mind!)

So; how can I make this faster? and ideally keep memory usage as low as possible at the same time? This need not be pure python. If you can make it zippy in Cython or ctypes or something, that's great. This code will form part of the preprocessing for a neural net so there's also some GPUs sitting around waiting for data at this point; if you can make this utilise those then all the better. Multiprocessing might also be an option that I haven't managed to explore yet, but the problem there is that it requires a copy of the string:int mapping table per process, which is a) slow to generate and b) uses lots of memory.

EDIT:

Forgot to provide some data. You can run the following to get an input dataset that's in similar format to mine:

import numpy as np
import pandas as pd

a = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

X = pd.Series([[a[np.random.randint(0, 26)] for i in range(np.random.randint(0, 10))] for j in range(5000)])

classes = dict(zip(a, np.arange(0, 26)))
unknownItem = 26
noHistory = 27

Only 5000 rows, but that should be enough to accurately determine which method is faster.

encoding numpy optimization c python
2 Answers

Here's one based on NumPy's searchsorted -

k,v = classes.keys(),classes.values()
k,v = np.array(list(k)),np.array(list(v))

cl = np.concatenate(s)

sidx = k.argsort()
idx = np.searchsorted(k,cl, sorter=sidx)
out_of_bounds_mask = idx==len(k)

idx[out_of_bounds_mask] = 0
ssidx = sidx[idx]
invalidmask = k[ssidx] != cl
out_of_bounds_mask |= invalidmask

vals = v[ssidx]
vals[out_of_bounds_mask] = unknownItem

lens = list(map(len,s))
E = [noHistory] # use np.array() if you need outputs for empty entries as arrays
out = []
start = 0
for l in lens:
    if l==0:
        out.append(E)
    else:
        out.append(vals[start:start+l])
        start += l

Another way is basically encode_labels from posted question but optimized with less accesses to inputs and avoiding the try-catch -

def encode_labels2(X, table, noHistory, unknownItem):
    L0 = len(X)
    res = [[noHistory]]*L0
    for i in range(L0):
        L = len(X[i])
        if L != 0:
            res_i = [unknownItem]*L
            for j in range(L):
                Xij = X[i][j]
                if Xij in table:
                    res_i[j] = table[Xij]
            res[i] = res_i
    return res

Then, we can introduce numba's jit compilation. So, the changes would be -

from numba import jit

@jit
def encode_labels2(X, table, noHistory, unknownItem):
# .. function stays the same

There would be few warnings, which it seems to be because we are working with lists and not arrays. Those could be ignored.

user_32938810

With the following Cython function I get a speed-up factor of about 5. It uses a temporary list for row-wise copies of relevant data which should be initialized big enough so that it can hold each row's data (i.e. if an upper bound for the maximum number of elements per row is known, use that one, otherwise use a heuristic value that keeps the number of necessary resizes to a minimum).

cpdef list encode_labels_cy_2(cnp.ndarray X, dict table, int noHistory, int unknownItem):

    cdef Py_ssize_t i, n
    cdef list result = []
    cdef list tmp = [noHistory] * 10  # initialize big enough so that it's likely to fit all elements of a row

    for row in X:
        n = len(row)
        while len(tmp) < n:  # if too small, resize
            tmp.append(noHistory)
        if n > 0:
            i = 0
            while i < n:
                tmp[i] = table.get(row[i], unknownItem)
                i += 1
        else:
            tmp[0] = noHistory
            i = 1
        result.append(tmp[:i])

    return result

If the number of elements per row varies strongly and no good estimate can be made up-start you can also resize the tmp list by over-allocating similar to CPython's list growth pattern.

user_37672390
Related