В цикле, который собирает некоторые выборки, мне нужно время от времени получать статистику об их отсортированных индексах, для которых argsort возвращает именно то, что мне нужно. Однако каждая итерация добавляет только одну выборку, и это огромная трата ресурсов на то, чтобы продолжать передавать весь массив выборок в функцию argsort, тем более что массив выборок очень велик. Разве нет инкрементной эффективной техники, эквивалентной argsort?
Я полагаю, что эффективная функция инкрементного argsort может быть реализована путем ведения упорядоченного списка выборок, который можно искать для правильных вставок индексов при поступлении новой выборки. Такие индексы могут затем использоваться как для поддержания порядка списка выборок, так и для генерации желаемого выходного результата, подобного аргсорту.
До сих пор я использовал функцию searchsorted2d от @Divakar с небольшими изменениями для получения индексов вставки и создал некоторую подпрограмму, которая может получить желаемый вывод, если он вызывается после каждой вставки образца (b = 1 ).
Тем не менее, это неэффективно, и я хотел бы вызвать подпрограмму после сбора k-х выборок (например, b = 10). В случае массовых вставок searchsorted2d, кажется, возвращает неправильные индексы, и это было, если я остановился!
import time
import numpy as np
# By Divakar
# See https://stackoverflow.com/a/40588862
def searchsorted2d(a, b):
m, n = a.shape
max_num = np.maximum(a.max() - a.min(), b.max() - b.min()) + 1
r = max_num * np.arange(m)[:,np.newaxis]
p = np.searchsorted((a + r).ravel(), (b + r).ravel()).reshape(b.shape)
return p #- n * (np.arange(m)[:,np.newaxis])
# The following works with batch size b = 1,
# but that is not efficient ...
# Can we make it work for any b > 0 value?
class incremental(object):
def __init__(self, shape):
# Express each row offset
self.ranks_offset = np.tile(np.arange(shape[1]).reshape(1, -1),
(shape[0], 1))
# Storage for sorted samples
self.a_sorted = np.empty((shape[0], 0))
# Storage for sort indices
self.a_ranks = np.empty((shape[0], 0), np.int)
def argsort(self, a):
if self.a_sorted.shape[1] == 0: # Use np.argsort for initialization
self.a_ranks = a.argsort(axis=1)
self.a_sorted = np.take_along_axis(a, self.a_ranks, 1)
else: # In later itterations,
# searchsorted the input increment
indices = searchsorted2d(self.a_sorted, a)
# insert the stack pos to track the sorting indices
self.a_ranks = np.insert(self.a_ranks, indices.ravel(),
self.ranks_offset.ravel() +
self.a_ranks.shape[1]).reshape((n, -1))
# insert the increments to maintain a sorted input array
self.a_sorted = np.insert(self.a_sorted, indices.ravel(),
a.ravel()).reshape((n, -1))
return self.a_ranks
M = 1000 # number of iterations
n = 16 # vector size
b = 10 # vectors batch size
# Storage for samples
samples = np.zeros((n, M)) * np.nan
# The proposed approach
inc = incremental((n, b))
c = 0 # iterations counter
tick = time.time()
while c < M:
if c % b == 0: # Perform batch computations
#sample_ranks = samples[:,:c].argsort(axis=1)
sample_ranks = inc.argsort(samples[:,max(0,c-b):c]) # Incremental argsort
######################################################
# Utilize sample_ranks in some magic statistics here #
######################################################
samples[:,c] = np.random.rand(n) # collect a sample
c += 1 # increment the counter
tock = time.time()
last = ((c-1) // b) * b
sample_ranks_GT = samples[:,:last].argsort(axis=1) # Ground truth
print('Compatibility: {0:.1f}%'.format(
100 * np.count_nonzero(sample_ranks == sample_ranks_GT) / sample_ranks.size))
print('Elapsed time: {0:.1f}ms'.format(
(tock - tick) * 1000))
Я бы ожидал 100% совместимости с функцией argsort, но она должна быть более эффективной, чем вызов argsort. Что касается времени выполнения с инкрементным подходом, кажется, что 15 мс или около того должно быть более чем достаточно для данного примера.
Пока что только одно из этих двух условий может быть выполнено с помощью любой из изученных техник.
<ч />
Короче говоря, показанный выше алгоритм выглядит как вариант дерева статистики заказов для оценки рангов данных, но он этого не делает при массовом добавлении выборок (b > 1 ). Пока что это работает только при вставке семплов один за другим (b = 1). Однако массивы копируются каждый раз, когда вызывается insert, что приводит к огромным накладным расходам и создает узкое место, поэтому пробы должны добавляться в объемах, а не по отдельности.
Можете ли вы представить более эффективный инкрементный алгоритм argsort или хотя бы выяснить, как поддерживать массовую вставку (b > 1) в приведенном выше?
Если вы решите начать с того места, где я остановился, проблема может быть уменьшена до исправления ошибки в следующем снимке:
import numpy as np
# By Divakar
# See https://stackoverflow.com/a/40588862
def searchsorted2d(a, b):
m, n = a.shape
max_num = np.maximum(a.max() - a.min(), b.max() - b.min()) + 1
r = max_num * np.arange(m)[:,np.newaxis]
p = np.searchsorted((a + r).ravel(), (b + r).ravel()).reshape(b.shape)
# It seems the bug is around here...
#return p - b.shape[0] * np.arange(b.shape[1])[np.newaxis]
#return p - b.shape[1] * np.arange(b.shape[0])[:,np.newaxis]
return p
n = 16 # vector size
b = 2 # vectors batch size
a = np.random.rand(n, 1) # Samples array
a_ranks = a.argsort(axis=1) # Initial ranks
a_sorted = np.take_along_axis(a, a_ranks, 1) # Initial sorted array
new_data = np.random.rand(n, b) # New block to append into the samples array
a = np.hstack((a, new_data)) #Append new block
indices = searchsorted2d(a_sorted, new_data) # Compute insertion indices
ranks_offset = np.tile(np.arange(b).reshape(1, -1), (a_ranks.shape[0], 1)) + a_ranks.shape[1] # Ranks to insert
a_ranks = np.insert(a_ranks, indices.ravel(), ranks_offset.ravel()).reshape((n, -1)) # Insert ransk according to their indices
a_ransk_GT = a.argsort(axis=1) # Ranks ground truth
mask = (a_ranks == a_ransk_GT)
print(mask) #Why they are not all True?
assert(np.all(mask)), 'Oops!' #This should not fail, but it does :(
<ч />
Кажется, что массовая вставка более сложна, чем я изначально думал, и что searchsorted2d не должно быть обвинено. Возьмите случай отсортированного массива a = [ 1, 2, 5 ] и двух новых элементов block = [3, 4] для вставки. Если мы повторим и вставим, то np.searchsorted(a, block[i]) вернет [2] и [3], и это нормально. Однако, если мы вызовем np.searchsorted(a, block) (желаемое поведение - эквивалентное итерации без вставки), мы получим [2, 2]. Это проблематично для реализации добавочного argsort, так как даже np.searchsorted(a, block[::-1]) приведет к тому же самому. Есть идеи?