Skip to content

Instantly share code, notes, and snippets.

@coolaj86
Last active Mar 21, 2022
Embed
What would you like to do?

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

"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:");
});
"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");
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment