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

[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. Самое интересное было тогда, когда размер массива увеличивался в каждой итерации цикла.

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

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

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

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

[TheXpert]

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

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

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

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

[Sceptic Philozoff]

Ну да, сумма арифметической прогрессии. Надо пробегать от начала массива к его концу на каждой итерации. Так?

[Алексей Тарабанов]

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

Да. Нетривиально.

[Алексей Тарабанов]

TheXpert:

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

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

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

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

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

[Sceptic Philozoff]

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

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