Очистка массива от заданного (ых) элементов - страница 29

Новый комментарий
 
Sergey Dzyublik:
По сути вами используется структура данных статический HashSet с исходным массивом данных для решения коллизий.
Но реализация - просто вырви глаз...

Вместо вызова функции ("FindValueInSortArray") с 100-500 ненужных параметров, обычно используют класс, где эти параметры выступают в виде полей класса (выигрыш на передаче параметров, если компилятор не додумался сделать implicit inline).
Если имеется нужда использовать пару массивов одинакового размера и с одной целью применения ( int p1[]; int p2[];) обычно используют массив структуры (выигрыш на доступе по индексу, уменьшение шанса cache miss).

Да, знаю. Согласен, мне самому стрёмно от собственной реализации. Но моя цель - это алгоритм, а не реализация. Как говориться - "собрал на коленках"(где-то за полтора часа), чтобы проверить правильность и скорость алгоритма. Напомню, что в этой ветке обсуждается вопрос (цитирую) "самого быстрого способа очистки массива от ненужных значений" .

Хотя и к собственному алгоритму у меня много претензий, т.к. он далеко не универсален. Вижу пути улучшения алгоритма, но код значительно усложнится. Жалко времени.

ЗЫ Про HashSet слышу впервые , т.к. не силен в теории. Прекрасно понимаю, что я не изобрел чего-то нового, а все придумано до меня. :)) Выигрыш данного алгоритма налицо, если массив удаляемых элементов имеет равномерное распределение. Если распределение сильно отличается от равномерного, то данная реализация может уступать в скорости другим уже существующим в этой ветке. 

 
Taras Slobodyanik:

заменил расчет суммы на CRC32 )

Спасибо. Конечно так правильнее.

Но насколько я понял, переход на CRC32 не выявил ошибок. :)

 

Скажу я вам, что лично меня впечатляет возможности современных компьютеров и MQL5 в частности.

Ведь на поиск около тысячи различных значений в массиве из одного миллиона элементов, их удаление(около 100 000 ячеек) и переупаковку очищенного массива уходит всего 1/40 секунды(!!!)

 
optimized
Файлы:
ArrayDeleteValue21.mq5  40 kb
 
nicholi shen :

Все гениальное просто! :))

Но, правда, пямять кушает такой алгоритм бесконтрольно.

Так, например если заменить:

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

на

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

то ситуация уже совсем другая:

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 микросекунд
Файлы:
ArrayDeleteValue21.mq5  40 kb
 
Добавил в проекте ArrayDeleteValue еще паре человек, права на редактирование. Кого раньше пропустил.
 
Nikolai Semko:

Спасибо. Конечно так правильнее.

Но насколько я понял, переход на CRC32 не выявил ошибок. :)

да, но теперь те, кто видели своими глазами результат только одного алгоритма, могут убедиться, что и другие получают такой же результат)

 
Прошу писать по теме. Без флуда и ругани. Спасибо.
 
nicholi shen:

Неплохая идея но при наличии отрицательных значений в массиве или векторе вы получите ошибку  array out of range 

кроме того размер массива с фильтрующими флагами может достигать размера  2 147 483 647, а это слишком много

можно конечно уменьшить в 32 раза заменив установку 32-х BOOL переменных на битовую маску примерно так:

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


но всё равно размер останется слишком большим, а скорость упадёт приблизительно вдвое 

 
Nikolai Semko:

Все гениальное просто! :))

Но, правда, пямять кушает такой алгоритм бесконтрольно.

Так, например если заменить:

на

то ситуация уже совсем другая:

Ваш вариант тоже хорош, но и у вас к сожалению тоже есть слабое место. При скажем так "домашних" условиях, тоесть небольших массивах размером ~100 и небольшом векторе ~5-10

ваш алгоритм окажется медленее всех тех,которые тут представлены.,хотя разница в микросекундах настолько незначительна,что наверное не имеет значения,а вот на больших размерах массивов он лучший.

P.S Думаю, чтобы функция была универсальной нужно совместить в ней несколько разных алгоритмов подобранных в соответствии с входными данными. 

1...222324252627282930
Новый комментарий