Soru Python'un Yerleşik Sözlükleri Nasıl Uygulandı?


Python için yerleşik sözlük türünün nasıl uygulandığını bilen var mı? Anladığım kadarıyla bir çeşit karma masa var, ama herhangi bir kesin cevap bulamadım.


205
2017-11-29 07:35


Menşei




Cevaplar:


İşte Python dikteleriyle ilgili bir araya getirebileceğim her şey (muhtemelen herkesin bilmesini istediğiden daha fazla, ama cevap kapsamlı).

  • Python sözlükleri şu şekilde uygulanır: hash tabloları.
  • Karma tablolar izin vermelidir karma çarpışmalar Yani, iki farklı anahtar aynı karma değere sahip olsa bile, tablonun uygulamasının anahtar ve değer çiftlerini belirsiz bir şekilde yerleştirme ve geri alma stratejisi olmalıdır.
  • piton dict kullanımları açık adresleme karma çarpışmaları çözmek için (aşağıda açıklanmıştır) (bkz. dictobject.c: 296-297).
  • Python karma tablosu sadece bitişik bir bellek bloğu (bir dizi gibi bir dizi, böylece bir O(1) dizine göre arama).
  • Tablodaki her bir yuva, bir ve yalnızca bir girişi saklayabilir. Bu önemli.
  • Her giriş tabloda aslında üç değerin bir kombinasyonu: <hash, anahtar, değer>. Bu bir C yapısı olarak uygulanır (bkz. dictobject.h: 51-56).
  • Aşağıdaki şekil bir Python hash tablosunun mantıksal bir temsilidir. Aşağıdaki şekilde, 0, 1, ..., i, ... solda ise yuvalar hash tablosunda (onlar sadece açıklayıcı amaçlıdırlar ve tablo ile birlikte belli bir şekilde saklanmazlar!).

    # Logical model of Python Hash table
    -+-----------------+
    0| <hash|key|value>|
    -+-----------------+
    1|      ...        |
    -+-----------------+
    .|      ...        |
    -+-----------------+
    i|      ...        |
    -+-----------------+
    .|      ...        |
    -+-----------------+
    n|      ...        |
    -+-----------------+
    
  • Yeni bir dict başlatıldığında, 8 ile başlar yuvalar. (görmek dictobject.h: 49)

  • Tabloya girişler eklerken, biraz boşlukla başlıyoruz. iBu, anahtarın karmaşasına dayanır. CPython başlangıçta kullanır i = hash(key) & mask (nerede mask = PyDictMINSIZE - 1ama bu gerçekten önemli değil. Sadece ilk yuvaya dikkat edin i, bu kontrol edilir bağlıdır esrar anahtarın
  • Bu yuva boşsa, giriş yuvaya eklenir (girişle, yani, <hash|key|value>). Ama ya o yuva doluysa !? Büyük olasılıkla başka bir giriş aynı karma (karma çarpışma!) Çünkü
  • Yuva işgal edilmişse, CPython (ve PyPy) karşılaştırır karma ve anahtar (karşılaştırmak demekle == karşılaştırma değil is Yuvadaki girdinin, eklenecek geçerli girişin hash ve anahtarına göre karşılaştırılması (dictobject.c: 337,344-345) sırasıyla. Eğer her ikisi de eşleşme, daha sonra girdinin zaten var olduğunu düşünür, pes eder ve eklenecek sonraki girişe geçer. Karma veya anahtar eşleşmiyorsa, başlar sondalama.
  • Prob, sadece boş bir yuva bulmak için yuvaları yuvaya göre aradığı anlamına gelir. Teknik olarak tek tek gidebiliriz. i+1, i+2, ... ve ilk kullanılabilir olanı kullanın (bu doğrusal taramadır). Ama yorumlarda güzelce açıklanmış nedenlerle (bkz. dictobject.c: 33-126), CPython kullanır rasgele problama. Rasgele problamada, bir sonraki slot, rastgele bir sırayla toplanır. Giriş, ilk boş yuvaya eklenir. Bu tartışma için, bir sonraki yuvayı seçmek için kullanılan gerçek algoritma gerçekten önemli değil (bkz. dictobject.c: 33-126 sondalama algoritması için). Önemli olan, yuvaların ilk boş yuva bulunana kadar problanmasıdır.
  • Aynı şey aramalar için de gerçekleşir, sadece ilk slot i ile başlar (anahtarın karmaşasına bağlı olduğum yerde). Karma ve anahtar her ikisi de yuvadaki girişi eşleşmezse, bir eşleşme ile bir yuva bulana kadar problamaya başlar. Tüm yuvalar bittiğinde, bir hata bildirir.
  • Btw dict üçte ikisi doluysa yeniden boyutlandırılacaktır. Bu, aramaları yavaşlatır. (görmek dictobject.h: 64-65)

NOT: Python Dict uygulamasında kendi araştırmamla ilgili araştırma yaptım soru Bir dict'taki birden fazla girişin aynı karma değerlere sahip olabileceği hakkında. Burada cevabın biraz düzenlenmiş bir versiyonunu yayınladım çünkü tüm araştırmalar bu soru için çok alakalı.


342
2018-01-26 17:52



Kullanarak py2 ve py3'te hem deney yaptım d={1:1, 1:2, 1:1.5, 1:False}, Her zaman bir dict alacağım {1:False}son öğeyi saklı tutar. İlk ifadelerde yer alan tüm öğeler aynı anahtar ve farklı değere sahiptir, bu da anahtarların karmaları aynıdır. Ve neden her zaman son maddeyi seçiyor? Python dict her zaman en son öğeyi, ilk cevabını, cevabınızda belirttiğiniz aynı hatayı içeren anahtarları başlatma ve yok saymayı deniyor mu? Python ilk girişi ilk öğeyi seçmezse, deneme sonucu gerçekten kafa karıştırıcı olur. - Zen
Çünkü sadece 1 anahtarınız var ve siz bunun üzerine yazıyorsunuz. Bunun için kontrol etmeniz gereken, aynı karma değere sahip farklı tuşlardır. Bunu düşünün, endeksle aynı anahtarı kullanarak farklı değerleri nasıl elde edersiniz? Aynı tuş için birden çok değer istiyorsanız, bir tuple / liste kullanabilirsiniz. - Tushar Vazirani


Python sözlükler kullanımı Açık adresleme (güzel kod içinde başvuru)

NB!  Açık adresleme, diğer adıyla kapalı hashing Vikipedi'de belirtildiği gibi, bunun tam tersi ile karıştırılmamalıdır açık hashing!

Açık adresleme, dict'ın dizi yuvaları kullandığı ve bir nesnenin ana pozisyonunun taslakta alındığı zaman, nesnenin noktasının, nesnenin karma değerinin parçası olduğu bir "pertürbasyon" şeması kullanılarak, aynı dizide farklı bir endekste aranır. .


40
2018-06-08 11:00



"karşıt açık karmaşasıyla karıştırılmamalıdır! (kabul edilen cevapta görürüz)." - Bunu yazarken hangi cevabın kabul edildiğinden emin değilim, ya da o zaman cevabın ne söylediği - ama bu parantezli yorum şu anda kabul edilen cevap için geçerli değil ve en iyi şekilde kaldırılacaktı. - Tony Delroy


Python'un Yerleşik Sözlükleri Nasıl Uygulandı?

İşte kısa kurs:

  • Onlar hash masaları.
  • Python 3.6'dan itibaren yeni bir prosedür / algoritma bunları yapar
    • Anahtar eklemeye göre sıralı ve
    • daha az yer kapla,
    • performansta neredeyse hiç maliyet yok.
  • Diğer bir optimizasyon, dicts anahtarları (özel durumlarda) paylaştıklarında yerden tasarruf sağlar.

Sipariş edilen yön, Python 3.6'dan itibaren gayri resmi, ancak Python 3.7 resmi.

Python'un Sözlükleri Hash Tabloları

Uzun bir süre, tam olarak böyle çalıştı. Python, 8 boş satırı önceden ayırır ve anahtar değeri çiftini nereye yapıştırılacağını belirlemek için karma değerini kullanır. Örneğin, anahtarın karması 001'de sona erdiyse, bunu 1 dizinine yapıştırır (aşağıdaki örnekte olduğu gibi).

     hash         key    value
     null        null    null
...010001    ffeb678c    633241c4 # addresses of the keys and values
     null        null    null
      ...         ...    ...

Her satır, 64 bit mimaride 24 bit, 32 bitte 12 alır. (Sütun başlıklarının sadece etiket olduğunu unutmayın - aslında bellekte bulunmazlar.)

Eğer karma, önceden var olan bir anahtarın karma değeriyle aynıysa, bu bir çarpışmadır ve daha sonra anahtar-değer çiftini farklı bir yere yapıştıracaktır.

5 anahtar-değer kaydedildikten sonra, başka bir anahtar-değer çifti eklerken, karma çarpışma olasılığı çok büyüktür, bu yüzden sözlük ikiye katlanır. Yeniden boyutlandırmadan önce, 64 bit işlemle, 72 bayt boş olur ve ondan sonra, 10 boş satır nedeniyle 240 bayt boşa harcıyoruz.

Bu çok yer kaplar, ancak arama süresi oldukça sabittir. Anahtar karşılaştırma algoritması, hashı hesaplamak, beklenen konuma gitmek, anahtarın kimliğini karşılaştırmaktır - aynı nesne ise, bunlar eşittir. Eğer değilse o zaman karma değerleri karşılaştırınız. değil aynı, eşit değiller. Öyleyse, sonunda eşitlik için anahtarları karşılaştırırız ve eşitse, değeri döndürürler. Eşitlik için son karşılaştırma oldukça yavaş olabilir, ancak önceki kontroller genellikle son karşılaştırmayı kısaltır, bu da aramaları çok hızlı yapar.

(Çarpışmalar yavaşlatır ve bir saldırgan teorik olarak bir hizmet reddi saldırısı gerçekleştirmek için karma çarpışmaları kullanabilirdi. Bu nedenle, karma işlevini her yeni Python işlemi için farklı bir hash hesaplayacak şekilde randomize ettik.)

Yukarıda açıklanan boş alan, sözlüklerin uygulanmasını değiştirmemize yol açmıştır ki, yeni (gayri resmi) bir özellik ile, sözlüklerin şimdi sipariş edilmesi (ekleme yoluyla).

Yeni Kompakt Karma Tablolar

Bunun yerine, ekleme endeksi için bir diziyi önceden açarak başlarız.

İlk anahtar-değer çiftimiz ikinci yuvaya girdiğinden, şu şekilde indeksleniyoruz:

[null, 0, null, null, null, null, null, null]

Ve masamız sadece kampanya siparişiyle dolduruluyor:

     hash         key    value
...010001    ffeb678c    633241c4 
      ...         ...    ...

Bu nedenle, bir anahtar için bir arama yaptığımızda, beklediğimiz pozisyonu kontrol etmek için hashı kullanırız (bu durumda, dizinin 1'inci dizinine düz gidersiniz), daha sonra hash tablosundaki o indekse gidin (örn. İndex 0). ), tuşların eşit olduğunu kontrol edin (daha önce açıklanan aynı algoritmayı kullanarak) ve eğer öyleyse, değeri döndürün.

Önceden varolan uygulamada oldukça fazla yer kapladığımızda, bazı durumlarda ve bazı durumlarda kazançlarda küçük hız kayıplarıyla sürekli arama sürelerini koruyoruz. Boş yer olan boş alan dizin dizisindeki boş baytlardır.

Raymond Hettinger bunu tanıttı piton-dev 2012 yılının Aralık ayında. Sonunda CPython'a girdi. Python 3.6. Ekleme yoluyla sipariş vermek, Python'un diğer uygulamalarına yetişme şansı veren bir uygulama ayrıntısı olarak kabul edilir.

Paylaşılan Anahtarlar

Yer kazanmak için başka bir optimizasyon, anahtarları paylaşan bir uygulamadır. Bu nedenle, tüm bu alanı kaplayan gereksiz sözlükler yerine, paylaşılan anahtarların ve anahtarların 'karmalarını yeniden kullanan sözlüklerimiz var. Bunun gibi düşünebilirsiniz:

     hash         key    dict_0    dict_1    dict_2...
...010001    ffeb678c    633241c4  fffad420  ...
      ...         ...    ...       ...       ...

64 bit'lik bir makine için, bu, ekstra sözlük başına anahtar başına 16 bayta kadar tasarruf sağlayabilir.

Özel Nesneler ve Alternatifler için Paylaşılan Anahtarlar

Bu paylaşılan anahtar dicts özel nesneler için kullanılmak üzere tasarlanmıştır __dict__. Bu davranışı elde etmek için, __dict__ Bir sonraki nesneyi oluşturmadan öncePEP 412'ye bakınız). Bu, tüm özelliklerinizi __init__ veya __new__, ama alan tasarrufunuzu alamayabilirsiniz.

Ancak, tüm özelliklerinizi zamanında biliyorsanız, __init__ yürütülür, ayrıca sağlayabilir __slots__ nesneniz için ve garanti __dict__hiç oluşturulmaz (ebeveynlerde mevcut değilse), hatta izin ver __dict__ Ancak, öngörülen özelliklerin zaten yuvalarda saklandığını garanti edin. Daha fazla için __slots__, cevabımı burada gör.

Ayrıca bakınız:


23
2018-06-12 21:54



"Biz" ve "Python'un diğer uygulamalarını yakalama şansına sahip olmak için" dediniz - bu "şeyleri bilmeniz" anlamına geliyor ve bu kalıcı bir özellik haline gelebilir mi? Spesifikasyonlar tarafından sipariş edilmek için herhangi bir olumsuzluk var mı? - toonarmycaptain
Sipariş edilmenin olumsuz tarafı, eğer diktelerin sipariş edilmesi bekleniyorsa, sipariş edilmeyen daha iyi / hızlı bir uygulamaya kolayca geçememeleridir. Olsa da böyle olması olası görünmüyor. Ben “şeyleri biliyorum” çünkü çok fazla görüşme izliyorum ve çekirdek üyeler ve diğerleri tarafından benimkinden daha iyi bir gerçek dünya itibarı ile yazılmış pek çok şey okuyorum. Bu nedenle, benim için hemen kullanılabilir bir kaynağım olmasa bile, genellikle Ben bahsettiğim şey. Ama sanırım bu noktayı Raymond Hettinger'in görüşmelerinden alabilirsiniz. - Aaron Hall♦
Eklemenin nasıl çalıştığını biraz açık bir şekilde belirttiniz (“Eğer karma, önceden var olan bir anahtarın karmasıyla aynı şeyi bitirdiyse, o zaman anahtar-değer çiftini farklı bir yere yapıştıracaktır”), ama açıklamıyorsunuz Arama ve üyelik testi nasıl çalışır? Konumun hash tarafından nasıl belirlendiği de net değil, ama büyüklüğün her zaman 2'lik bir güç olduğunu ve sizde karmaşanın son birkaç parçasını aldığınızı sanıyorum ... - Alexey
@Alexey Sağladığım son bağlantı size iyi açıklanmış bir dict uygulamasını verir - ki bu işlevi şu anki 969 no'lu sıraya göre yaparsınız. find_empty_slot: github.com/python/cpython/blob/master/Objects/dictobject.c#L969 - ve hatta 134 numaralı hattan başlayarak bunu açıklayan bir düzyazı var. - Aaron Hall♦