Я наткнулся на странное поведение 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 вызывает функцию сортировки, передавая один и тот же элемент в обоих параметрах, чего не должно быть.
Я что-то пропустил? Как мне получить ожидаемый результат?
Поиграться с кодом можно здесь.
Чтобы решить вашу проблему, просто вернитесь при сравнении одного и того же элемента.
if a == b then
return
end
Внутренне алгоритм сортировки Lua представляет собой быструю сортировку схемы разделения Хоара. Во время разделения сводное значение будет сравнивать каждый элемент один за другим с каждой стороны, пока не будет найден элемент с тем же или противоположным значением, поэтому существует вероятность, что сравнивается один и тот же элемент.
Спасибо. Было бы неплохо, если бы в документации упоминалась эта деталь!