Re^2: search algo to reach a number

[vijesh]

There is a requirement to get a scaled number by considering certain parameters (memory usage, cpu usage..). eg: if I configure 1000 numbers in a machine, its mem goes to 85%. if I configure 900 numbers in a machine, its mem goes to 82%. ---- ---- I need to find a number where machines memory does not cross 80%. Hence I have to go up and down and get the exact number that hit 80%. my algo starts with 100 goes all the way till 1000. When cross 1000, I presume, my machine hit util of > 80%. Hence I need to descent and then reach 1000. Am I clear now?

[davido]

The most computationally inexpensive solution would be a mathematical formula, rather than a brute force search through your problem domain.

If it's impossible to come up with an exact formula, I suppose you could use a binary search, which guarantees that you will find your target in a list of numbers between 100 and 1000 in ten iterations or less.

Let's say you are able to determine that some set of criteria produces some known result. And let's say that there is a tolerable range; you wouldn't want to have more than some amount of resources idle, nor would you want to have more than some amount of resources in use. So you are ok with some narrow range surrounding, say, your 80% target. You can binary search using a derivation function and a custom comparator.:

use List::BinarySearch qw/ binsearch /;

my @domain = ( 100 .. 1000 );

print "Target: ", $domain[ binsearch { comparator( $a, $b ) } 80, @dom
+ain ], "\n";


sub comparator {
  my( $low, $high ) = derive($b);
  return -1 if $a < $low;
  return  1 if $a > $high;
  return 0;
}

sub derive {
  my $raw = shift;
  my $low = $raw * .14;
  my $high = $raw * .19;
  return ( $low, $high );
}
__END__
__OUTPUT__
422

My derive function is highly contrived. Presumably you have some way of knowing what your resource load will be for a given set of inputs, and that's what would need to be calculated in the derive function.

I don't fully understand the challenges you are facing, but incrementing by 30 and then descending from some number again is a linear approach, whereas a binary search is a logarithmic approach. I have no idea what you would need to stick into derive() to make this technique work. But I do hope it gives you some ideas.