Безопасное удаление элементов из таблицы массивов во время итерации

Ответ 1

общий случай итерации по массиву и удаление случайных элементов из середины, продолжая итерацию

Просто используйте table.remove. Однако, если вы повторяете фронт-к-назад, когда вы удаляете элемент N, следующий элемент вашей итерации (N + 1) сместится вниз в эту позицию. Если вы увеличиваете свою итерационную переменную (как это делает ipairs), вы пропустите этот элемент. Мы можем с этим справиться.

Использование этих данных:

    input = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p' }
    remove = { f=true, g=true, j=true, n=true, o=true, p=true }

Мы можем удалить элементы input во время итерации:

• Итерация с обратной стороны.

  for i=#input,1,-1 do
      if remove[input[i]] then
          table.remove(input, i)
      end
  end
  

• Управление переменной цикла вручную, поэтому мы можем пропустить ее при удалении элемента:

  local i=1
  while i <= #input do
      if remove[input[i]] then
          table.remove(input, i)
      else
          i = i + 1
      end
  end
  

Для таблиц без массива вы выполняете итерацию с использованием next или pairs (которая реализована в терминах next) и устанавливайте элементы, которые вы хотите удалить, на nil.

Ответ 2

Я бы избегал table.remove и проходил массив после установки ненужных записей в nil, а затем пересекал массив, снова уплотняя его, если это необходимо.

Вот код, который я имею в виду, используя пример из Mud answer:

local input = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p' }
local remove = { f=true, g=true, j=true, n=true, o=true, p=true }

local n=#input

for i=1,n do
        if remove[input[i]] then
                input[i]=nil
        end
end

local j=0
for i=1,n do
        if input[i]~=nil then
                j=j+1
                input[j]=input[i]
        end
end
for i=j+1,n do
        input[i]=nil
end

Ответ 3

Попробуйте эту функцию:

function ripairs(t)
    -- Try not to use break when using this function;
    -- it may cause the array to be left with empty slots
    local ci = 0
    local remove = function()
        t[ci] = nil
    end
    return function(t, i)
        --print("I", table.concat(array, ','))
        i = i+1
        ci = i
        local v = t[i]
        if v == nil then
            local rj = 0
            for ri = 1, i-1 do
                if t[ri] ~= nil then
                    rj = rj+1
                    t[rj] = t[ri]
                    --print("R", table.concat(array, ','))
                end
            end
            for ri = rj+1, i do
                t[ri] = nil
            end
            return
        end
        return i, v, remove
    end, t, ci
end

Он не использует table.remove, поэтому он должен иметь сложность O(N). Вы можете переместить функцию remove в генератор-генератор, чтобы удалить потребность в upvalue, но это будет означать новое замыкание для каждого элемента... и это не практическая проблема.

Пример использования:

function math.isprime(n)
    for i = 2, n^(1/2) do
        if (n % i) == 0 then
            return false
        end
    end
    return true
end

array = {}
for i = 1, 500 do array[i] = i+10 end
print("S", table.concat(array, ','))
for i, v, remove in ripairs(array) do
    if not math.isprime(v) then
        remove()
    end
end
print("E", table.concat(array, ','))

Соблюдайте осторожность, чтобы не использовать break (или иначе выходить преждевременно из цикла), поскольку он оставит массив с элементами nil.

Если вы хотите, чтобы break означал "прервать" (как и в, ничего не удалено), вы можете сделать это:

function rtipairs(t, skip_marked)
    local ci = 0
    local tbr = {} -- "to be removed"
    local remove = function(i)
        tbr[i or ci] = true
    end
    return function(t, i)
        --print("I", table.concat(array, ','))
        local v
        repeat
            i = i+1
            v = t[i]
        until not v or not (skip_marked and tbr[i])
        ci = i
        if v == nil then
            local rj = 0
            for ri = 1, i-1 do
                if not tbr[ri] then
                    rj = rj+1
                    t[rj] = t[ri]
                    --print("R", table.concat(array, ','))
                end
            end
            for ri = rj+1, i do
                t[ri] = nil
            end
            return
        end
        return i, v, remove
    end, t, ci
end

Это имеет то преимущество, что можно отменить весь цикл без удаления элементов, а также предоставить возможность пропускать элементы, уже отмеченные как "подлежащие удалению". Недостатком является накладные расходы новой таблицы.

Я надеюсь, что они вам полезны.

Ответ 4

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

Пример реализации очереди приоритетов см. в этом списке рассылки: http://lua-users.org/lists/lua-l/2007-07/msg00482.html

Ответ 5

Я также рекомендую не использовать table.remove по причинам производительности (что может быть более или менее актуальным для вашего конкретного случая).

Вот какой тип этого цикла обычно выглядит для меня:

local mylist_size = #mylist
local i = 1
while i <= mylist_size do
    local value = mylist[i]
    if value == 123 then
        mylist[i] = mylist[mylist_size]
        mylist[mylist_size] = nil
        mylist_size = mylist_size - 1
    else
        i = i + 1
    end
end

Обратите внимание, что это изменит порядок элементов в массиве.

Если вы хотите сохранить порядок элементов, вы можете использовать table.remove, и я делаю это следующим образом:

local mylist_size = #mylist
local i = 1
while i <= mylist_size do
    local value = mylist[i]
    if value == 123 then
        table.remove(mylist, i)
    else
        i = i + 1
    end
end

Ответ 6

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

function processEventsBefore( timestamp )
  while timestampedEvents[1] and timestampedEvents[1][1] <= timestamp do
    processEventData( timestampedEvents[1][2] )
    table.remove( timestampedEvents, 1 )
  end
end

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

Ответ 7

Вы можете использовать функтор для проверки элементов, которые необходимо удалить. Дополнительный коэффициент усиления заключается в том, что он завершается в O (n), поскольку он не использует table.remove

function table.iremove_if(t, f)
    local j = 0
    local i = 0
    while (i <= #f) do
        if (f(i, t[i])) then
            j = j + 1
        else
            i = i + 1
        end
        if (j > 0) then
            local ij = i + j
            if (ij > #f) then
                t[i] = nil
            else
                t[i] = t[ij]
            end
        end
    end
    return j > 0 and j or nil -- The number of deleted items, nil if 0
end

Использование:

table.iremove_if(myList, function(i,v) return v.name == name end)

В вашем случае:

table.iremove_if(timestampedEvents, function(_,stamp)
    if (stamp[1] <= timestamp) then
        processEventData(stamp[2])
        return true
    end
end)