Странное поведение jsPerf для рекурсивной функции - PullRequest
Новая
       21

Странное поведение jsPerf для рекурсивной функции

1 голос
/ 29 января 2012

У меня есть следующий код в тестовом примере на jsPerf: 

var arr = [0, 45, 96, 8, 69, 62, 80, 91, 89, 24, 6, 23, 49, 88, 26, 40, 87, 61, 83, 2, 60, 53, 43, 82, 67, 3, 65, 37, 42, 77, 73, 38, 9, 46, 75, 10, 63, 15, 47, 28, 79, 55, 59, 95, 11, 93, 70, 98, 25, 48, 30, 5, 72, 12, 84, 1, 29, 13, 50, 33, 19, 7, 31, 57, 32, 44, 74, 51, 35, 90, 86, 54, 4, 64, 92, 71, 22, 41, 16, 17, 27, 76, 39, 18, 99, 94, 36, 66, 85, 20, 21, 56, 34, 81, 14, 78, 68, 58, 97, 52];

Array.prototype.remove = function(from, to) {
  var rest = this.slice((to || from) + 1 || this.length);
  this.length = from < 0 ? this.length + from : from;
  return this.push.apply(this, rest);
};

function quicksort( arr ) {
  if ( arr.length <= 1 ) 
    return arr;
  var i = 0, 
      len = arr.length, 
      less = [], 
      greater = [], 
      random = Math.floor( Math.random() * len ), 
      pivot = arr[ random ];
  arr.remove( random );
  for ( ; i < len - 1; i++ ){
    if ( arr[ i ] <= pivot )
      less.push( arr[ i ] );
    else 
      greater.push( arr[ i ] );
  }
  return quicksort( less ).concat( pivot, quicksort( greater ) );
};

Если вы скопируете это в консоль и запустите quicksort( arr ), вы увидите, что он правильно возвращает отсортированный массив.

Но по какой-то причине в этом тестовом примере на jsPerf моя функция быстрой сортировки, похоже, возвращает только одно число (как это видно в «Выводе кода разделения»).Похоже, что он работает намного быстрее, чем, вероятно, следовало бы.

Любой, кто задумывается о том, что происходит, будет высоко оценен.

1 Ответ

2 голосов
/ 29 января 2012

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

Когда я делаю это, сначала создаю копию массива , а затем, похоже, работает.

...