Verilen eleman(lar)ın bir dizisini temizleme - sayfa 29

Yeni yorum
 
Sergey Dzyublik :
Özünde, çarpışmaları çözmek için bir ilk veri dizisine sahip statik bir HashSet veri yapısı kullanıyorsunuz.
Ama uygulama - sadece gözlerinizi çıkarın ...

100-500 gereksiz parametreye sahip bir işlevi ("FindValueInSortArray") çağırmak yerine, genellikle bu parametrelerin sınıf alanları gibi davrandığı bir sınıf kullanırlar (derleyici örtük satır içi düşünmediyse parametreleri geçerken kazanır).
Aynı boyutta ve aynı kullanım amacına sahip bir çift dizi kullanmak gerekirse ( int p1[]; int p2[];), genellikle bir yapı dizisi kullanılır (erişimde indeksle kazanma, azaltma önbellek kaçırma şansı).

Evet biliyorum. Katılıyorum, kendim kendi uygulamamdan aptalım. Ama benim amacım algoritma, uygulama değil. Dedikleri gibi - algoritmanın doğruluğunu ve hızını kontrol etmek için "dizlerimde toplandı" (yaklaşık bir buçuk saat). Bu konunun (alıntı yapıyorum) "bir dizi gereksiz değeri temizlemenin en hızlı yolu" sorusunu tartıştığını hatırlatmama izin verin.

Kendi algoritmam hakkında çok şikayetim olmasına rağmen, çünkü evrensel olmaktan uzaktır. Algoritmayı iyileştirmenin yollarını görüyorum, ancak kod çok daha karmaşık hale gelecek. Yazık bir zaman.

ZY HashSet Hakkında İlk defa duyuyorum, tk. teoride güçlü değil. Yeni bir şey icat etmediğimi çok iyi anlıyorum, ama her şey benden önce icat edildi. :)) Bu algoritmanın avantajı, kaldırılacak eleman dizisinin düzgün bir dağılımı varsa açıktır. Dağılım, tek tipten çok farklıysa, bu uygulama, bu dalda halihazırda mevcut olan diğerlerine göre hız açısından daha düşük olabilir.

 
Taras Slobodyanik :

toplam hesaplamayı CRC32 ile değiştirdi)

Teşekkür ederim. Tabii ki böylesi daha iyi.

Ama anladığım kadarıyla CRC32'ye geçiş herhangi bir hata ortaya çıkarmadı. :)

 

Modern bilgisayarların ve özellikle MQL5'in yeteneklerinden şahsen etkilendiğimi söyleyeceğim.

Gerçekten de, bir milyon öğelik bir dizide yaklaşık bin farklı değeri aramak, bunları silmek (yaklaşık 100.000 hücre) ve temizlenmiş diziyi yeniden paketlemek saniyenin yalnızca 1/40'ı (!!!) sürer.

 
optimize edilmiş
Dosyalar:
ArrayDeleteValue21.mq5  40 kb
 
nicholi shen :

Ustaca olan her şey basit! :))

Ancak böyle bir algoritmanın kontrolsüz bir şekilde hafızayı tükettiği doğrudur.

Örneğin, değiştirirseniz: 

arr[i]= rand ()% 10000 ;
....
Value2[i]= rand ()% 10000 ;

üzerinde 

arr[i]= rand ()* rand ();
....
Value2[i]= rand ()* rand ();

o zaman durum oldukça farklıdır:

 2018.11 . 19 23 : 25 : 57.593 ArrayDeleteValue21 (NZDUSD,D1)  вариант nicholi shen: Контрольная сумма = 3902843984.813025 ; элементов - 999983 ; время выполнения -  603551 микросекунд
2018.11 . 19 23 : 25 : 57.980 ArrayDeleteValue21 (NZDUSD,D1)  вариант Nikitin     : Контрольная сумма = 3902843984.813025 ; элементов - 999983 ; время выполнения -  383847 микросекунд
2018.11 . 19 23 : 25 : 58.043 ArrayDeleteValue21 (NZDUSD,D1)  вариант fan9        : Контрольная сумма = 3902843984.813025 ; элементов - 999983 ; время выполнения -   61414 микросекунд
2018.11 . 19 23 : 25 : 58.074 ArrayDeleteValue21 (NZDUSD,D1)  вариант Semko       : Контрольная сумма = 3902843984.813025 ; элементов - 999983 ; время выполнения -   28430 микросекунд
Dosyalar:
ArrayDeleteValue21.mq5  40 kb
 
ArrayDeleteValue projesine düzenleme haklarıyla birkaç kişi daha eklendi. Daha önce kimi özledin?
 
Nikolai Semko :

Teşekkür ederim. Tabii ki böylesi daha iyi.

Ama anladığım kadarıyla CRC32'ye geçiş herhangi bir hata ortaya çıkarmadı. :)

evet, ama şimdi sadece bir algoritmanın sonucunu kendi gözleriyle görenler, başkalarının da aynı sonucu alacağından emin olabilir)

 
Lütfen konuya yazınız. Küfür ve küfür yok. Teşekkür ederim.
 
nicholi shen :

Fena fikir değil, ancak bir dizi veya vektörde negatif değerler varsa, dizi aralık dışı hatası alırsınız.

ek olarak, filtreleme bayraklı dizinin boyutu 2 147 483 647 boyutuna ulaşabilir ki bu çok fazla

32 BOOL değişkeninin ayarını aşağıdaki gibi bir bit maskesiyle değiştirerek elbette 32 faktörü azaltılabilir:

 int array_filter( int &a[], const int &b[]) //nicholishen
{
   int e= ArraySize (a);
   int c[];
   int d =b[ ArrayMaximum (b)]+ 1 ;
   ArrayResize (c, b[ ArrayMaximum (b)]/ 32 + 1 );
   ArrayInitialize (c, 0 );
   int i= 0 ;
   int ii= 0 ;
   while (i< ArraySize (b))
   {     
     ii=b[i]/ 32 ;
     c[ii]|=( 1 <<(b[i]-(ii* 32 )));
     i++; 
   } 
   
   int g= 0 , h= 0 , f= 0 ;
   for (g= 0 ; g<e; g++){
      f = a[g];
      ii=f/ 32 ;
       if (f >= d || !(c[ii] & ( 1 <<(f-(ii* 32 )))) )
      {
         a[h]=f;
         h++;
      }
   }
   return ArrayResize (a, h);
}


ama yine de boyut çok büyük kalacak ve hız yaklaşık yarı yarıya düşecek

 
Nikolai Semko :

Ustaca olan her şey basit! :))

Ancak böyle bir algoritmanın kontrolsüz bir şekilde hafızayı tükettiği doğrudur.

Örneğin, değiştirirseniz:

üzerinde

o zaman durum oldukça farklıdır:

Versiyonunuz da iyi ama maalesef sizin de bir zayıf noktanız var. Diyelim ki "ev" koşulları altında, yani ~100 boyutunda küçük diziler ve ~5-10 küçük bir vektör

algoritmanız burada sunulanların hepsinden daha yavaş olacaktır. mikrosaniyelerdeki fark o kadar önemsizdir ki muhtemelen önemli değildir, ancak büyük dizi boyutlarında daha iyidir.

PS, işlevin evrensel olması için, giriş verilerine göre seçilen birkaç farklı algoritmayı birleştirmek gerektiğini düşünüyorum.

1...222324252627282930
Yeni yorum