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   , 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. makalede  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   canlı VM geçişi örneğini inceleyebilirsiniz. bağlantıda   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   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: yazımda  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ı:    /boyutu yapısı  sokmak  aramak  taranan düğümler  bağlantılı liste  1.234s  ∞  ∞  RB ağacı, dinamik  20.1'ler  11.335s  1248179373  atlama listesi, 16 seviye  460.124s  461.121'ler  37584859275  atlama listesi, 20 seviye  25.18s  26.267s  4230008370  atlama listesi, 24 seviye  15.429s  12.452s  2548665327  atlama listesi, 28 seviye  15.429s  12.187s  2516402553  atlama listesi, 32 seviye  15.429s  12.215s  2516402553  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ı:  yapı/boyut  sokmak  aramak  taranan düğümler  bağlantılı liste  1.225s  ∞  ∞  RB ağacı, dinamik  22.314s  13.215s  1248179373  atlama listesi, 16 seviye  9.429'lar  482.073s  39673590460  atlama listesi, 20 seviye  10.429s  30.295s  4439292732  atlama listesi, 24 seviye  10.429s  15.156s  2545126580  atlama listesi, 28 seviye  10.141s  16.1'ler  2491915022  atlama listesi, 32 seviye  10.193s  15.1'ler  2491915022  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:  yapı/boyut  sokmak  aramak  taranan düğümler  RB ağacı, dinamik  19.499'lar  13.1'ler  1255153312  atlama listesi, 32 seviye  199.262s  232.004s  2569836454  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.

Read My Stories

Bu ses hikayenin orijinal dilinde üretilmiştir!

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

About Author

YORUMLAR

ETİKETLERİ ASIN

BU YAZI

Related Stories

HackerNoon Yazma Yarışmasını mı Kazanmak İstiyorsunuz? İşte #crypto-api Yarışması Kazananlarının Önerileri

Forumlardan Feed'lere: Sosyal Medya Algoritmaları Dijital Etkileşimi Nasıl Şekillendiriyor

Yapay Zekanın Gücünü Ortaya Çıkarıyoruz. En Son Tekniklerin Sistematik Bir İncelemesi: Özet ve Giriş

Bu 18 Geliştirici Aracıyla Üretkenliğinizi Artırın 🚀🔥

HackerNoon Yazma Yarışmasını mı Kazanmak İstiyorsunuz? İşte #crypto-api Yarışması Kazananlarının Önerileri

Forumlardan Feed'lere: Sosyal Medya Algoritmaları Dijital Etkileşimi Nasıl Şekillendiriyor

Yapay Zekanın Gücünü Ortaya Çıkarıyoruz. En Son Tekniklerin Sistematik Bir İncelemesi: Özet ve Giriş

Bu 18 Geliştirici Aracıyla Üretkenliğinizi Artırın 🚀🔥

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps