ferrante quiz

Benchmark created by Tomasz Elendt on March 22, 2011

Preparation HTML

<script>
  var range = [];
  for (var i = -10000; i < 10001; i++) {
   range.push(i);
  }
  var testArr1 = range.slice(0, 10000); // wszystkie ujemne
  var testArr2 = range.slice(5000, 15001); // "symetryczna"
  var testArr3 = range.slice(10001, 20001); // wszystkie dodatnie
  /**
   * Funkcja rozwiązująca zadanie konkursowe
   *
   * @version 201103061820
   * @author Yann Kowalsky
   * @param array input Jednowymiarowa, posortowana rosnąco tablica unikalnych
   * liczb całkowitych.
   * @return array Tablica z niepowtarzającymi się liczbami dodatnimi, których
   * wartość absolutna pojawiła się w tablicy dwa razy.
   */
  
  window.solve = function(input) {
   var output = [];
   var length = input.length;
   var a, b; // "cache"
   // iteruje tablicę input od początku i od końca, porównując kolejno
   // wartość bezwzględną elementów
   for (
   var i = 0, j = ~ - length, a = -input[0];
   (a = -input[i]) > 0; ++i) {
    // mały boost - po pierwsze zatrzymaj się tu, bo i tak nie spotkasz
    // wartości równych, po drugie - j przy następnym przebiegu pętli for
    // będzie startowało od ostatniej wartości, a nie od początku
    while (a < (b = input[j])) {
     --j;
    }
  
    // wartość bezwględna taka sama
    if (a == b) {
     output[output.length] = b;
     // output[output.length] szybsze od output.push()...
     --j;
    }
   }
  
   return output;
  }
  
  window.solve_elus_v8 = function(input) {
   var output = [],
       i = 0,
       j = input.length - 1,
       left, right = input[j];
   while ((left = -input[i++]) > 0 && right > 0) {
    while (right > left) {
     right = input[--j];
    }
    if (right === left) {
     output.push(left);
     right = input[--j];
    }
   }
   return output;
  }
  
  window.solve_elus_fx = function(input) {
   // assert input+'' === input.map(Number).sort(function(a,b){return a-b})+''
   var output = [],
       i = 0,
       j = input.length - 1,
       k = 0,
       left, right = input[j];
   while ((left = -input[i]) > 0 && right > 0) {
    i += 1;
    while (right > left) {
     j -= 1;
     right = input[j];
    }
    if (right == left) {
     output[k] = left;
     k += 1;
     j -= 1;
     right = input[j];
    }
   }
   return output;
  }
</script>

Test runner

solve(testArr1);
solve(testArr2);
solve(testArr3);

solve_elus_v8(testArr1);
solve_elus_v8(testArr2);
solve_elus_v8(testArr3);

solve_elus_fx(testArr1);
solve_elus_fx(testArr2);
solve_elus_fx(testArr3);

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published by Tomasz Elendt on March 22, 2011