réseau de diffusion 1D contre tableau 2D pour lexsort: Permutation pour trier chaque colonne indépendamment lorsque l'on considère encore un autre vecteur

Question

Considérons la matrice a

np.random.seed([3,1415]) 
a = np.random.randint(10, size=(5, 4)) 
a 

array([[0, 2, 7, 3], 
     [8, 7, 0, 6], 
     [8, 6, 0, 2], 
     [0, 4, 9, 7], 
     [3, 2, 4, 3]]) 

je peux créer b qui contient la permutation pour trier chaque colonne.

b = a.argsort(0) 
b 

array([[0, 0, 1, 2], 
     [3, 4, 2, 0], 
     [4, 3, 4, 4], 
     [1, 2, 0, 1], 
     [2, 1, 3, 3]]) 

Je peux trier a avec b

a[b, np.arange(a.shape[1])[None, :]] 

array([[0, 2, 0, 2], 
     [0, 2, 0, 3], 
     [3, 4, 4, 3], 
     [8, 6, 7, 6], 
     [8, 7, 9, 7]]) 

---

Ce fut l'amorce pour illustrer la sortie que je cherche. Je veux un tableau b qui a la permutation requise pour trier la colonne correspondante dans a en considérant également un lexsort avec un autre tableau.

np.random.seed([3,1415]) 
a = np.random.randint(10, size=(10, 4)) 
g = np.random.choice(list('abc'), 10) 

a 

array([[0, 2, 7, 3], 
     [8, 7, 0, 6], 
     [8, 6, 0, 2], 
     [0, 4, 9, 7], 
     [3, 2, 4, 3], 
     [3, 6, 7, 7], 
     [4, 5, 3, 7], 
     [5, 9, 8, 7], 
     [6, 4, 7, 6], 
     [2, 6, 6, 5]]) 

g 

array(['c', 'a', 'c', 'b', 'a', 'a', 'a', 'b', 'c', 'b'], 
     dtype='<U1') 

Je veux produire un réseau b où chaque colonne est la permutation requise pour lexsort la colonne correspondante a. Et le lexsort est de trier la colonne d'abord par les groupes définis par g puis par les valeurs dans chaque colonne dans a.

Je peux générer les résultats avec:

r = np.column_stack([np.lexsort([a[:, i], g]) for i in range(a.shape[1])]) 
r 

array([[4, 4, 1, 4], 
     [5, 6, 6, 1], 
     [6, 5, 4, 5], 
     [1, 1, 5, 6], 
     [3, 3, 9, 9], 
     [9, 9, 7, 3], 
     [7, 7, 3, 7], 
     [0, 0, 2, 2], 
     [8, 8, 0, 0], 
     [2, 2, 8, 8]]) 

Nous pouvons voir que cela fonctionne

g[r] 

array([['a', 'a', 'a', 'a'], 
     ['a', 'a', 'a', 'a'], 
     ['a', 'a', 'a', 'a'], 
     ['a', 'a', 'a', 'a'], 
     ['b', 'b', 'b', 'b'], 
     ['b', 'b', 'b', 'b'], 
     ['b', 'b', 'b', 'b'], 
     ['c', 'c', 'c', 'c'], 
     ['c', 'c', 'c', 'c'], 
     ['c', 'c', 'c', 'c']], 
     dtype='<U1') 

et

a[r, np.arange(a.shape[1])[None, :]] 

array([[3, 2, 0, 3], 
     [3, 5, 3, 6], 
     [4, 6, 4, 7], 
     [8, 7, 7, 7], 
     [0, 4, 6, 5], 
     [2, 6, 8, 7], 
     [5, 9, 9, 7], 
     [0, 2, 0, 2], 
     [6, 4, 7, 3], 
     [8, 6, 7, 6]]) 

---

Question

Existe-t-il un moyen de "diffuser" l'utilisation du tableau de regroupement g pour une utilisation dans toutes les colonnes lexsort? Quel est un moyen plus efficace de le faire?

Answer 1

est ici une approche -

def app1(a, g): 
    m,n = a.shape 

    g_idx = np.unique(g, return_inverse=1)[1] 
    N = g_idx.max()+1 

    g_idx2D = g_idx[:,None] + N*np.arange(n) 
    r_out = np.lexsort([a.ravel('F'), g_idx2D.ravel('F')]).reshape(-1,m).T 
    r_out -= m*np.arange(n) 
    return r_out 

L'idée est simplement que nous créons une grille 2D de la version entière de la matrice g de chaînes et compensons chaque colonne par une barrière qui limiterait la recherche lexsort dans chaque colonne .

Maintenant, sur la performance, il semble que pour les grands ensembles de données, lexsort lui-même serait le goulot d'étranglement. Pour notre problème, nous traitons seulement deux colonnes. Ainsi, nous pouvons créer notre propre lexsort personnalisé qui met à l'échelle la deuxième colonne en fonction d'un décalage, qui est la limite maximale de nombre de la première colonne.La mise en œuvre pour la même ressemblerait à quelque chose comme ça -

def lexsort_twocols(A, B): 
    S = A.max() - A.min() + 1 
    return (B*S + A).argsort() 

Ainsi, en intégrant cela dans notre méthode proposée et d'optimiser la création de g_idx2D, nous aurions une fonction officielle comme si -

def proposed_app(a, g): 
    m,n = a.shape 

    g_idx = np.unique(g, return_inverse=1)[1] 
    N = g_idx.max()+1 

    g_idx2D = (g_idx + N*np.arange(n)[:,None]).ravel() 
    r_out = lexsort_twocols(a.ravel('F'), g_idx2D).reshape(-1,m).T  
    r_out -= m*np.arange(n) 
    return r_out 

test d'exécution

approche originale:

def org_app(a, g): 
    return np.column_stack([np.lexsort([a[:, i], g]) for i in range(a.shape[1])]) 

synchronisations -

In [763]: a = np.random.randint(10, size=(20, 10000)) 
    ...: g = np.random.choice(list('abcdefgh'), 20) 
    ...: 

In [764]: %timeit org_app(a,g) 
10 loops, best of 3: 27.7 ms per loop 

In [765]: %timeit app1(a,g) 
10 loops, best of 3: 25.4 ms per loop 

In [766]: %timeit proposed_app(a,g) 
100 loops, best of 3: 5.93 ms per loop 

Answer 2

je signale que ce d'avoir un bon endroit pour montrer mon travail dérivé, basé sur la réponse de Divakar. Sa fonction lexsort_twocols fait tout ce dont nous avons besoin et peut tout aussi bien être appliquée pour diffuser une seule dimension sur plusieurs autres. Nous pouvons renoncer au travail supplémentaire en proposed_app parce que nous pouvons utiliser axis=0 dans le argsort dans la fonction lexsort_twocols.

def lexsort2(a, g): 
    n, m = a.shape 
    f = np.unique(g, return_inverse=1)[1] * (a.max() - a.min() + 1) 
    return (f[:, None] + a).argsort(0) 

lexsort2(a, g) 

array([[5, 5, 1, 1], 
     [1, 1, 5, 5], 
     [9, 9, 9, 9], 
     [0, 0, 2, 2], 
     [2, 2, 0, 0], 
     [4, 4, 6, 4], 
     [6, 6, 4, 6], 
     [3, 3, 7, 3], 
     [7, 7, 3, 7], 
     [8, 8, 8, 8]]) 

---

J'ai aussi pensé à cela ... mais pas presque aussi bien parce que je suis toujours compter sur np.lexsort qui, comme Divakar a souligné, peut être lent.

def lexsort3(a, g): 
    n, m = a.shape 
    a_ = a.ravel() 
    g_ = np.repeat(g, m) 
    c_ = np.tile(np.arange(m), n) 
    return np.lexsort([c_, a_, g_]).reshape(n, m) // m 

lexsort3(a, g) 

array([[5, 5, 1, 1], 
     [1, 1, 5, 5], 
     [9, 9, 9, 9], 
     [0, 0, 2, 2], 
     [2, 2, 0, 0], 
     [4, 4, 6, 4], 
     [6, 6, 4, 6], 
     [3, 3, 7, 3], 
     [7, 7, 3, 7], 
     [8, 8, 8, 8]]) 

---

En supposant que mon premier concept est lexsort1

def lexsort1(a, g): 
    return np.column_stack(
     [np.lexsort([a[:, i], g]) for i in range(a.shape[1])] 
    ) 

---

from timeit import timeit 
import pandas as pd 

results = pd.DataFrame(
    index=[100, 300, 1000, 3000, 10000, 30000, 100000, 300000, 1000000], 
    columns=['lexsort1', 'lexsort2', 'lexsort3'] 
) 

for i in results.index: 
    a = np.random.randint(100, size=(i, 4)) 
    g = np.random.choice(list('abcdefghijklmn'), i) 
    for f in results.columns: 
     results.set_value(
      i, f, 
      timeit('{}(a, g)'.format(f), 'from __main__ import a, g, {}'.format(f)) 
     ) 

results.plot() 

Merci encore @Divakar. S'il vous plaît upvote sa réponse !!!