Numpy: dapatkan indeks elemen-elemen dari array 1d sebagai array 2d

Saya memiliki array numpy seperti ini: [1 2 2 0 0 1 3 5]

Apakah mungkin untuk mendapatkan indeks elemen sebagai array 2d? Misalnya jawaban untuk input di atas adalah[[3 4], [0 5], [1 2], [6], [], [7]]

Saat ini saya harus mengulang nilai-nilai yang berbeda dan memanggil numpy.where(input == i)untuk setiap nilai, yang memiliki kinerja mengerikan dengan input yang cukup besar.

Berikut ini adalah pendekatan O (maks (x) + len (x)) menggunakan scipy.sparse:

import numpy as np
from scipy import sparse

x = np.array("1 2 2 0 0 1 3 5".split(),int)
x
# array([1, 2, 2, 0, 0, 1, 3, 5])


M,N = x.max()+1,x.size
sparse.csc_matrix((x,x,np.arange(N+1)),(M,N)).tolil().rows.tolist()
# [[3, 4], [0, 5], [1, 2], [6], [], [7]]

Ini bekerja dengan membuat matriks jarang dengan entri pada posisi (x [0], 0), (x [1], 1), ... Menggunakan format CSC(kolom jarang dikompresi) ini agak sederhana. Matriks tersebut kemudian dikonversi ke LILformat (daftar tertaut). Format ini menyimpan indeks kolom untuk setiap baris sebagai daftar di rowsatributnya, jadi yang perlu kita lakukan adalah mengambilnya dan mengubahnya menjadi daftar.

Perhatikan bahwa untuk argsortsolusi berbasis array kecil mungkin lebih cepat tetapi pada beberapa ukuran tidak gila besar ini akan menyeberang.

EDIT:

argsort-berbasis numpy-hanya solusi:

np.split(x.argsort(kind="stable"),np.bincount(x)[:-1].cumsum())
# [array([3, 4]), array([0, 5]), array([1, 2]), array([6]), array([], dtype=int64), array([7])]

Jika urutan indeks dalam grup tidak masalah Anda juga dapat mencoba argpartition(kebetulan tidak ada bedanya dalam contoh kecil ini tetapi ini tidak dijamin secara umum):

bb = np.bincount(x)[:-1].cumsum()
np.split(x.argpartition(bb),bb)
# [array([3, 4]), array([0, 5]), array([1, 2]), array([6]), array([], dtype=int64), array([7])]

EDIT:

@Ivakar merekomendasikan untuk tidak menggunakan np.split. Alih-alih, satu loop mungkin lebih cepat:

A = x.argsort(kind="stable")
B = np.bincount(x+1).cumsum()
[A[B[i-1]:B[i]] for i in range(1,len(B))]

Atau Anda bisa menggunakan operator walrus baru (Python3.8 +):

A = x.argsort(kind="stable")
B = np.bincount(x)
L = 0
[A[L:(L:=L+b)] for b in B.tolist()]

EDIT (Diedit):

(Tidak murni numpy): Sebagai alternatif untuk numba (lihat posting @ senderle) kita juga bisa menggunakan pythran.

Kompilasi dengan pythran -O3 <filename.py>

import numpy as np

#pythran export sort_to_bins(int[:],int)

def sort_to_bins(idx, mx):
    if mx==-1: 
        mx = idx.max() + 1
    cnts = np.zeros(mx + 2, int)
    for i in range(idx.size):
        cnts[idx[i] + 2] += 1
    for i in range(3, cnts.size):
        cnts[i] += cnts[i-1]
    res = np.empty_like(idx)
    for i in range(idx.size):
        res[cnts[idx[i]+1]] = i
        cnts[idx[i]+1] += 1
    return [res[cnts[i]:cnts[i+1]] for i in range(mx)]

Di sini numbadimenangkan oleh penampilan kumis:

repeat(lambda:enum_bins_numba_buffer(x),number=10)
# [0.6235917090671137, 0.6071486569708213, 0.6096088469494134]
repeat(lambda:sort_to_bins(x,-1),number=10)
# [0.6235359431011602, 0.6264424560358748, 0.6217901279451326]

Hal-hal yang lebih tua:

import numpy as np

#pythran export bincollect(int[:])

def bincollect(a):
    o = [[] for _ in range(a.max()+1)]
    for i,j in enumerate(a):
        o[j].append(i)
    return o

Pengaturan waktu vs. numba (lama)

timeit(lambda:bincollect(x),number=10)
# 3.5732191529823467
timeit(lambda:enumerate_bins(x),number=10)
# 6.7462647299980745

Salah satu opsi potensial tergantung pada ukuran data Anda adalah hanya keluar numpydan menggunakan collections.defaultdict:

In [248]: from collections import defaultdict

In [249]: d = defaultdict(list)

In [250]: l = np.random.randint(0, 100, 100000)

In [251]: %%timeit
     ...: for k, v in enumerate(l):
     ...:     d[v].append(k)
     ...:
10 loops, best of 3: 22.8 ms per loop

Kemudian Anda berakhir dengan kamus {value1: [index1, index2, ...], value2: [index3, index4, ...]}. Penskalaan waktu cukup dekat dengan linier dengan ukuran array, jadi 10.000.000 membutuhkan ~ 2.7 pada mesin saya, yang tampaknya cukup masuk akal.

Meskipun permintaan adalah numpysolusi, saya memutuskan untuk melihat apakah ada numbasolusi berbasis- menarik . Dan memang ada! Berikut adalah pendekatan yang mewakili daftar dipartisi sebagai array kasar yang disimpan dalam satu buffer yang dialokasikan sebelumnya. Ini mengambil beberapa inspirasi dari argsortpendekatan yang diusulkan oleh Paul Panzer . (Untuk versi yang lebih lama yang tidak melakukannya juga, tetapi lebih sederhana, lihat di bawah.)

@numba.jit(numba.void(numba.int64[:], 
                      numba.int64[:], 
                      numba.int64[:]), 
           nopython=True)
def enum_bins_numba_buffer_inner(ints, bins, starts):
    for x in range(len(ints)):
        i = ints[x]
        bins[starts[i]] = x
        starts[i] += 1

@numba.jit(nopython=False)  # Not 100% sure this does anything...
def enum_bins_numba_buffer(ints):
    ends = np.bincount(ints).cumsum()
    starts = np.empty(ends.shape, dtype=np.int64)
    starts[1:] = ends[:-1]
    starts[0] = 0

    bins = np.empty(ints.shape, dtype=np.int64)
    enum_bins_numba_buffer_inner(ints, bins, starts)

    starts[1:] = ends[:-1]
    starts[0] = 0
    return [bins[s:e] for s, e in zip(starts, ends)]

Ini memproses daftar sepuluh juta item dalam 75ms, yang hampir 50x percepatan dari versi berbasis daftar yang ditulis dengan Python murni.

Untuk versi yang lebih lambat tetapi agak lebih mudah dibaca, inilah yang saya miliki sebelumnya, berdasarkan pada dukungan eksperimental yang baru-baru ini ditambahkan untuk "daftar yang diketik," yang berukuran dinamis yang memungkinkan kami mengisi setiap nampan dengan cara yang tidak sesuai pesanan jauh lebih cepat.

Ini sedikit bergulat dengan numbatipe mesin inferensi, dan saya yakin ada cara yang lebih baik untuk menangani bagian itu. Ini juga ternyata hampir 10x lebih lambat dari yang di atas.

@numba.jit(nopython=True)
def enum_bins_numba(ints):
    bins = numba.typed.List()
    for i in range(ints.max() + 1):
        inner = numba.typed.List()
        inner.append(0)  # An awkward way of forcing type inference.
        inner.pop()
        bins.append(inner)

    for x, i in enumerate(ints):
        bins[i].append(x)

    return bins

Saya menguji ini terhadap yang berikut:

def enum_bins_dict(ints):
    enum_bins = defaultdict(list)
    for k, v in enumerate(ints):
        enum_bins[v].append(k)
    return enum_bins

def enum_bins_list(ints):
    enum_bins = [[] for i in range(ints.max() + 1)]
    for x, i in enumerate(ints):
        enum_bins[i].append(x)
    return enum_bins

def enum_bins_sparse(ints):
    M, N = ints.max() + 1, ints.size
    return sparse.csc_matrix((ints, ints, np.arange(N + 1)),
                             (M, N)).tolil().rows.tolist()

Saya juga mengujinya terhadap versi cython yang dikompilasi mirip dengan enum_bins_numba_buffer(dijelaskan secara rinci di bawah).

Pada daftar sepuluh juta int acak ( ints = np.random.randint(0, 100, 10000000)) saya mendapatkan hasil berikut:

enum_bins_dict(ints)
3.71 s ± 80.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

enum_bins_list(ints)
3.28 s ± 52.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

enum_bins_sparse(ints)
1.02 s ± 34.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

enum_bins_numba(ints)
693 ms ± 5.81 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

enum_bins_cython(ints)
82.3 ms ± 1.77 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

enum_bins_numba_buffer(ints)
77.4 ms ± 2.06 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Secara mengesankan, cara ini bekerja dengan numbamengungguli cythonversi dari fungsi yang sama, bahkan dengan memeriksa batas dimatikan. Saya belum memiliki cukup keakraban pythranuntuk menguji pendekatan ini menggunakannya, tetapi saya akan tertarik untuk melihat perbandingan. Tampaknya berdasarkan pada percepatan ini bahwa pythranversi mungkin juga sedikit lebih cepat dengan pendekatan ini.

Inilah cythonversi untuk referensi, dengan beberapa instruksi pembuatan. Setelah Anda cythonmenginstal, Anda akan memerlukan setup.pyfile sederhana seperti ini:

from distutils.core import setup
from distutils.extension import Extension
from Cython.Build import cythonize
import numpy

ext_modules = [
    Extension(
        'enum_bins_cython',
        ['enum_bins_cython.pyx'],
    )
]

setup(
    ext_modules=cythonize(ext_modules),
    include_dirs=[numpy.get_include()]
)

Dan modul Cython, enum_bins_cython.pyx:

# cython: language_level=3

import cython
import numpy
cimport numpy

@cython.boundscheck(False)
@cython.cdivision(True)
@cython.wraparound(False)
cdef void enum_bins_inner(long[:] ints, long[:] bins, long[:] starts) nogil:
    cdef long i, x
    for x in range(len(ints)):
        i = ints[x]
        bins[starts[i]] = x
        starts[i] = starts[i] + 1

def enum_bins_cython(ints):
    assert (ints >= 0).all()
    # There might be a way to avoid storing two offset arrays and
    # save memory, but `enum_bins_inner` modifies the input, and
    # having separate lists of starts and ends is convenient for
    # the final partition stage.
    ends = numpy.bincount(ints).cumsum()
    starts = numpy.empty(ends.shape, dtype=numpy.int64)
    starts[1:] = ends[:-1]
    starts[0] = 0

    bins = numpy.empty(ints.shape, dtype=numpy.int64)
    enum_bins_inner(ints, bins, starts)

    starts[1:] = ends[:-1]
    starts[0] = 0
    return [bins[s:e] for s, e in zip(starts, ends)]

Dengan dua file ini di direktori kerja Anda, jalankan perintah ini:

python setup.py build_ext --inplace

Anda kemudian dapat mengimpor fungsi menggunakan from enum_bins_cython import enum_bins_cython.

Inilah cara yang sangat aneh untuk melakukan ini, itu mengerikan, tetapi saya merasa terlalu lucu untuk tidak berbagi - dan semuanya numpy!

out = np.array([''] * (x.max() + 1), dtype = object)
np.add.at(out, x, ["{} ".format(i) for i in range(x.size)])
[[int(i) for i in o.split()] for o in out]

Out[]:
[[3, 4], [0, 5], [1, 2], [6], [], [7]]

EDIT: ini adalah metode terbaik yang bisa saya temukan di sepanjang jalan ini. Masih 10x lebih lambat dari argsortsolusi @PaulPanzer :

out = np.empty((x.max() + 1), dtype = object)
out[:] = [[]] * (x.max() + 1)
coords = np.empty(x.size, dtype = object)
coords[:] = [[i] for i in range(x.size)]
np.add.at(out, x, coords)
list(out)

Anda dapat melakukannya dengan membuat kamus angka, kunci akan menjadi angka dan nilai harus menjadi indeks yang dilihat angka, ini adalah salah satu cara tercepat untuk melakukannya, Anda dapat melihat kode di bawah ini:

>>> import numpy as np
>>> a = np.array([1 ,2 ,2 ,0 ,0 ,1 ,3, 5])
>>> b = {}
# Creating an empty list for the numbers that exist in array a
>>> for i in range(np.min(a),np.max(a)+1):
    b[str(i)] = []

# Adding indices to the corresponding key
>>> for i in range(len(a)):
    b[str(a[i])].append(i)

# Resulting Dictionary
>>> b
{'0': [3, 4], '1': [0, 5], '2': [1, 2], '3': [6], '4': [], '5': [7]}

# Printing the result in the way you wanted.
>>> for i in sorted (b.keys()) :
     print(b[i], end = " ")

[3, 4] [0, 5] [1, 2] [6] [] [7] 

Kodesemu:

1. dapatkan "jumlah array 1d dalam array 2d", dengan mengurangi nilai minimum array numpy Anda dari nilai maksimum dan kemudian ditambah satu. Dalam kasus Anda, itu akan menjadi 5-0 + 1 = 6

2. inisialisasi array 2d dengan jumlah array 1d di dalamnya. Dalam kasus Anda, inisialisasi array 2d dengan 6 array 1d di dalamnya. Setiap array 1d sesuai dengan elemen unik dalam array numpy Anda, misalnya, array 1d pertama akan sesuai dengan '0', array 1d kedua akan sesuai dengan '1', ...

3. loop melalui array numpy Anda, masukkan indeks elemen ke dalam array 1d yang tepat. Dalam kasus Anda, indeks elemen pertama di array numpy Anda akan dimasukkan ke array 1d kedua, indeks elemen kedua di array numpy Anda akan dimasukkan ke array 1d ketiga, ....

Pseudocode ini akan membutuhkan waktu linier untuk berjalan karena tergantung pada panjang array numpy Anda.

Ini memberi Anda apa yang Anda inginkan dan akan memakan waktu 2,5 detik selama 10.000.000 pada mesin saya:

import numpy as np
import timeit

# x = np.array("1 2 2 0 0 1 3 5".split(),int)
x = np.random.randint(0, 100, 100000)

def create_index_list(x):
    d = {}
    max_value = -1
    for i,v in enumerate(x):
        if v > max_value:
            max_value = v
        try:
            d[v].append(i)
        except:
            d[v] = [i]
    result_list = []
    for i in range(max_value+1):
        if i in d:
            result_list.append(d[i])
        else:
            result_list.append([])
    return result_list

# print(create_index_list(x))
print(timeit.timeit(stmt='create_index_list(x)', number=1, globals=globals()))

Jadi diberi daftar elemen, Anda ingin membuat (elemen, indeks) pasangan. Dalam waktu linier, ini dapat dilakukan sebagai:

hashtable = dict()
for idx, val in enumerate(mylist):
    if val not in hashtable.keys():
         hashtable[val] = list()
    hashtable[val].append(idx)
newlist = sorted(hashtable.values())

Ini membutuhkan waktu O (n). Saya tidak bisa memikirkan solusi yang lebih cepat seperti sekarang, tetapi akan memperbarui di sini jika saya lakukan.