Эффективный алгоритм сортировки Python с TieBreaking

Question

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

Мне нужно, чтобы время выполнения было максимально быстрым, меня не особо волнуют требования к памяти.Если есть лучший способ представить мои данные так, чтобы это было легко, это тоже полезный ответ.

Данные, которые я хочу отсортировать, имеют не более 15 значений, поэтому время выполнения в этом отношении неплохое, я просто хочу сделать это 100 раз.

Псевдокод будет выглядеть как-токак это:

Iterator = 0    
maxVal = max value of wins
maxes = teams with wins == maxVal
If len(maxes) == 1
    rank[values] = iterator
    iterator += 1
    sort(restOfData)
Else 
    # H2Hwins computes the amount of wins for teams currently tied incase of 2 or more teams tied  
    counts = sorted([(h2hwins(t, maxes), pointDifferential) for team in maxes])
    for c in counts
        rank[value] = iterator
        iterator += 1
    sort(restOfData)
return rank

Так что, если бы у меня были следующие входы, это были бы выходы:

# Columns are Team, Wins, H2H Tiebreaks, Point Differential
# Lakers win tie based on H2H with Clippers
testData = [['Lakers', 48, ['Clippers'], 6], ['Clippers', 48, ['Warriors'], 8], ['Warriors', 47, ['Lakers'], 10]]
magicSort(testData)
>>> ['Lakers', 'Clippers', 'Warriors']

# Warriors have 2 H2H tiebreakers so they are 1st.  Lakers have 1 H2H tiebreaker so they are 2nd.
testData2 = [['Lakers', 48, ['Clippers'], 6], ['Clippers', 48, [''], 8], ['Warriors', 48, ['Lakers', 'Clippers'], 10]]
magicSort(testData2)
>>> ['Warriors', 'Lakers', 'Clippers']

# All 3 are tied so we default to point differential
testData3 = [['Lakers', 47, ['Clippers'], 6], ['Clippers', 47, ['Warriors'], 8], ['Warriors', 47, ['Lakers'], 10]]
magicSort(testData3)
>>> ['Warriors', 'Clippers', 'Lakers']

Я мог бы придумать больше тестовых случаев, если это необходимо, но я считаю, что этоохватывает край чехлов

Answer 1

Не изобретай велосипед.Это было реализовано уже десятилетия назад.Просто используйте queue.PriorityQueue уже, что реализовано с использованием heapq

• heapq - это более эффективная предварительно отсортированная структура данных, предназначенная для оптимизации поиска самых маленьких (/ наибольших) элемент.

• heapq обрабатывает только целые числа;queue.PriorityQueue обобщает на объекты. Вашему объекту понадобится класс с пользовательским методом сравнения (__lt__; в 2.x мы использовали __cmp__)

• По умолчанию кучаявляются минимальными кучами, то есть они оптимизируются для извлечения наименьшего элемента, сохраняя его в корне кучи (и перебалансируя остальную часть кучи).

• Но вы хотите max-куча :
  • , поэтому либо отмените целочисленное поле при вставке (put) и извлечении (get)
  • проще - простоизмените метод __cmp__ вашего объекта так, чтобы более крупный элемент "потерял" сравнение (следовательно, оказывается в верхней части heapq).Я бы настроил __cmp__ вместо того, чтобы взламывать метод __lt__, чтобы избежать явной путаницы.