37% Optimal Search Stopping

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 );