Snusmumriken
че там. преподаешь вайб кодинг?
Преподаю троллинг агронубов простыми задачками.
Михаил
Snusmumriken
Нет
Михаил
ну ладно
Михаил
так им и надо
Snusmumriken
Это не злобный троллинг, это мозговправлятельный троллинг
Laimadoo
Не надо, если сделано нормально
Самый банальный способ это обратный цикл 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
Вот мой варик
UtoECat
Snusmumriken, а мой вариант норм?
у вас вот этой строчки не хватает, без неё не до конца очищается массив без/c но вариант когда очистка отдельным циклом в конце - лучше.
UtoECat
у вас вот этой строчки не хватает, без неё не до конца очищается массив без/c но вариант когда очистка отдельным циклом в конце - лучше.
я по-старинке на while накидал...) у снуса оно компактнее. function remove_odd(arr) local i = 1 local j = 1 local n = #arr -- shift valid elements to the start up to j-1 while i <= n do if arr[i] % 2 == 0 then arr[j] = arr[i] j = j + 1 end i = i + 1 end -- delete all elements after j, including j while n >= j do arr[n] = nil n = n - 1 end end
Snusmumriken
Он кинул как раз такой вариант
Чем меньше сдвигов тем хуже. table.remove — сдвигает все элементы после себя. Если даже проходить в обратном порядке, хвост постоянно пытается подтянуться до курсора идущего к голове. Сколько раз удаляем — столько раз каждый элемент хвоста сдвигается. Если проходить даже прямо, но с двумя курсорами "текущим" и "тем, куда перемещаем текущий элемент на место удалённых" — всё отлично, это вполне O(n)
Laimadoo
Тогда уж с проверкой: if i ~= n then t[i] = nil end
Snusmumriken
?
При использовании table.remove.
Snusmumriken
Если ты хранишь два курсора и сразу перемещаешь элемент к точке где он будет стоять до конца — это ништяк, и фактически всё выполняется за один проход по массиву. table.remove — проходит по массиву для сдвига остальных элементов на единичку.
UtoECat
Тогда уж с проверкой: if i ~= n then t[i] = nil end
а, ну да, кронер-кейс закрался. Но я всё-же сосредоточился на том что стоит вынести в отдельный цикл ниже удаление - так меньше головняка сразу о некорректных удалениях, и меньше проверок в цикле.
Snusmumriken
Ну вот типа да. На "перемещения из точки на ту же точку" можно забить, это ерунда, в сравнении со скрытым циклом в table.remove.
Snusmumriken
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
Сижу жду
Snusmumriken
Нет, 10 лямов слишком много, не хочу ждать пол часа
Laimadoo
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
если память не тревожит и массивы небольшие - можно... реализации что мы со снусом показали, на теоретическом уровне - ровно то-же самое. С единственным нюансом - массив фильтруется сам в себя, вместо нового объекта.
Laimadoo
Лишь бы игры не писать
Лёгкий (хотя для кого как) дефамин получать хочется
Сергей
Сижу жду
как оно может настолько сильно отличаться
Сергей
до скольки там n
Сергей
1e7?
Snusmumriken
как оно может настолько сильно отличаться
Как раз из-за внутреннего цикла с table.remove.
Сергей
Сижу жду
а table.remove точно не за линию работает?
UtoECat
то что я показал так же
да, твоя вариант тоже экономный. А предложение дипсика из сферы жабаскриптеров) У них там вечно всё дублируется)
Snusmumriken
а table.remove точно не за линию работает?
За линию. Но оно в цикле. И выполняется много раз для каждого элемента. Линия на линию на линию — уже n^3
Laimadoo
а table.remove точно не за линию работает?
Ну смотри считай из-за table.remove - o(n^2)
Сергей
хочешь сказать второй фильтр не за квадрат тогда работает
Snusmumriken
Ооо, уменьшил до миллиона.
Snusmumriken
Ооо, уменьшил до миллиона.
Всего полторы минуты считал то что можно посчитать за сотую секунды.
Сергей
я просто не понимаю что означает Olog(n)
Laimadoo
я просто не понимаю что означает Olog(n)
Это как поиск с помощью деления на 2
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))
Сергей
я так и не понимаю чота
Laimadoo
Ой, я наврал, (O)N * log(n), вот так точнее.
хммм b! это умножение от 1 до b, а как называется когда плюс?
Сергей
ясно телега приказала долго жить первоапрельский рофл от дурова
Сергей
ну типа че эта
Сергей
вот примерно так это называется
Laimadoo
b*(b+1) / 2 :D
Вот так и запишем O(N + N*(N+1)/2)
Сергей
ну это на самом деле O(N^2)
Сергей
10 + 55 = 100?
никак нет, сэр
Сергей
поэтому я и не говорю, что будет N^2 операций, а говорю, что будет O(N^2) операций