Genel sınıflar kütüphanesi - hatalar, açıklamalar, sorular, kullanım özellikleri ve öneriler - sayfa 5

Yeni yorum
 
Sergey Dzyublik :

Beklenen öğe sayısına sözlük boyutu izin veriyorsa, hash'ler ortalama olarak O(1)'dir.
Ve sonra, çarpışmaları çözmek için uygulamalara bir bağımlılık var, bu bir liste, hatta belki bir alt hash aracılığıyla olabilir ....

Terminolojik cehaletim anlama sürecine müdahale ediyor. Örnekleri bekleyeceğim. Kısa ve öz istiyorum - emirler, keneler ve benzerleri.

 
fxsaber :

Terminolojik cehaletim anlama sürecine müdahale ediyor. Örnekleri bekleyeceğim. Kısa ve öz istiyorum - emirler, keneler ve benzerleri.


Fırında siparişler. Fırsatlarla ilgileniyor.

 
fxsaber :

Wiki'de okuyun. Sezgisel akıl yürütmenin mantığını hiç anlamadığınız durum.


365 gün sözlük boyutu sınırıdır
sınıftaki öğrenci sayısı, koleksiyondaki beklenen öğe sayısıdır.
doğum günü maçları bir çarpışmadır

 
Sergey Dzyublik :

365 gün sözlük boyutu sınırıdır
sınıftaki öğrenci sayısı, koleksiyondaki beklenen öğe sayısıdır.
doğum günü maçları bir çarpışmadır

Teşekkürler, bu terminolojik tanım daha açıktır. Bu "paradoksun" şube konusuyla ne ilgisi olduğunu anlamıyorum?

 
Sergey Dzyublik :

365 gün sözlük boyutu sınırıdır
sınıftaki öğrenci sayısı, koleksiyondaki beklenen öğe sayısıdır.
doğum günü maçları bir çarpışmadır


Bu örnekte, karma öğrencinin doğum günüdür.
Öğrenci günlüklerini içeren 365 raflı bir dolabımız var.
Her günlüğü, öğrencinin doğum gününe karşılık gelen bir rafa koyarız.

Petrov'un bir öğrencisinin günlüğüne ihtiyacımız var ve ne zaman doğduğunu biliyoruz.
Şimdi, doğum gününe göre, O(1)'de Petrov'un günlüğünü kolayca bulabiliriz, tıpkı diğer öğrencilerin günlüğü gibi.
Bunun istisnası, iki öğrencinin aynı doğum gününe sahip olmasıdır - buna çarpışma denir.

Çarpışma çözümü, iki veya daha fazla günlükten hangisine ihtiyacımız olduğunu belirlemek için ek bilgilerin kullanılmasıdır.
Bir liste aracılığıyla çözümleme, bir çarpışmaya katılan tüm öğelerin istenen öğeyle eşleşmesi için basit bir sıralı numaralandırmadır. Her günlüğü yırtın ve kimin olduğunu görün.
Alt karma sıralama, çarpışmaya dahil olan öğelerin bir karma tablosunun farklı bir kritere göre düzenlenmesidir. Örneğin, öğrenci doğduğunda.


Konuyla ilgileniyorsanız, youtube'daki MailRu'dan algoritmalar ve veri yapıları hakkında kursu tavsiye ederim.

 
Sergey Dzyublik :

Bu örnekte, karma öğrencinin doğum günüdür.
Öğrenci günlüklerini içeren 365 raflı bir dolabımız var.
Her günlüğü, öğrencinin doğum gününe karşılık gelen bir rafa koyarız.

Petrov'un bir öğrencisinin günlüğüne ihtiyacımız var ve ne zaman doğduğunu biliyoruz.
Artık O(1)'in doğum gününe kadar Petrov'un günlüğünü ve başka bir öğrenciyi kolayca bulabiliriz.
İstisna, iki öğrencinin aynı doğum gününe sahip olmasıdır - buna çarpışma denir.

Çarpışma çözümü, iki veya daha fazla günlükten hangisine ihtiyacımız olduğunu belirlemek için ek bilgilerin kullanılmasıdır.
Bir liste aracılığıyla çözümleme, bir çarpışmaya katılan tüm öğelerin istenen öğeyle eşleşmesi için basit bir sıralı numaralandırmadır. Her günlüğü yırtın ve kimin olduğunu görün.
Alt karma sıralama, çarpışmaya dahil olan öğelerin bir karma tablosunun farklı bir kritere göre düzenlenmesidir. Örneğin, öğrenci doğduğunda.


Konuyla ilgileniyorsanız, youtube'daki MailRu'dan algoritmalar ve veri yapıları hakkında kursu tavsiye ederim.

Her şey ilk başta hayal ettiğim gibi. Sadece neyin vurgulandığını anlamıyorum. Karma bir dizin değildir, bu nedenle onu bir dizi işaretçide ofset ile hemen bulabilirsiniz. Aynı şekilde, Listeye bakmanız gerekir. Ve bu, uygun sıralamaya sahip ikili bir aramadır.

 
fxsaber :

Her şey ilk başta hayal ettiğim gibi. Sadece neyin vurgulandığını anlamıyorum. Karma bir dizin değildir, bu nedenle onu bir dizi işaretçide ofset ile hemen bulabilirsiniz. Aynı şekilde, Listeye bakmanız gerekir. Ve bu, uygun sıralamaya sahip ikili bir aramadır.


Vurgulananlar sözlü yazım hatalarıdır)) Ve zaten düzeltildi.
Hash bir indekstir. Sözlüğün boyutuna göre dökülür.

Her raf aynı yüksekliğe sahiptir ve raf sayısına göre tam olarak hangi yükseklikte arayacağınızı bilebilirsiniz. O(1)

 

1 numaralı ilişkisel dizi hakkında mümkün olduğunca basit

Generic'te sunulan algoritmaların çoğu, şu veya bu şekilde bir ilişkisel dizi veya sözlüğe dayanmaktadır. Ayrıca en sık kullanılan iki algoritmadan biridir. Programlamadaki tüm görevlerin %90'ının diziler ve sözlükler tarafından kapsandığını söylersem gerçeğe yakın olacağımı düşünüyorum. Uygulamaya geçmeden önce, bazı detayları kasıtlı olarak basitleştirerek, sözlüğün çalışmasını mümkün olduğunca basit ve anlaşılır bir şekilde anlatacağız.

Sözlüğü çok basit bir örnek kullanarak analiz edeceğiz: sıradan bir kelime sözlüğü. Diyelim ki elimizde bu kelimelerden sadece birkaçı var ve hepsi alfabenin farklı harfleriyle başlıyor:

 string words[] = { "apple" , "cat" , "fog" , "dog" , "walk" , "zero" };

İngiliz alfabesi 26 karakter içerir. 26 elemanlı bir dizi dizi oluşturalım:

 string dictionary[ 26 ];

Şimdi, kelimeleri ilk harflerine karşılık gelen dizinlerde saklamayı kabul edersek, en basit sözlüğü elde ederiz. İndekslemeyi sıfırdan yapacağız. "Elma" kelimesi 0 dizininde saklanacaktır, çünkü "a" karakteri alfabenin ilk harfidir, "kedi" - dizin 1'de, "köpek" - dizin 3'te, sis - dizin 4'ü işgal edecektir, yürü - dizin 24 ve sıfır, son 25. dizindir.

5 ile 23 arasındaki dizinlerin kullanılmayacağını unutmayın. Bu ek bir bellek masrafıdır, ancak örneğin "yürümek" kelimesine anında erişebiliriz, çünkü eğer varsa, o zaman indeks 24'te bulunduğunu biliyoruz.

İlk boş sözlüğümüzü yazalım:

 //+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link        "http://www.mql5.com"
#property version    "1.00"
string words[ 26 ];

bool Contains( string word)
{
   uchar index = ( uchar ) StringGetCharacter (word, 0 )- 97 ;
   return words[index] != NULL ;
}
bool Add( string word)
{
   uchar index = ( uchar ) StringGetCharacter (word, 0 )- 97 ;
   if (words[index] == NULL )
   {
      words[index] = word;
       return true ;
   }
   return false ;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart ()
  {
//---
   Add( "apple" );
   if (Contains( "apple" ))
       printf ( "Словарь содержит слово apple" );
   else
       printf ( "Словарь не содержит слово apple" );
  }
//+------------------------------------------------------------------+

Buna "elma" kelimesini ekler ve sonra onu bulursanız, bu kelimeye erişim bulma işlemi anında olacaktır. Çünkü bu kelimenin bulunabileceği indeksi önceden biliyoruz. Dizin için başka seçenek olamaz, bu nedenle tüm listenin yinelenmesi gerekli değildir. Hemen hemen tüm sözlükler bu özelliğe dayanmaktadır.

Aşağıdaki örnekte, aynı harfle başlayan kelimeleri depolayabilmesi için onu iyileştireceğiz.

 

2 numaralı ilişkisel dizi hakkında mümkün olduğunca basit

Farklı kelimeler alfabenin aynı harfiyle başlar. Bir önceki sözlüğümüze "elma" kelimesini koyarsak ve sonra oraya "uygulama" koymaya çalışırsak, ondan hiçbir şey çıkmaz. Dizin 0 zaten elma kelimesi tarafından işgal edilecektir. Bu durumda, bir hash fonksiyonu çarpışmasından söz edilir. Karma işlevimiz çok basittir - kelimenin ilk karakterinin numarasını döndürür, bu nedenle bu işlevdeki çarpışmalar çok sık olacaktır. Aynı harfle başlayan farklı kelimeleri saklamak için bir ekleme yapacağız: elemanları bir dizide değil, bir dizi dizisinde saklayacağız. Ardından, 0 dizininde iki kelime içeren başka bir dizi olacaktır: "elma" ve "uygulama":

 //+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link        "http://www.mql5.com"
#property version    "1.00"
#include <Arrays\ArrayObj.mqh>
#include <Arrays\ArrayString.mqh>
CArrayString* WordsArray[ 26 ];

bool Contains( string word)
{
   uchar index = ( uchar ) StringGetCharacter (word, 0 )- 97 ;
   CArrayString* words = WordsArray[index];
   if (words == NULL )
       return false ;
   for ( int i = 0 ; i < words.Total(); i++)
       if (word == words.At(i))
         return true ;
   return false ;
}
bool Add( string word)
{
   uchar index = ( uchar ) StringGetCharacter (word, 0 )- 97 ;
   CArrayString* words;
   if (WordsArray[index] == NULL )
      WordsArray[index] = new CArrayString();
   words = WordsArray[index];
   for ( int i = 0 ; i < words.Total(); i++)
       if (word == words.At(i))
         return false ;
   words.Add(word);
   return true ;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart ()
  {
//---
   //ArrayResize(WordsArray, 26);
   Add( "apple" );
   Add( "application" );
   if (Contains( "application" ))
       printf ( "Словарь содержит слово application" );
   else
       printf ( "Словарь не содержит слово application" );
  }
//+------------------------------------------------------------------+

Artık sözlüğümüz aynı harfle başlayan kelimeleri bile saklıyor. Ancak ilk harfi aynı olan kelimelere erişim fiyatı artıyor. Çünkü artık 'application' kelimesinin sözlükte olup olmadığını anlamak için 'a' ile başlayan tüm kelimelerin tam olarak aranması gerekiyor. Eğer hash fonksiyonumuz, kelimeler bir karakter ile farklılık gösterse bile farklı sayılar üretseydi, aynı indekse sahip kelimeler üzerinde yineleme olasılığı sıfıra ve rastgele bir öğeye erişim o(1) eğilimine girerdi . Bu tam olarak gerçek sözlüklerde olan şeydir, orada kullanılan fonksiyonlar çarpışmalara karşı dayanıklıdır, bu yüzden kesinlikle bu koleksiyonlardaki öğelere erişimin çok hızlı ve neredeyse numaralandırma olmadan olduğunu söyleyebiliriz.

 
Vasili Sokolov :

Bir ilişkisel dizi hakkında mümkün olduğunca basit

Generic'te sunulan algoritmaların çoğu bir şekilde bir ilişkisel diziye veya sözlüğe dayanmaktadır. Ayrıca en sık kullanılan iki algoritmadan biridir. Programlamadaki tüm görevlerin %90'ının diziler ve sözlükler tarafından kapsandığını söylersem gerçeğe yakın olacağımı düşünüyorum. Uygulamaya geçmeden önce, bazı detayları kasıtlı olarak basitleştirerek, sözlüğün çalışmasını mümkün olduğunca basit ve anlaşılır bir şekilde anlatacağız.

Sözlüğü çok basit bir örnek kullanarak analiz edeceğiz: sıradan bir kelime sözlüğü. Diyelim ki elimizde bu kelimelerden sadece birkaçı var ve hepsi alfabenin farklı harfleriyle başlıyor:

İngiliz alfabesi 26 karakter içerir. 26 elemanlı bir dizi dizi oluşturalım:

Şimdi, kelimeleri ilk harflerine karşılık gelen dizinlerde saklamayı kabul edersek, en basit sözlüğü elde ederiz. İndekslemeyi sıfırdan yapacağız. "Elma" kelimesi 0 dizininde saklanacaktır, çünkü "a" karakteri alfabenin ilk harfidir, "kedi" - dizin 1'de, "köpek" - dizin 3'te, sis - dizin 4'ü işgal edecektir, yürü - dizin 24 ve sıfır, son 25. dizindir.

5 ile 23 arasındaki dizinlerin kullanılmayacağını unutmayın. Bu ek bir bellek masrafıdır, ancak örneğin "yürümek" kelimesine anında erişebiliriz, çünkü eğer varsa, o zaman indeks 24'te bulunduğunu biliyoruz.

İlk boş sözlüğümüzü yazalım:

Buna "elma" kelimesini ekler ve sonra onu bulursanız, bu kelimeye erişim bulma işlemi anında olacaktır. Çünkü bu kelimenin bulunabileceği indeksi önceden biliyoruz. Dizin için başka seçenek olamaz, bu nedenle tüm listenin yinelenmesi gerekli değildir. Hemen hemen tüm sözlükler bu özelliğe dayanmaktadır.

Aşağıdaki örnekte, aynı harfle başlayan kelimeleri depolayabilmesi için onu iyileştireceğiz.

Çözüm mükemmel. Her şey mümkün olduğunca basit. Yalnızca işlevler, diziler ve uygun veri organizasyonu. Bunun hakkında konuştum.
123456789101112...38
Yeni yorum
Neden: