Cancellare un array di elementi definiti - pagina 29

Nuovo commento
 
Sergey Dzyublik:
Essenzialmente state usando una struttura dati statica HashSet con un array iniziale di dati per risolvere le collisioni.
Ma l'implementazione è semplicemente illuminante...

Invece di chiamare la funzione ("FindValueInSortArray") con 100-500 parametri non necessari, di solito si usa la classe dove questi parametri agiscono come campi della classe (guadagno sul passaggio dei parametri, se il compilatore non ha indovinato di fare inline implicito).
Se c'è bisogno di usare una coppia di array della stessa dimensione e con uno scopo d'uso ( int p1[]; int p2[];), di solito si usa un array di strutture (vantaggio di accesso all'indice, meno possibilità di cache miss).

Sì, lo so. Sono d'accordo, anch'io ho paura della mia attuazione. Ma il mio obiettivo è l'algoritmo, non l'implementazione. Come si dice - "assemblato in ginocchio" (circa un'ora e mezza), per verificare la correttezza e la velocità dell'algoritmo. Ricordate che questo thread discute (e cito) "il modo più veloce per lavare un array di valori spazzatura".

Anche se ho molte lamentele sul mio algoritmo, perché è tutt'altro che universale. Posso vedere modi per migliorare l'algoritmo ma il codice diventerà molto più complesso. Un peccato per il tempo.

ZZY HashSet prima sentito, perché non sono forte in teoria. So bene che non ho inventato niente di nuovo e che tutto è stato inventato prima di me. :)) Il vantaggio di questo algoritmo è evidente quando l'array di elementi da cancellare ha una distribuzione uniforme. Se la distribuzione è molto diversa dall'uniforme, questa implementazione può essere inferiore in velocità ad altre che già esistono in questo ramo.

 
Taras Slobodyanik:

ha cambiato il calcolo dell'importo in CRC32 )

Grazie. Naturalmente è più corretto.

Ma per quanto ho capito, il passaggio a CRC32 non ha rivelato alcun errore. :)

 

Lasciate che vi dica che sono personalmente impressionato dalle capacità dei computer moderni e di MQL5 in particolare.

Dopo tutto, ci vuole solo 1/40 secondi(!!!) per cercare un migliaio di valori diversi in un array di un milione di elementi, cancellarli (circa 100.000 celle) e riconfezionare l'array pulito.

 
ottimizzato
File:
ArrayDeleteValue21.mq5  40 kb
 
nicholi shen :

È tutto brillantemente semplice! :))

Ma, tuttavia, questo algoritmo consuma memoria in modo incontrollato.

Così, per esempio, se si sostituisce

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

con .

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

la situazione è completamente diversa:

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 микросекунд
File:
ArrayDeleteValue21.mq5  40 kb
 
Aggiunto ArrayDeleteValue a un altro paio di persone nel progetto, diritti di modifica. Che mi sono perso prima.
 
Nikolai Semko:

Grazie. Questo è certamente il modo giusto di procedere.

Ma per quanto ho capito, il passaggio a CRC32 non ha rivelato alcun errore. :)

Sì, ma ora chi ha visto con i propri occhi il risultato di un solo algoritmo, può fare in modo che altri ottengano lo stesso risultato)

 
Per favore, scrivi sull'argomento. Nessuna sbavatura o imprecazione. Grazie.
 
nicholi shen:

Non è una cattiva idea, ma se ci sono valori negativi in un array o in un vettore, otterrete un errore di array fuori portata

Inoltre, la dimensione di un array con i flag di filtraggio può raggiungere2 147 483 647, che è troppo

Naturalmente, potete ridurre la dimensione di 32 volte sostituendo l'impostazione di 32 variabili BOOL con una bitmask come questa:

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);
}


ma sarebbe comunque troppo grande e la velocità scenderebbe di circa la metà.

 
Nikolai Semko:

È tutto brillantemente semplice! :))

Ma, tuttavia, questo algoritmo consuma memoria in modo incontrollato.

Così, per esempio, se si sostituisce

con .

la situazione è molto diversa:

La tua versione è anche buona, ma purtroppo hai anche un punto debole. In condizioni "domestiche", cioè piccoli array di dimensioni ~100 e piccoli vettori ~5-10

il vostro algoritmo sarà più lento di tutti quelli presentati qui, anche se la differenza in microsecondi è così insignificante che probabilmente non importa, ma su array più grandi è il migliore.

P.S. Penso che la funzione dovrebbe essere universale, è necessario combinare in essa alcuni algoritmi diversi raccolti secondo i dati di input.

1...222324252627282930
Nuovo commento