Перейти к содержимому
  • 0
Belzebub

Не работает сортировка

Вопрос

Привет.

Пишу програмку для варпа и столкнулся с проблемкой сортировки.

Тематика такая:
Прога выводит на экран всех владельцев варпа и показывает как долго они онлайн/оффлайн что-бы посетители знали к кому можно обратиться по каким-то вопросам.

Я сортирую последовательную таблицу участников варпа по функции:
https://pastebin.com/aE4EHBk3
Сортировка буд-то бы в случайном порядке сортирует людей на экране:

Это так-же не работает с кастомной функцией сортировки:
https://pastebin.com/tnY2PeTR
В итоге должно было получиться что-то вроде:
warp.thumb.png.289e5e19db19bcb616dc085f657ff042.png
сначала идут онлайн пользователи, они отсортированы по 'время сессии'.
далее идут оффлайн юзеры, они отсортированы по 'был в сети'.

Что я делаю не так?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Рекомендуемые сообщения

Начнём с того, что изначальный метод сортировки невалиден для table.sort, т.к. не учитывал все возможные варианты напрямую. Да, нативный sort в этом плане слегка туповат:

 

iDl8QO4.png

 

Также рискну предположить, что вывод игроков на экран был хаотичным из-за использования for k, v in pairs вместо for i = 1, #array (который, к слову, еще и быстрее). Поэтому вот:

local members = {
  {
    name = "Vasya",
    online = false,
    playtime = 10,
    offline_time = 2
  },
  {
    name = "Petya",
    online = true,
    playtime = 14,
    offline_time = 2
  },
  {
    name = "Sanya",
    online = true,
    playtime = 15,
    offline_time = 2
  },
  {
    name = "Igor",
    online = false,
    playtime = 1,
    offline_time = 3
  },
  {
    name = "Dima",
    online = false,
    playtime = 1,
    offline_time = 8
  },
}

table.sort(members, function(ply1, ply2)
  if ply1.online and ply2.online then
    return ply1.playtime > ply2.playtime
  elseif ply1.online and not ply2.online then
    return true
  elseif not ply1.online and ply2.online then
    return false
  else
    return ply1.offline_time < ply2.offline_time
  end
end)

for i = 1, #members do
  print(members[i].name)
end

Результат:

 

XHbCXYS.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Спасибо <3
Я изменил код клоузуры на твои ветвления и всё заработало.
По поводу pairs и for i = 1, #tbl - всё и так ок.

алсо я использую ipairs, не знаю как оно в обычном луа - но бэнчмарки в JIT показывают результат в 15-20% быстрее
https://pastebin.com/vEH362LC

Изменено пользователем Belzebub

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
1 час назад, ECS сказал:

изначальный метод сортировки невалиден для table.sort, т.к. не учитывал все возможные варианты

Да, дело именно в этом. Вместо else нужно было писать elseif not ply1.online and not ply2.online then, а также поменять знак при сравнении offline_time.

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
1 час назад, Belzebub сказал:

По поводу pairs и for i = 1, #tbl - всё и так ок.

алсо я использую ipairs, не знаю как оно в обычном луа - но бэнчмарки в JIT показывают результат в 15-20% быстрее
https://pastebin.com/vEH362LC

Во-первых, твой тест заведомо некорректен, т.к. в первом случае при каждой итерации ты индексируешь таблицу (причём индексация - это довольно жирная операция), а во втором тело цикла попросту пустое. Уверен, что JIT-компилятор скипает цикл во втором случае, пытаясь оптимизировать код:

 

s0QIzrd.png

 

Во-вторых, тема твоего поста и моя рекомендация по ipairs относится к опенкомпам, где по дефолту не поддерживается JIT-компиляция. Зачем прилагать бенчмарк на GMod/LuaJIT вместо бенчмарка на опенкомпах - мне не ясно

 

В-третьих, у тебя используется GMod'овский таймер вместо нативного os.clock, который, напомню, и следует использовать для бенчмарка алгоритмов согласно Lua wiki

 

Поэтому если адаптировать твой код под чистый луа, то результат будет диаметрально противоположным:

local function Benchmark(uid, func, count, onfinish)
  local time = os.clock()

  for i = 1, count do
    func()
  end

  print(uid, os.clock() - time)
      
  if onfinish then onfinish() end
end

.......................

Bench()
:Add("for i = 1, #tbl do", function()
    for i = 1, #tbl do
        local var = tbl[i]
    end
end)
:Add("for i, v in ipairs(tbl) do", function()
    for i, v in ipairs(tbl) do
        local var = v
    end
end)
:Start(10000000) -- 10 000 000

Ой, что же это? Медленнее в 2.7 раза? Ой-ой-ой

 

hIxhGtd.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

os.clock - крутая штука для бэнчей на чистом луа, но SysTime в глуа намного точнее.
Индексация, не индесация - один фиг с любым телом цикла ipairs на luajit работает быстрее.

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

Изменено пользователем Belzebub

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
26 минут назад, Belzebub сказал:

SysTime в глуа намного точнее.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
1 час назад, ECS сказал:

Ой, что же это? Медленнее в 2.7 раза?

Не всё так плохо. Конечно, в синтетических тестах с пустым циклом разница получается значительная. В реальных же циклах разница не столь велика, потому что вклад ipairs в общую нагрузку снижается на фоне вычислений внутри цикла. А циклы-то обычно не пустые.

 

При этом использование ipairs позволяет писать более читаемый код, позволяя отказаться как от использования индексов, так и от объявления локальной переменной внутри цикла. Ценой такого решения будет снижение быстродействия, но оно не всегда критично, а читаемость кода может оказаться важнее.

 

Как найти оптимум, это отдельный и сложный вопрос. Пожалуй, хорошей привычкой будет писать обычные циклы for i=1,#tbl, и если код кажется трудно читаемым, хорошенько подумав о последствиях, применять for i,v in ipairs(tbl).

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
27 минут назад, eu_tomat сказал:

При этом использование ipairs позволяет писать более читаемый код, позволяя отказаться как от использования индексов, так и от объявления локальной переменной внутри цикла

Согласен, я и сам предпочитаю использовать ipairs в простых скриптах, где производительность не играет роли. Однако насчёт локальной переменной ты тут лишка хватил, т.к. любой итератор по типу pairs/ipairs является не более чем функцией-обёрткой, хранящей этот самый счётчик в виде скрытой локальной переменной. Те же яйца, только в профиль:

function myIPairs(t)
  local index, count = 0, #t

  return function()
    index = index + 1
    
    if index <= count then
      return t[index]
    end
  end
end

Я советовал использовать человеку конструкцию for i = 1, #t в первую очередь из-за потенциальной ошибки "хаотичного" порядка вывода игроков, т.к. у меня зачастую именно pairs был виной подобному поведению. А поскольку исходный код софта выложен не был, предположение могло оказаться не лишним. Это потом уже пошла дискуссия на тему "как быстрее"

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
2 часа назад, Belzebub сказал:

Индексация, не индесация - один фиг с любым телом цикла ipairs на luajit работает быстрее

Не-а. Специально даже скомпилил LuaJIT из интереса, а для честности оба тела цикла сделал максимально простыми, дабы тестить исключительно итерационную составляющую:

Bench()
:Add("for i = 1, #tbl do", function()
    for i = 1, #tbl do
        local var = 1
    end
end)
:Add("for i, v in ipairs(tbl) do", function()
    for i, v in ipairs(tbl) do
        local var = 1
    end
end)
:Start(10000000)

Y3yT5HZ.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Это тесты без индексации. Как на счет тестов с ней?

Bench()
:Add("for i = 1, #tbl do", function()
    for i = 1, #tbl do
        local var = tbl[i]
    end
end)
:Add("for i, v in ipairs(tbl) do", function()
    for i, v in ipairs(tbl) do
        local var = tbl[i]
    end
end)
:Start(10000000)

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
14 минуты назад, hohserg сказал:

Это тесты без индексации. Как на счет тестов с ней?

Хе-хе, я ждал этого вопроса. Как говорится, пути компиляторов неисповедимы: к примеру, если каким-либо образом обрабатывать элементы таблицы, создавая иллюзию реальной деятельности в теле цикла, то ipairs, разумеется, проигрывает, т.к. это функция-итератор, которая чисто технически не может быть быстрее простого цикла с числовым лимитом:

Bench()
:Add("for i = 1, #tbl do", function()
    for i = 1, #tbl do
        local var = math.floor(#tbl[i])
    end
end)
:Add("for i, v in ipairs(tbl) do", function()
    for i, v in ipairs(tbl) do
        local var = math.floor(#v)
    end
end)
:Start(100000000)

fnnf3Ev.png

 

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

Bench()
:Add("for i = 1, #tbl do", function()
    for i = 1, #tbl do
        local var = tbl[i]
    end
end)
:Add("for i, v in ipairs(tbl) do", function()
    for i, v in ipairs(tbl) do
        local var = v
    end
end)
:Start(100000000)

yzgbOEM.png

 

А вот в этом случае ipairs опять в пролёте даже несмотря на дополнительную индексацию по таблице в теле первого цикла, т.к. накладные расходы на вызов функции-итератора превышают расходы на индексацию таблиц:

Bench()
:Add("for i = 1, #tbl do", function()
    for i = 1, #tbl do
        local var = #tbl[i] + math.floor(i)
    end
end)
:Add("for i, v in ipairs(tbl) do", function()
    for i, v in ipairs(tbl) do
        local var = #v + math.floor(i)
    end
end)
:Start(100000000)

HWn0ywP.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
33 минуты назад, ECS сказал:

Однако насчёт локальной переменной ты тут лишка хватил, т.к. любой итератор по типу pairs/ipairs является не более чем функцией-обёрткой, хранящей этот самый счётчик в виде скрытой локальной переменной.

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

33 минуты назад, ECS сказал:

Это потом уже пошла дискуссия на тему "как быстрее"

Да, я понял. Мне показался слишком категоричным призыв отказаться от использования итератора ipairs. Но сейчас твоя позиция мне полностью понятна.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Присоединяйтесь к обсуждению

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

Гость
Ответить на вопрос...

×   Вы вставили отформатированное содержимое.   Удалить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отобразить как ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.


×
×
  • Создать...