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

Yeni yorum
 
Alexey Oreshkin :

Harika bir teorik örnek! Uygulamada, kim-ne zaman-iş parçacığı binlerce işlemle çalıştı?

ps Bunun saçmalık olduğunu ve kimsenin bir şeye ihtiyacı olmadığını kanıtlamaya çalışmıyorum. Gerçek ticaretin değerini anlamaya çalışıyorum. Ben kesinlikle bir teorisyen değilim, saf bir uygulayıcıyım.

Bu yaklaşık 1000 veya sadece 10 işlem değil. İşin püf noktası, hem 10 hem de 1000000 ..... işlemle eşit derecede etkili çalışan bir kısa kod yazmamızdır.
 

CHashMap'in mevcut uygulaması hakkında kısaca: 

template<typename TKey,typename TValue>
class CHashMap: public IMap<TKey,TValue>
  {
protected :
   int                m_buckets[];                        
   Entry<TKey,TValue>m_entries[];
   int                m_count;
   int                m_free_list;
   int                m_free_count;
   IEqualityComparer<TKey>*m_comparer;
   bool               m_delete_comparer;

     .................................

     .................................

  }

Öncelikle Entry<TKey,TValue>' nin ne olduğunu anlamanız gerekir.
Aslında, bu, aşağıdakileri içeren CLinkedList'teki gibi bir Düğümdür:

- bir anahtar ve değer kabına yerleştirilir
- anahtar için önbelleğe alınmış karma değer - hash_code
- sonraki - çarpışmaları tek başına bağlantılı bir liste yoluyla çözmek için bir sonraki <TKey,TValue> Girişine "işaretçi"


m_entries[] - sonra eklenen anahtar ve değerin, hash_code'un yerleştirildiği bir "hücre" dizisi. Dizinin boyutu Kapasiteye karşılık gelir.
m_count - m_entries içindeki ilk kullanılmayan hücrenin dizinini gösterir. Başlangıç değeri 0'dır, Kapasite'ye kadar büyür, ardından tüm diziler Kapasite ve tüm dizilerin boyutunda bir artışla yeniden oluşturulur.
m_buckets[] - m_entries[] üzerindeki dizin dizisi. Varsayılan değer -1'dir. Dizinin boyutu Kapasiteye karşılık gelir.


Çarpışma yok, CHashMap kapsayıcısına benzersiz bir değer ekliyor:

  1. Anahtarla hash'i hesaplıyoruz, hash_code alıyoruz
  2. Anahtar, değer, hash_code değerlerini m_count dizininde m_entries[] içine yerleştiriyoruz. (sonraki = -1 çünkü örnekte çarpışma yok)
  3. m_buckets[] dizinine hash_code % (ArraySize(m_buckets)) dizinine yeni eklenen öğenin m_entries[] dizin değerini koyduk (bu m_count'tur).
  4. m_count değerini +1 artırıyoruz

Çarpışma yok, CHashMap kapsayıcısında anahtara göre değer alıyor:

  1. Anahtarla hash'i hesaplıyoruz, hash_code alıyoruz
  2. m_buckets[] dizininden hash_code % (ArraySize(m_buckets)) dizininden m_entries[] dizisinden bir dizin olan bir değer alırız
  3. Elde edilen indeks m_buckets[hash_code % (ArraySize(m_buckets))] tarafından m_entries[] dizisinden değer değerimizi alırız.

Çarpışma çözünürlüğü:

Farklı anahtarlar için hash_code_key_1 % (ArraySize(m_buckets)), hash_code_key_2 % (ArraySize(m_buckets)) değerine eşit olacaktır. Buna çarpışma denir.
Bir çarpışma ile m_entries[] öğesine eklenen tüm öğeler, next aracılığıyla tek başına bağlantılı bir listeyle birbirine bağlanır (bkz. Entry<TKey,TValue> yapısı)
Ve m_buckets[] her zaman bu çarpışma listesindeki ilk head öğesinin dizinine işaret eder.
Çarpışmalı büyük bir liste değil, birçok küçük liste ortaya çıkıyor.


Çarpışma, CHashMap kapsayıcısında anahtara göre değer alma:

  1. Anahtarla hash'i hesaplıyoruz, hash_code alıyoruz
  2. m_buckets[] dizininden hash_code % (ArraySize(m_buckets)) dizininden m_entries[] dizisinden bir dizin olan bir değer alırız
  3. Bir sonraki değerin -1'e eşit olmadığını görüyoruz, bu da bir çarpışmanın varlığını gösterir.
  4. Tek tek bağlantılı bir m_entries[] öğeleri listesinden geçiyoruz ve eşitlik için istenen değeri kaydedilmiş anahtarlarla karşılaştırıyoruz


Bir CHashMap kapsayıcısından bir değeri kaldırma:

- m_entries[] içindeki bir hücreyi silerken hiçbir silme gerçekleşmez, hücre serbest olarak belirtilir ve hash_code = -1 olur.
- serbest hücreler kendi serbest hücre listelerini oluştururlar (Entry<TKey,TValue>'den sonraki ile aynı), m_free_list liste baş indeksinden sorumludur
 - Container'a yeni değerler eklendiğinde ilk olarak serbest hücreler kullanılır.
- m_free_count , mevcut boş hücre sayısını kontrol etmek için kullanılır


Hash tablosunu yeniden oluşturma (Kapasite artırma süreci):

- yeniden oluşturma yalnızca Kapasite %100 dolu olduğunda gerçekleşir.
- aşağıdaki Kapasite listeden alınmıştır:

 const static int   CPrimeGenerator::s_primes[]=
  {
   3 , 7 , 11 , 17 , 23 , 29 , 37 , 47 , 59 , 71 , 89 , 107 , 131 , 163 , 197 , 239 , 293 , 353 , 431 , 521 , 631 , 761 , 919 ,
   1103 , 1327 , 1597 , 1931 , 2333 , 2801 , 3371 , 4049 , 4861 , 5839 , 7013 , 8419 , 10103 , 12143 , 14591 ,
   17519 , 21023 , 25229 , 30293 , 36353 , 43627 , 52361 , 62851 , 75431 , 90523 , 108631 , 130363 , 156437 ,
   187751 , 225307 , 270371 , 324449 , 389357 , 467237 , 560689 , 672827 , 807403 , 968897 , 1162687 , 1395263 ,
   1674319 , 2009191 , 2411033 , 2893249 , 3471899 , 4166287 , 4999559 , 5999471 , 7199369
  };

- m_entries[] ve m_buckets[] dizilerinin boyutları artar.
- m_buckets[] temizlenir ve m_entries[]'den alınan verilere göre tamamen yeniden doldurulur (anahtar - hash_code için önbelleğe alınmış karma değer)



Ticaret, otomatik ticaret sistemleri ve ticaret stratejilerinin test edilmesi hakkında forum

Genel sınıf kitaplığı - hatalar, açıklama, sorular, kullanım ve öneriler

Sergey Dzyublik , 2017.12.09 01:12

CHashMap uygulamasıyla tanıştım
 Dürüst olmak gerekirse, beğendim.


Olası iyileştirme için birkaç öneri var:

1) Benim düşünceme göre, uygulama tamamen doğru olmayan bir kapasite seçimi içeriyor - hem ilk boyut 3 hem de hash tablosu yeniden oluşturulduğunda sonrakiler.
Evet, doğru, düzgün dağılım için bir asal sayı seçmeniz gerekiyor.
Ancak, CPrimeGenerator uygulaması beklentileri karşılamıyor ve eksik asal sayılar içeriyor.
Böyle bir "jeneratörün" amacı açıktır - otomatik asal sayılar oluşturma ile 1.2 mertebesinde bir büyüme faktörü sağlamak.
Ancak, bu çok küçük bir faktör değil mi? Vektörler için C++'da katsayı genellikle kitaplığa bağlı olarak 1.5-2.0'dır (çünkü işlemin ortalama karmaşıklığını büyük ölçüde etkiler).
Çıktı sabit bir katsayı olabilir, ardından bir asal sayılar listesinde ikili arama yoluyla sayı bir asal sayıya yuvarlanabilir .
Ve başlangıçtaki kapasite boyutu 3 çok küçük, geçen yüzyılda yaşamıyoruz.

2) Şu anda, karma tablosunun yeniden oluşturulması (Yeniden boyutlandırma) yalnızca %100 doldurma kapasitesi ile gerçekleştirilmektedir (tüm m_entries[] doldurularak)
Bu bağlamda, çok düzgün dağılıma sahip olmayan anahtarlar için önemli sayıda çarpışma mümkündür.
Bir seçenek olarak, karma tablo yeniden oluşturma işlemini gerçekleştirmek için gereken sınıra göre %100 azaltacak bir doldurma faktörü eklemeyi düşünün.


 
Alexey Oreshkin :

Uygulamada, kim-ne zaman-iş parçacığı binlerce işlemle çalıştı?

Evet, birçok insan tek geçişte tarihe milyonlarca gönderme yapıyor.

 
Vasili Sokolov :

Kalelerde, her ilk.

Temiz.

Algoritma tarafından hft siparişleri göndermek ve daha sonra bunları analiz için almak iki farklı şeydir. Bu karmalar, daha sonra tamamen farklı bir şey analiz edildiğinden, analiz için de gönderme için gerekli değildir.

Genelde suç yok. Teori de gereklidir.

 
Alexey Oreshkin :

Temiz.

Algoritma tarafından hft siparişleri göndermek ve daha sonra bunları analiz için almak iki farklı şeydir. Bu karmalar, daha sonra tamamen farklı bir şey analiz edildiğinden, analiz için de gönderme için gerekli değildir.

Genelde suç yok. Teori de gereklidir.


Bulaşık makinesi kullanmıyorum, süngerim var.
Genelde suç yok. Bulaşık makineleri gallimdir, neden sadece ihtiyaç duyulur.

 
Alexey Oreshkin :

Temiz.

Algoritma tarafından hft siparişleri göndermek ve daha sonra bunları analiz için almak iki farklı şeydir. Bu karmalar, daha sonra tamamen farklı bir şey analiz edildiğinden, analiz için de gönderme için gerekli değildir.

Genelde suç yok. Teori de gereklidir.

Ne şikayetleri? Koltuk değneklerini daha fazla yaz.

 
Sergey Dzyublik :

Kısaca CHashMap'in mevcut uygulaması hakkında

Teşekkürler, kaynakları ayrıştırırken kullanacağım.

 
Vasili Sokolov :

Ne şikayetleri? Koltuk değneklerini daha fazla yaz.

İşin aslı, burada önerilen konuyu kullanmıyorum ve haklı olup olmadığımı anlamaya çalışıyorum. Yeterince sıradan ilişkisel dizim var ama her zaman daha iyi olmak istiyorum.
 
fxsaber :

Teşekkürler, kaynakları ayrıştırırken kullanacağım.


Yeni bir anahtar/değer çifti eklerken kapta bir anahtarın varlığının kontrolünü atladım, önce bu yapılır.
Ama önemli değil.

 
Bunun olmamasından kaynaklanan bir hata mesajıyla karşılaşıldı
 //+------------------------------------------------------------------+
//| Gets the element at the specified index.                         |
//+------------------------------------------------------------------+
template < typename T>
bool CArrayList::TryGetValue( const int index,T &value) const

Lütfen bunu tüm Genel'de düzeltin.

1...101112131415161718192021222324...38
Yeni yorum