Скачать MetaTrader 5

Небольшое исследование: функция ArrayResize()

Авторизуйтесь или зарегистрируйтесь, чтобы добавить комментарий
Sceptic Philozoff
Модератор
17841
Sceptic Philozoff  

Решил провести один натурный эксперимент. Поводом послужило замечание FAQ вот тут:

FAQ: интересно, сколько уйдет времени на чтение скажем пары мегабайт таким методом ? и сколько памяти загребет при этом терминал ? вы не задумывались ?

Суть исследования была в том, чтобы посмотреть, насколько велика разница по времени, если, заполняя некий массив в цикле, увеличивать его размер в каждой итерации - или явно указывать размер массива еще до цикла. Исследование оказалось неожиданно нетривиальным. Для определения влияния разницы написал такой скрипт:

#property show_inputs

extern int _N = 10000;        /// 10 thousand

extern bool _before = false;  /// когда устанавливать размер массива - ДО цикла или не до цикла, т.е. наращивая в каждой итерации

int start( )
{
   int st = GetTickCount( );
   int array[ ];

   if( _before )
   {
         ArrayResize( array, _N );
         for( int i = 0; i < _N; i ++ )          array[ i ] = i ;
         
         int fin = GetTickCount( );
         double gone = ( fin - st ) / 1000.;
         Print( _N + ": time = " + gone + " sec." );
   }
   else
   {
      for( int J = _N; J <= 60 * _N; J += 10000 )
      {
         for( i = 0; i < J; i ++ )      
         {
            ArrayResize( array, i + 1 );
            array[ i ] = i;
         }
    
         fin = GetTickCount( );
         gone = ( fin - st ) / 1000.;
         Print( J + ": time = " + gone + " sec." );
         st = fin;          
      }   
   }   
   
   return( 0 );
}//+------------------------------------------------------------------+

Внутренние вычисления были намеренно сделаны очень простыми, чтобы увидеть влияние функции ArrayResize() на разных размерах массива. Сразу отмечу, что при указании размера массива до цикла всё выполнялось практически мгновенно, за доли секунды, не фиксируемые GetTickCount( ) даже при размере массива 300000. Самое интересное было тогда, когда размер массива увеличивался в каждой итерации цикла.

Выводятся следующие данные: размер массива и время выполнения цикла.

Результат исполнения скрипта:


Как видим, время растет явно нелинейно в зависимости от размера массива. Есть гипотеза, как это объяснить, но это, думаю, лучше сделают зубры кодирования.

Так что в следующий раз, если Вам не дай бог потребуется заполнить массив с размером главного измерения, составляющим сотни тысяч, учтите эти результаты.

Комбинатор
16618
Комбинатор  

Скорее всего растет квадратно.

Смысл прост -- отсутствие запаса, т.н. capacity, насколько я понимаю. В 5ке он есть.

При ресайзе не всегда можно расширить диапазон в том же куске памяти, поэтому надо искать кусок большего размера и копировать данные. Это уже линейная операция (O(n))

Увеличиваем размер по единичкам, тоже O(n). При перемножении грубо получаем квадратную зависимость.

Sceptic Philozoff
Модератор
17841
Sceptic Philozoff  
Ну да, сумма арифметической прогрессии. Надо пробегать от начала массива к его концу на каждой итерации. Так?
Алексей Тарабанов
7331
Алексей Тарабанов  
Mathemat:
Ну да, сумма арифметической прогрессии. Надо пробегать от начала массива к его концу на каждой итерации. Так?

Да. Нетривиально.
Алексей Тарабанов
7331
Алексей Тарабанов  
TheXpert:

Скорее всего растет квадратно.

Смысл прост -- отсутствие запаса, т.н. capacity, насколько я понимаю. В 5ке он есть.

При ресайзе не всегда можно расширить диапазон в том же куске памяти, поэтому надо искать кусок большего размера и копировать данные. Это уже линейная операция (O(n))

Увеличиваем размер по единичкам, тоже O(n). При перемножении грубо получаем квадратную зависимость.



Экстента называется этот кусок

Sceptic Philozoff
Модератор
17841
Sceptic Philozoff  

Нет, не квадратично, а существенно круче. Построив зависимость времени выполнения от размера массива в дважды логкоординатах, получим степень где-то 2.45 (на больших размерах массива, примерно от 200 тысяч, когда кривая похожа на прямую). Я вычислял ее фунцией slope() в Open Office. Сильный разброс в конце - потому, что просто не выдержал и стал запускать другие задачи.

Короче, вывод можно сделать такой: сам по себе вызов функции ArrayResize() для небольших массивов трудно назвать очень дорогим. Но его массовое использование на массивах с базовой размерностью порядка десятков тысяч к добру не приводит, сильно замедляя исполнение кода.

Авторизуйтесь или зарегистрируйтесь, чтобы добавить комментарий