38

この質問は、 「キーが削除されている間に lua テーブルを安全に反復するにはどうすればよいですか」に似ていますが、明らかに異なります。

概要

Lua 配列 ( から始まる連続した整数であるキーを持つテーブル) が与えられた場合、この配列を反復処理してエントリの一部を削除する1最良の方法は何ですか?

実際の例

Lua 配列テーブルにタイムスタンプ付きのエントリの配列があります。エントリは常に配列の末尾に追加されます ( を使用table.insert)。

local timestampedEvents = {}
function addEvent( data )
  table.insert( timestampedEvents, {getCurrentTime(),data} )
end

ときどきこのテーブルを (順番に) 実行し、特定のエントリを処理して削除する必要があります。

function processEventsBefore( timestamp )
  for i,stamp in ipairs( timestampedEvents ) do
    if stamp[1] <= timestamp then
      processEventData( stamp[2] )
      table.remove( timestampedEvents, i )
    end
  end
end

残念ながら、上記のコードのアプローチでは反復が中断され、一部のエントリがスキップされます。インデックスを手動で歩くよりも、これを行うためのより良い（タイピングは少ないが安全な）方法はありますか：

function processEventsBefore( timestamp )
  local i = 1
  while i <= #timestampedEvents do -- warning: do not cache the table length
    local stamp = timestampedEvents[i]
    if stamp[1] <= timestamp then
      processEventData( stamp[2] )
      table.remove( timestampedEvents, i )
    else
      i = i + 1
    end
  end
end
4

12 に答える 12

47

配列を反復処理し、反復を継続しながら中央からランダムなアイテムを削除する一般的なケース

前から後ろに反復している場合、要素Nを削除すると、反復の次の要素（N + 1）がその位置にシフトダウンされます。（ipairsのように）反復変数をインクリメントすると、その要素はスキップされます。これに対処するには2つの方法があります。

このサンプルデータの使用：

    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反復中に要素を削除するには、次の方法があります。

  1. 後ろから前に繰り返します。

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

  2. ループ変数を手動で制御するため、要素を削除するときにループ変数のインクリメントをスキップできます。

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

配列以外のテーブルの場合は、nextor pairs（の観点から実装されnextます）を使用して繰り返し、削除するアイテムをに設定しますnil。

table.remove呼び出されるたびに後続のすべての要素がシフトするため、N個の削除のパフォーマンスは指数関数的であることに注意してください。多くの要素を削除する場合は、LHFまたはMitchの回答のように、自分でアイテムをシフトする必要があります。

于 2012-09-12T23:47:05.443 に答える
21

table.remove不要なエントリを設定したら、配列を避けて走査しnil、必要に応じて配列を再度走査して圧縮します。

Mud's 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
于 2012-09-13T00:13:40.730 に答える
5

この機能を試してください：

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)関数を for-generator に移動し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

これには、要素を削除せずにループ全体をキャンセルできるという利点があり、すでに「削除する」とマークされている要素をスキップするオプションが提供されます。欠点は、新しいテーブルのオーバーヘッドです。

これらがお役に立てば幸いです。

于 2012-09-15T07:11:24.953 に答える
2

パフォーマンス上の理由から、を使用しないことをお勧めし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

注:これは高速ですが、2 つの注意点があります。

  • 比較的少数の要素を削除する必要がある場合は、より高速です。(保持する必要がある要素に対しては、実質的に機能しません)。
  • 配列は未ソートのままになります。並べ替えられた配列を気にしない場合もあります。その場合、これは便利な「ショートカット」です。

要素の順序を保持したい場合、またはほとんどの要素を保持しないと予想される場合は、Mitch のソリューションを調べてください。これが私と彼の大まかな比較です。https://www.lua.org/cgi-bin/demoで実行したところ、ほとんどの結果は次のようになりました。

[    srekel] elapsed time: 0.020
[     mitch] elapsed time: 0.040
[    srekel] elapsed time: 0.020
[     mitch] elapsed time: 0.040

もちろん、特定のデータによって異なることを覚えておいてください。

テストのコードは次のとおりです。

function test_srekel(mylist)
    local mylist_size = #mylist
    local i = 1
    while i <= mylist_size do
        local value = mylist[i]
        if value == 13 then
            mylist[i] = mylist[mylist_size]
            mylist[mylist_size] = nil
            mylist_size = mylist_size - 1
        else
            i = i + 1
        end
    end

end -- func

function test_mitch(mylist)
    local j, n = 1, #mylist;

    for i=1,n do
        local value = mylist[i]
        if value ~= 13 then
            -- Move i's kept value to j's position, if it's not already there.
            if (i ~= j) then
                mylist[j] = mylist[i];
                mylist[i] = nil;
            end
            j = j + 1; -- Increment position of where we'll place the next kept value.
        else
            mylist[i] = nil;
        end
    end
end

function build_tables()
    local tables = {}
    for i=1, 10 do
      tables[i] = {}
      for j=1, 100000 do
        tables[i][j] = j % 15373
      end
    end

    return tables
end

function time_func(func, name)
    local tables = build_tables()
    time0 = os.clock()
    for i=1, #tables do
        func(tables[i])
    end
    time1 = os.clock()
    print(string.format("[%10s] elapsed time: %.3f\n", name, time1 - time0))
end

time_func(test_srekel, "srekel")
time_func(test_mitch, "mitch")
time_func(test_srekel, "srekel")
time_func(test_mitch, "mitch")
于 2015-03-09T12:28:40.717 に答える
2

単純..

values = {'a', 'b', 'c', 'd', 'e', 'f'}
rem_key = {}

for i,v in pairs(values) do
if remove_value() then
table.insert(rem_key, i)
end
end

for i,v in pairs(rem_key) do
table.remove(values, v)
end
于 2018-11-01T11:54:17.263 に答える
1

並べ替えられた配列の代わりに優先キューを使用することを検討してください。エントリを順番に削除すると、プライオリティ キューは効率的に圧縮されます。

プライオリティ キューの実装例については、次のメーリング リスト スレッドを参照してください: http://lua-users.org/lists/lua-l/2007-07/msg00482.html

于 2012-09-13T12:26:22.357 に答える
0

キューの先頭からのみエントリをシフトするという私の特別なケースでは、次の方法でこれをはるかに簡単に行うことができます。

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

ただし、配列を反復処理し、反復処理を継続しながら途中からランダムな項目を削除するという一般的なケースを処理しないため、これを答えとして受け入れません。

于 2012-09-12T19:22:35.720 に答える
0

ファンクターを使用して、削除する必要がある要素を確認できます。追加の利点は、table.remove を使用しないため、O(n) で完了することです。

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)
于 2017-07-28T11:14:07.637 に答える