README.md

BogoSort Wins!

The for loop outperforms the binary search.
(well, the forEach did, until we changed the caching in an unrelated function)

And the optimizations have (almost) nothing to do with the algorithms.
(changing any code can massively change the performance of any benchmark)

See the video: https://www.youtube.com/watch?v=0mmi44ZB2C0

aaa-football.js

"use strict";

// 1,000,000
// 1,000,000,000

// return... read problem description
function ajCount(refs, inputs) {
  let outputs = [];
  /*
    refs.forEach(function (ref, i) {
        inputs.forEach(function (val) {
            if (val <= ref) {
                outputs[i] += 1;
            }
        });
    });
    */

  // starts just a little to the right
  let m = Math.floor(inputs.length / 2);
  inputs.sort(function (a, b) {
    return a - b;
  });
  //console.log();
  //console.log("inputs:", inputs);
  //console.log("m:", m);
  refs.forEach(function (ref) {
    //console.log();
    //console.log("ref:", ref);
    // let count = sort.lastIndexOf(inputs, ref) + 1;
    let i = m;
    let left = 0;
    let right = inputs.length - 1;

    // debug
    let count = 0;

    // ref: 5
    // m: 3 i: 3 v: 5
    // m: 3 i: 7 v: 6000000
    for (;;) {
      // debug
      if (count > 10) {
        break;
      }
      count += 1;

      // 27
      // 200
      // 190, 210
      let v = inputs[i];
      //console.log("left:", left, "right:", right);
      //console.log("m:", m, "i:", i, "v:", v);

      // Move to the left
      // (guarantee that i will move left if it can)
      // 210 > 200
      if (v > ref) {
        //console.log("(1)<= L, R, i", left, right, i);
        right = i; //- 1;
        let j = left + Math.floor((i - left) / 2);
        //console.log("(2)<= L, R, j", left, right, j);
        if (i === j) {
          break;
        }
        i = j;
        continue;
      }

      // Move to the right
      // 190 <= 200
      if (v <= ref) {
        //console.log("(1)=> L, R, i", left, right, i);
        left = i;
        // 3 + 2 = ((7 - 3) / 2)
        let j = i + Math.floor((right - i) / 2);
        //console.log("(2)=> L, R, j", left, right, j);
        if (i === j) {
          break;
        }
        i = j;
        continue;
      }
    }
    while (inputs[i] === inputs[i + 1] && i < inputs.length) {
      i += 1;
    }
    outputs.push(i + 1);
  });

  return outputs;
}

function ajCountLeftAlloc(refs, inputs) {
  //let outputs = new Array(refs.length);
  let outputs = [];
  //outputs.length = refs.length;
  /*
    refs.forEach(function (ref, i) {
        inputs.forEach(function (val) {
            if (val <= ref) {
                outputs[i] += 1;
            }
        });
    });
    */

  // starts just a little to the right
  inputs.sort(sortFn);
  //console.log();
  //console.log("inputs:", inputs);
  //console.log("m:", m);
  refs.forEach(function (ref) {
    //console.log();
    //console.log("ref:", ref);
    // let count = sort.lastIndexOf(inputs, ref) + 1;
    let left = 0;
    let right = inputs.length - 1;
    let i = left;

    // debug
    let count = 0;

    // ref: 5
    // m: 3 i: 3 v: 5
    // m: 3 i: 7 v: 6000000
    for (;;) {
      // debug
      if (count > 10) {
        break;
      }
      count += 1;

      // 27
      // 200
      // 190, 210
      let v = inputs[i];
      //console.log("left:", left, "right:", right);
      //console.log("m:", m, "i:", i, "v:", v);

      // Move to the left
      // (guarantee that i will move left if it can)
      // 210 > 200
      if (v > ref) {
        //console.log("(1)<= L, R, i", left, right, i);
        right = i; //- 1;
        let j = left + Math.floor((i - left) / 2);
        //console.log("(2)<= L, R, j", left, right, j);
        if (i === j) {
          break;
        }
        i = j;
        continue;
      }

      // Move to the right
      // 190 <= 200
      if (v <= ref) {
        //console.log("(1)=> L, R, i", left, right, i);
        left = i;
        // 3 + 2 = ((7 - 3) / 2)
        if (i === right) {
          break;
        }
        let j = i + Math.floor((right - i) / 2);
        //console.log("(2)=> L, R, j", left, right, j);
        if (i === j) {
          j += 1;
        }
        i = j;
        continue;
      }
    }
    while (inputs[i] === inputs[i + 1] && i < inputs.length) {
      i += 1;
    }
    outputs.push(i + 1);
  });

  return outputs;
}

function ajCountLeft(refs, inputs) {
  let outputs = [];
  let cache = {};

  let orefs = refs.slice(0);

  refs.sort(sortFn);

  // starts just a little to the right
  inputs.sort(sortFn);

  //console.log();
  //console.log("inputs:", inputs);
  //console.log("m:", m);
  refs.forEach(function (ref) {
    //console.log();
    //console.log("ref:", ref);
    // let count = sort.lastIndexOf(inputs, ref) + 1;
    let left = 0;
    let right = inputs.length - 1;
    let i = left;

    // debug
    let count = 0;

    // ref: 5
    // m: 3 i: 3 v: 5
    // m: 3 i: 7 v: 6000000
    for (;;) {
      // debug
      if (count > 10) {
        break;
      }
      count += 1;

      // 27
      // 200
      // 190, 210
      let v = inputs[i];
      //console.log("left:", left, "right:", right);
      //console.log("m:", m, "i:", i, "v:", v);

      // Move to the left
      // (guarantee that i will move left if it can)
      // 210 > 200
      if (v > ref) {
        //console.log("(1)<= L, R, i", left, right, i);
        right = i; //- 1;
        let j = left + Math.floor((i - left) / 2);
        //console.log("(2)<= L, R, j", left, right, j);
        if (i === j) {
          break;
        }
        i = j;
        continue;
      }

      // Move to the right
      // 190 <= 200
      if (v <= ref) {
        //console.log("(1)=> L, R, i", left, right, i);
        left = i;
        // 3 + 2 = ((7 - 3) / 2)
        let j = i + Math.floor((right - i) / 2);
        //console.log("(2)=> L, R, j", left, right, j);
        if (i === j) {
          break;
        }
        i = j;
        continue;
      }
    }
    while (inputs[i] === inputs[i + 1] && i < inputs.length) {
      i += 1;
    }
    let total = i + 1;
    cache[ref] = total;
  });

  orefs.forEach(function (ref) {
    outputs.push(cache[ref]);
  });
  return outputs;
}

function ajCountDoubleLeft(refs, inputs) {
  let outputs = [];

  let refsMap = refs.map(function (ref, i) {
    return [ref, i];
  });
  refsMap.sort(function (a, b) {
    return a[0] - b[0];
  });

  // starts just a little to the right
  inputs.sort(function (a, b) {
    return a - b;
  });

  //console.log();
  //console.log("inputs:", inputs);
  //console.log("m:", m);
  let left = 0;
  refsMap.forEach(function (tref) {
    //console.log();
    //console.log("ref:", ref);
    // let count = sort.lastIndexOf(inputs, ref) + 1;
    let right = inputs.length - 1;
    let i = left;

    // debug
    let count = 0;

    // ref: 5
    // m: 3 i: 3 v: 5
    // m: 3 i: 7 v: 6000000
    for (;;) {
      // debug
      if (count > 10) {
        break;
      }
      count += 1;

      // 27
      // 200
      // 190, 210
      let v = inputs[i];
      //console.log("left:", left, "right:", right);
      //console.log("m:", m, "i:", i, "v:", v);

      // Move to the left
      // (guarantee that i will move left if it can)
      // 210 > 200
      let ref = tref[0];
      if (v > ref) {
        //console.log("(1)<= L, R, i", left, right, i);
        right = i; //- 1;
        let j = left + Math.floor((i - left) / 2);
        //console.log("(2)<= L, R, j", left, right, j);
        if (i === j) {
          break;
        }
        i = j;
        continue;
      }

      // Move to the right
      // 190 <= 200
      if (v <= ref) {
        //console.log("(1)=> L, R, i", left, right, i);
        left = i;
        // 3 + 2 = ((7 - 3) / 2)
        let j = i + Math.floor((right - i) / 2);
        //console.log("(2)=> L, R, j", left, right, j);
        if (i === j) {
          break;
        }
        i = j;
        continue;
      }
    }
    while (inputs[i] === inputs[i + 1] && i < inputs.length) {
      i += 1;
    }
    outputs[tref[1]] = i + 1;
  });

  return outputs;
}

function sortFn(a, b) {
  return a - b;
}

function duncanCount(teamA, teamB) {
  // shallow copy teamB:
  const _teamB = [...teamB];

  // sort numerically
  teamA.sort(sortFn);
  _teamB.sort(sortFn);

  const cache = {};
  let previousAIndex = 0;

  _teamB.reduce((previousMatches, score) => {
    while (teamA[previousAIndex] <= score) {
      previousMatches++;
      previousAIndex++;
    }
    cache[score] = previousMatches;
    return previousMatches;
  }, 0);

  teamB.forEach((score, i) => {
    teamB[i] = cache[score];
  });
  return teamB;
}

function eachCount(teamA, teamB) {
  // shallow copy teamB:
  //const _teamB = [...teamB];
  const _teamB = teamB.slice(0);

  // sort numerically
  teamA.sort(sortFn);
  _teamB.sort(sortFn);

  const cache = {};
  let previousAIndex = 0;

  let previousMatches = 0;
  _teamB.forEach((score) => {
    while (teamA[previousAIndex] <= score) {
      previousMatches++;
      previousAIndex++;
    }
    cache[score] = previousMatches;
    return previousMatches;
  });

  teamB.forEach((score, i) => {
    teamB[i] = cache[score];
  });
  return teamB;
}

function forCount(teamA, teamB) {
  // shallow copy teamB:
  const _teamB = [...teamB];

  // sort numerically
  teamA.sort(sortFn);
  _teamB.sort(sortFn);

  const cache = {};
  let previousAIndex = 0;

  let previousMatches = 0;
  for (let score of _teamB) {
    while (teamA[previousAIndex] <= score) {
      previousMatches++;
      previousAIndex++;
    }
    cache[score] = previousMatches;
    return previousMatches;
  }

  teamB.forEach((score, i) => {
    teamB[i] = cache[score];
  });
  return teamB;
}

let tests = [
  {
    inputs: [1, 4, 2, 4],
    refs: [3, 5],
    expected: [2, 4],
  },
  {
    inputs: [1, 2, 3],
    refs: [2, 4],
    expected: [2, 3],
  },
  {
    inputs: [2, 16, 6000000, 5, 1, 79, 250, 3],
    // [1, 2, 3, 5, 16, 79, 250, 6000000];
    refs: [5, 100],
    expected: [4, 6],
  },
];

tests.forEach(function (test) {
  let answer = ajCount(test.refs, test.inputs);
  if (test.expected.toString() !== answer.toString()) {
    console.info("Fail", test.expected.toString(), answer.toString());
    return;
  }
  console.info("Pass");
});

let bench = [
  {
    inputs: 100000,
    refs: 100000,
  },
  {
    inputs: 1000000,
    refs: 1000000,
  },
];

function scoresGenerator(size) {
  const returnArray = [];

  for (let i = 0; i < size; i += 1) {
    returnArray.push(Math.floor(Math.random() * 1e6));
  }

  return returnArray;
}

bench.forEach(function (sizes) {
  let oinputs = scoresGenerator(sizes.inputs);
  let orefs = scoresGenerator(sizes.refs);
    let inputs;
    let refs;

  inputs = oinputs.slice(0);
  refs = orefs.slice(0);
  console.time("Binary Search:");
  ajCount(refs, inputs);
  console.timeEnd("Binary Search:");

  inputs = oinputs.slice(0);
  refs = orefs.slice(0);
  console.time("Binary Search (left):");
  ajCountLeft(refs, inputs);
  console.timeEnd("Binary Search (left):");

  inputs = oinputs.slice(0);
  refs = orefs.slice(0);
  console.time("Binary Search (left alloc):");
  ajCountLeftAlloc(refs, inputs);
  console.timeEnd("Binary Search (left alloc):");

  inputs = oinputs.slice(0);
  refs = orefs.slice(0);
  console.time("Binary Search (double left):");
  ajCountDoubleLeft(refs, inputs);
  console.timeEnd("Binary Search (double left):");

  inputs = oinputs.slice(0);
  refs = orefs.slice(0);
  console.time("reducer:");
  duncanCount(refs, inputs);
  console.timeEnd("reducer:");

  inputs = oinputs.slice(0);
  refs = orefs.slice(0);
  console.time("forEach:");
  eachCount(refs, inputs);
  console.timeEnd("forEach:");

  inputs = oinputs.slice(0);
  refs = orefs.slice(0);
  console.time("for:");
  eachCount(refs, inputs);
  console.timeEnd("for:");
});

binary-football.js

"use strict";

// 1,000,000
// 1,000,000,000

// return... read problem description
function count(refs, inputs) {
    let outputs = [];
    /*
    refs.forEach(function (ref, i) {
        inputs.forEach(function (val) {
            if (val <= ref) {
                outputs[i] += 1;
            }
        });
    });
    */

    // starts just a little to the right
    let m = Math.floor(inputs.length / 2);
    inputs.sort(function (a, b) {
        return a - b;
    });
    console.log();
    console.log("inputs:", inputs);
    console.log("m:", m);
    refs.forEach(function (ref) {
        console.log();
        console.log("ref:", ref);
        // let count = sort.lastIndexOf(inputs, ref) + 1;
        let i = m;
        let left = 0;
        let right = inputs.length - 1;

        // debug
        let count = 0;

        // ref: 5
        // m: 3 i: 3 v: 5
        // m: 3 i: 7 v: 6000000
        for (;;) {
            // debug
            if (count > 10) {
                break;
            }
            count += 1;

            // 27
            // 200
            // 190, 210
            let v = inputs[i];
            console.log("left:", left, "right:", right);
            console.log("m:", m, "i:", i, "v:", v);

            // Move to the left
            // (guarantee that i will move left if it can)
            // 210 > 200
            if (v > ref) {
                console.log("(1)<= L, R, i", left, right, i);
                right = i; //- 1;
                let j = left + Math.floor((i - left) / 2);
                console.log("(2)<= L, R, j", left, right, j);
                if (i === j) {
                    break;
                }
                i = j;
                continue;
            }

            // Move to the right
            // 190 <= 200
            if (v <= ref) {
                console.log("(1)=> L, R, i", left, right, i);
                left = i;
                // 3 + 2 = ((7 - 3) / 2)
                let j = i + Math.floor((right - i) / 2);
                console.log("(2)=> L, R, j", left, right, j);
                if (i === j) {
                    break;
                }
                i = j;
                continue;
            }
        }
        while (inputs[i] === inputs[i + 1] && i < inputs.length) {
            i += 1;
        }
        outputs.push(i + 1);
    });

    return outputs;
}

var tests = [
    {
        inputs: [1, 4, 2, 4],
        refs: [3, 5],
        expected: [2, 4],
    },
    {
        inputs: [1, 2, 3],
        refs: [2, 4],
        expected: [2, 3],
    },
    {
        inputs: [2, 16, 6000000, 5, 1, 79, 250, 3],
        // [1, 2, 3, 5, 16, 79, 250, 6000000];
        refs: [5, 100],
        expected: [4, 6],
    },
];

tests.forEach(function (test) {
    let answer = count(test.refs, test.inputs);
    if (test.expected.toString() !== answer.toString()) {
        console.info("Fail");
        return;
    }
    console.info("Pass");
});