Fonksiyonel Dillerde Ağaç Veri Yönetimi: Zipper Tekniği
Fonksiyonel Dillerde Ağaç Veri Yönetimi Fonksiyonel Dillerde Ağaç Veri Yönetimi kapsamında, Ağaç yapılı verilerle çalışırken genellikle belirli bir düğüme gitmemiz ve onu değiştirmemiz gerekir. Zorunlu dillerde, değişken durum ve ana işaretçiler sayesinde bu genellikle basittir. Ancak…
Fonksiyonel Dillerde Ağaç Veri Yönetimi
Fonksiyonel Dillerde Ağaç Veri Yönetimi kapsamında, Ağaç yapılı verilerle çalışırken genellikle belirli bir düğüme gitmemiz ve onu değiştirmemiz gerekir. Zorunlu dillerde, değişken durum ve ana işaretçiler sayesinde bu genellikle basittir. Ancak işlevsel dillerde değişmezlik bu modeli daha az belirgin hale getirir.
Fonksiyonel Dillerde Ağaç Veri Yönetimi kapsamında, Bu yazıda, fermuar adı verilen bir teknik kullanarak ağaç yapılarında işlevsel dillerde verimli bir şekilde nasıl gezinileceğini ve değiştirileceğini keşfedeceğiz. Basit JSON sorgu dili Basit bir JSON sorgu aracı uyguladığımızı varsayalım. Dil, bir JSON nesnesindeki değerlere erişmemize ve bunları değiştirmemize olanak tanır. Sorgu dilinin dört basit işlemi vardır: yolu ayarla = değer — yoldaki değeri değiştirin.
Fonksiyonel Dillerde Ağaç Veri Yönetimi kapsamında, yolu al – yoldaki değeri okuyun. sorgu | sorgu — soldan sağa iki sorgu çalıştırın. at path { query } – imleci bir yola taşıyın ve o düğüme göre bir sorgu çalıştırın. Zorunlu bir ortamda, JSON’u ana işaretçilere sahip bir ağaç olarak temsil edebilir, bu da gezinmeyi (hem aşağı hem de yukarı) önemsiz hale getirebiliriz.
Tasarım ve teknik ayrıntılar
Fonksiyonel Dillerde Ağaç Veri Yönetimi kapsamında, Haskell gibi işlevsel bir dilde, genellikle ebeveyn işaretçilerinden kaçınırız çünkü bunları değişmezlik altında doğru şekilde sürdürmek zordur. Bunun yerine farklı bir yaklaşıma ihtiyacımız var.
Fonksiyonel Dillerde Ağaç Veri Yönetimi kapsamında, Örnek Aşağıdaki JSON nesnesine sahip olduğumuzu varsayalım: { “bir”:{ “b”:{ “x”:1, “y”:2 } } } Aynı şeyi yapan ancak sözdizimleri farklı olan aşağıdaki iki sorgumuz var: set .a.b.x = 42 | .a.b.y = 43’ü .a.b’de ayarlayın { .x = 42 olarak ayarlayın | .y = 43’ü ayarlayın } at bloğunun içinde yollar .a.b’ye göredir. Blok bittiğinde imleç önceki konumuna döner.
Fonksiyonel Dillerde Ağaç Veri Yönetimi kapsamında, Bu örneği Haskell’de güncelleme işlemlerini uygulamanın iki yolunu karşılaştırmak ve ağaç veri yapısında verimli bir şekilde gezinmek ve değiştirmek için fermuarların nasıl kullanılacağını karşılaştırmak için kullanacağız. Ağaçlarda Gezinme ve Değiştirme Kalıcı veri yapısı Haskell’de veri yapıları genellikle değişmezdir.
Bugünden bakınca ne kadar güvenilir?
Fonksiyonel Dillerde Ağaç Veri Yönetimi kapsamında, Bir ağaçtaki bir düğümü değiştirmek için, değişmeyen düğümleri orijinal ağaçla paylaşırken, değiştirilen düğümü içeren yeni bir ağaç oluşturmamız gerekir. Buna kalıcı veri yapısı denir.
Fonksiyonel Dillerde Ağaç Veri Yönetimi kapsamında, Minimal bir ağaç türü tanımlıyoruz: veri Ağacı = Atom Dahili | Nesne [(Dize, Ağaç)] türetme (Göster) Örnek değer: kök :: Ağaç root = Object [(“a”, Object [(“b”, Object [(“x”, Atom 1), (“y”, Atom 2)])])] Birinci Yaklaşım: Kök Tabanlı İlk sorgu seti .a.b.x = 42 | set .a.b.y = 43, hedef düğüme erişilip onu değiştirerek, ardından değiştirilmiş kök düğüm aracılığıyla başka bir hedef düğüme erişerek ve onu yeniden değiştirerek uygulanabilir.
Fonksiyonel Dillerde Ağaç Veri Yönetimi kapsamında, Bir düğüme erişmek için, kökten hedef düğüme giden yolu yinelemeli olarak takip ederiz ve yol boyunca yinelemeli olarak yeni düğümler yaratırız. Değişmeyen düğümler orijinal ağaç ile yeni ağaç arasında paylaşılır. Erişim işlevi tarafından değiştirilen düğümlerin sayısı O(derinlik(düğüm))’dür; burada derinlik(düğüm), ağaçtaki hedef düğümün derinliğidir.
Okuyucu için pratik anlamı
Fonksiyonel Dillerde Ağaç Veri Yönetimi kapsamında, erişim :: [Strin g] -> (Ağaç -> Ağaç) -> Ağaç -> Ağaç erişim [] f t = f t erişim (k : ks) f (Nesne ts) | let (önce, dinlenme) = mola ((== k) . fst) ts , ((_, v) : sonra) <- dinlenme = let değiştirilmişChild = erişim ks f v Object'te (++'dan önce (k, değiştirilmişChild) : sonra) erişim _ _ _ = hata "Geçersiz erişim yolu" Yol boş olduğunda, f değiştirme fonksiyonunu geçerli düğüme uygularız.
Fonksiyonel Dillerde Ağaç Veri Yönetimi kapsamında, Aksi takdirde, k anahtarına sahip çocuğu buluruz, kalan yolla ona geri döneriz ve geçerli düğümü değiştirilen çocukla yeniden oluştururuz. Maliyet, değişiklik başına O(derinlik(düğüm)) yeni düğümdür.
Erişim örneği “x” düğümünü erişim [“a”, “b”, “x”] (const $ Atom 42) kökü ile 42’ye değiştirdiğimizi varsayalım, yeni ağaç ve orijinal ağaç aşağıdaki gibi görünecektir: Diyagramda, ağaç_a, “a” anahtarına sahip kök düğümün çocuğu olan bir Ağaç düğümünü temsil eder. Tree_a’, ağaç_a’nın değiştirilmiş alt düğümü “x” ile değiştirilmiş bir sürümüdür.
Kök’, orijinal kök düğümün değiştirilmiş düğümlerle değiştirilmiş bir versiyonudur. Tree_b’ de öyle. Diyagramdan, değiştirilmiş “x” düğümünün 42 değerine sahip yeni bir düğüm olduğunu ve onun ana düğümü “b”nin aynı zamanda değişmemiş alt düğümü “y”yi orijinal ağaçla paylaşan yeni bir düğüm olduğunu görebiliriz.
Sorgu yürütme Sorgunun tamamı aşağıdaki Haskell koduna çevrilebilir: ( erişim [“a”, “b”, “y”] (const $ Atom 43) . erişim [“a”, “b”, “x”] (const $ Atom 42) ) kök kümesi .a.b.x = 42 transladır Bir ağacı alıp yeni bir ağaç döndüren bir işlev olarak değerlendirilen [“a”, “b”, “x”] (const $ Atom 42) erişimine erişim sağlandı. | operatörü, fonksiyon bileşimine çevrilir, yani . Haskell’de.
İki erişim işlevi bir araya getirilir ve elde edilen işlev, değiştirilmiş ağacı elde etmek için orijinal ağaç köküne uygulanır. Sorguda N değişiklik varsa, değiştirilen toplam düğüm sayısı O(N * derinlik(ağaç)) olur. Birbirine yakın modifikasyonlar için bu, birçok gereksiz modifikasyona yol açabilir. Örneğimizde “a” ve “b” düğümleri iki kez değiştirilmiştir, bu da verimsizdir.
İkinci yaklaşım: imleç tabanlı .a.b adresindeki sorgu { set .x = 42 | set .y = 43 } ağaçtaki belirli bir düğüme odaklanmamızı ve odaklanılan düğümü kök düğüm olarak kullanarak bir sorgu yürütmemizi sağlayan bir imleç sunar. at sorgusu, Fermuarlar adı verilen bir teknik kullanılarak uygulanabilir. Fermuarlar Fermuarlar, ağaçlar gibi kalıcı veri yapılarında gezinmek ve bunları değiştirmek için güçlü bir tekniktir.
Bir düğüme erişmek için her zaman kök düğüme dönmemize gerek kalmadan, bir ana düğüme veya belirli bir alt düğüme çok daha verimli bir şekilde gitmemize olanak tanırlar.
veri Fermuar = Fermuar { odak :: Ağaç , ekmek kırıntıları :: [Kırıntı] } veri Kırıntı = Kırıntı { önce :: [(Dize, Ağaç)] , delikKey :: String , sonra :: [(Dize, Ağaç)] } Bir Fermuar aşağıdakilerden oluşur: o anda odaklanılmış olan tre e düğümü, kökten geçerli düğüme giden yolu saklayan içerik kırıntılarının listesi. Bir Kırıntı, bir Ağacın kaldırılması dışında bir Ağaca benzer; en son indiğimiz düğümdür.
HoleKey, kaldırılan düğümün anahtarını saklar, önce önceki kardeşleri içerir ve sonra aşağıdaki kardeşleri içerir. emptyZipper :: Ağaç -> Fermuar emptyZipper t = Fermuar t [] Köke odaklanan bir Fermuar oluşturuyoruz: Diyagramda odak düğümü orijinal kök düğümle aynı değere sahip ve kök düğümde olduğumuz için kırıntı yığını boş.
Aşağı git goDown :: String -> Fermuar -> Fermuar goDown k (Fermuar (Nesne ts) bs) | (l, (_, v) : r) <- break ((== k) .fst) ts = Fermuar v (Kırıntı l k r : bs) goDown k (Zipper f _) = error $ "Ağaçtaki '' alt öğeye gidilemiyor'" ++ k ++ "': " ++ show f Aşağıya doğru hareket etmek, yeni odak düğümü haline gelen hedef alt öğeyi çıkararak üst düğümden bir Kırıntı oluşturur. Kırıntı daha sonra kırıntı yığınına itilir.
“a”ya indiğimizde, Fermuar aşağıdaki gibi görünecektir: Diyagramda, kırıntı_0, kırıntı yığınındaki en üstteki Kırıntıdır. HoleKey, “a” düğümünün kök düğümden uzaklaştırıldığını ve “a”nın kardeşi olmadığı için önceki ve sonraki alanların boş olduğunu belirtir. Odak düğümü, orijinal ağaçtaki “a” düğümüyle aynıdır. Daha sonra “b”ye gidin: Odak düğümü, yukarıdaki “b” ile aynıdır. e orijinal ağaç.
Kırıntı_1, ağaç_a’ya benzer, ancak “b” düğümü alınır ve HoleKey alanıyla gösterilen bir delik ile değiştirilir. Öncesi ve sonrası alanları boş. Şimdi “x”e indiğimizde, Fermuar aşağıdaki gibi görünecektir: Yeni eklenen kırıntı_2, “x” düğümünün “b” düğümünden alındığını ve “y” düğümünün “x”in kardeşi olduğunu, dolayısıyla Kırıntının sonraki alanında depolandığını gösterir.
Odak düğümü orijinal ağaçtaki “x” düğümüyle aynıdır. Odak değişikliği Şimdi “x” değerini 42 olarak değiştiriyoruz. Odak düğümünde yalnızca değiştirme işlevini çağırıyoruz: changeZipper :: (Ağaç -> Ağaç) -> Fermuar -> Fermuar changeZipper f (Zipper t bs) = Fermuar (f t) bs Odak düğümünün değiştirilmesi içerik kırıntılarını değiştirmez veya yeni bir kök düğüm döndürmez.
Yani, changeZipper’ın zaman karmaşıklığı O(1)’dir. “x” düğümünü 42 olarak değiştiriyoruz. Artık fermuarda, odak düğümü 42 değerine sahip yeni bir düğümdür. Yukarı git goUp :: Fermuar -> Fermuar goUp (Fermuar t (Kırın l tuşu r : bs)) = Fermuar (Object (l ++ (anahtar, t) : r)) bs goUp (Fermuar _ []) = hata “Zaten en üstte” Yukarı doğru hareket etmek, aşağıya doğru hareket etmenin tersi bir süreçtir.
Kırıntıdaki deliği mevcut odak düğümüyle doldurarak, Kırıntıyı kırıntı listesinden çıkararak ve yeniden birleştirilen ağacı yeni odak düğümü yaparak ağacı yeniden birleştirir. Şimdi yukarı çıktığımızda Fermuar aşağıdaki gibi görünecektir: Yukarıdaki diyagramda, yeni odak düğümü, kırıntıdaki deliğin değeri 42 olan değiştirilmiş “x” düğümüyle doldurulmasıyla oluşturulur.
Yeni odak düğümü, değişmemiş alt düğüm “y”yi orijinal “b” düğümüyle paylaşır. Fermuar ile erişim Yeni bir kök düğüm döndüren erişimin aksine, erişimZ hedef düğüme gider, işlevi odak düğümüne uygular ve ardından ağaçtaki aynı konuma geri döner. AccessZ tarafından değiştirilen düğümlerin sayısı O(mesafe(düğüm, imleç)), burada mesafe(düğüm, imleç) hedef düğümün geçerli imleç düğümünden olan derinliğidir.
Hedef düğüm imleç düğümüne yakınsa, değiştirilen düğümlerin sayısı, erişime göre değiştirilen düğümlerin sayısı olan O(derinlik(düğüm))’den çok daha küçük bir sayıdır.
erişimZ :: [String] -> (Fermuar -> Fermuar) -> Fermuar -> Fermuar erişimZ [] f z = f z erişimZ (k : ks) f z = erişimZ ks f (goAşağı k z) & goUp (&) :: a -> (a -> b) -> b x & f = f x AccessZ fonksiyonunda öncelikle yolun boş olup olmadığını kontrol ederiz. Eğer öyleyse, f değiştirme fonksiyonunu mevcut Fermuar’a uygularız.
Yol boş değilse, k tuşuyla alt düğüme ineriz, kalan k yolu ile alt düğümde yinelemeli olarak erişimZ’yi çağırırız ve sonra orijinal konuma geri döneriz. (&) operatörü, işleneni fonksiyondan önce yazmamızı sağlayan bir ters fonksiyon uygulama operatörüdür. Haskell’deki Data.Function’da zaten tanımlanmıştır, ancak tamlık sağlamak için onu burada tanımlıyoruz.
uygulamada Hedef düğüme gitmek, değişikliği uygulamak ve ardından kök düğüme geri dönmek için AccessZ’yi kullanarak at sorgusunu uygulayabiliriz. withCursor işlevi, bir Fermuar alan ve değiştirilmiş bir Fermuar ve orijinal ağacı döndüren bir değişiklik işlevi olan hedef düğüme giden yolu alır. Değişikliklerin uygulandığı yeni bir ağaç döndürür.
withCursor :: [String] -> (Fermuar -> Fermuar) -> Ağaç -> Ağaç withCursor path ft = focus $ erişimZ yolu f (emptyZipper t) AccessWCursor işlevi, erişime benzer şekilde çalışan ve bir ağaç düğümünü değiştirmemize izin veren bir yardımcı işlevdir.
erişimWCursor :: [String] -> (Ağaç -> Ağaç) -> Fermuar -> Fermuar erişimWCursor yolu f = erişimZ yolu (modifyZipper f) Sorgu yürütme .a.b adresindeki ikinci sorgu { set .x = 42 | set .y = 43 } aşağıdaki koda çevrilecektir: withCursor [“a”, “b”] (accessWCursor [“y”] (const $ Atom 43) .
erişimWCursor [“x”] (const $ Atom 42)) root “b” düğümüne gitmek için withCursor’u kullanır, ardından imleç olarak “b” ile “x” düğümünü ve “y” düğümünü erişimWCursor ile değiştirir. İmleçten ortalama uzaklığı m olan N değişiklik varsa, yeniden oluşturulan düğümlerin toplam sayısı O(N * m + derinlik(ağaç)) olur.
m, derinlikten(ağaç) çok daha küçük olduğunda, bu, kök tabanlı yaklaşımın O(N * derinlik(ağaç)) değerinden daha verimlidir. İki yaklaşımın karşılaştırılması L Aşağıdakileri varsayarak, iki yaklaşımı düğüm tahsisi sayısı ve zaman karmaşıklığı açısından karşılaştıralım: Çocuk aramaları ve ebeveyn yeniden yapılandırmaları O(1) zaman alır İmleçten hedef düğüme olan ortalama yürüme mesafesi m’dir.
Yaklaşım Ağaç düğümleri yeniden oluşturuldu Zaman karmaşıklığı Kök tabanlı erişim O(N derinlik(ağaç)) O(N derinlik(ağaç)) Fermuarlar O(N m + derinlik(ağaç)) O(N m + derinlik(ağaç)) Fermuarlar ne zaman kullanılmalı Fermuarlar evrensel olarak kök tabanlı erişimden daha iyi değildir. Avantajları erişim düzenine bağlıdır.
Yüksek uzamsal konum Bir sorgu ağacın aynı bölgesinde birçok değişiklik gerçekleştirdiğinde, fermuarlar yolun kökten gereksiz şekilde yeniden oluşturulmasını önler. Yüksek konumlu Haskell ağaç geçişi karşılaştırmasında, Fermuarların Performans Analizi, kök tabanlı uygulamaya göre %280’e varan bir hızlanma bildirdi.
Anahtar faktör mekansal konumdur: Düzenlemeler birbirine (ve imlece) ne kadar yakın olursa, fayda da o kadar büyük olur. Değişiklikler ağacın ilgisiz bölümlerine dağıldığında, fermuarın her biri için yukarı ve aşağı gitmesi gerekir ve her adımda kırıntı yaratmanın getirdiği ek yük, onu her seferinde kökten erişimi çağırmaktan daha yavaş hale getirebilir.
Salt okunur erişim Fermuar gezintisi, sarmalayıcıları ayırmaya devam eder ve yukarıya doğru hareket etmek, hiçbir değer değiştirilmediğinde bile üst düğümleri yeniden yapılandırır. Salt okunur aramalar için bu ek yük boşa harcanır. Bir alternatif ise t o ağaç boyunca değerlere giden yollardan bir önbellek bulundurun.
Değişiklikler hem ağacı (bir fermuar aracılığıyla) hem de önbelleği günceller; okumalar herhangi bir gezinme olmadan doğrudan önbelleğe başvurur. Örneğin, .a.b’ye odaklanan ancak alt öğesi .x’in değerini okuması gereken bir sorgu düşünün: at .a.b { .y’yi ayarla = .x + 1’i al } Okuma, mutlak yolu [“a”, “b”, “x”] hesaplayarak ve onu bir önbellekte arayarak, fermuar gezinmesinden tamamen kaçınarak çözülebilir.
Temel Kural Senaryosu Tercih edilen yaklaşım Birçok düzenleme tek bir alt ağaçta toplanmıştır Fermuar Düzenlemeleri ağaca dağılmış durumda Kök tabanlı erişim Salt okunur aramalar Önbellek arama / doğrudan yol arama Fermuar uygulamasının karmaşıklığı Fermuar uygulamasında, özellikle ağaç yapısı karmaşık olduğunda, çok sayıda standart kod bulunabilir.
Örneğin, eğer şu Değer ağacımız varsa: data Value = Atom Int | Liste [Değer] | Harita [(Dize, Değer)] | BinOp Dize Değeri Değer | UnOp String Value Çocuk sahibi olabilecek her düğüm türü için karmaşık bir Kırıntı tanımlamamız gerekir: data ValueCrumb = ListCrumb Int [Value] [Value] | MapCrumb String [(Dize, Değer)] [(Dize, Değer)] | BinOpLeftCrumb Dize Değeri | BinOpRightCrumb Dize Değeri | UnOpCrumb String Bir sonraki yazımızda standart kodun nasıl azaltılabileceğinden bahsedeceğiz.
Sonuç Zorunlu programlama bakış açısından fermuarlar, bir ağaçta gezinmemize ve değişiklik yapmamıza izin verdikleri için doğal görünebilirler.
İlgili yazılar
Editörün Notu
Fonksiyonel dillerde ağaç yapılarında gezinme ve güncelleme için zipper tekniği, değişmezlik prensibini koruyarak verimli ve temiz kod yazmayı sağlar; özellikle karmaşık veri manipülasyonlarında bu yöntem performans ve sadelik sunar.
