Générer des valeurs uniques basées sur des lignes dans un tableau numpy

Question

J'ai un tableau numpy 3D, arr, de forme m*n*k.

pour chaque ensemble de valeurs le long de l'axe m (par exemple arr[:, 0, 0]) Je veux générer une valeur unique pour représenter cet ensemble, de sorte que je peux retrouver avec une matrice 2D, n*k. Si un ensemble de valeurs le long de l'axe m est répété, alors nous devrions générer la même valeur à chaque fois.

C'est un problème de hachage.

J'ai créé une solution au problème en utilisant un dictionnaire, mais cela réduit considérablement les performances. Pour chaque ensemble de valeurs, j'appeler cette fonction:

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 

Le tableau lui-même est généralement de la taille 30 * 256 * 256, donc un ensemble de valeurs aura 30 valeurs. J'ai des centaines de ces tableaux à traiter en même temps. Actuellement, tout le traitement qui doit être effectué pour calculer le hachage prend 1,3 s pour un bloc de 100 baies. Y compris les bosses de hachage jusqu'à 75s.

Existe-t-il un moyen plus rapide de générer la valeur représentative unique?

Answer 1

S'il est à peu près hash essayer cette

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 

Cependant, l'utiliser avec prudence et de tester d'abord ce code avec votre code. Tout ce que je peux dire, c'est que cela fonctionne pour cet exemple simple.

En outre, il se peut que deux valeurs aient la même valeur de hachage, bien qu'elles soient différentes. Ceci est un problème qui peut toujours se produire en utilisant la fonction de hachage, mais ils sont très peu susceptibles

Modifier: Afin de comparer avec les autres solutions

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

Answer 2

Selon le nombre de nouvelles clés vs anciennes clés ont besoin Pour être généré, il est difficile de dire ce qui sera optimal. Mais en utilisant votre logique, ce qui suit devrait être assez rapide:

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:

I maintenant mis à jour pour boucler toutes les séries de données en fonction de votre question en utilisant des progrès:

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 

Ce qui précède fait 256x256 recherches/affectations de 30 tableaux d'éléments chacun. Il n'y a bien sûr aucune garantie que le hachage md5 ne soit pas en collision. Si cela devrait être un problème, vous pouvez bien sûr passer à d'autres hachages dans la même bibliothèque.

Edit 2:

Étant donné que vous semblez faire la majorité des opérations coûteuses sur le premier axe de votre tableau 3D, je vous suggère de réorganiser votre tableau:

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 

Ne pas avoir de sauter des distances longues autour de la mémoire ne environ une vitesse de 25%

Edit 3:

S'il n'y a pas besoin réel pour mettre en cache un hachage pour int consultation, mais que vous avez juste besoin hash réels et si le tableau 3D est de int8 -type, puis donné l'organisation A2 et A2_strided, le temps peut être réduit un peu plus . De ce 15ms est le tuple-looping.

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

Cela pourrait être une approche à l'aide numpy fonctions de base -

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

run échantillon -

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)