Lua table.sort вызывает функцию сравнения с тем же элементом

Я наткнулся на странное поведение table.sort(), при котором функция сравнения вызывается путем передачи одного и того же элемента массива в обоих параметрах.

Рассмотрим код ниже. Я хочу отсортировать массив от самого высокого до самого низкого значения свойства v и, если они равны (и поскольку table.sort() алгоритм нестабилен на момент документации), я хочу отсортировать их по исходным индексам элементы.

-- The array to sort
local arr = {
  {id = "A", v = 1},
  {id = "B", v = 1},
  {id = "C", v = 0},
  {id = "D", v = 1},
  {id = "E", v = 1}
}

-- A map containing the original index of the elements in the array: element => originalIndex
local original_indices = {}
for index, elem in ipairs(arr) do
  original_indices[elem] = index
end

-- Sort the array
table.sort(arr, 
  function(a, b) 
    assert(a ~= b, "Comparing the same element in the array!")
    
    -- Compare the value
    if a.v > b.v then
      return true
    elseif a.v < b.v then
      return false
    end
    
    -- Values are equal. Compare original indices, which should always
    -- decide the final order.
    local ia = original_indices[a]
    local ib = original_indices[b]
    
    if ia < ib then
      return true
    elseif ia > ib then
      return false
    end
    
    error("BUG! Comparing the same element in the array!") 
  end
)

Ожидаемый результат должен быть:

{  
  {id = "A", v = 1},
  {id = "B", v = 1},
  {id = "D", v = 1},
  {id = "E", v = 1},
  {id = "C", v = 0}
}

Но вместо этого я получаю сообщение об ошибке, потому что Lua вызывает функцию сортировки, передавая один и тот же элемент в обоих параметрах, чего не должно быть.

Я что-то пропустил? Как мне получить ожидаемый результат?

Поиграться с кодом можно здесь.

Алгоритм сортировки слиянием (с кодом на Python, Java, JavaScript, PHP, C++)
Алгоритм сортировки слиянием (с кодом на Python, Java, JavaScript, PHP, C++)
Merge sort - самый популярный алгоритм сортировки, основанный на принципе алгоритма "разделяй и властвуй".
Сортировка hashmap по значениям
Сортировка hashmap по значениям
На Leetcode я решал задачу с хэшмапой и подумал, что мне нужно отсортировать хэшмапу по значениям.
2
0
69
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Чтобы решить вашу проблему, просто вернитесь при сравнении одного и того же элемента.

if a == b then
  return
end

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

Спасибо. Было бы неплохо, если бы в документации упоминалась эта деталь!

Claudi 16.07.2024 23:49

Другие вопросы по теме