#arrays #algorithm #sorting #ranking #decision-tree
#массивы #алгоритм #сортировка #Рейтинг #дерево принятия решений
Вопрос:
Я создаю алгоритм дерева решений. Сортировка в этом алгоритме очень дорогая, потому что для каждого разделения мне нужно сортировать каждый столбец. Итак, в начале — еще до построения дерева я предварительно сортирую переменные — я создаю матрицу, поэтому для каждого столбца в матрице я сохраняю его рейтинг. Затем, когда я хочу отсортировать переменную в некотором разделении, я на самом деле не сортирую ее, а использую предварительно отсортированный ранжирующий массив. Проблема в том, что я не знаю, как сделать это эффективным способом.
Наивное решение этой проблемы приведено ниже. Это только для 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 и # 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, чтобы:
- Ранжирование элементов остается неизменным (для каждой пары i, j, если
A[i] < A[j]
тогдаB[i] < B[j]
- Массив 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
Комментарии:
1. Зачем вам нужны 2 сорта? Как на второй сорт влияет первый?
2. Сначала argsort создает сортировочную перестановку так, чтобы sorted(A) = A[argsort(A)] . Второй argsort создает ранжирование A, так что min(A) имеет рейтинг 1, а max (A) имеет рейтинг N (где N — размер (A)), и каждый элемент ранжирования определяет позицию в отсортированном (A). Может быть, есть лучший способ создать рейтинг, но я его не знаю.