function random(factor){
factor = factor || 1;
return Math.ceil( ( 1 - Math.random() ) * factor );
}
function randomArray(factor){
return function( size ){
size = size || 1;
var result = [];
for( var i = 0; i < size; i++ ){
result.push( random(factor) );
}
return result;
};
}
function maximizer(prev, curr ){
prev = prev || 0;
if( curr > prev ){
return curr;
} else {
return prev;
}
}
function optimalMaximizer( testArray ){
var result = null;
var score = 0;
if( Array.isArray(testArray) ){
if( testArray.length > 1 ){
var sampleSize = Math.ceil( testArray.length * 0.37 );
var sample = testArray.slice(0,sampleSize);
result = sample.reduce(maximizer);
var remainder = testArray.slice(sampleSize);
console.log( "Remainder HEAD : ", remainder[0] );
var searchedItems = sampleSize;
var totalSize = testArray.length;
for( var i = 0; i < remainder.length; i++ ){
var current = remainder[i];
searchedItems++;
if( current >= result ){
result = current;
console.log( "Maximum found @ ", searchedItems );
break;
}
}
console.log( "Search stopped at ", searchedItems, " (", Math.ceil( ((searchedItems)/totalSize) * 100 ), "%)" );
score = 1 - (searchedItems/totalSize);
console.log( "Effectiveness Score : ", score );
} else {
result = testArray[0];
}
}
return [result,score];
}
var testSampleSizes = [10, 1000, 100000, 1000000, 1000000 ];
var iterationsPerSize = 10;
var outComes = [];
var weightedOutcomes = [];
testSampleSizes.forEach(function(param){
var arrayGenerator = randomArray(param*999);
for( var i = 0; i < iterationsPerSize; i++ ){
var testArray = arrayGenerator(param);
console.log( "===================================" );
console.log( "Sample Size : ", param, " Iteration : ", i+1 );
if( param < 100 ){
console.log( testArray );
}
var trueMax = testArray.reduce(maximizer);
var optimizedResult = optimalMaximizer(testArray);
outComes.push(optimizedResult[1]);
var optimizedMax = optimizedResult[0];
var optimizedMaxError = ( trueMax - optimizedMax ) / trueMax;
weightedOutcomes.push( optimizedResult[1] * (1-optimizedMaxError) );
console.log( "Exhaustive Search : ", trueMax );
console.log( "Optimally Stopped Search : ", optimizedMax );
console.log( "Optimally Stopped Error : ", trueMax - optimizedMax, "(", ( ( trueMax - optimizedMax ) / trueMax )*100, "%)" );
}
});
console.log( "=======================================================" );
console.log("Average Score : ", outComes.reduce((prev,x)=>(prev||0) + x, 0 )/outComes.length );
console.log("Average Weighted Score : ", weightedOutcomes.reduce((prev,x)=>(prev||0) + x, 0 )/weightedOutcomes.length );