Как сформировать лог игроков в онлайне?

[kintser31 0]

Здраствуйте!
У меня на досуге появился вопрос, возможно ли сделать такой список:
дата. время. игрок зашёл/вышел.
20.12 20:10:37 n зашёл (Пример)
Главный аспект это без учета списка чтобы всех подряд писало.

[eu_tomat 2 148]

1 час назад, kintser31 сказал:

возможно ли сделать такой список:
дата. время. игрок зашёл/вышел.
20.12 20:10:37 n зашёл (Пример)
Главный аспект это без учета списка чтобы всех подряд писало.

Теоретически возможно. Практически же ответ зависит от доступных модов и разрешённых на сервере крафтов.

[Anon 25]

Мне в голову пришло две идеи: использовать чатбокс из computronics, или дебаг-карту из opencomputers. Однако идея с чатбоксом оказалась неудачной, он не стал ловить сообщения о подключении игроков, а дебаг-карта требует наличия креатива. 

 

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

Скрытый текст

local component = require ("component")
local computer = require ("computer")
local fs = require ("filesystem")
local dbg = component.debug

----------------------------------------------------

local timezone = 3 -- GMT+3, Moscow

----------------------------------------------------

local function getRealTime ()
    local handle, reason = fs.open ("/tmp/timestamp", "w")
    if not handle then
        error ("failed to open " .. reason)
    end

    handle:close ()
    
    local timestamp = 60*60*timezone + fs.lastModified ("/tmp/timestamp") / 1000
    fs.remove ("/tmp/timestamp")

    return timestamp
end

local function log (format, ...)
    local text = string.format (
        "[%s]: %s", 
        os.date ("%d.%m.%Y, %X", getRealTime ()),
        string.format (format, ...)
    )
    
    print (text)

    local handle, reason = fs.open ("/players.log", "a")
    if not handle then
        error (reason)
    end

    handle:write (text .. "\n")
    handle:close ()
end

local function copyTable (src)
    local copy = {}
    for key, value in pairs (src) do
        copy[key] = value
    end

    return copy
end

local function findRemovedElements (src, res)
    local removedElements = {}

    for srcIndex = 1, #src do
        found = false
        for resIndex = 1, #res do
            if src[srcIndex] == res[resIndex] then
                found = true
                break
            end
        end

        if not found then
            table.insert (removedElements, src[srcIndex])
        end
    end

    return removedElements
end

local function compareTableValues (a, b)
    return {
        removed = findRemovedElements (a, b),
        added = findRemovedElements (b, a)
    }
end

----------------------------------------------------

print ("Press Q to exit")

local running, lastPlayers = true
while running do
    local players = dbg.getPlayers ()

    if lastPlayers then
        local difference = compareTableValues (lastPlayers, players)
        if #difference.added   > 0 then log ("%s joined the game", table.concat (difference.added,   ", ")) end
        if #difference.removed > 0 then log ("%s left the game",   table.concat (difference.removed, ", ")) end
    end

    lastPlayers = copyTable (players)
    
    local eventType, _, key = computer.pullSignal (0)
    if eventType == "key_down" and string.char (key) == "q" then
        running = false
    end 
end

----------------------------------------------------

 

 

Программа работает на OpenOS; Информация о подключении/выходе игроков отобразится на экране и запишется в файл /players.log

Изменено 23 декабря, 2022 пользователем Anon

[eu_tomat 2 148]

В 23.12.2022 в 03:45, Anon сказал:

эта программа подойдёт

В первом приближении, конечно, подойдёт. Но, судя по коду, это лагодром:

• В лог пишется время с точностью до секунды, хотя программа зачем-то уточняет список игроков 20 раз в секунду.
• Время сервера зачем-то запрашивается при каждом вызове функции log, хотя она при очередном обновлении списка может вызываться более одного раза.
• Сравнение списков реализовано крайне неэффективно. При онлайне 20 игроков для оценки изменений в списке потребуется 800 сравнений строк, хотя достаточно было бы лишь 20 раз запросить поле таблицы. Во-первых, два прохода списков не требуются, всё можно сделать за один проход. Во-вторых, ассоциативные свойства таблиц позволяют отказаться от перебора одной из таблиц в длинном цикле, тем самым ускорив поиск нужного значения.

 

[Anon 25]

7 минут назад, eu_tomat сказал:

В первом приближении, конечно, подойдёт. Но, судя по коду, это лагодром:

• В лог пишется время с точностью до секунды, хотя программа зачем-то уточняет список игроков 20 раз в секунду.
• Время сервера зачем-то запрашивается при каждом вызове функции log, хотя она при очередном обновлении списка может вызываться более одного раза.
• Сравнение списков реализовано крайне неэффективно. При онлайне 20 игроков для оценки изменений в списке потребуется 800 сравнений строк, хотя достаточно было бы лишь 20 раз запросить поле таблицы. Во-первых, два прохода списков не требуются, всё можно сделать за один проход. Во-вторых, ассоциативные свойства таблиц позволяют отказаться от перебора одной из таблиц в длинном цикле, тем самым ускорив поиск нужного значения.

 

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

Допустим, я бы ограничил частоту проверки игроков до 1 раза в секунду. Что программа будет делать остальные 950 миллисекунд?

Что ж, замечания у тебя делать получается, а вот твоего варианта программы всё нет. С нетерпением жду эффективный вариант, который, уверен, пригодится ОП, а эффективный метод сравнения таблиц я возьму себе на заметку

[eu_tomat 2 148]

2 минуты назад, Anon сказал:

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

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

 

14 минуты назад, Anon сказал:

если бы среди задач программы была производительность

Автор вопроса вообще не ставил никаких задач, он просто спросил, возможно ли это сделать. Я ответил, что теоретических ограничений нет. Ты продемонстрировал, что это возможно практически. Тут всё чётко.

 

Но до тех пор, пока кому-нибудь не придёт в голову установить эту программу на публичный сервер. Потенциальные пользователи должны знать, что это лагодром.

 

31 минуту назад, Anon сказал:

Что ж, замечания у тебя делать получается, а вот твоего варианта программы всё нет. С нетерпением жду эффективный вариант, который, уверен, пригодится ОП, а эффективный метод сравнения таблиц я возьму себе на заметку

Программы нет потому, что писать её я и не собирался. А для тех, кто вдруг соберётся, я и дал свои замечания. Я допускаю, что недостаточно чётко сформулировал свои мысли. Скажи, что именно тебе не ясно. Как избавиться от двух проходов при сравнении списков, или как уменьшить количество сравнений за счёт использования ассоциативных свойств таблиц? Что из этого нуждается в иллюстрации кодом?

[prop 19]

>lastPlayers = copyTable (players)
Копировать не надо, getPlayers() всегда возвращает новую таблицу

[eu_tomat 2 148]

9 минут назад, prop сказал:

Копировать не надо, getPlayers() всегда возвращает новую таблицу

Вызов component.debug.getPlayers выполняется за один такт времени. И за это время список пользователей может измениться. То есть, действуя таким образом, мы можем терять события.

[eu_tomat 2 148]

В 24.12.2022 в 17:40, Anon сказал:

Что ж, замечания у тебя делать получается, а вот твоего варианта программы всё нет. С нетерпением жду эффективный вариант, который, уверен, пригодится ОП, а эффективный метод сравнения таблиц я возьму себе на заметку

Вот более эффективный вариант сравнения таблиц игроков. При среднем онлайне 20 игроков такой способ сравнения выполняется в 3-4 раза быстрее твоего решения в лоб.

---------- конвертация предыдущего списка
lastPlayers = {}
for i=1, #players do
  lastPlayers[players[i]] = true
end
---------- получение текущего списка
players = getPlayers()
difference = { removed={}, added={} }
---------- поиск игроков, зашедших на сервер
for i, player in ipairs(players) do
  if lastPlayers[player] then
    lastPlayers[player] = nil
  else
    table.insert( difference.added, player )
  end
end
---------- поиск игроков, покинувших сервер
for player in pairs(lastPlayers) do
  table.insert( difference.removed, player )
end

Это, скорее всего, не предел. Чисто алгоритмически потенциал для дальнейшего ускорения имеется, но удастся ли реализовать его именно на языке Lua, на вскидку я сказать не могу.

[Anon 25]

3 минуты назад, eu_tomat сказал:

Вот более эффективный вариант сравнения таблиц игроков. При среднем онлайне 20 игроков такой способ сравнения выполняется в 3-4 раза быстрее твоего решения в лоб.

---------- конвертация предыдущего списка
lastPlayers = {}
for i=1, #players do
  lastPlayers[players[i]] = true
end
---------- получение текущего списка
players = getPlayers()
difference = { removed={}, added={} }
---------- поиск игроков, зашедших на сервер
for i, player in ipairs(players) do
  if lastPlayers[player] then
    lastPlayers[player] = nil
  else
    table.insert( difference.added, player )
  end
end
---------- поиск игроков, покинувших сервер
for player in pairs(lastPlayers) do
  table.insert( difference.removed, player )
end

Это, скорее всего, не предел. Чисто алгоритмически потенциал для дальнейшего ускорения имеется, но удастся ли реализовать его именно на языке Lua, на вскидку я сказать не могу.

 

Ну вот, другое дело! Возьму алгоритм на заметку

[prop 19]

Скрытый текст

local component = require "component"
local dbg = component.debug

local lastPlayers = {}
local curr = {}

local function loop()
    local players = dbg.getPlayers()

    for _,v in ipairs(players) do
        curr[v] = 1
        if not lastPlayers[v] then 
            print("conn", v) 
        end
        lastPlayers[v] = nil
    end

    for k,_ in pairs(lastPlayers) do
        print("disc", k)
    end

    lastPlayers = curr
    curr = {}
end

while true do 
  loop()
  os.sleep(0)
end

 

 

 

Изменено 27 декабря, 2022 пользователем prop

[eu_tomat 2 148]

5 часов назад, prop сказал:

Опять какие-то экспериментальные данные, если разговор идет про алгоритмы, то использовать надо нормальные метрики.

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

 

5 часов назад, prop сказал:

Переписали O(n^2) в O(2n), малацы

Нет, не так. Доступ по ключу требует операций побольше чем O(n). Ускорение мы получили как за счёт уже оптимизированных алгоритмов поиска по хэш-таблицам, так и за счёт их реализации на языке низкого уровня. Какая там фактическая метрика, проверять я не планирую.

 

5 часов назад, prop сказал:

> в 3-4 раза
Опять какие-то экспериментальные данные, если разговор идет про алгоритмы, то использовать надо нормальные метрики.

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

 

5 часов назад, prop сказал:

> При онлайне 20 игроков для оценки изменений в списке потребуется 800 сравнений строк
Данные получены экспериментальным способом?

Нет. Это чисто умозрительная оценка. В эксперименте будет меньшее количество. Скорее всего, в 2 раза, т.к. автор кода останавливает поиск после обнаружения нужного значения. Судя по коду от @Anon, среднее количество составит 20*20/2*2. То есть, 400 сравнений, а не 800. Это я лишку хватил.

 

5 часов назад, prop сказал:

Ниче не понял. В особенности как это относится к тому, что я сказал.

Это я тебя не понял, поэтому возникла путаница. Согласен, копирование таблицы в алгоритме @Anon излишне.

 

5 часов назад, prop сказал:

Какой-то потанцевал точно есть потому что ты два раза по списку игроков проходишься.

Да, замечание верное. Но это мелкая оптимизация и, возможно, даже преждевременная. А танцевать, мне кажется, можно гораздо дальше. Нужен другой алгоритм.

 

5 часов назад, prop сказал:

> чисто алгоритмически
> потанцевал
Потанцевал существует только алгоритмически или аналитически тоже?

Алгоритмически, аналитически... Вбрасывая какую-либо идею на форуме, я далеко не всегда погружаюсь в глубокий анализ. Например, когда я делал замечания по коду товарища @Anon, я не имел какого-либо кода. В мыслях у меня был не алгоритм и не код, а нечто смутное вроде: этот процесс заменяем другим и получаем ускорение. И анализа в его привычном смысле также не было. Было стойкое чувство, основанное на опыте использования ассоциативных массивов в Lua.

 

Говоря же про имеющийся потенциал, я не то что не мог провести анализ, я даже алгоритм не сформулировал. У меня была лишь смутная картинка в виде пляшущих строк из двух таблиц, пытающихся совместиться друг с другом. И видеть эту картинку я мог, лишь находясь в состоянии полусна, когда аналитическое мышление притупляется, но память ещё позволяет что-то запомнить. За сутки эта смутная картинка превратилась в более-менее оформленный набор тезисов. Если ты готов к спокойному восприятию этой ещё не до конца сформулированной идеи, слушай:

 

В большинстве случаев сравниваемые списки будут полностью идентичны друг другу. И для подтверждения этого факта в случае среднего онлайна 20 игроков будет достаточно выполнить лишь 20 сравнений строк. Правда, при наличии сортировки в таблицах. Скорее всего, ещё быстрее будет работать проверка количества игроков и тупое сравнение результатов table.concat. Но даже если таблицы отличаются, то в большинстве случаев не сильно. При обнаружении отличия надо лишь определить, строки какой из двух таблиц следует сдвинуть, и на сколько. А после вычисления размера сдвига можно продолжить линейное сравнение. Задача чем-то похожа на вывод различий строк двух текстовых файлов. Она, наверное, даже проще, т.к. в текстовые файлы могут быть добавлены огромные блоки строк, а списки игроков не успевают меняться настолько интенсивно.

 

Что нам может помочь? Для начала надо проверить, не отсортированы ли уже списки игроков, возвращаемые отладочной платой. Даже если сортировка отсутствует, можно воспользоваться встроенной сортировкой Lua. Предполагаю, что она будет выполняться заметно быстрее, чем используемое мной формирование ассоциативного массива в цикле. А он в новом алгоритме не потребуется. Уже хороший размен.

[eu_tomat 2 148]

В 26.12.2022 в 22:02, eu_tomat сказал:

За сутки эта смутная картинка превратилась в более-менее оформленный набор тезисов.

Алгоритм стал предельно ясным после выбора модели входящих данных. Модель выбрана такая: изменения в списке игроков маловероятны. Поэтому нет смысла использовать какие-либо сложные оптимизации алгоритма. Достаточно выполнять линейное сравнение записей в двух отсортированных таблицах. При обнаружении различий в очередной паре строк нет смысла в использовании сложных алгоритмов поиска совпадения. Достаточно сдвинуть одну из таблиц на одну строку и двигаться дальше. С большой вероятностью следующая пара строк совпадёт.

 

После всех этих упрощений у меня получился такой код:

-- старый и новый списки строк
local old, new = {}, {}
-- текущие позиции в списках и их размер
local o, n, oo, nn = 0,0, 0,0
-- списки добавленных и удалённых строк
local add, rmv = {}, {}
-- и их фактические размеры
local a, r

while true do
  -- обновить список игроков
  old, oo = new, nn
  new = genNextTable()
  nn = #new
  table.sort(new)
  -- установить на первую запись текущие позиции в старом и новом списках
  o, n = 1, 1
  -- очистить списки добавленных и удалённых записей.
  a, r = 0, 0
  -- основной цикл обработки таблиц
  ::_continue::
    -- Если исчерпан старый список, весь остаток записей из нового копируем в добавленные
    if o > oo then
      for n = n, nn do
        a = a + 1
        add[a] = new[n]
      end
      goto _break
    end
    -- Если исчерпан новый список, весь остаток записей из старого копируем в удалённые
    if n > nn then
      for o = o, oo do
        r = r + 1
        rmv[r] = old[o]
      end
      goto _break
    end
    -- Если текущие записи в старом и новом списках совпали, пропускаем их обработку
    if old[o] == new[n] then
      o = o + 1
      n = n + 1
      goto _continue
    end
    -- Если запись в старом списке меньше чем в новом, то её следует скопировать в удалённые
    if old[o] < new[n] then
      r = r + 1
      rmv[r] = old[o]
      o = o + 1
      goto _continue
    -- Если запись в новом списке меньше чем в старом, то ее следует скопировать в добавленные
    else
      a = a + 1
      add[a] = new[n]
      n = n + 1
      goto _continue
    end
  ::_break::
end

Переход на линейный алгоритм сравнения таблиц, а также различные мелкие оптимизации позволили ускорить вычисления в 1.5-2 раза, а по итогу (в сравнении с реализацией от @Anon) в 5-6 раз. Для таблиц размером 20 записей.

 

@prop Вот теперь имеющийся потенциал полностью растанцован, и оснований для дальнейшего значимого улучшения я уже не вижу даже смутно. Возможно, получится сделать ещё какие-либо мелкие оптимизации. Но сейчас у меня глаз замылен, поэтому я с радостью выслушаю любые предложения.

 

@prop Судя по всему, ты лучше меня разбираешься в теме алгоритмической сложности. Растолкуй, как её правильно посчитать применительно к моему коду.