Удаление элементов в больших таблицах.

Страницы: 1
RSS
Удаление элементов в больших таблицах., Крайне медленная работа table.remove и возможные обходные пути для быстрого удаления большого числа элементов крупных массивов/таблиц.
 
Столкнулся с проблемой - скрипты "падают" из-за нехватки памяти. В одной из них формируется несколько сотен таблиц, в каждую из которых два раза в секунду добавляется новые элемент (история бид, оффер и сделок, подробнее см. https://forum.quik.ru/forum10/topic2958/). Я пришел к выводу, что без удаления "старых" исторических значений из этих таблиц в течение сессии / одного запуска не обойтись. Однако, обнаружилось, что это очень затратная по ресурсам / времени процедура для которой я не вижу удобных альтернатив.
Стандартный подход - использовать table.remove. Однако, он дает возможность удалять только один элемент, при удалении первых элементов в массиве, многократно меняются индексы всех последующих элементов, что требует много времени. Так удаление первых 5 тысяч элементов таблицы с 10 тыс. полей заняло у меня 6,5 сек. - непозволительно долго.
Пример кода:
local ElemToKeep = 5000
tab1 = tabInit (1000000)
while #tab1 > ElemToKeep do
table.remove (tab1,1)
end

Есть обходные пути.
Можно использовать простое удаление элементов, например, так:
--local numElement = #tab2
--local toremove = numElement - ElemToKeep
--for k = 1, toremove, 1 do
--tab2[k] = nil
--end
Работа такого кода происходит гораздо быстрее (приблизительно в 2 тысячи раз в упомянутых условиях!). Однако, если мы удалим элементы в начале таблицы, например, с 1 по 2000, мы не сможем использовать их перебор через  ipairs, и хуже того, мы не сможем оперативно посчитать число элементов в таблице с использованием #. Их число можно будет получить только путем перебора с вставкой счетчика в цикл pairs.
Можно изголяться дальше в этом направлении. Например, каждый раз вставлять новые элементы в таблицу с использованием table.insert и присваивать им индекс 1, сдвигая все остальные в конец. Это решит проблему с ipairs, # и подсчетом элементов - достаточно будет обрезать "хвост" массива/таблицы, индексы будут начинаться с единицы и будут идти без пробелов. Однако, такой подход означает, что мы все равно выполняем ресурсозатратную процедуру (переименование индексов) -- с меньшей потерей времени, но чаще (при каждом добавлении нового элемента).
Есть ли у кого-то пример эффективного решения подобной проблемы?
 
Пока что вижу для себя такое решение -- формируем временную таблицу куда записываем только те элементы большой таблицы, которые нужно сохранить. Затем ставим знак равенства между большой нуждающейся в "обрезке" таблицей и временным вариантом (второй вариант, см. код ниже). Быстрее стандартного варианта в несколько сотен раз.


function tabInit (number)
local tab ={}
for i =1,number do
tab[i]=i
end
return tab
end

function tabCount2 (Thetab)
local count = 0
for k,v in ipairs (Thetab) do
count = count+1
end
return count
end


-- ОЦЕНКА ПРОИЗВОДИТЕЛЬНОСТИ
local ElemToKeep = 5000
tab1 = tabInit  (10000)
tab2 = tabInit    (10000)

-- Первая реализация
local start = os.clock()
while #tab1 > ElemToKeep do
table.remove (tab1,1)
end
local ne1 = tabCount2 (tab1)
local finish1 = os.clock()
local time1 = finish1 - start
message (tostring(time1).."-"..tostring(ne1))

-- Вторая реализация
local tempTab = {}
local numElement = #tab2
local startElement = numElement - ElemToKeep + 1
local minus = numElement - ElemToKeep

for i=startElement, numElement do
tempTab[i-minus] = tab2[i]
end
tab2 = tempTab
local ne2 = tabCount2 (tab2)
local finish2 = os.clock()
local time2 = finish2 - finish1
message (tostring(time2).."-"..tostring(ne2))

У меня на машине обрезка первым способом заняла 1,69 сек, а вторым - 0,002 сек.
 
Иван Ру,

вам действительно нужно хранить в памяти все эти десятки тысяч записей?
Я понимаю, когда речь идет о текущей итерации скрипта, но ведь вы храните даже не агрегированные данные, а непосредственно данные по сделкам. Какой в этом смысл, если сделка прошла, условно говоря, 15 минут назад, а за это время вы получили еще 5000 сделок? Если вам необходимо сохранять эти сделки для последующей обработки сторонним приложением, так пишите их сразу в файл, но не сохраняйте в памяти.
Все же мое мнение со стороны (оно может быть ошибочным): необходимо оптимизировать логику скрипта как такового, "облегчая" его.
 
Цитата
Andrei2016 написал:
Иван Ру  ,

вам действительно нужно хранить в памяти все эти десятки тысяч записей?
Я понимаю, когда речь идет о текущей итерации скрипта, но ведь вы храните даже не агрегированные данные, а непосредственно данные по сделкам. Какой в этом смысл, если сделка прошла, условно говоря, 15 минут назад, а за это время вы получили еще 5000 сделок? Если вам необходимо сохранять эти сделки для последующей обработки сторонним приложением, так пишите их сразу в файл, но не сохраняйте в памяти.
Все же мое мнение со стороны (оно может быть ошибочным): необходимо оптимизировать логику скрипта как такового, "облегчая" его.
Это не принципиально - т.к. речь о проблеме кодинга и языка.
Есть ли нужда в таком? Не скажу что критичная, но есть -- данные нужны для оперативного подсчета средних значений, и не по барам, а за произвольный период. Причем этот подсчет должен производиться максимально быстро.
 
Судя по написанному, Вам нужно реализовать в своём скрипте циклический буфер (кольцевой буфер) на базе массиве.

https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BB%D1%8C%D1%86%D0%B5%D0%B2%D0%BE%D0­%B9_%D0%B1%D1%83%D1...

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

Пример реализации на lua (не ручаюсь за качество): https://gist.github.com/johndgiese/3e1c6d6e0535d4536692
 
Цитата
Иван Ру написал:
Пока что вижу для себя такое решение -- формируем временную таблицу куда записываем только те элементы большой таблицы, которые нужно сохранить. Затем ставим знак равенства между большой нуждающейся в "обрезке" таблицей и временным вариантом (второй вариант, см. код ниже). Быстрее стандартного варианта в несколько сотен раз.


function tabInit (number)
local tab ={}
for i =1,number do
tab=i
end
return tab
end

function tabCount2 (Thetab)
local count = 0
for k,v in ipairs (Thetab) do
count = count+1
end
return count
end


-- ОЦЕНКА ПРОИЗВОДИТЕЛЬНОСТИ
local ElemToKeep = 5000
tab1 = tabInit  (10000)
tab2 = tabInit    (10000)

-- Первая реализация
local start = os.clock()
while #tab1 > ElemToKeep do
table.remove (tab1,1)
end
local ne1 = tabCount2 (tab1)
local finish1 = os.clock()
local time1 = finish1 - start
message (tostring(time1).."-"..tostring(ne1))

-- Вторая реализация
local tempTab = {}
local numElement = #tab2
local startElement = numElement - ElemToKeep + 1
local minus = numElement - ElemToKeep

for i=startElement, numElement do
tempTab[i-minus] = tab2
end
tab2 = tempTab
local ne2 = tabCount2 (tab2)
local finish2 = os.clock()
local time2 = finish2 - finish1
message (tostring(time2).."-"..tostring(ne2))

У меня на машине обрезка первым способом заняла 1,69 сек, а вторым - 0,002 сек.
У вас ошибка в подсчете времени
вы включили в него время подсчета числа элементов - local ne2 = tabCount2 (tab2)
кроме того вместо удаления одного элемента можно удалять например половину копированием в новый массив и переприсвоением
время будет таким же как во втором случае
local ElemToKeep = 5000
local N=10000
--Новая  реализация
tab1 = tabInit  (N)
local tempTab = {}
local numElement = #tab1
local startElement = numElement - ElemToKeep
start = os.clock()
for i=1, ElemToKeep do tempTab[i] = tab1[startElement+i] end
tab1 = tempTab
time1 = os.clock() - start
ne1 = tabCount2 (tab1)
print ("Новая="..tostring(time1)..";"..tostring(ne1))
------------------
Первая=1.682;5000
Вторая=0.00099999999999989;5000
Новая=0.0010000000000001;5000
 
в рассмотренных примерах для удаления данных требуется создание еще одной таблицы
можно уменьшить требуемый объем памяти если переписывать данные в туже таблицу а в конце ставить nil
при этом методе надо после записи последнего элемента записывать nil
например так:
--Новая  реализация 2
tab1 = tabInit  (N)
numElement = #tab1
startElement = numElement - ElemToKeep + 1
minus = numElement - ElemToKeep
start=hrt.clock()
for i=1, ElemToKeep do  tab1[i] = tab1[startElement+i]  end
tab1[ ElemToKeep+1] =nill
time=t_mcs(hrt.clock()-start)
ne1 = tabCount2 (tab1)
print ("Новая2="..time..";"..ne1)
--------------------------

для точного измерения времени исполнения надо отключать сборщик мусора
----------------
в итоге получим следующий результат время в  мс:
Первая=1.661;5000
Вторая=0.777;5000
Новая1=0.758;5000
Новая2=0.704;4999
>Exit code: 0
 
исправлено:
--------------------------
-Новая  реализация 2
tab1 = tabInit  (N)
numElement = #tab1
startElement = numElement - ElemToKeep
minus = numElement - ElemToKeep
start=hrt.clock()
for i=1, ElemToKeep do  tab1[i] = tab1[startElement+i]  end
tab1[ ElemToKeep+1] =nill
time=t_mcs(hrt.clock()-start)
ne1 = tabCount2 (tab1)
print ("Новая2="..time..";"..ne1)
--------------------------
Первая=1.566;5000
Вторая=0.783;5000
Новая1=0.756;5000
Новая2=0.718;5000
>Exit code: 0
Страницы: 1
Читают тему (гостей: 1)
Наверх