Как я могу оптимизировать порядковое кодирование двумерного массива строк в Python?

Question

У меня есть серия Pandas, в которой содержится массив строк на строку:

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

Моя цель - сделать несколько простых порядковых кодировок здесь, но так же эффективно (с точки зрения времени и памяти). ) насколько возможно, со следующими предостережениями:

1. В пустых списках должно быть целое число, обозначающее «Пустой список», который также является уникальным. (например, если имеется 100 уникальных строк, пустые списки могут быть закодированы как [101]).
2. Кодировка должна быть каким-то образом сохранена, чтобы в будущем я мог идентично кодировать другие списки
3. Если эти будущие списки содержат строку, которой нет в исходных входных данных, она должна закодировать свое собственное отдельное целое число, чтобы обозначить «Никогда не видел это до сопряжения».

Очевидный вопрос: «Почему Вы не просто используете OrdinalEncoder из sklearn ". Что ж, кроме отсутствия обработчика неизвестных элементов, на самом деле также ужасно медленно применять его по строкам таким образом (нам нужно было бы разместить его в объединенном одном массиве всех отдельных строк, а затем использовать Series.apply(lambda x: oe.transform(x)) для преобразования каждой строки ), потому что для построения таблицы сопоставления для каждой строки требуется определенное диктовочное понимание, а для этого требуется время. Не очень много времени на вызов , всего около 0,01 секунды, но это все еще слишком медленно для объема данных, которые у меня есть.

Одно из решений - вывести это изощренное понимание из часть каждой строки и создайте таблицу сопоставления перед циклом по строкам, как в этой функции:

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

Это значительно лучше, чем по строкам .apply(), но все же не самый быстрый фрагмент кода. Я могу цитонизировать его и выполнить ряд других оптимизаций, чтобы ускорить процесс, но это не на порядок лучше:

%%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)

(это для выборки из 5000 строк, а не для целой набор данных).

ОБНОВЛЕНИЕ: Мне удалось заставить реализацию работать в ctypes, и что на быстрее, чем для строки .apply () и моего исходного натива python, но он все еще медленнее, чем Cython (что, на мой взгляд, не должно иметь место!)

Итак; как я могу сделать это быстрее? и в идеале держать потребление памяти как можно ниже в то же время? Это не обязательно должно быть чисто python. Если вы можете сделать это быстрым в Cython или ctypes или что-то, это здорово. Этот код станет частью предварительной обработки для нейронного net, поэтому в этот момент также есть несколько графических процессоров, которые ждут данных; если вы можете сделать это, используйте их, тем лучше. Многопроцессорная обработка также может быть вариантом, который мне пока не удалось изучить, но проблема в том, что для этого требуется копия строки: таблица отображения int на процесс, а) медленная генерация и б) использование большого количества памяти. ,

РЕДАКТИРОВАТЬ :

Забыл предоставить некоторые данные. Вы можете запустить следующее, чтобы получить входной набор данных, который похож на мой формат:

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

Всего 5000 строк, но этого должно быть достаточно, чтобы точно определить, какой метод быстрее.

Answer 1

С помощью следующей функции Cython я получаю коэффициент ускорения около 5. Он использует временный список для построчных копий соответствующих данных, который должен быть инициализирован достаточно большим, чтобы он мог хранить данные каждой строки (т. Е. Если известна верхняя граница для максимального количества элементов в строке, используйте этот, в противном случае используйте значение heuristi c, которое сводит количество необходимых размеров к минимуму).

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

Если число количество элементов в ряду сильно различается, и при первоначальной оценке невозможно составить точную оценку, вы также можете изменить размер списка tmp, перераспределив аналогично шаблону роста списка CPython .

Answer 2

Вот один из них, основанный на 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

Другой способ - это, в основном, encode_labels из опубликованного вопроса, но оптимизированный с меньшим доступом к входам и избежанием попытки поймать -

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

Затем мы можем представить jit-компиляцию numba. Таким образом, изменения будут -

from numba import jit

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

Предупреждений будет немного, что, по-видимому, связано с тем, что мы работаем со списками, а не с массивами. Это можно игнорировать.