collections.OrderedDict sınıfı, Python 2.7/3.1'de, topluluğun hash tabanlı haritalarda belirleyici anahtar sıralaması ihtiyacına bir yanıt olarak ortaya çıkmıştır. Bu, dil spesifikasyonu standart sözlükler için ekleme sırasının korunmasını garanti etmeden yıllar önce olmuştur. Temel sorun, anahtarları O(1) erişim sağlamak için hafıza kovalarında sahte-rasgele dağıtan hash tabloları ile düzeni koruyan fakat düzenleme için arama hızını feda eden sıralı veri yapıları arasındaki mimari gerilimdir. OrderedDict, her girişi eklenme sırasını kaydeden dairesel çift bağlı liste içinde saklarken, aynı zamanda doğrudan erişim için anahtar hash değerleri ile indekslenen geleneksel bir hash tablosunda bu girdileri depolayarak bu durumu çözer.
Bu çift-düzen mimarisi, kapsayıcının, belirli zaman karmaşıklığı için anahtar geri alma işlemlerini hash tablosuna devretmesine ve yineleme sırasında bağlı listeyi dolaşarak öğeleri orijinal eklenme sırasına göre sunmasına olanak tanır. Yeni bir anahtar eklendiğinde, OrderedDict anahtar-değer çiftini içeren bir düğüm tahsis eder, bunu bağlı listenin sonuna ekler ve hesaplanan hash altında hash tablosuna bellekteki adresini kaydeder. Silmeler, hem hash tablosundan hem de bağlı listeden düğümü çıkararak yanındaki düğümlerin prev ve next işaretçilerini ayarlamayı gerektirir, böylece pahalı yeniden hashleme veya veri taşıma işlemleri gerektirmeden her iki işlem için O(1) karmaşıklık korunur.
Bir finansal ticaret platformu için yüksek frekanslı bir iş kuyruğu işlemcisi tasarlarken, eklenme sırasına göre işlem yapılması gereken sıkı bir gereklilikle karşılaştık. Ancak belirli siparişleri benzersiz kimlikleriyle iptal etmek için mikro saniye ölçeğinde aramalara ihtiyaç duyuyorduk. İlk prototip, kronolojik sıralamayı koruyan bir liste ve ID’yi indekse eşleştiren bir dict kullandı; ancak bu yaklaşım, listenin ortasındaki tamamlanmış siparişleri kaldırırken O(n) silme maliyetleriyle sorun yaşadı ve bu kabul edilemez gecikmelere neden oldu. İşlem SLA'sını ihlal etti.
Sonrasında, indekslenmiş zaman damgası sütunlarıyla bir sqlite3 bellek içi veritabanını değerlendirdik. Bu, ACID garantileri ve karmaşık sorgulama yetenekleri sundu ancak basit anahtar-değer erişim desenlerimiz için gereksiz yük getirdi. Bu çözüm, şema yönetimi ve bağlantı işlemleri gerektirdiği için dağıtım yüklemesini karmaşık hale getirdi ve gün içi işlem süresi kadar geçici bir bellek içi önbellek için fazla göründü.
Başka bir alternatif, siparişli mesajlaşma ve kalıcılıkta mükemmel olan Redis akışlarıydı, ancak ağ gidiş-dönüşleri, paylaşımlı bellek mimarisi kısıtlamalarımıza aykırıydı. Bu dış bağımlılık, olumsuz noktalar ve alt-milisaniye gecikme gereksinimleri için kabul edilemez serileştirme yükü getirdi.
Sonuç olarak, collections.OrderedDict'u bellek içi depolama omurgası olarak seçtik çünkü bağlı liste ve hash tablo birleşimi, gereksinim duyduğumuz hesaplama karmaşıklığı profilini sundu. Bu mimari, yeni siparişler için kuyruğa ekleme için O(1), sipariş iptali için O(1) silme ve veri kopyalamadan veya indeks yönetiminden kaçınarak art arda işleme için O(n) sağladı. Bu seçim, iki veri yapısının senkronizasyon yükünü ortadan kaldırdı ve kısmi doldurma gerçekleştiğinde siparişlerin önceliklerini etkili bir şekilde yeniden sıralamak için move_to_end() yönteminden yararlandı ve liste-artı-dict yaklaşımına göre sipariş yönetim gecikmesinde %40'lık bir azalma elde edildi.
Neden collections.OrderedDict, Python 3.7+'de standart sözlüklerin ekleme sırasını korumasına rağmen hala önemlidir?
CPython 3.7+'de standart sözlükler varsayılan olarak ekleme sıralı olarak uygulanmasına rağmen, OrderedDict, devam eden varlığı için haklı kılan belirgin davranış farklılıkları sunar. Sınıf, mevcut anahtarların bir ucuna O(1) yeniden sıralama için move_to_end() yöntemini sunar ve standart sözlükler, anahtarın yineleme pozisyonunu değiştirmek için anahtarı silip yeniden eklemeden bu işlemi gerçekleştiremez. Ayrıca, OrderedDict eşitlik karşılaştırmalarında sıralamayı dikkate alır; bu, tanımlayıcı anahtar-değer çiftlerine sahip iki örneğin farklı eklenme sıraları ile karşılaştırılması durumunda eşit olmadıkları anlamına gelir. Oysa standart dict eşitliği tamamen ekleme sırasını görmezden gelir ve yalnızca anahtar-değer çiftinin eşleşmesini dikkate alır.
Linked-list yapısı OrderedDict'un popitem(last=False) işlemini nasıl O(n) karmaşıklığına düşmeden gerçekleştirir?
Çift bağlı liste mimarisi, bellek şeması dairesel kök düğümü ile birlikte açıkça head ve tail işaretçileri tutar, böylece koleksiyondaki en eski ve en yeni girdilere O(1) erişim sağlar. popitem(last=False) çağrıldığında, OrderedDict, head bekçisinden hemen sonraki düğüme doğrudan erişir, anahtar-değer çiftini çıkarır, head işaretçisini silinen düğümü atlayacak şekilde günceller ve ilgili hash tablosu girişini siler. Bu, standart sözlüklerin ilk eklenen öğeyi bulmak için içsel seyrek dizileri taramak zorunda kalmalarına karşıt olarak, OrderedDict için her zaman sabit zaman sağlar, koleksiyon boyutundan bağımsız olarak popitem işlemlerinin O(n) olmasına neden olur.
Linkli liste uygulamasının, kompakt sözlüklere göre ne tür bir bellek yükü vardır ve bu ne zaman sorunlu hale gelir?
Her bir girişin OrderedDict içinde dairesel çift bağlı listede prev ve next bağlantılarını korumak için iki ek işaretçi gerektirdiğinden, genellikle 64-bit sistemlerde standart hash tablo gereksinimlerinin ötesinde her giriş için 16 baytlık bir yük ekler. Milyonlarca küçük kayıt depolayan uygulamalar için, bu yük modern standart sözlükler tarafından optimizasyon amacıyla kullanılan kompakt, bitişik dizi depolama ile karşılaştırıldığında bellek tüketimini %30-50 artırabilir. Bu yük, bellek kısıtlamalarına sahip ortamlarda veya büyük veri kümelerini önbelleğe alırken özellikle sorunlu hale gelir ve yeniden sıralama yetenekleri ile mevcut RAM kaynakları arasında dikkatli bir analiz gerektirir.