11 Veri Yapıları

11 Veri Yapıları

Lua'da tablolar veri yapılarından BİRİ değil; VERİ YAPISIDIR. Diğer dillerin sunduğu tüm yapılar —diziler, kayıtlar, listeler, kuyruklar, kümeler— (array, record, list, queue, set) Lua tablolarıyla temsil edilebilir. Daha da önemlisi Lua tabloları tüm bu yapıları verimli bir şekilde uygular.

C ve Pascal gibi geleneksel dillerde diziler ve listelerle (listeler = kayıtlar + işaretçiler) çoğu veri yapısını uygularız. Lua tabloları kullanarak diziler ve listeleri uygulayabilsek de (ve bazen bunu yaparız) tablolar, diziler ve listelerden daha güçlüdür; birçok algoritma tabloların kullanımı ile önemli derecede basitleşir. Örneğin Lua'da nadiren bir arama yazarız çünkü tablolar herhangi tipte direkt erişim sunar.

Tabloları verimli bir şekilde nasıl kullanılacağını öğrenmek biraz zaman alır. Burada tipik veri yapılarını tablolarla nasıl uygulayacağımızı göstereceğim ve kullanımlarına ilişkin bazı örnekler sunacağım. Diziler ve listelerle başlayacağız çünkü diğer yapılar için onlara ihtiyacımız yok ama çoğu programcı zaten onlara aşina. Dille ilgili bölümlerde bu materyalin temellerini zaten gördük ancak tamlık için burada tekrarlayacağım.

11.1 Diziler

tabloları tam sayılarla indeksleyerek Lua'da dizileri basitçe uygularız. Velhasıl, dizilerin sabit bir boyu yoktur ama ihtiyaç kadar büyür. Genellikle, diziyi ilklediğimizde boyunu dolaylı olarak tanımlarız. Örneğin aşağıdaki koddan sonra 1-1000 aralığı dışındaki bir alana erişmek için herhangi bir girişim sıfır yerine nil döndürecek:

a = {} -- yeni dizi
for i = 1, 1000 do
    a[i] = 0
end

Bir dizinin boyunu bulmak için uzunluk operatörünün ('#') şu imkanı kullanılır:

print(#a) --> 1000

bir dizi indeksini 0, 1 veya başka herhangi bir değerle başlatabilirsiniz:

-- -5den 5'e indeksli bir dizi yarat
a = {}
for i = -5, 5 do
    a[i] = 0
end

Bununla birlikte Lua'da dizileri 1 indeksiyle başlatmak gelenekseldir. Lua kütüphaneleri bu düzene uymaktadır; uzunluk operatörü de öyle. Dizileriniz 1 ile başlamazsa bu imkanları kullanamazsınız.

Tek bir ifadede dizileri yaratmak ve ilklemek için bir oluşturucu kullanabiliriz:

tamKare = {1, 4, 9, 16, 25, 36, 49, 64, 81}

Bu tür kurucular ihtiyacınız olduğu kadar büyük olabilir (birkaç milyon öğeye kadar).

11.2 Matrisler ve çok boyutlu diziler

Lua'da matrisleri temsil etmenin iki ana yöntemi vardır. Birincisi, bir dizilerin dizisi yani her öğenin başka bir tablo olduğu bir tablo kullanmak. Örneğin aşağıdaki kodla M N boyutlu sıfır matrisi oluşturabilirsiniz:

mt = {} -- matris yarat
for i = 1, N do
    mt[i] = {} -- yeni bir satır yarat
    for j = 1, M do
        mt[i][j] = 0
    end
end

Tablolar Lua'da nesneler olduğundan, bir matris oluşturmak için açıkça her satırı oluşturmanız gerekir. Bir taraftan, bu, C veya Pascal'da yaptığınız gibi sadece bir matris deklare edilmesinden kesinlikle daha ayrıntılı. Öteki taraftan, size daha fazla esneklik sağlar. Örneğin, önceki örnekteki for j=1,i do...end 'i , for j=1,M do...end döngüsüne çevirerek üçgen matris oluşturabilirsiniz. Bu kodla Üçgen matris orjinalinin sadece yarısı kadar bellek kullanır.

Lua'da bir matrisi temsil etmenin ikinci yöntemi, iki indeksi tek bir indeksle oluşturmaktır. İki indeks tamsayı ise, birincisini uygun bir sabitle çarpabilir ve ikinci indekse ekleme yapabilirsiniz. Bu yaklaşımla, aşağıdaki kod sıfır matrisimizi M N boyutlarına göre oluşturacaktır:

mt = {} -- matris yarat
for i = 1, N do
    for j = 1, M do
        mt[(i - 1) * M + j] = 0
    end
end

indeksler string ise, onları ayırmak için aralarında bir karakterle her iki indeksi birleştiren tek bir indeks oluşturabilirsiniz. Örneğin, m[s..":"..t] kodu ile  t ve s string indeksleri ile bir m matrisini indeksleyebilirsiniz, hem s hem de t'nin : içermemesi koşuluyla; aksi takdirde, (“a:”,“b”) ve (“a”,“:b”) gibi çiftleri tek bir indekse getirme “a::b” suya düşer. Şüpheniz olduğunda, indeksleri ayırmak için ‘\0’ gibi bir kontrol karakteri kullanabilirsiniz.

Çoğu zaman, uygulamalar bir matris olarak çoğu öğesi 0 veya nil olan  seyrek(sparse) matris kullanır. Örneğin, bir graf'ı(graph) komşu(adjacency) matris ile temsil edebilirsiniz, m ve n düğümlerinin cost x ile ilişkilendirildiğinde; bu düğümler bağlı olmadığında, m, n konumdaki değer nildir. Her düğümün yaklaşık beş komşusu olan on bin düğüm içeren bir graf'ı temsil etmek için, yüz milyon girişi olan bir matrise (10000 sütunlu ve 10000 satırlı bir kare matris ) ihtiyacınız olacak, ancak yaklaşık elli bin tanesi nil olmayacak (her bir düğümün beş komşusuna karşılık gelen her satır için beş nil olmayan sütun). Veri yapılarına ilişkin birçok kitap, 400 Megabayt belleği boşa harcamadan bu tür seyrek matrislerin nasıl uygulanacağını uzun uzuna tartışır, ancak Lua'da programlama yaparken bu tekniklere ihtiyacınız yoktur. Diziler tablolar ile temsil edildiğinden, doğal olarak seyrektir. İlk temsilimiz (tabloların tabloları) ile, her biri yaklaşık beş elemana sahip on bin tabloya, toplamda elli bin girdiye ihtiyacınız olacak. İkinci temsil ile, içinde elli bin giriş bulunan tek bir tabloya sahip olacaksınız. Temsil ne olursa olsun, yalnızca nil olmayan öğeler için alana ihtiyacınız var. 

Aktif girişler arasındaki delikler(nil değerleri) nedeniyle, uzunluk operatörünü seyrek matrisler üzerinde kullanamayız. Bu büyük bir kayıp değil; yapabilsek bile yapmamalıyız. Çoğu işlem için, tüm bu boş girişleri dolaşmak oldukça verimsiz olurdu. Bunun yerine, yalnızca nil olmayan öğeleri dolaşmak için pairs'i kullanabiliriz. Örneğin, bir satırı bir sabitle çarpmak için aşağıdaki kodu kullanabiliriz:

function mult(a, rowindex, k)
    local row = a[rowindex]
    for i, v in pairs(row) do
        row[i] = v * k
    end
end

Tabi, anahtarların tabloda herhangi içsel sıralamaya sahip olmadığına dikkat, bu nedenle pairs'le iterasyon, sütunları artan düzende ziyaret etmemizi sağlamaz. Bazı görevler için (önceki örneğimiz gibi), bu bir problem değil. Diğer görevler için,  alternatif bir yaklaşıma ihtiyacınız olabilir, misal bağlı listeler .

11.3 Bağlı Listeler

Tablolar dinamik öğeler olduğundan, Lua'da bağlı listelerin uygulanması kolaydır. Her düğüm bir tabloyla temsil edilir ve bağlantılar diğer tablolara referanslar içeren tablo alanlarıdır. Örneğin, her düğümün iki alana, sonraki ve deger'e sahip olduğu temel bir listeyi uygulamak için, liste kökü olarak bir değişken oluştururuz:

list = nil

Listenin başına bir öğe eklemek için, deger v ile, şunu yaparız:

list = {sonraki = list, deger = v}

Listeyi dolaşmak için şunu yazarız:

local l = list
while l do
    <l.deger ziyareti>
    l = l.sonraki
end

Çift bağlı listeler veya çember listeler gibi diğer listeler de kolayca uygulanır. Tabi, nadiren Lua'da bu yapılara gereksinirsiniz çünkü genellikle bağlı listeleri kullanmadan verilerinizi temsil etmenin daha basit yolu var. Örneğin, (sınırsız) bir diziyle bir yığını(stack) temsil edebiliriz

11.4 Kuyruklar ve Çift Kuyruklar

Lua 'da kuyrukları uygulamanın basit yolu insert ve remove fonksiyonlarıyladır (table kütüphanesinden) . Bu fonksiyonlar, bir dizinin herhangi bir pozisyonuna öğe ekler ve çıkarır, bu işleme mütakip diğer öğeleri taşır. Bununla birlikte, bu taşıma büyük yapılar için masraflı olabilir.

Daha verimli bir uygulama, biri ilk öğe için, diğeri sonuncu için, iki indeks kullanmaktır:

function ListNew()
    return {first = 0, last = -1}
end

genel alanı kirletmekten kaçınmak için, List olarak adlandırılan bir tablonun içinde tüm liste işlemlerini tanımlayacağız (yani, bir modül oluşturacağız). Bu nedenle, son örneğimizi şu şekilde yeniden yazıyoruz:

List = {}
function List.new()
    return {first = 0, last = -1}
end

Artık, vefalı bir sürede her iki uca da bir eleman yerleştirebilir veya kaldırabiliriz:

function List.pushfirst(list, value)
    local first = list.first - 1
    list.first = first
    list[first] = value
end

function List.pushlast(list, value)
    local last = list.last + 1
    list.last = last
    list[last] = value
end

function List.popfirst(list)
    local first = list.first
    if first > list.last then
        error("liste boş")
    end
    local value = list[first]
    list[first] = nil -- çöp toplamaya imkan vermek için
    list.first = first + 1
    return value
end

function List.poplast(list)
    local last = list.last
    if list.first > last then
        error("liste boş")
    end
    local value = list[last]
    list[last] = nil -- çöp toplamaya imkan vermek için
    list.last = last - 1
    return value
end

Bu yapıyı sıkı bir kuyruk disiplininde kullanırsanız, yalnızca pushlast ve popfirst çağırarak, hem first hem de last sürekli artacak. Ancak, Lua'da dizileri tablolarla temsil ettiğimizden bunları 1 ila 20 veya 16777216 ile 16777236 arasında indeksleyebilirsiniz. Lua sayıları temsil etmek için çift hassasiyet kullandığından programınız iki yüz yıl çalışabilir ve taşmalarla ilgili sorunlar yaşamadan saniyede bir milyon ekleme yapabilir.

11.5 Kümeler ve Torbalar(Bag)

Bir programın kaynak kodunda kullanılan tüm tanımlayıcıları listelemek istediğinizi varsayalım;

bir şekilde reserve kelimeleri listenizden filtrelemeniz gerekiyor. Bazı C programcılarına, reserve sözcük kümesini bir stringler dizisi olarak temsil etmek ve daha sonra belli bir kelimenin kümede olup olmadığını öğrenmek için bu diziyi aramak cazip gelebilir. Aramayı hızlandırmak için kümeyi temsil etmek üzere ikili ağaç(binary tree) bile kullanabilirler.

Lua'da bu tür kümeleri temsil etmenin verimli ve basit yolu,  bir tabloya indeksler olarak kümenin öğelerini koymaktır. Ardından belirli bir öğe için tabloyu aramak yerine sadece tabloyu indeksleyip sonucun nil olup olmadığını test edersiniz. Örneğimizde, sıradaki kodu şöyle yazabiliriz:

reserved = {
    ["while"] = true, ["end"] = true,
    ["function"] = true, ["local"] = true,
}
   
for w in allwords() do
   if not reserved[w] then
      <'w' ile birseyler yap> -- ’w’ reserve bir kelime değil
   end
end

(Bu kelimeler Lua'da reserve olduğu için tanımlayıcılar olarak kullanamazsınız; örneğin, while=true yazamayız. Bunun yerine, ["while"]=true notasyonunu kullanıyoruz.)

kümeyi oluşturmak için yardımcı bir fonksiyon kullanarak daha net bir ilkleme olabilir:

function Set(list)
    local set = {}
    for _, l in ipairs(list) do
        set[l] = true
    end
    return set
end

reserved = Set{"while", "end", "function", "local", }

Multiset(çoklu küme) olarak da adlandırılan torbalar, her bir öğenin birden çok kez görünebileceği normal kümelerden farklılığıdır. Lua'da torbalar için kolay temsil, kümeler için önceki temsile benzer, ama her bir anahtar ile bir sayaç ilişkilendiririz. Bir öğe eklemek için sayacını arttırıyoruz:

function insert(bag, element)
    bag[element] = (bag[element] or 0) + 1
end

Bir öğeyi kaldırmak için sayacını azaltıyoruz:

function remove(bag, element)
    local count = bag[element]
    bag[element] = (count and count > 1) and count - 1 or nil
end

hali hazırda var ve hala sıfırdan büyükse sayacı olduğu gibi tutuyoruz.

11.6 String Tamponları

Parça parça bir string oluşturduğunuzu varsayalım, örneğin satır satır bir dosya okuyorsunuz. Tipik kodunuz şöyle görünür:

local buff = ""
for line in io.lines() do
    buff = buff .. line .. "\n"
end

Masum görünümüne rağmen, Lua'daki bu kod büyük dosyalar için büyük bir performans sıkıntısına neden olabilir: örneğin, 350 Kilobaytlık bir dosyayı okumak neredeyse bir dakika sürer.

Niye? Olanı anlamak için, okuma döngüsünün ortasında olduğumuzu varsayalım; her satır 20 bayt ve hazırda 2500 satırlık okuma yaptın, bu yüzden buff 50 kilobaytlık bir string oldu. Lua, buff..line.."\n" birleştirmesini yaptığında 50020 baytlık yeni bir string oluşturur ve buff'den 50000 bayt bu yeni stringe kopyalar. Yani, her yeni satır için Lua 50 kilobaytlık belleğe ulaşır, ve büyür de büyür. 100 yeni satır okuduktan sonra (sadece 2 kilobaytlık), Lua hazırda 5 megabayt bellekten fazlasına ulaşmış. Daha da önemlisi, algoritma kuadratik. Lua 350 kilobaytlık okumayı bitirdiğinde 50 gigabayt'dan fazlasına ulaşmış olur.

Bu sorun Lua'a özgü değil: stringlerin değişmez değerli olduğu diğer diller de, Java en ünlü örnek, benzer bir davranış sunar.

Devam etmeden önce, söylediğim her şeye rağmen, bu durumun genel bir sorun olmadığını belirtmeliyiz. Küçük stringler için yukarıdaki döngü iyidir. Tüm dosyayı okumak için, Lua, bikerede dosyayı okuyan, io.read("*all") seçeneğini sağlar. Bununla birlikte, bazen bu problemle yüzleşmeliyiz. Java,  sorunu iyileştirmek için StringBuffer yapısını sunar. Lua'da, string tamponu olarak tablo kullanabiliriz. Bu yaklaşımın anahtarı, verilen bir listenin tüm stringlerini birleştirimişini döndüren , table.concat fonksiyonudur. concat'ı kullanarak aşağıdaki gibi önceki döngüyü yazabilirsiniz:

local t = {}
for line in io.lines() do
    t[#t + 1] = line .. "\n"
end
local s = table.concat(t)

Bu algoritma, orijinal kodla okuması neredeyse bir dakika süren dosya için 0,5 saniyeden daha az sürede okuma yapar. (Tabii ki, bütün bir dosyayı okumak için “*all” seçeneğiyle io.read'i kullanmak daha iyi.)

Daha iyisini yapabiliriz. concat fonksiyonu, stringler arasına eklenecek bir ayırıcı olacak isteğe bağlı bir ikinci argüman kabul eder. Bu ayırıcıyla, her satırdan sonra "\n" eklememiz gerekmez:

local t = {}
for line in io.lines() do
    t[#t + 1] = line
end
s = table.concat(t, "\n") .. "\n"

concat fonksiyonu stringler arasına ayırıcı ekler ancak yine de son "\n" eklememiz gerekir.

Bu son birleştirme, oldukça uzun olabilen nihai stringi çoğaltır. Bu ekstra ayırıcıyı concat ile eklemek için bir seçenek yok ancak onu aldatabiliriz, t'e ekstra boş bir string ekleyebiliriz:

t[#t + 1] = ""
s = table.concat(t, "\n")

İstediğimiz gibi, nihai stringinin sonundaki bu boş stringden önce concat ekstra "\n" ekler.

İçsel olarak, hem concat hem de io.read("*all") birçok küçük stringi birleştirmek için aynı algoritmayı kullanır. Standart kütüphanelerden diğer bazı fonksiyonlar da bu algoritmayı büyük stringler oluşturmak için kullanır. Nasıl çalıştığına bir göz atalım.

Orjinal döngümüz, sorunu çözmek için bir depo içinde tek tek küçük stringleri birleştirdiği,  doğrusal bir yaklaşım almıştı. Bu yeni algoritma bir ikili yaklaşımı kullanarak sıkıntıları önler. içlerindeki küçük stringleri birleştirir ve ortaya çıkan büyük stringleri diğer büyüklerle birleştirir. Algoritmanın kalbi olan yığın, alt kısmında hazırda oluşturulmuş büyük stringleri tutar ; küçük stringler üstten girer. Bu yığının ana değişmezi, popüler(programcılar arasında en azından) Hanoi kulesine  benzer:

yığındaki bir string asla daha kısa bir string üzerinde bulunamaz. Yeni bir string daha kısa bir string üzerine konulduğunda, algoritma ikisini birleştirir(sadece o zaman). Bu birleştirme, artık, önceki kattaki komşusundan daha büyük olabilecek daha büyük bir string oluşturur. Bu olursa, onlar da birleştirilir. Bu birleştirmeler, döngü daha büyük bir stringe veya yığının alt kısmına ulaşıncaya kadar yığının altına doğru iner.

function addString(stack, s)
    stack[#stack + 1] = s -- yığına ’s’ 'i koy
    for i = #stack - 1, 1, -1 do
        if #stack[i] > #stack[i + 1] then
            break
        end
        stack[i] = stack[i] .. stack[i + 1]
        stack[i + 1] = nil
    end
end

Tamponun nihai içeriğini elde etmek için tüm stringleri aşağıya doğru birleştiriyoruz.

11.7 Graph

Herhangi bir makul dil gibi, Lua graf'lar için, her biri belli algoritmalara daha iyi adapte olan, birden fazla uyarlamaya imkan verir. Burada, düğümleri nesneler (aslında tablolar elbette) ve düğümler arasında referanslar olarak yayları temsil ettiğimiz basit bir nesne yönelimli uyarlama göreceğiz.

Liste 11.1. bir dosyadan graf okuma:

function readgraph()
    local graph = {}
    for line in io.lines() do
        -- satırı iki isme böl
        local namefrom, nameto = string.match(line, "(%S+)%s+(%S+)")
        -- uyan düğümleri bul 
        local from = name2node(graph, namefrom)
        local to = name2node(graph, nameto)
        -- ’from’ 'nın bitişik kümesine 'to' 'u ekle
        from.adj[to] = true
    end
    return graph
end

Her bir düğümü iki alana sahip bir tablo olarak temsil edeceğiz: name, düğümün adı; ve adj, buna bitişik düğümler kümesi. Bir metin dosyasından graf'ı okuyacağımız için, adı verilen bir düğümü bulmak için bir yola ihtiyacımız var. Mamafi, düğümlerle isimleri eşlemek için ekstra bir tablo kullanacağız. verilen bir isimle(name), name2node fonksiyonu karşılık gelen düğümü döndürür:

local function name2node(graph, name)
    if not graph[name] then
        -- düğüm yok; yeni bir tane yarat
        graph[name] = {name = name, adj = {}}
    end
    return graph[name]
end

Liste 11.1 bir graf oluşturan fonksiyonu gösterir. bir dosya okur, her satır , ilk düğümden ikincisine bir yay olduğu anlamına gelen iki düğüm adına sahiptir. Her satır için, satırı iki ada bölmek için string.match kullanır, bu adlara karşılık gelen düğümleri bulur (gerekirse düğümleri oluşturur) ve düğümleri bağlar.

Liste 11.2 bu tür graf'ı kullanan bir algoritma göstermektedir. findpath fonksiyonu, Depth-first search (DFS - derin arama)  kullanarak iki düğüm arasında bir yol arar. İlk parametresi geçerli düğümdür; ikincisi hedeftir; üçüncü parametre orijinden geçerli düğüme yolu tutar; son parametre, hazırda ziyaret edilen (döngülerden kaçınmak için) tüm düğümlerin bir kümesidir. Algoritmanın, adlarını kullanmadan düğümleri doğrudan nasıl manipüle ettiğine dikkat. Örneğin, visited , düğümlerin kümesi, düğümlerin adları değil. Benzer şekilde, path düğümlerin listesidir.

Liste 11.2. iki node arasında yolu bulma:

function findpath(curr, to, path, visited)
    path = path or {}
    visited = visited or {}
    if visited[curr] then -- hazırda düğüm ziyaret edildi mi?
        return nil -- burada yol yok
    end
    visited[curr] = true -- düğümü ziyaret edildi olarak işaretle
    path[#path + 1] = curr -- yola onu ekle
    if curr == to then -- final düğüm?
        return path
    end
    -- tüm bitişik düğümleri dene
    for node in pairs(curr.adj) do
        local p = findpath(node, to, path, visited)
        if p then
            return p
        end
    end
    path[#path] = nil -- yoldan düğümü çıkar
end

Bu kodu test etmek üzere,  path'i(yolu) yazdıracak bir fonksiyon ekliyor, tüm çalışmaları bir araya getiriyoruz:

function printpath(path)
    for i = 1, #path do
        print(path[i].name)
    end
end

g = readgraph()
a = name2node(g, "a")
b = name2node(g, "b")
p = findpath(a, b)
if p then printpath(p) end