Genişletilmiş Bağlantılı Listeler: Temel Bir Kılavuz

Bağlantılı Liste Nasıl Çalışır?

Bağlantılı liste, her verinin alanlarının uzaklıklar yerine işaretçilerle bağlandığı bir veri yapısıdır. Düğüm öğeleri olarak adlandırılan, gerekli tüm kullanıcı alanlarını (telefon, sahip, şirket vb.) içeren ilk ve son öğeleri saklayan bir ana öğeden ve bir sonraki düğüme işaret eden bir işaretçiden oluşur. Son öğe, listenin sonunu belirten NULL alanına bağlanır.

Bağlantılı listeye yeni bir öğe eklendiğinde, ana düğüm "kuyruk" işaretçisini yeni uç düğüme güncellemeli ve önceki NULL işaretçisi yeni kuyruğa güncellenmelidir.

Bu veri yapısı, tüm dizinin yeniden boyutlandırılmasına gerek kalmadan yeni verilerin verimli bir şekilde kaydedilmesine olanak tanır. Bu, salt yazılır verileri depolamak için etkili bir yöntemdir ve öğe miktarının önceden bilinmesini gerektirmez. Bu basit bir veri yapısıdır ve hafızada şöyle görünür:

Tahliye Anahtarları için Bağlantılı Liste

Daha önceki bir makalede , her öğe silme işleminden sonra ağaçtan ayrılmadan ağacı taramak için bir ara belleğe duyulan ihtiyacı tartışmıştık. GC'li dillerde bu bir sorun değildir. Ancak uygulama kodu belleği yönettiğinde, güncelliğini yitirmiş öğeler içeren bağlantılı listeyi temel alan bir arabellek bir çözüm olabilir.

Bağlantılı bir liste, öğelerin hızlı bir şekilde eklenmesine olanak tanır. Ancak bağlantılı listede herhangi bir şey bulmak sıralı taramayı gerektirdiğinden hızlı anahtar alımı için uygun değildir. Bu nedenle, verileri günlüğe kaydetmek, geçici arabellekler oluşturmak ve ana düğümlerden sıralı okumalar yapmak üzere verileri düzenlemek için etkili bir çözümdür.

Önlenecek unsurları bulmak böyle bir göreve bir örnektir. Ön alım genellikle farklı önbellek uygulamalarında kullanılır. Önbellek, diğer bellek kaynaklarından daha büyük gecikmeyle geri yüklenebilecek verileri içerir. Önbellek genellikle ana bellekte saklanır. Ana bellek sınırlıdır ve etkili kullanım için ana bellekte yalnızca küçük bir veri anlık görüntüsü saklanabilir.

Belleği daha akıllıca kullanmamızı, nadiren istenen veriler için bellek kullanımından kaçınmamızı ve çok seyrek talep edilmesi durumunda bu tür verileri kaldırmamızı gerektirir.

Önbellekteki alanları çıkarmak için etkili bir yöntem, En son kullanılan (LRU) yöntemidir. Aşağıdaki LRU gösterimi aşağıdadır:

Bu durumda uygulama, en son kullanılan nesneleri depolamak için en az bir bağlantılı liste içerir ve hızlı arama için başka veri yapılarına (karma tablosu gibi) sahiptir. Düğümler birbirine bağlıdır.

Bir kullanıcı hash tablosundan veri aldığında bağlantılı liste bu veriyi kuyruğa taşıyarak yeniler. Sonuç olarak, birkaç işlemden sonra kuyruk, son zamanlarda kullanılan verileri içerirken, baş, nadiren istenen verileri tutar.

Bellek taşması durumunda uygulama, yeterli belleği serbest bırakmak için ilk N öğeyi tarayabilir. Bağlantılı liste sıralı taramalara uyum sağladığı için bu basit bir işlemdir. Nadiren kullanılan verileri içeren bellek serbest bırakılacak ve daha sık kullanılan yeni düğümler önbellekte depolanabilecek.

 #include <stdlib.h> #include <stdio.h> typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr; } lnode_t; typedef struct list_t { lnode_t *head; lnode_t *tail; } list_t; lnode_t* lru_insert(list_t *list, char *ptr) { if (!list->head) { list->head = list->tail = calloc(1, sizeof(lnode_t)); list->head->ptr = ptr; return list->head; } lnode_t *saved_tail = list->tail; lnode_t *new = calloc(1, sizeof(sizeof(lnode_t))); new->ptr = ptr; saved_tail->next = new; new->prev = saved_tail; list->tail = new; return new; } void lru_update(list_t *list, lnode_t *lnode) { if (list->tail == lnode) { return; } lnode_t *saved_tail = list->tail; saved_tail->next = lnode; if (!lnode->prev) list->head = lnode->next; lnode->next = NULL; lnode->prev = saved_tail; list->tail = lnode; } void lru_evict(list_t *list, int items, void (*func)(void* arg, void *ptr), void* arg) { lnode_t *lnode = list->head; while(items-- && lnode) { func(arg, lnode->ptr); lnode_t *prev = lnode->prev; lnode_t *next = lnode->next; if (prev) prev->next = next; if (next) next->prev = prev; free(lnode); lnode = next; } if (!lnode) list->head = list->tail = NULL; } void print_deleted_obj(void *arg, void *ptr) { printf("evicted: %p\n", ptr); deleteThisInTheOtherStructure(arg, ptr); } int main() { list_t *list = calloc(1, sizeof(list_t)); lnode_t *test = lru_insert(list, "some data"); lru_insert(list, "another data"); lru_update(list, test); lru_evict(list, 1, print_deleted_obj, otherStructure); }

Bir açıklama: Kullanılan öğelerin sayısının sıklığı önemli ölçüde farklılık gösterdiğinde (örneğin, isteklerin %95'i 1 milyon anahtardan ilk 100'e dağıtıldığında), Splay Tree önbellek depolamak için daha uygun olabilir. Bu ağaç, her düğümün kullanım sıklığına göre dengelenir.

Splay Tree'nin ana fikri LRU'nun tam tersidir; en çok kullanılan öğeler kökün yakınında bulunur, bu da bu veri yapısını önbellek için birincil yapı olarak ideal kılar.

Tahliye iki şekilde çözülebilir: ana yapıya bağlı bağlantılı bir liste kullanarak veya bir Yayılım Ağacını Dişli İkili Ağaç olarak değiştirerek. Görünüm Ağacındaki düğümler zaten kullanım sıklığına göre sıralanmıştır. Ağaç yapraklarının ek iş parçacığı işlenmesi daha fazla CPU zamanı gerektirse de, bu nedenle bellekten tasarruf sağlayabilir.

Bellekteki son kullanılan verilerin hızlanmasını daha iyi anlamak için bu bağlantıda canlı VM geçişi örneğini inceleyebilirsiniz.

Bağlantılı Listenin Tarama Hızını Artırın

Daha önce de belirtildiği gibi bağlantılı listeler veri yazma konusunda en hızlı çözümü sunar. Tarama hızları iyidir ancak dizideki tarama hızından daha yavaştır.

Bu sorunu bir önceki yazımda veri yerelliği olarak anlatmıştım. Ancak ikili ağaçlara benzerliği nedeniyle bağlantılı listelerin iyileştirme potansiyeli vardır. Bağlantılı listelerin açılması, listenin her düğümünde daha fazla veri depolamanıza olanak tanır. Böylece, bir sonraki işaretçi düğümünde bellekten tasarruf sağlar ve bazen öğenin boyutunun CPU önbellek satırına uyması koşuluyla performansı artırır:

Ana fikir değişmeden kalır ancak listenin hafızadaki temsili değişecektir.

Birçok yönden değişecek. Aşağıda 2 seçenek bulunmaktadır:

Bu iyileştirmeler bağlantılı listelerin performansını artırır ancak koda bir miktar karmaşıklık katar. Bağlantılı listeye sahip disk işlemleri için, yuvarlanmamış bir düğüm daha fazla öğeye sahip olabilir. Nasıl çalıştığını anlamanın kolay bir yolu, bağlantılı bir dizi listesi hayal etmektir.

Kodda yapı açıklamasını değiştirmemiz ve bundan sonra yapının dizisindeki her bir öğeyi okumamız veya yazmamız gerekiyor:

 typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr[3]; } lnode_t;

Listeyi Atla

Atlama listesi, bağlantılı bir listedeki arama öğelerinin hız özelliklerini iyileştirmeye yönelik bir yöntemdir. Bu tür bağlantılı liste, bağlantılı listeyi sıralamak için bir anahtar saklar ve düğümleri basit bir tarama işleminden daha verimli bir şekilde bulmak için ekstra işaretçiler içerir.

Ekstra düğümler, atlama listesindeki düğümler arasında geçiş hızını artırır. İkili arama gibi çalışır. Aksine yeni unsurların eklenmesi daha fazla zaman alır. Bu nedenle atlama listelerinin mutlaka bir anahtarı olmalıdır. Uygulamalar, hız özelliklerini geliştirmek için herhangi bir sayıda seviye yapabilir. Çoğu durumda, ağaçtaki yükseklikten biraz daha az veya hemen hemen aynı seviyelere sahip olmak daha iyi bir seçimdir. (Yukarıdaki resme bakın)

Arama yaparken bir uygulama en hızlı rota olan en üst seviyeden başlar. Yakın anahtarı tespit ettikten sonra istenen düğüm bulunana kadar daha düşük bir seviyeye iner.

Bu süreç O(log(n)) kadar zaman karmaşıklığına neden olur. Örneğin, 16 düğümlü bir atlama listesi için 4 düzey, 1 milyon düğüm için 20 düzey ve 4 milyar düğüm için 32 düzey kullanmak, RB ağacına benzer zaman karmaşıklığı sağlar.

Atlama listesi aşağıdaki nedenlerden dolayı daha iyidir:

• Uygulamanın basitliği. RB ağacına benzer özelliklerine rağmen uygulanması ve bakımı çok daha kolaydır.

• Atlama listesinin sonuna yeni düğümler eklemede yüksek verimlilik.

• Atlama listesinin iş parçacığı açısından güvenli bir uygulamasını oluşturmak, ağaçtan daha kolaydır.

Bu konseptin uygulanmasını keşfedelim!

Yapı düğümleri:

 typedef struct skip_node { uint64_t key; uint64_t value; struct skip_node **forward; } skip_node; typedef struct skip_t { uint64_t level; uint8_t max_level; skip_node *header; } skip_t;

Düğüm oluşturma işlevi:

 skip_node* create_skip_node(uint64_t key, int value, int level) { skip_node *newskip_node = (skip_node*)malloc(sizeof(skip_node)); newskip_node->key = key; newskip_node->value = value; newskip_node->forward = malloc(sizeof(skip_node)*level); for (uint64_t i = 0; i < level; i++) { newskip_node->forward[i] = NULL; } return newskip_node; } skip_t* skip_new(uint8_t max_level) { skip_t *list = (skip_t*)malloc(sizeof(skip_t)); list->level = 0; list->max_level = max_level; skip_node *header = create_skip_node(0, 0, max_level); list->header = header; for (uint64_t i = 0; i < max_level; i++) { header->forward[i] = NULL; } return list; }

Ekleme sırasında görev, düğümün depolanacağı doğru konumun tespitini ve bu düğüme bağlanacak seviye sayısının belirlenmesini içerir. Seviyeleri belirlemek için rastgele bir fonksiyonun kullanılması, her yeni düğüm için sürecin basitleştirilmesine yardımcı olur. Ortalama olarak, bu işlev vakaların %50'sinde ikinci düzeyi, %25'inde üçüncü düzeyi vb. tahsis eder. Bu yöntem, öğeleri yeniden dengelemek için belleğe erişim süresini en aza indirir.

 uint64_t random_level(uint8_t max_level) { uint64_t level = 1; while (rand() < RAND_MAX / 2 && level < max_level) { level++; } return level; } void skip_insert(skip_t *list, uint64_t key, int value) { skip_node *update[list->max_level]; skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } update[i] = current; } current = current->forward[0]; if (current == NULL || current->key != key) { uint64_t newLevel = random_level(list->max_level); if (newLevel > list->level) { for (uint64_t i = list->level; i < newLevel; i++) { update[i] = list->header; } list->level = newLevel; } skip_node *newskip_node = create_skip_node(key, value, newLevel); for (uint64_t i = 0; i < newLevel; i++) { newskip_node->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newskip_node; } } }

Düğümleri arama işlevi:

 skip_node* skip_search(skip_t *list, uint64_t key) { skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } } current = current->forward[0]; ++nodes_scan; if (current != NULL && current->key == key) return current; else return NULL; }

Bağlantılı listenin, atlama listesinin ve RB ağacının performansını test etmeye yönelik bir kıyaslama işlevi. Anahtar olarak kullanılan değerler ikinin kuvvetleri olarak ayarlanır. Test amaçlı değer önemli değildir.

 skip_t *skipList = skip_new(atoi(argv[1])); list_t *llist = list_new(); tree_t *tree = calloc(1, sizeof(*tree)); size_t to_index = 50000000; struct timespec s_icalc; struct timespec e_icalc; struct timespec s_scalc; struct timespec e_scalc; clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) tree_insert(tree, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; nodes_scan = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { node_t *node = tree_get(tree, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) skip_insert(skipList, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { skip_node* ret = skip_search(skipList, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) list_add(llist, NULL, NULL); clock_gettime(CLOCK_REALTIME, &e_icalc);

Bu veri yapılarının sıralı olarak büyüyen anahtarlar üzerinde test edilmesinin sonuçları:

Bu, ekleme için en iyi zamandır (eğer basit bir bağlantılı listeyi hesaba katmazsanız) ve öğeleri aramak için oldukça hızlı bir yöntemdir.

Bu veri yapılarının sıralı olarak azalan anahtarlar üzerinde test edilmesinin sonuçları:

Bunu anlamak kolaydır: atlama listesinin bu uygulamasında yalnızca ilk öğeye yönelik bir baş işaretçi bulunur. Sona düğüm eklemek daha karmaşıktır. Bu yaklaşımı değiştirmek için ikinci bir işaretçi (kuyruğa) ekleyebilir veya ters atlama listesini (baş büyük değerleri işaret edecektir) ekleyebiliriz. Bu, bir atlama listesinin Kafka akışları gibi günlük verileri için etkili bir veri yapısı olduğu anlamına gelir. Bu durumda RB ağacından en az iki kat daha hızlı olabilir ve uygulanması daha kolay olabilir.

Atlama Listesi, Bağlantılı listenin ekleme hızını azaltır, ancak sıralı veriler için, özellikle anahtarlar sıralı olarak büyürken, öğelere logaritma erişim süresi ile diğer veri yapılarına göre daha hızlı kalır. Bununla birlikte, anahtarların herhangi bir sıralı büyümesi, ağacın dengesini korumak için çok sayıda dönüşe neden olduğundan, ağaca eklemeleri karmaşık hale getirir.

Yalnızca dizi boyunca değer arttığında (veya azaldığında) etkili bir şekilde çalışır. Örneğin, anahtarları rastgele seçersek sonuçlar farklı olacaktır:

Görüldüğü gibi değerler arasındaki dağılım RB ağacının hız karakteristiğini önemli ölçüde etkilemez ancak atlama listesinin performansını belirgin şekilde etkiler.

Sonuçlar

Günümüzde uygulamalarımız hafızadaki veya diskteki verileri farklı şekillerde organize edebiliyor. Haritalar ve listeler, verilerin farklı amaçlar için farklı sıralarda düzenlenmesinde önemli bir rol oynamaktadır. Bu yapılar yeterli performansı, kaynak verimliliğini ve yeteneği sağlar.

Bazen ihtiyaçlarımıza yetmiyor ve uygulamanın kritik kısımlarında daha optimum olacak şekilde değiştirilmesi gerekiyor. Bazı durumlarda, tam olmayan eşleştirme veya bellek ekonomisi için ağaçlar gibi daha uygun veri yapılarının kullanılması yararlı olabilir. Diğerleri - bireysel iş parçacığı performansını artırmak için eşzamansız yöntemlerin kullanılması gibi algoritmanın iyileştirmelerinden.

Burada diğer tüm seçenekler tükendiğinde geriye kalan yaklaşım, veri yapısını uyarlamak ve kullanım metodolojisini ayarlamaktır. Bunları pratik olarak spesifik bir göreve daha uygun hale getirmek için veri yapısında bazı değişikliklerin örnekleri vardır.

Bağlantılı liste öncelikle salt yazılır ve sıralı tarama yapan bir veri yapısı olsa da, RB ağacından daha fazla optimize edilebilir ve salt yazılır durumda verimli kalabilir. Ancak belirli özelliklerin artması diğerlerini de etkileyebilir. Bu nedenle en iyi yol, önemli olana öncelik vermek ve önemsiz olanı atmaktır.