"LRU önbellek eleme algoritmasını" gerçekleştirmek için "bağlantılı listeyi" kolayca anlamak için animasyonu izleyin
Yazar | Wu Zhibo
Sorumlu Editör | Hu Weiwei
Önceki bölümlerde, "bağlantılı liste" ve "zaman ve uzay karmaşıklığı" kavramlarını öğrendim. Bu bölüm, çok ilginç bir önbellek eliminasyonu tasarlamak için "döngüsel bağlantılı liste", "çift bağlantılı liste" ve "zaman için alan kullanma tasarım fikrini" birleştirecek. Strateji: LRU önbellek eleme algoritması.
En yaygın üç bağlantılı liste yapısı
Döngüsel bağlantılı liste kavramı
Yukarıdaki şekilde gösterildiği gibi: tek bağlı listenin son düğümünün işaretçisi boş bir adrese işaret ederek bunun son düğüm olduğunu belirtir. Dairesel bağlantılı listenin son düğüm işaretçisi, bağlantılı listenin baş düğümünü gösterir.
Bu nedenle, döngüsel bağlantılı liste özel bir tek bağlantılı listedir. Onunla tek bağlantılı liste arasındaki tek fark, son düğümdür. Bir halka gibi uçtan uca bağlıdır, bu nedenle buna "dairesel bağlantılı liste" denir.
Döngüsel bağlantılı listenin özellikleri
Tekil bağlantılı listelerle karşılaştırıldığında, dairesel bağlantılı listelerin avantajı, zincir ucundan zincir başlığına geçmenin daha uygun olmasıdır.İşlenecek veriler dairesel yapı özelliklerine sahip olduğunda, dairesel bağlantılı listeler uygundur.
Çift bağlantılı liste konsepti
Çift bağlantılı liste, bir tür bağlantılı liste olan çift bağlantılı liste olarak da adlandırılır.Bağlantı yönü çift yönlüdür.İçindeki her veri düğümü, sırasıyla doğrudan halefi ve doğrudan öncülü işaret eden iki işaretçi içerir.
Bu nedenle, çift bağlantılı listedeki herhangi bir düğümden başlayarak, önceki ve sonraki düğümlerine kolayca erişebilirsiniz.
Çift bağlantılı listenin veri yapısında, iki önemli parametre daha olacaktır: ön ve sonraki.
- ön önceki veri yapısını gösterir
- sonraki veri yapısının sonraki noktaları
Tek bağlantılı liste ile çift bağlantılı listenin karşılaştırılması
Çift bağlantılı listenin özellikleri
- Tek bağlantılı listelerle karşılaştırıldığında, çift bağlantılı listelerin önceki düğüme işaret etmek için bir işaretçiye daha ihtiyacı vardır Bu nedenle, aynı miktarda veri depolanırsa, çift bağlantılı listeler, tek bağlantılı listelerden daha fazla bellek alanı kaplar.
- Çift bağlantılı listelerin eklenmesi ve silinmesi, hem sonraki hem de önceki işaretçileri korumalıdır.
- Çift bağlantılı listedeki öğelere erişim sıralı erişim gerektirir ve iki yönlü geçişi destekler Bu, çift bağlantılı liste işlemlerinin temel esnekliğidir.
Çift bağlantılı listenin temel çalışması
1. Öğeleri ekleyin.
Tekil bağlantılı listelerle karşılaştırıldığında, çift bağlantılı listeler O (1) zaman karmaşıklığında ele alınabilirken, tekil bağlantılı listeler O (n) zaman karmaşıklığı gerektirir.
Çift bağlantılı listenin eklenen öğeleri, baş enterpolasyonunu ve kuyruk enterpolasyonunu içerir.
Baş ve kuyruk yerleştirme
Başlık ekleme yöntemi: Bağlı listenin sol tarafına bağlantılı listenin başı denir ve sağ tarafa bağlantılı listenin kuyruğu denir. Baş yerleştirme yöntemi, sağ tarafı sabitlemektir ve her yeni eleman sol başa eklenir.
Kuyruk ekleme yöntemi: Bağlı listenin sol tarafına bağlantılı listenin başı denir ve sağ tarafa bağlantılı listenin kuyruğu denir. Kuyruk ekleme yöntemi, sol tarafı sabitlemektir ve her yeni ekleme, bağlantılı listenin sağ tarafının sonundadır.
2. Sorgu öğeleri
Sorgu öğesi
Çift bağlantılı bir listenin esnekliği, bağlantılı listedeki bir elemanın yapısının bilinmesinin, gerekli eleman yapısını bulmak için sola veya sağa hareket etmeye başlayabilmesidir. Bu nedenle, sıralı bir bağlantılı liste için, çift bağlantılı bir listenin değerine göre sorgulamanın verimliliği, tek bağlantılı bir listeninkinden daha yüksektir. Son aranan pozisyon p'yi, her sorguladığımızda, aranacak değer ile p arasındaki boyut ilişkisine göre kaydedebildiğimiz için, ileri mi yoksa geri mi arama yapacağımıza karar veririz, bu nedenle ortalama olarak verilerin yalnızca yarısını aramamız gerekir.
3. Öğeleri silin
Gerçek yazılım geliştirmede, bağlantılı listeden bir veri parçasını silmek şu iki durumdan başka bir şey değildir:
- Düğümde "belirli bir değere eşit değer" olan düğümü silin.
- Verilen işaretçinin gösterdiği düğümü silin.
Öğeyi sil
Çift bağlantılı bir liste için, çift bağlantılı listedeki düğümler, önceki düğümlerin işaretçilerini zaten kaydetmiştir ve silme sırasında tekil bağlantılı bir liste gibi gezinmeye gerek yoktur. Bu nedenle, ikinci durum için, tek bağlantılı liste silme işlemi O (n) zaman karmaşıklığı gerektirirken, çift bağlantılı liste yalnızca O (1) zaman karmaşıklığına ihtiyaç duyar.
Çift bağlantılı liste
Çift bağlantılı liste
Şekilde gösterildiği gibi, çift bağlantılı liste kavramı iyi anlaşılmıştır: "çift bağlantılı liste" + "döngüsel bağlantılı liste" kombinasyonu.
Önbellek yok etme stratejisi
Önbelleğe alma, veri okuma performansını artırmaya yönelik bir teknolojidir. Yaygın CPU önbelleği, veritabanı önbelleği, tarayıcı önbelleği vb. Gibi donanım tasarımı ve yazılım geliştirmede yaygın olarak kullanılır.
Önbelleğin boyutu sınırlıdır Önbellek dolduğunda hangi veriler temizlenmeli ve hangi veriler tutulmalıdır? Bu, karar vermek için bir önbellek eleme stratejisi gerektirir. Üç yaygın strateji vardır: FIFO (İlk Giren, İlk Çıkar), LFU (En Az Sık Kullanılan) ve LRU (En Az Son Kullanılan).
LRU önbelleğe alma stratejileri, çeşitli dillerde üçüncü taraf çerçevelerde yaygın olarak kullanılmaktadır. Programcı Xiao Wu, Java'da "Mybatis", iOS'ta "YYCache" ve "Lottie" vb. İle iletişime geçti.
LRU önbellek eliminasyon algoritması:
LRU, son zamanlarda en az kullanılan stratejinin kısaltmasıdır. Verilerin geçmiş erişim kayıtlarına dayalı olarak verileri ortadan kaldırır. Temel fikri, "Veriye yakın zamanda erişilmişse, gelecekte erişim olasılığı da daha yüksektir."
LRU kavramı
Bağlantılı liste LRU'yu gerçekleştirir
Önbelleğin tüm konumları çift bağlantılı bir liste ile bağlantılıdır.Bir konuma vurulduğunda, konum bağlantılı listenin yönünü ayarlayarak bağlantılı listenin başına ayarlanır ve yeni eklenen Önbellek doğrudan bağlantılı listenin başına eklenir.
Bu şekilde, çoklu Önbellek işlemlerinden sonra, yakın zamanda vurulanlar bağlantılı listenin başına taşınırken, vurulmayanlar bağlantılı listenin arkasına taşınacaktır.Bağlantılı listenin sonu, en az kullanılan Önbelleği temsil eder.
İçeriğin değiştirilmesi gerektiğinde, bağlantılı listenin son konumu en az ulaşılan konumdur ve biz sadece bağlantılı listenin son bölümünü kaldırmamız gerekir.
Bağlantılı liste, LRU animasyon gösterimini gerçekleştirir
- Önbellek şu anda dolu değilse, bu düğümü doğrudan bağlantılı listenin başına ekleyin.
- Bu sırada önbellek doluysa, bağlantılı listenin son düğümü silinir ve bağlantılı listenin başına yeni bir veri düğümü eklenir.
Bağlantılı liste LRU'yu gerçekleştirir
Önbellek alanı yeterince büyükse, o zaman yeterli verinin saklandığı ve önbellekten verilere ulaşma olasılığının daha yüksek olduğu, bu da kodun yürütme hızını artıran animasyondan görülebilir. Bu, zaman için mekânın tasarım fikridir.
Program geliştirme için zaman karmaşıklığı ve uzay karmaşıklığı birbirine dönüştürülebilir. Meslekten olmayan terimlerle, bu:
- Yavaş çalışan programlar için, bellek tüketerek (yani yeni veri yapıları oluşturarak) optimizasyon yapabilirsiniz;
- Bellek tüketen program, zaman harcayarak bellek tüketimini azaltabilir.
Yazar hakkında: Harbin Teknoloji Enstitüsü'nde bir pislik olan yazar, programcı Xiao Wu, şu anda algoritmaları öğreniyor. Açık kaynak projesi "LeetCodeAnimation" 5500star, GitHub Trendler listesinde bir ay boyunca birinci sırada yer aldı. Herkese açık WeChat hesabımı takip etmelerine hoş geldiniz: algoritmaları beş dakikada öğrenin, birlikte öğrenin ve birlikte ilerleyin!
Feragatname: Bu makale yazar tarafından sunulmuştur ve telif hakkı kendisine aittir.
