Блог

Я создаю алгоритм дерева решений. Сортировка в этом алгоритме очень дорогая, потому что для каждого разделения мне нужно сортировать каждый столбец. Итак, в начале — еще до построения дерева я предварительно сортирую переменные — я создаю матрицу, поэтому для каждого столбца в матрице я сохраняю его рейтинг. Затем, когда я хочу отсортировать переменную в некотором разделении, я на самом деле не сортирую ее, а использую предварительно отсортированный ранжирующий массив. Проблема в том, что я не знаю, как сделать это эффективным способом.

Наивное решение этой проблемы приведено ниже. Это только для 1 переменной (v) и 1 разделения (split_ind).

 import numpy as np

v = np.array([60,70,50,10,20,0,90,80,30,40])
sortperm = v.argsort()                            #1 sortperm = array([5, 3, 4, 8, 9, 2, 0, 1, 7, 6]) 
rankperm = sortperm.argsort()                     #2 rankperm = array([6, 7, 5, 1, 2, 0, 9, 8, 3, 4])

split_ind = np.array([3,6,4,8,9])                 # this is my split (random)

# split v and sortperm 
v_split = v[split_ind]                            # v_split        = array([10, 90, 20, 30, 40])
rankperm_split = rankperm[split_ind]              # rankperm_split = array([1, 9, 2, 3, 4])

vsorted_dummy = np.ones(10)*-1                    #3 allocate "empty" array[N]
vsorted_dummy[rankperm_split] = v_split
vsorted = vsorted_dummy[vsorted_dummy!=-1]        # vsorted = array([ 10.,  20.,  30.,  40.,  90.])
 

В принципе, у меня есть 2 вопроса:

1. Необходима ли двойная сортировка для создания ранжирующего массива? (# 1 и # 2)
2. В строке # 3 я выделяю array[N] . Это очень неэффективно с точки зрения пространства, потому что даже при разделении размера n << N я должен выделить весь массив. Проблема здесь в том, как вычислить rankperm_split . В исходном примере rankperm_split = [1,9,2,3,4] пока так и должно быть на самом деле [1,5,2,3,4] . Эту проблему можно переформулировать так, что я хочу создать «плотный» целочисленный массив с максимальным разрывом 1, который сохраняет ранжирование массива без изменений.

Обновить

Я думаю, что второй момент здесь является ключевым. Эта проблема может быть переопределена как

A[N] — массив размером N B[N] — массив размером N

Я хочу преобразовать массив A в массив B, чтобы:

1. Ранжирование элементов остается неизменным (для каждой пары i, j, если A[i] < A[j] тогда B[i] < B[j]
2. Массив B содержит только элементы от 1 до N, где каждый элемент уникален.

Несколько примеров этого преобразования:

• [3,4,5] => [1,2,3]
• [30,40,50] => [1,2,3]
• [30,50,40] => [1,3,2]
• [3,4,50] => [1,2,3]

Наивная реализация (с сортировкой) может быть определена следующим образом (в Python)

 def remap(a):
    a_ = sorted(a)
    b = [a_.index(e) 1 for e in a]
    return b