Lua 테이블 처리 기법

Lua는 높은 효율성을 자랑하며, 이 중 테이블 구현이 큰 역할을 했습니다. Lua의 테이블은 배열과 해시 맵의 두 가지 기능을 동시에 제공하므로, 이러한 특성을 고려하여 배열로 사용할 때도 효율 감소를 최소화하도록 설계되었습니다.

Lua는 테이블을 배열 부분과 해시 부분으로 나눕니다. 숫자 키는 일반적으로 배열 부분에 저장되며, 초기화되지 않은 키 값은 nil로 설정됩니다. 숫자 키가 너무 흩어져 있을 경우 일부 큰 숫자 키는 해시 부분으로 이동될 수 있습니다. 이 경계는 배열 부분의 사용률이 최소 50% 이상이라는 기준으로 정해집니다. 또한 0과 음수 키는 무조건 해시 부분에 저장됩니다.

문자열과 숫자 모두 해시에 포함되며 각각 다른 알고리즘을 사용하지만 결과는 동일한 범위 내에 위치합니다. 해시 부분은 폐쇄 해싱 방법을 사용하며, 충돌이 발생하면 빈 슬롯에 추가 정보를 기록하여 추가 공간 할당 없이 해결합니다. 테이블이 가득 차면 해시 부분이 확장되고 모든 항목이 다시 해싱되어 충돌이 크게 줄어듭니다.

이러한 테이블 구조는 검색 효율성을 우선시합니다. 배열로 사용할 때는 C 배열과 비슷한 성능을 보이며, 해시 부분에서는 해시 값을 계산하는 것 만으로 대부분의 검색이 이루어집니다. 충돌이 발생할 경우 약간의 추가 시간이 소요되지만 공간 낭비는 크게 없습니다. 테이블이 가득 찬 상태에서 삽입이 발생하면 빈 슬롯을 찾기 위해 순차적으로 검색하며, 각 슬롯은 다음 포인터로 충돌된 키 간 연관성을 유지합니다.

다음은 몇 가지 예제입니다.

local tbl = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,6}
for i = 1, 20 do
    tbl[i] = nil
    table.insert(tbl, 20)
end
for i = 1, 30 do
    print(tbl[i])
end
-- 출력 결과:
-- 20
-- 20
-- 20
-- 20
-- nil
-- nil
-- nil
-- nil
-- nil
-- nil
-- nil
-- nil
-- nil
-- nil
-- nil
-- nil
-- nil
-- nil
-- nil
-- nil
-- 1
-- 1
-- 1
-- 1
-- 6
-- 20
-- 20
-- 20
-- 20
-- 20

또 다른 예제:

for startIdx = 1, 10 do
    local tbl = {}
    for j = startIdx, 15 do
        tbl[j] = j
    end
    table.insert(tbl, "InsertedValue")
    local tblStr = ""
    for i = 1, 16 do
        if tbl[i] == nil then
            tblStr = tblStr .. "nil" .. " | "
        else
            tblStr = tblStr .. tbl[i] .. " | "
        end
    end
    print("StartIndex = " .. startIdx .. ", The Table = " .. tblStr)
end
-- 출력 결과:
-- StartIndex = 1, The Table = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | InsertedValue | 
-- StartIndex = 2, The Table = nil | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | InsertedValue | 
-- StartIndex = 3, The Table = nil | nil | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | InsertedValue | 
-- StartIndex = 4, The Table = nil | nil | nil | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | InsertedValue | 
-- StartIndex = 5, The Table = nil | nil | nil | nil | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | InsertedValue | 
-- StartIndex = 6, The Table = nil | nil | nil | nil | nil | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | InsertedValue | 
-- StartIndex = 7, The Table = nil | nil | nil | nil | nil | nil | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | InsertedValue | 
-- StartIndex = 8, The Table = InsertedValue | nil | nil | nil | nil | nil | nil | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | nil | 
-- StartIndex = 9, The Table = InsertedValue | nil | nil | nil | nil | nil | nil | nil | 9 | 10 | 11 | 12 | 13 | 14 | 15 | nil | 
-- StartIndex = 10, The Table = InsertedValue | nil | nil | nil | nil | nil | nil | nil | nil | 10 | 11 | 12 | 13 | 14 | 15 | nil |

태그: Lua Table hashing Array

8월 19일 07:46에 게시됨

괴물 클럽

Lua 테이블 처리 기법

인기 태그