Czy lepiej ustawić pustą tabelę lub ustawić wszystkie elementy tabeli na zero?

Question

Pytanie o kawałek lua pojawiło się podczas przeglądu kodu, który miałem niedawno. Kod w pytaniu jest przepłukiwanie cache i reinicjalizacji z niektórych danych:

for filename,_ in pairs(fileTable) do 
    fileTable[filename] = nil 
end 

-- reinitialize here 

Czy jest jakiś powód, dla którego powyżej pętli nie powinien zostać zastąpiony z tym?

fileTable = { } 

-- reinitialize here 

Answer 1

Jest to spowodowane zwiększeniem rozmiaru/ponownego obciążenia stołu. Kiedy tabela jest tworzona, jest pusta. Po wstawieniu elementu następuje ponowne uruchomienie, a rozmiar tabeli wzrasta do 1. To samo dzieje się po wstawieniu innego elementu. Reguła jest taka, że ​​tabela jest uprawiana, gdy brakuje miejsca (w tablicy lub części hash), aby pomieścić inny element. Nowy rozmiar to najmniejsza potęga 2, która może pomieścić wymaganą liczbę elementów. Na przykład. rehash pojawia się po wstawieniu elementu, jeśli tabela zawiera elementy 0, 1, 2, 4, 8 itd.

Technika, którą opisujesz, zapisuje te rehy, ponieważ Lua nie zmniejsza tabel. Więc jeśli masz częste operacje wypełniania/spłukiwania, lepiej jest (zgodnie z wydajnością) robić to tak, jak w twoim przykładzie, niż tworzyć pustą tabelę.

Aktualizacja:

mam postawić mały test:

local function rehash1(el, loops) 
    local table = {} 
    for i = 1, loops do 
     for j = 1, el do 
      table[j] = j 
     end 
     for k in ipairs(table) do table[k] = nil end 
    end 
end 

local function rehash2(el, loops) 
    for i = 1, loops do 
     local table = {} 
     for j = 1, el do 
      table[j] = j 
     end 
    end 
end 


local function test(elements, loops) 
    local time = os.time(); 
    rehash1(elements, loops); 
    local time1 = os.time(); 
    rehash2(elements, loops); 
    local time2 = os.time(); 

    print("Time nils: ", tostring(time1 - time), "\n"); 
    print("Time empty: ", tostring(time2 - time1), "\n"); 

end 

Wyniki rzucić ciekawe. Uruchomienie test(4, 10000000) na Lua 5.1 dało 7 sekund dla nils i 10 sekund dla opróżnień. W przypadku stołów większych niż 32 elementy pusta wersja była szybsza (im większy stół, tym większa różnica). test(128, 400000) dał 9 sekund dla nils i 5 sekund dla opróżnień.

Teraz na LuaJIT, gdzie operacje przydziału i gc są stosunkowo powolne, uruchomienie test(1024, 1000000) dało 3 sekundy dla nils i 7 sekund dla opróżnień.

P.S. Zwróć uwagę na różnice w wydajności między zwykłymi Lua i LuaJIT. W przypadku 1024-elementowych tabel, zwykły Lua wykonał 100 000 testowych iteracji w około 20 sekund, LuaJIT wykonał 1 000 000 iteracji przez 10 sekund!

Answer 2

Przydzielanie nową tabelę jest kosztowna operacja w Lua (co jest prawdą dla każdej alokacji obiektów w prawie każdym języku dynamicznym). Dodatkowo, nieustanne "tracenie" nowo utworzonego do GC będzie dodatkowo obciążać wydajność, a także pamięć, ponieważ każda utworzona tabela będzie nadal w pamięci, dopóki GC nie podejmie się jej odebrania.

Technika w twoim przykładzie wymienia te wady na czas wymagany do jawnego usunięcia wszystkich elementów z tabeli. To zawsze będzie zapisywanie w pamięci i, w zależności od ilości elementów, często może być również poprawa wydajności.

Answer 3

Jeśli nie masz dowodów, że jest inaczej, lepiej będzie, jeśli zaufasz zbieraniu śmieci Lua: po prostu stwórz nowy, pusty stolik, kiedy go potrzebujesz.