Ваш текущий алгоритм занимает квадратичное c время, которое не будет масштабироваться до больших входов. Вы можете сделать это намного лучше.
Один из способов сделать это лучше - использовать отсортированную структуру данных, например sortedcontainers.SortedList, и выполнить серию поисков и вставок. В следующем примере реализации возвращается список, предполагается, что нет связей, и значения рангов начинаются с 0:
import sortedcontainers
def rank(nums):
sortednums = sortedcontainers.SortedList()
ranks = []
for num in nums:
ranks.append(sortednums.bisect_left(num))
sortednums.add(num)
return ranks
Большая часть работы выполняется внутри реализации SortedList, а SortedList довольно быстро, поэтому это не следует не слишком много Python накладных расходов. Наличие sortedcontainers определенно делает это более удобным, чем следующий параметр, если не обязательно более эффективным.
Этот параметр выполняется за ... O (n log n) -i sh время. SortedList использует двухслойную иерархию вместо традиционной древовидной структуры, что делает преднамеренный компромисс между большим перемещением данных и меньшей погоней за указателями, поэтому теоретически вставка не является O (log n), но она эффективна на практике.
Следующим вариантом будет использование расширенной сортировки слиянием. Если вы сделаете это, вы захотите использовать Numba или Cython, потому что вам придется писать циклы вручную.
Основная идея c состоит в том, чтобы выполнить сортировку слиянием, но с отслеживанием ранга. каждого элемента в его подмассиве, как вы go. При объединении двух отсортированных подмассивов каждый элемент с левой стороны сохраняет свой старый ранг, в то время как значения ранга для элементов с правой стороны корректируются в сторону увеличения на количество элементов слева, которое было меньше их.
Это опция запускается в O (n log n).
Неоптимизированная реализация, работающая со списками Python, предполагающая отсутствие связей и начальные ранги в 0, будет выглядеть следующим образом:
def rank(nums):
_, indexes, ranks = _augmented_mergesort(nums)
result = [None]*len(nums)
for i, rank_ in zip(indexes, ranks):
result[i] = rank_
return result
def _augmented_mergesort(nums):
# returns sorted nums, indexes of sorted nums in original nums, and corresponding ranks
if len(nums) == 1:
return nums, [0], [0]
left, right = nums[:len(nums)//2], nums[len(nums)//2:]
return _merge(*_augmented_mergesort(left), *_augmented_mergesort(right))
def _merge(lnums, lindexes, lranks, rnums, rindexes, rranks):
nums, indexes, ranks = [], [], []
i_left = i_right = 0
def add_from_left():
nonlocal i_left
nums.append(lnums[i_left])
indexes.append(lindexes[i_left])
ranks.append(lranks[i_left])
i_left += 1
def add_from_right():
nonlocal i_right
nums.append(rnums[i_right])
indexes.append(rindexes[i_right] + len(lnums))
ranks.append(rranks[i_right] + i_left)
i_right += 1
while i_left < len(lnums) and i_right < len(rnums):
if lnums[i_left] < rnums[i_right]:
add_from_left()
elif lnums[i_left] > rnums[i_right]:
add_from_right()
else:
raise ValueError("Tie detected")
if i_left < len(lnums):
nums += lnums[i_left:]
indexes += lindexes[i_left:]
ranks += lranks[i_left:]
else:
while i_right < len(rnums):
add_from_right()
return nums, indexes, ranks
Для оптимизированной реализации вам понадобится базовый вариант сортировки вставок, вы захотите использовать Numba или Cython, вам захочется работать с массивами, и вы не захотите делать так много выделения.