Yeniden Boyutlandırma ve Doluluk Oranı
Performans ayarlama
Yeniden Boyutlandırma ve Doluluk Oranı, CoddyKit'te ücretsiz bir C Academy dersidir. Bu, 4 dersinin 4. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, C Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. C Academy kursu toplamda 4 dersten oluşur.
Doluluk Oranı Nedir
Doluluk oranı, saklanan girdilerin kova sayısına oranıdır: alpha = size / capacity. Tablonun ne kadar dolu olduğunu ölçer ve performansı doğrudan etkiler.
Doluluk Oranı Neden Önemlidir
Doluluk oranı arttıkça kovalar daha uzun zincirler tutar (veya araştırmalar kümelenir); bu nedenle işlemler yavaşlar.
- Düşük alpha: hızlıdır ancak belleği boşa harcar
- Yüksek alpha: daha sıkıdır ancak yavaştır
Zincirleme için yaygın hedef 0.75'tir.
Doluluk Oranını Hesaplama
Bir eşikle karşılaştırabilmek için oranı kayan noktalı değer olarak hesaplayın.
#include <stdio.h>
int main(void) {
unsigned size = 12, capacity = 16;
double alpha = (double)size / capacity;
printf("load factor = %.2f\n", alpha);
return 0;
}Ne Zaman Yeniden Boyutlandırılmalı
Her eklemeden sonra doluluk oranının eşiği aşıp aşmadığını denetleyin. Aşarsa tabloyu büyütün (genellikle kapasiteyi iki katına çıkararak) ve yeniden özetleyin.
#include <stdio.h>
int should_grow(unsigned size, unsigned cap) {
return (double)size / cap > 0.75;
}
int main(void) {
printf("%d\n", should_grow(13, 16)); /* 0.8125 -> 1 */
printf("%d\n", should_grow(10, 16)); /* 0.625 -> 0 */
return 0;
}Yeniden Özetleme Açıklaması
Kovaları doğrudan kopyalayamazsınız; çünkü her anahtarın dizini kapasiteye bağlıdır. Yeniden özetleme, her anahtarın yeni kapasiteye göre kova dizinini yeniden hesaplar ve anahtarı yeniden ekler.
Yeniden Boyutlandırma İşlevi
Yeni ve daha büyük bir kova dizisi ayırın; her eski düğümü dolaşıp yeni kapasiteyi kullanarak yeni diziye taşıyın; ardından dizileri değiş tokuş edin. Burada dizini yeniden hesaplamanın temel kısmı gösterilmektedir.
#include <stdio.h>
unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}
int main(void) {
const char *key = "session";
unsigned old_cap = 8, new_cap = 16;
printf("old slot = %lu\n", djb2(key) % old_cap);
printf("new slot = %lu\n", djb2(key) % new_cap);
return 0;
}Yeniden Bellek Ayırmadan Düğümleri Taşıma
Zincirleme yönteminde yeni düğümler ayırmak yerine mevcut düğümleri yeni diziye taşıyabilirsiniz. Her düğümün bağlantısını ayırın, kovasını yeniden hesaplayın ve düğümü listenin başına ekleyin.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { char *key; struct Node *next; } Node;
unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}
int main(void) {
Node *old[2] = {0};
Node *a = malloc(sizeof *a); a->key = strdup("x"); a->next = NULL; old[0] = a;
Node *new_b[4] = {0};
/* move node a */
unsigned i = djb2(a->key) % 4;
a->next = new_b[i]; new_b[i] = a;
printf("moved to slot %u\n", i);
return 0;
}Büyüme Stratejisi
Kapasiteyi iki katına çıkarmak, paylaştırılmış ekleme maliyetini O(1) düzeyinde tutar: Yeniden boyutlandırma O(n) olsa da yeterince seyrek gerçekleştiği için ekleme başına ortalama maliyet sabit kalır.
İkinin kuvvetleri, hızlı AND maskesini kullanmanıza da olanak tanır.
#include <stdio.h>
int main(void) {
unsigned cap = 8;
for (int i = 0; i < 4; i++) {
printf("capacity = %u\n", cap);
cap *= 2;
}
return 0;
}Küçültme
Çok sayıda silme işleminden sonra doluluk oranı çok düşerse (örneğin 0.1'in altına inerse) isteğe bağlı olarak tabloyu küçültün. Küçültme belleği geri kazandırır; ancak yeniden özetleme maliyeti ekler. Bu nedenle sık sık büyüyüp küçülmeyi önlemek için işlemi ölçülü yapın.
Açık Adresleme ve Doluluk Oranı
Açık adreslemeli tablolar doluluk oranına çok daha duyarlıdır. alpha 1'e yaklaştıkça performans çöker; bu nedenle genellikle zincirlemedeki 0.75 değerinden daha düşük olan 0.5 ile 0.7 arasında yeniden boyutlandırılırlar.
Paylaştırılmış Maliyet Gösterimi
Kapasiteyi 0.75 doluluk oranında iki katına çıkaran eklemeleri benzetin ve toplam işi hesaplayarak ortalamanın düşük kaldığını gösterin.
#include <stdio.h>
int main(void) {
unsigned cap = 4, size = 0;
long work = 0;
for (int i = 0; i < 100; i++) {
size++; work++; /* the insert */
if ((double)size / cap > 0.75) { work += size; cap *= 2; } /* rehash */
}
printf("inserts=%u total_work=%ld avg=%.2f\n", size, work, (double)work/size);
return 0;
}Kısa Kontrol
Yeniden boyutlandırma hakkındaki anlayışınızı sınayın.
Özet
Özet tablosu performansını ayarlamayı öğrendiniz.
- Doluluk oranı = boyut / kapasite
- Bir eşiği aştığında yeniden boyutlandırın (zincirleme için yaklaşık 0.75)
- Dizinler kapasiteye bağlı olduğundan yeniden özetleme yapın
- Kapasiteyi iki katına çıkarmak, paylaştırılmış O(1) ekleme maliyeti sağlar
Sıkça Sorulan Sorular
“Yeniden Boyutlandırma ve Doluluk Oranı” dersi ücretsiz mi?
Evet — “Yeniden Boyutlandırma ve Doluluk Oranı” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve C Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. C Academy kursu toplamda 4 dersten oluşur.
“Yeniden Boyutlandırma ve Doluluk Oranı” dersinde ne öğreneceğim?
Performans ayarlama C Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
C Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te C Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 4. dersidir.
“Yeniden Boyutlandırma ve Doluluk Oranı” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu C Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her C Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Özetleme İşlevleri
- Çakışma İşleme
- Ekleme, Arama, Silme
- Yeniden Boyutlandırma ve Doluluk Oranı