Limpar um conjunto de elementos definidos - página 29

Novo comentário
 
Sergey Dzyublik:
Essencialmente você está usando uma estrutura de dados estática HashSet com uma matriz inicial de dados para resolver colisões.
Mas a implementação está apenas abrindo os olhos...

Em vez de chamar a função ("FindValueInSortArray") com 100-500 parâmetros desnecessários, geralmente se usa classe onde esses parâmetros atuam como campos de classe (ganho na passagem de parâmetros, se o compilador não adivinhou fazer em linha implícita).
Se houver necessidade de usar um par de matrizes do mesmo tamanho e com um propósito de uso ( int p1[]; int p2[];), geralmente é usada uma matriz de estrutura (vantagem de acesso de índice, menos chance de falha de cache).

Sim, eu sei. Concordo, eu mesmo estou com medo de minha própria implementação. Mas meu objetivo é o algoritmo, não a implementação. Como eles dizem - "montado de joelhos" (cerca de uma hora e meia), para verificar a correção e a velocidade do algoritmo. Lembre-se de que este tópico discute (e cito) "a maneira mais rápida de descarregar uma série de valores de lixo".

Embora eu tenha muitas reclamações sobre meu próprio algoritmo, porque ele está longe de ser universal. Posso ver maneiras de melhorar o algoritmo, mas o código se tornará muito mais complexo. Uma pena sobre o tempo.

ZZY HashSet ouviu pela primeira vez, porque eu não sou forte em teoria. Estou bem ciente de que não inventei nada de novo e tudo foi inventado antes de mim. :)) A vantagem deste algoritmo é evidente quando o conjunto de itens a serem excluídos tem uma distribuição uniforme. Se a distribuição for muito diferente do uniforme, esta implementação pode ser inferior em velocidade a outras que já existem neste ramo.

 
Taras Slobodyanik:

alterou o cálculo do montante para CRC32 )

Obrigado. É claro que é mais correto.

Mas até onde eu entendi, a mudança para CRC32 não revelou nenhum erro. :)

 

Deixe-me dizer-lhe que estou pessoalmente impressionado com as capacidades dos computadores modernos e da MQL5 em particular.

Afinal, leva apenas 1/40 segundos(!!!) para procurar cerca de mil valores diferentes em um conjunto de um milhão de elementos, apagá-los (cerca de 100.000 células) e reembalar o conjunto limpo.

 
otimizado
Arquivos anexados:
ArrayDeleteValue21.mq5  40 kb
 
nicholi shen :

É tudo brilhantemente simples! :))

Mas, no entanto, este algoritmo consome a memória de forma incontrolável.

Assim, por exemplo, se você substituir

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

com .

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

a situação é completamente diferente:

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 микросекунд
Arquivos anexados:
ArrayDeleteValue21.mq5  40 kb
 
Acrescentou ArrayDeleteValue a mais duas pessoas no projeto, direitos de edição. De quem eu sentia falta antes.
 
Nikolai Semko:

Obrigado. Este é certamente o caminho certo a ser seguido.

Mas até onde eu entendi, a mudança para CRC32 não revelou nenhum erro. :)

Sim, mas agora aqueles que viram com seus próprios olhos o resultado de apenas um algoritmo, podem garantir que outros obtenham o mesmo resultado)

 
Por favor, escreva sobre o assunto. Sem flubbing ou palavrões. Obrigado.
 
nicholi shen:

Não é uma má idéia, mas se houver valores negativos em um array ou vetor, você obterá um array fora do intervalo de erro

Além disso, o tamanho de uma matriz com bandeiras filtrantes pode chegar a2 147 483 647, o que é demais.

Naturalmente, você pode reduzir o tamanho em 32 vezes substituindo a configuração de 32 variáveis BOOL por uma máscara de bit como esta:

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


mas ainda seria muito grande e a velocidade cairia pela metade.

 
Nikolai Semko:

É tudo brilhantemente simples! :))

Mas, no entanto, este algoritmo consome a memória de forma incontrolável.

Assim, por exemplo, se você substituir

com .

a situação é bem diferente:

Sua versão também é boa, mas infelizmente você também tem um ponto fraco. Sob condições "domésticas", ou seja, pequenas matrizes de tamanho ~100 e pequeno vetor ~5-10

seu algoritmo será mais lento do que todos os aqui apresentados, embora a diferença em microssegundos seja tão insignificante que provavelmente não importa, mas em matrizes maiores é o melhor.

P.S. Eu acho que essa função deve ser universal, é necessário combinar nela alguns algoritmos diferentes captados de acordo com os dados de entrada.

1...222324252627282930
Novo comentário