че там. преподаешь вайб кодинг?
Преподаю троллинг агронубов простыми задачками.
Snusmumriken
Михаил
Snusmumriken
Нет
Михаил
ну ладно
Михаил
так им и надо
Snusmumriken
Это не злобный троллинг, это мозговправлятельный троллинг
Сергей
Дай ему вот такое:
local t = {1, 2, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10, 10, 11}
Скажи что это падает:
for i = 1, #t do
if t[i] % 2 == 0 then
table.remove(t, i)
end
end
А это неправильно удаляет, пропуская элементы под удаление идущие подряд:
for i, v in ipairs(t) do
if t[i] % 2 == 0 then
table.remove(t, i)
end
end
print(require'inspect'(t)) --> {1, 2, 3, 5, 7, 7, 9, 10, 11}
-- ^ ^
за удаление элементов во время итерации надо расстреливать
Snusmumriken
за удаление элементов во время итерации надо расстреливать
Не надо, если сделано нормально
Laimadoo
Не надо, если сделано нормально
Самый банальный способ это обратный цикл for. Вполне себе нормально работает с table.remove(tbl, i)
Snusmumriken
Самый банальный способ это обратный цикл for. Вполне себе нормально работает с table.remove(tbl, i)
Это средне-медленный. Не отвратительный но весьма.
Laimadoo
Я через некоторое время кину тот который предпологаю
Snusmumriken
Кстати а какой способ даёт o(n)?
https://github.com/HDPLocust/snus_stuff/blob/555058c73c87aac3541ef01a4474b73f0e361f39/snus_table.lua#L345
Laimadoo
local t = {}
for i = 1, 20 do
t[i] = math.random(1, 10)
end
local function remove(t, func)
local i = 1
local n = 1
while t[i] do
if func(t[i]) then
t[n] = t[i]
if i ~= n then t[i] = nil end
n = n+1
else
t[i] = nil
end
i = i+1
end
return t
end
remove(t, function(v) return v % 2 == 0 end)
for i = 1, #t do
print(i, t[i])
end
Laimadoo
Вот мой варик
Laimadoo
Он прочитал? Если да то смотрим на крутящиеся шестерёнки в голове ))
Он не увидел. Ща решит
Laimadoo
UtoECat
Snusmumriken, а мой вариант норм?
UtoECat
Snusmumriken
Он кинул как раз такой вариант
Чем меньше сдвигов тем хуже.
table.remove — сдвигает все элементы после себя.
Если даже проходить в обратном порядке, хвост постоянно пытается подтянуться до курсора идущего к голове.
Сколько раз удаляем — столько раз каждый элемент хвоста сдвигается.
Если проходить даже прямо, но с двумя курсорами "текущим" и "тем, куда перемещаем текущий элемент на место удалённых" — всё отлично, это вполне O(n)
Laimadoo
Snusmumriken
Если ты хранишь два курсора и сразу перемещаешь элемент к точке где он будет стоять до конца — это ништяк, и фактически всё выполняется за один проход по массиву.
table.remove — проходит по массиву для сдвига остальных элементов на единичку.
UtoECat
Тогда уж с проверкой:
if i ~= n then t[i] = nil end
а, ну да, кронер-кейс закрался.
Но я всё-же сосредоточился на том что стоит вынести в отдельный цикл ниже удаление - так меньше головняка сразу о некорректных удалениях, и меньше проверок в цикле.
Snusmumriken
Laimadoo
Laimadoo
Для об'nil'ения, да, вполне норм.
DeepSeek предложил более простую реализацию:
local function remove_simple(t, func)
local new_t = {}
for _, v in ipairs(t) do
if func(v) then
table.insert(new_t, v)
end
end
return new_t
end
Laimadoo
В том, что реализация проще я согласен
Laimadoo
Но в том, что тут только пространственная сложность O(N)... не согласен
Snusmumriken
DeepSeek предложил более простую реализацию:
local function remove_simple(t, func)
local new_t = {}
for _, v in ipairs(t) do
if func(v) then
table.insert(new_t, v)
end
end
return new_t
end
DeepSeek нифига не экономит память.
Представим что у нас табличка содержит десять миллионов элементов.
Snusmumriken
Лол, я тут решил запустить бенчмарк варианта с table.remove и варианта с двумя курсорами.
Snusmumriken
Laimadoo
DeepSeek нифига не экономит память.
Представим что у нас табличка содержит десять миллионов элементов.
И тогда кирдык лялям кукум
Snusmumriken
Нет, 10 лямов слишком много, не хочу ждать пол часа
Lucky
Лишь бы игры не писать
UtoECat
DeepSeek предложил более простую реализацию:
local function remove_simple(t, func)
local new_t = {}
for _, v in ipairs(t) do
if func(v) then
table.insert(new_t, v)
end
end
return new_t
end
если память не тревожит и массивы небольшие - можно...
реализации что мы со снусом показали, на теоретическом уровне - ровно то-же самое. С единственным нюансом - массив фильтруется сам в себя, вместо нового объекта.
Сергей
до скольки там n
Сергей
1e7?
Laimadoo
Snusmumriken
как оно может настолько сильно отличаться
Как раз из-за внутреннего цикла с table.remove.
UtoECat
то что я показал так же
да, твоя вариант тоже экономный.
А предложение дипсика из сферы жабаскриптеров) У них там вечно всё дублируется)
Snusmumriken
а table.remove точно не за линию работает?
За линию.
Но оно в цикле. И выполняется много раз для каждого элемента.
Линия на линию на линию — уже n^3
Сергей
хочешь сказать второй фильтр не за квадрат тогда работает
Snusmumriken
Ооо, уменьшил до миллиона.
Laimadoo
Snusmumriken
Ооо, уменьшил до миллиона.
Сергей
я просто не понимаю что означает Olog(n)
Snusmumriken
Ой, я наврал, (O)N * log(n), вот так точнее.
UtoECat
я просто не понимаю что означает Olog(n)
это скорее по перемещениям, сколько эоементов было сдвинуто. С каждой итерацией и чем дальше, перемещаться будет всё меньший кусок.
Но проходка по всему массиву каждый раз, да.
Snusmumriken
O(N) может таки кхм)
Если с двумя курсорами — O(N).
Если с table.remove с конца — O(N * log(n) или в худшем случае N^2)
Сергей
как она может быть O(N logN) если за квадрат работает
Snusmumriken
как она может быть O(N logN) если за квадрат работает
Потому что не всё удаляется, часть остаётся. Плюс удалённые объекты не обсчитаны.
Сергей
ну по такой логике можно и сказать что O(N) если ничего не удалится
Snusmumriken
Так и есть.
Snusmumriken
Лучший O(N), худший O(N^2) (точнее меньше но не очень сильно), средний O(N*log(n))
Сергей
Лучший O(N), худший O(N^2) (точнее меньше но не очень сильно), средний O(N*log(n))
вот из каких соображений
Сергей
я так и не понимаю чота
Laimadoo
Ой, я наврал, (O)N * log(n), вот так точнее.
хммм b! это умножение от 1 до b, а как называется когда плюс?
Сергей
ясно телега приказала долго жить
первоапрельский рофл от дурова
Сергей
Сергей
вот примерно так это называется
Сергей
ну это на самом деле O(N^2)
Сергей
поэтому я и не говорю, что будет N^2 операций, а говорю, что будет O(N^2) операций