Genel sınıflar kütüphanesi - hatalar, açıklamalar, sorular, kullanım özellikleri ve öneriler - sayfa 10
Ticaret fırsatlarını kaçırıyorsunuz:
- Ücretsiz ticaret uygulamaları
- İşlem kopyalama için 8.000'den fazla sinyal
- Finansal piyasaları keşfetmek için ekonomik haberler
Kayıt
Giriş yap
Gizlilik ve Veri Koruma Politikasını ve MQL5.com Kullanım Şartlarını kabul edersiniz
Hesabınız yoksa, lütfen kaydolun
Hash fonksiyonları hakkında
Önceki örneklerden, hash fonksiyonunun yükün büyük kısmını üstlendiği açıkça görülmektedir. Karma işlevi olabildiğince hızlı yapılabilir, ancak büyük olasılıkla bu durumda çarpışmalara oldukça açık olacaktır. Tersine, bir karma işlevi mümkün olduğunca çarpışmalara karşı dirençli hale getirilebilir, ancak hesaplama karmaşıklığı gerçekleştirilen görev için yetersiz olacaktır. İki uç örneğe bakalım. Örnek 1, en hızlı hash fonksiyonu:
Her zaman aynı numarayı döndürür. Sözlüğümüz sadece bir kelimeyi saklayacaksa, çalışması yeterli olacaktır, çünkü bu kelime indeks 0'da olacaktır. Ancak, eğer 10 kelime varsa, o zaman on kelimenin tümü sıfır indeksinde olacaktır (bir dizi dizimiz olduğunu unutmayın).
İkinci örnek için, örneğin N turlu bir Feistel ağına dayalı olarak tersine çevrilebilir şifrelemeye dönelim.Bu bir karma işlevi değildir ve çarpışmalara tabi değildir. Onlar. iki farklı dizi için garantili farklı sayılar elde ederiz. Ortaya çıkan sayıların uzunluğu, dizenin uzunluğuna eşit olacaktır. Bu nedenle, 1000 karakter uzunluğunda bir dize için 1000 boyutunda bir uchar dizisi alacağız. Bu dizeyi 3 öğe boyutunda bir sözlükte saklamamız gerekirse, bunun garip olduğunu kabul edeceksiniz. sadece üç elemanlı bir kelime aramak için böyle karmaşık bir kodu hesaplamak.
Bu nedenle, her zaman bir orta yol aramalıyız (fxsaber'ın haklı olarak işaret ettiği gibi): hash'i hızlı bir şekilde hesaplayacak ve kural olarak çarpışma vermeyecek bir fonksiyona ihtiyacımız var. Önceki hash fonksiyonumuzun çarpışma olasılığını tahmin edelim:
Alfabede 26 karakter vardır. 'a' karakteriyle başlayan kelimelerin sayısının, herhangi bir başka karakterle başlayan kelimelerin sayısına eşit olduğunu varsayacağız. O zaman sözlüğümüzde 988 kelime varsa, bunlardan 38'i a harfiyle, 38'i - b harfiyle, 38 - c harfiyle, ... 38 - w harfiyle ve 38'i harfiyle başlayacak - z . Her durumda çarpışma olasılığı 1/26 veya %3,8461 olacaktır. 988 kelimemiz varsa, indeks başına 988*3.8461 = 37.999 kelime elde ederiz.
Aynı harf için ne kadar çok kelime olursa, belirli bir kelimeyi bulmanın o kadar zor olduğu açıktır. Bizim durumumuzda, sadece ilk harfin indeksini hesaplamak değil, aynı zamanda kelimeleri tam olarak karşılaştırmak için aynı harfle başlayan tüm kelimeleri sıralamak gerekecektir. Her ne ise, hash fonksiyonunu karmaşık hale getirebiliriz:
Onlar. zaten bir kelimenin ilk iki karakterini alıyoruz. O zaman 26 olası kombinasyon olmayacak, ancak 26^2 = 676 olacak. Karma işlevinin hesaplanmasının ikinci varyantının karmaşıklığının doğrusal olarak, kabaca iki kez arttığını, çarpışmalara karşı direncinin doğrusal olmayan bir şekilde arttığını not ediyorum, kare.
İkinci seçenek için ortalama olarak her 676 kelime için bir çarpışma olacaktır. Bizim durumumuzda 988 kelime için indeks başına 988/676 = 1.4615 çarpışma olacaktır. Onlar. her dizin ortalama olarak bir kelime veya 2 kelime içerecektir. Onlar. ortalama olarak, hiç arama yapılmayacaktır (bir karşılaştırma) veya çok kısa olacaktır (iki karşılaştırma).
Sözlük boyutunun karma işlev kombinasyonlarına oranı 1.0000000 eğilimindeyse, ortalama olarak numaralandırmaya gerek yoktur, çünkü her öğe yalnızca kendi dizininde yer alacaktır. Eğer hash fonksiyonu çok geniş bir değer aralığı üretecekse, o zaman sözlüğün boyutunun hash fonksiyonunun olası kombinasyonlarına oranı her zaman 1.0'dan bile az olacaktır. Örneğin, karma işlevi 2^32 kombinasyon üretecekse, 2^32'den küçük herhangi bir N boyutu için N/2^32 < 1.0 oranı karşılanacaktır. N çok küçükse, özet fonksiyonu tarafından elde edilen sayıyı her zaman N limitinde olacak şekilde normalleştiririz:
int index = GetHashCode(word)% ArraySize (m_array);
Karma işlevi tek tip sonuçlar veriyorsa, ortalama olarak 1.000 oranını elde ederiz. onlar. dizi indeksi başına sadece bir kelime olacaktır. Bu nedenle, bir sözlüğün, bir dizin yerine bir anahtarın belirtildiği bir dizinin özel bir durumu olduğunu söyleyebiliriz.
Bir dizinin boyutu, bir sözlüğün boyutuna uyacak şekilde kolayca değiştirilebilir.
Sonsuz seçenekler dikkate alınmaz.
İşin aslı, bir sözlüğün boyutunun çoğu zaman bilinmemesidir. Basit bir örnek, diyelim ki bir Uzman Danışmanımız var. Tamamlanan işlemlerin kaydını tutar. Anlaşmanın tarihe geçmesinden sonra, bu anlaşmayı, diyelim ki uzmanın büyüsüyle ilişkilendirmek gerekiyor. Bunu yapmak için bir sözlük kullanmak mantıklıdır. İşlem numarasının anahtar (benzersiz tanımlayıcı) olarak kullanıldığı ve uzmanın sihirli numarasının değer olarak kullanıldığı durumlarda. Sorun şu ki, bir danışman başlatırken, 100 işlemimiz mi yoksa 1000 işlemimiz mi olacağını önceden belirlemek imkansız. Önceden ne kadar bellek ayırırsanız ayırın, yine de ya çok az ya da çok fazla olacaktır.
İşin aslı, bir sözlüğün boyutunun çoğu zaman bilinmemesidir. Basit bir örnek, diyelim ki bir Uzman Danışmanımız var. Tamamlanan işlemlerin kaydını tutar. Anlaşmanın tarihe geçmesinden sonra, bu anlaşmayı, diyelim ki uzmanın büyüsüyle ilişkilendirmek gerekiyor. Bunu yapmak için bir sözlük kullanmak mantıklıdır. İşlem numarasının anahtar (benzersiz tanımlayıcı) olarak kullanıldığı ve uzmanın sihirli numarasının değer olarak kullanıldığı durumlarda. Sorun şu ki, bir danışman başlatırken, 100 işlemimiz mi yoksa 1000 işlemimiz mi olacağını önceden belirlemek imkansız. Önceden ne kadar bellek ayırırsanız ayırın, yine de ya çok az ya da çok fazla olacaktır.
Eh, görevlerin farklı olduğu açıktır.
Bir insan dili için uygun bir sözlük oluşturmanın gerekli olduğu bir sorunu çözdüm. Dizimin boyutu kesin değil, ancak onu belirli bir dildeki sözcük sayısına uydurmanın sorunu nedir? Oraya kolayca sığar.
Örneğin, Rusça. Diyelim ki 10.000 temel kelime içeriyor. Tüm bu kelimeler dizime mükemmel bir şekilde yerleştirilebilir.
İlk boyut 66 harftir (küçük ve büyük), ikinci boyut bir kelimedeki harf sayısıdır (örneğin 25'e kadar), üçüncü boyut ilk harf ve harf sayısı - 50 için eşleşmelerdir.
Bütün dil sığacak.
//------------------------------------
Başlangıçta, tam olarak bu sorunu çözdüm. Şimdi asıl sorunu bir başkasıyla değiştiriyorsunuz ve çözümün iyi olmadığını söylüyorsunuz.
Önceden ne kadar bellek ayırırsanız ayırın, yine de ya çok az ya da çok fazla olacaktır.
Doğru.
Tüm problemler için evrensel bir çözüm olmadığı da doğrudur.
Doğru.
Tüm problemler için evrensel bir çözüm olmadığı da doğrudur.
Kesinlikle inkar edilemez.
Sessiz yoldaş. Hiç kimse hatalardan bağışık değildir, sen bile. Bu nedenle, nazik olun, başkalarının hatalarını daha yumuşak bir tonda belirtin. Şimdi düzelteceğim.
Ve doğru seçenek bir sır olarak kalacak ???
Prensip olarak, hash tablolarının ve hash'lerin doğru bir versiyonu olamaz - bunların hepsi belirli hedeflere ve kullanım koşullarına bağlıdır.
Sandviç yapmak gibi. Belki biri mayonez ya da ketçap yemiyor ya da vegan....
Ancak masaya ketçap serpmek ve üzerine ekmek koymak - bunun olmadığı açık görünüyor ....
Tembel için konuyla ilgili temel bilgiler:
https://www.slideshare.net/mkurnosov/6-32402313
Gerçekte, her şey çok daha karmaşıktır ve ilgili literatürde veya iyi "algoritmalar ve veri yapıları" derslerinde tartışılmaktadır.
Kısacası, önce karma işlevi çalışmalıdır: hızlı, ikincisi - tamamen karmaşık bir şey icat etmeye gerek yoktur, çünkü aynı değerlerin görünümü normalde sözlük içinde doğrudan numaralandırma ile çözülür. Ana şey, çok sık çarpışma olmamasıdır, hepsi bu. Generic'te, HashFunction.mqh dosyasındaki bir dizi işlev, temel türlerin işlev karmasından sorumludur. Orada her şeyin basit olduğundan emin olmak için nasıl çalıştığını görelim:
Tamsayı türleri ya olduğu gibi döndürülür ya da kısa tamsayı türleri için basit bit düzeyinde dönüştürme işlemleri kullanılır. 32 bit'e sığmayan türler için, sağ ve sol kısımların özel veya ardından gelen birleşimi kullanılır. Dizeler için, doğrudan numaralandırma yoluyla karmaşık olmayan bir karma da hesaplanır. Reel sayılar için birleşim yardımı ile bir bit gösterimi alınır ve zaten hash olarak kullanılır.
Sözlük tipi algoritmalar şartlı olarak iki kısma ayrılır:
CHashSet nedir? Bu, her öğenin benzersiz olduğu bir koleksiyondur (özünde bir dizi). Örneğin, böyle bir koleksiyon 2,5,1,7,10,15,1024 sayılarını içerebilir. Ama hiçbir iki sayı aynı değildir. Ayrıca diziler, gerçek sayılar ve hatta kullanıcı tanımlı karmaşık türleri de içerebilir (daha sonra anlatacağız). Ancak herhangi bir tür için kural aynıdır - sözlükte böyle bir tane olamaz.
CHashMap nedir? Bu, her öğenin karmaşık bir anahtar/değer türü olduğu bir koleksiyondur (özünde de bir dizidir):
CHashMap'e çok benzer şekilde yapılandırılmıştır, ancak set öğesi 1'in set 2'ye karşılık gelmesi için iki seti eşlemenize izin verir. Bu, ortalama bir O(1) yürütme süresi ile çok verimli sorgu algoritmaları yazmanıza izin veren çok kullanışlı bir özelliktir.
Daha sonra, örnekler kullanarak bir tür yazışmanın yapısını inceleyeceğiz.
İlginç bir şekilde, herhangi bir anahtar/değer sözlüğü doğal olarak böyle önemsiz olmayan bire çok ilişki kurar. Örneğin, elimizde bir sürü tarihi emir ve bunlara dayalı olarak gerçekleştirilen bir sürü işlem var. Her anlaşma yalnızca bir siparişe karşılık gelir, ancak bir sipariş birkaç anlaşmaya karşılık gelebilir. Böyle bir ilişkinin sözlüğü, anlaşmanın numarasını bir anahtar olarak ve bir değer olarak, onu açmaya yarayan siparişin numarasını saklayabilir.