ФорумРазделы

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

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

Сравните 2 варианта кода по одному ТЗ: 

//+------------------------------------------------------------------+
//|                                             Erase and Resize.mq5 |
//|                                                      Peter Konow |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Peter Konow"
#property link      "https://www.mql5.com"
#property version   "1.00"
//--------------------------------------------------------------------
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
  {
   int Arr[20] = {1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2};
   ulong q1 = GetMicrosecondCount(); 
   //--------------------------------
   int deleted = 0,q = 0;
   //-------------- 
   for(int a1 = 0; a1 < ArraySize(Arr); a1++)
     {
      if(deleted)Arr[q] = Arr[q + deleted];
      if(Arr[q] == 3){deleted++; q--;}
      q++;
     }
   //--------------
   ulong q2 = GetMicrosecondCount(); 
   //--------------------------------
   //ArrayResize(Arr, ArraySize(Arr) - deleted);    
   //--------------------------------
   Print(Arr[0],",",Arr[1],",",Arr[2],",",Arr[3],",",Arr[4],",",Arr[5],",",Arr[6],",",Arr[7],",",Arr[8],",",Arr[9],
        ",",Arr[10],",",Arr[11],",",Arr[12],",",Arr[13],",",Arr[14],",",Arr[15],",",Arr[16],",",Arr[17],",",Arr[18],",",Arr[19]);
   Print("Array new size  ",ArraySize(Arr),"  Тime of operation  ",q2-q1,"  deleted  ",deleted);
   //--------------------------------  
  }
//+------------------------------------------------------------------+

и: 

int Arr[20] = {1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2};
int deleted;
//-------------- 
for(int a1 = 0; a1 < ArraySize(Arr); a1++)
  {
   if(Arr[a1] == 3)
     {
      if(deleted)a1-= deleted;//Cмещение назад.
      deleted++; 
     }
   if(deleted)Arr[a1] = Arr[a1 + deleted];
  }
//-------------- 
ArrayResize(Arr, ArraySize(Arr) - deleted);
Это мог написать один человек с интервалом чуть более часа? Почерк вызывает сомнение ) 
Maxim Kuznetsov:

Алексей, вы прям таки убиваете юный талант...

этот маркетолог 5 лет не может начать продавать..а вы говорите что как программист он ещё хуже

Извините, добивать не хотел. 

Maxim Kuznetsov:

:-) если не пытаться сохранять порядок, то время O(1) , общее число шагов всех циклов=размер массива

правдо кодить лень :-)

1. ищем первую 3-ку слева направо.

2. если нашли, то ищем не-тройку справа-налево., найденное копируем на место 3-ки.

продолжаем пока 1,2 не пересекутся, обрезаем массив по числу копирований. 

идейно это ровно 1/2 от "сортировки пузырьком" :-) если вместо копирования, делать swap то на выходе получается частично упорядоченный массив (все 3-йки перемещены вправо) 

Общее число шагов всех циклов=размер массива - это сложность O(n).
Если входной массив отсортирован, то поставленная задача решается через бинарный поиск.
Сложность O(log(n)) в среднем и O(n) в худшем случаи.

Плохо, когда кодить лень. 
Nikolai Semko:

Все таки осилил вариант Петра.

вполне себе компактный и даже правильно работает. Респект Петру.
Но по скорости занимает второе место с конца. Или первое место с конца если не считать изначальный совсем негодный по скорости вариант хозяина этой ветки.

Как ты тестировал?

Не вариант то что кидал, последнее. Надо перебор по любому.
Реter Konow:

Как ты тестировал?

Изучай код.

2018.11.14 03:26:49.182 ArrayDeleteValue (BTCUSD,M15)   вариант Pastushak: Контрольная сумма = 496575839; элементов - 998974; время выполнения = 131158 микросекунд
2018.11.14 03:26:49.185 ArrayDeleteValue (BTCUSD,M15)   вариант Korotky:   Контрольная сумма = 496575839; элементов - 998974; время выполнения = 2431 микросекунд
2018.11.14 03:26:49.188 ArrayDeleteValue (BTCUSD,M15)   вариант Fedoseev:  Контрольная сумма = 496575839; элементов - 998974; время выполнения = 1809 микросекунд
2018.11.14 03:26:49.190 ArrayDeleteValue (BTCUSD,M15)   вариант Semko:     Контрольная сумма = 496575839; элементов - 998974; время выполнения = 785 микросекунд
2018.11.14 03:26:49.194 ArrayDeleteValue (BTCUSD,M15)   вариант Pavlov:    Контрольная сумма = 496575839; элементов - 998974; время выполнения = 2839 микросекунд
2018.11.14 03:26:49.199 ArrayDeleteValue (BTCUSD,M15)   вариант Nikitin:   Контрольная сумма = 496575839; элементов - 997971; время выполнения = 4049 микросекунд
2018.11.14 03:26:49.204 ArrayDeleteValue (BTCUSD,M15)   вариант Vladimir:  Контрольная сумма = 496575839; элементов - 998974; время выполнения = 3888 микросекунд
2018.11.14 03:26:49.212 ArrayDeleteValue (BTCUSD,M15)   вариант Peter:     Контрольная сумма = 496575839; элементов - 998974; время выполнения = 7597 микросекунд
Файлы:
ArrayDeleteValue.mq5  17 kb
Алексей Тарабанов:
Плохо, когда кодить лень. 

не то чтобы совсем лень, но под рукой MT только на VDS-ах, а на них экспериментов не ставят. 

примерно так :

template <typename T>
int arrayFilter(const  T &arr[], const T x)
{
        int i=0;
        int j=ArraySize(arr)-1;
        for(;;) {
                while(arr[i]!=x && i<j) i++;
                while(arr[j]==x && i<j) j--;
                if (i<j) {
                        arr[i++]=arr[j--];
                } else break;
        }
        ArrayResize(j+1);
        return j+1;
}

+- 1 :-) с дачи вернусь через пару тройку дней, проверю..

ps. к тому-же в коде лишний вход в цикл по завершению..мелочь, но можно убрать

Maxim Kuznetsov:

не то чтобы совсем лень, но под рукой MT только на VDS-ах, а на них экспериментов не ставят. 

примерно так :

+- 1 :-) с дачи вернусь через пару тройку дней, проверю..

ps. к тому-же в коде лишний вход в цикл по завершению..мелочь, но можно убрать

Браво! После исправления пары ошибок Вы меня сбросили с пьедестала даже без применения ArrayCopy. Шах и Мат. :)) 

template <typename T>
int arrayFilter3(T &arr[], const T x)  // вариан Kuznetsov
{
        int i=0;
        int j=ArraySize(arr)-1;
        for(;;) {
                while(arr[i]!=x && i<j) i++;
                while(arr[j]==x && i<j) j--;
                if (i<j) {
                        arr[i++]=arr[j--];
                } else break;
        }
        ArrayResize(arr,j+1);
        return j+1;
}
2018.11.14 03:48:29.572 ArrayDeleteValue (USDRUB,M1)    вариант Pastushak: Контрольная сумма = 496206996; элементов - 999002; время выполнения = 131929 микросекунд
2018.11.14 03:48:29.576 ArrayDeleteValue (USDRUB,M1)    вариант Korotky:   Контрольная сумма = 496206996; элементов - 999002; время выполнения = 2411 микросекунд
2018.11.14 03:48:29.579 ArrayDeleteValue (USDRUB,M1)    вариант Fedoseev:  Контрольная сумма = 496206996; элементов - 999002; время выполнения = 1839 микросекунд
2018.11.14 03:48:29.581 ArrayDeleteValue (USDRUB,M1)    вариант Semko:     Контрольная сумма = 496206996; элементов - 999002; время выполнения = 782 микросекунд
2018.11.14 03:48:29.585 ArrayDeleteValue (USDRUB,M1)    вариант Pavlov:    Контрольная сумма = 496206996; элементов - 999002; время выполнения = 2813 микросекунд
2018.11.14 03:48:29.590 ArrayDeleteValue (USDRUB,M1)    вариант Nikitin:   Контрольная сумма = 496206996; элементов - 997969; время выполнения = 4200 микросекунд
2018.11.14 03:48:29.596 ArrayDeleteValue (USDRUB,M1)    вариант Vladimir:  Контрольная сумма = 496206996; элементов - 999002; время выполнения = 3597 микросекунд
2018.11.14 03:48:29.604 ArrayDeleteValue (USDRUB,M1)    вариант Peter:     Контрольная сумма = 496206996; элементов - 999002; время выполнения = 7684 микросекунд
2018.11.14 03:48:29.606 ArrayDeleteValue (USDRUB,M1)    вариант Kuznetsov: Контрольная сумма = 496206996; элементов - 999002; время выполнения = 681 микросекунд
Файлы:
ArrayDeleteValue.mq5  18 kb
Nikolai Semko:

Браво! После исправления пары ошибок Вы меня сбросили с пьедестала даже без применения ArrayCopy. Шах и Мат. :)) 

Правда не совсем так, т.к. на выходе массив то совсем другой - уже перемешанный. Но все равно круто!

Если имеем дело с котировками, то такой вариант конечно же не годится. Я снова на пьедестале. )) 

Я поменял способ подсчета контрольной суммы. Уже не простая сумма всех элементов, а сумма - (значение элемента)/(номер элемента).
И вот что получилось:

2018.11.14 04:20:26.063 ArrayDeleteValue (USDRUB,M1)    вариант Pastushak: Контрольная сумма = 7090.600736767353; элементов - 999003; время выполнения = 132291 микросекунд
2018.11.14 04:20:26.067 ArrayDeleteValue (USDRUB,M1)    вариант Korotky:   Контрольная сумма = 7090.600736767353; элементов - 999003; время выполнения = 2322 микросекунд
2018.11.14 04:20:26.071 ArrayDeleteValue (USDRUB,M1)    вариант Fedoseev:  Контрольная сумма = 7090.600736767353; элементов - 999003; время выполнения = 1831 микросекунд
2018.11.14 04:20:26.074 ArrayDeleteValue (USDRUB,M1)    вариант Semko:     Контрольная сумма = 7090.600736767353; элементов - 999003; время выполнения = 773 микросекунд
2018.11.14 04:20:26.079 ArrayDeleteValue (USDRUB,M1)    вариант Pavlov:    Контрольная сумма = 7090.600736767353; элементов - 999003; время выполнения = 2879 микросекунд
2018.11.14 04:20:26.085 ArrayDeleteValue (USDRUB,M1)    вариант Nikitin:   Контрольная сумма = 7093.903216084301; элементов - 998017; время выполнения = 3605 микросекунд
2018.11.14 04:20:26.090 ArrayDeleteValue (USDRUB,M1)    вариант Vladimir:  Контрольная сумма = 7090.600736767353; элементов - 999003; время выполнения = 3622 микросекунд
2018.11.14 04:20:26.100 ArrayDeleteValue (USDRUB,M1)    вариант Peter:     Контрольная сумма = 7090.600736767353; элементов - 999003; время выполнения = 7252 микросекунд
2018.11.14 04:20:26.102 ArrayDeleteValue (USDRUB,M1)    вариант Kuznetsov: Контрольная сумма = 7085.49357433088;  элементов - 999003; время выполнения = 691 микросекунд
Файлы:
ArrayDeleteValue.mq5  18 kb
1...34567891011121314151617...30
Новый комментарий