Создать уникальные значения на основе строк в массиве numpy

Question

У меня есть массив 3D numpy, arr, с формой m*n*k.

для каждого набора значений вдоль оси m (например, arr[:, 0, 0]) Я хочу, чтобы генерировать одно значение для представления этого набора, так что я может в конечном итоге с матрицей 2D, n*k. Если повторяется набор значений вдоль оси m, мы должны генерировать одно и то же значение каждый раз.

I.e Это проблема хэширования.

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

def getCellId(self, valueSet): 

    # Turn the set of values (a numpy vector) to a tuple so it can be hashed 
    key = tuple(valueSet) 

    # Try and simply return an existing ID for this key 
    try: 
     return self.attributeDict[key] 
    except KeyError: 

     # If the key was new (and didnt exist), try and generate a new Id by adding one to the max of all current Id's. This will fail the very first time we do this (as there will be no Id's yet), so in that case, just assign the value '1' to the newId 
     try: 
     newId = max(self.attributeDict.values()) +1 
     except ValueError: 
     newId = 1 
     self.attributeDict[key] = newId 
     return newId 

Сам массив, как правило, от размера 30 * 256 * 256, так что один набор значений будет иметь 30 значений. У меня есть сотни таких массивов для обработки в любой момент времени. В настоящее время выполнение всей обработки, которая должна быть выполнена до вычисления хэша , занимает 1,3 секунды для блока из 100 массивов. Включая хеширование, которое до 75 секунд.

Есть ли более быстрый способ генерации единственного репрезентативного значения?

Answer 1

Если речь идет просто о хеширования попробовать этот

import numpy as np 
import numpy.random 

# create random data 
a = numpy.random.randint(10,size=(5,3,3)) 

# create some identical 0-axis data 
a[:,0,0] = np.arange(5) 
a[:,0,1] = np.arange(5) 

# create matrix with the hash values 
h = np.apply_along_axis(lambda x: hash(tuple(x)),0,a) 

h[0,0]==h[0,1] 
# Output: True 

Однако использовать его с осторожностью и тест первого этот код с кодом. ... все, что я могу сказать, это то, что он работает на этом простом примере.

Кроме того, возможно, что два значения могут иметь одно и то же значение хэша, хотя они разные. Это вопрос, который всегда может произойти с использованием хэш-функции, но они вряд

Edit: Для того, чтобы сравнить с другими решениями

timeit(np.apply_along_axis(lambda x: hash(tuple(x)),0,a)) 
# output: 1 loops, best of 3: 677 ms per loop 

Answer 2

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

import collections 
import hashlib 

_key = 0 

def _get_new_key(): 
    global _key 
    _key += 1 
    return _key 

attributes = collections.defaultdict(_get_new_key) 

def get_cell_id(series):        
    global attributes 
    return attributes[hashlib.md5(series.tostring()).digest()] 

Edit:

теперь обновлены для зацикливания всех серий данных в соответствии с вашим вопросом с помощью махов:

In [99]: import numpy as np 

In [100]: A = np.random.random((30, 256, 256)) 

In [101]: A_strided = np.lib.stride_tricks.as_strided(A, (A.shape[1] * A.shape[2], A.shape[0]), (A.itemsize, A.itemsize * A.shape[1] * A.shape[2])) 

In [102]: %timeit tuple(get_cell_id(S) for S in A_strided) 
10 loops, best of 3: 169 ms per loop 

Вышеописанное 256x256 запросов/присвоений из 30 массивов элементов каждый. Конечно, нет никакой гарантии, что хеш md5 не столкнется. Если это должно быть проблемой, вы можете, конечно, перейти на другие хэши в том же lib.

Edit 2:

Учитывая, что вы, кажется, делают большинство дорогостоящих операций на первой оси 3D-массив, я хотел бы предложить вам реорганизовать массив:

In [254]: A2 = np.random.random((256, 256, 30)) 

In [255]: A2_strided = np.lib.stride_tricks.as_strided(A2, (A2.shape[0] * A2.shape[1], A2.shape[2]), (A2.itemsize * A2.shape[2], A2.itemsize)) 

In [256]: %timeit tuple(get_cell_id(S) for S in A2_strided) 
10 loops, best of 3: 126 ms per loop 

не имеющий прыгать на большие расстояния в памяти делает примерно на 25% к скорости до

Edit 3:

Если нет необходимости кэшировать хэш до int, посмотрите, что вам нужны только фактические хэши, и если 3D-массив имеет размер int8, то задаютсяи A2_strided, время может быть сокращено еще , Из этих 15 мс происходит чередование.

In [9]: from hashlib import md5 

In [10]: %timeit tuple(md5(series.tostring()).digest() for series in A2_strided) 
10 loops, best of 3: 72.2 ms per loop 

Answer 3

Это может быть один подход с использованием базовых функций - numpy

import numpy as np 

# Random input for demo 
arr = np.random.randint(0,3,[2,5,4]) 

# Get dimensions for later usage 
m,n,k = arr.shape 

# Reshape arr to a 2D array that has each slice arr[:, n, k] in each row 
arr2d = np.transpose(arr,(1,2,0)).reshape([-1,m]) 

# Perform lexsort & get corresponding indices and sorted array 
sorted_idx = np.lexsort(arr2d.T) 
sorted_arr2d = arr2d[sorted_idx,:] 

# Differentiation along rows for sorted array 
df1 = np.diff(sorted_arr2d,axis=0) 

# Look for changes along df1 that represent new labels to be put there 
df2 = np.append([False],np.any(df1!=0,1),0) 

# Get unique labels 
labels = df2.cumsum(0) 

# Store those unique labels in a n x k shaped 2D array 
pos_labels = np.zeros_like(labels) 
pos_labels[sorted_idx] = labels 
out = pos_labels.reshape([n,k]) 

Sample прогонов -

In [216]: arr 
Out[216]: 
array([[[2, 1, 2, 1], 
     [1, 0, 2, 1], 
     [2, 0, 1, 1], 
     [0, 0, 1, 1], 
     [1, 0, 0, 2]], 

     [[2, 1, 2, 2], 
     [0, 0, 2, 1], 
     [2, 1, 0, 0], 
     [1, 0, 1, 0], 
     [0, 1, 1, 0]]]) 

In [217]: out 
Out[217]: 
array([[6, 4, 6, 5], 
     [1, 0, 6, 4], 
     [6, 3, 1, 1], 
     [3, 0, 4, 1], 
     [1, 3, 3, 2]], dtype=int32)