Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

search algo to reach a number

by vijesh (Novice)
on Sep 27, 2013 at 15:05 UTC ( #1055995=perlquestion: print w/replies, xml ) Need Help??
vijesh has asked for the wisdom of the Perl Monks concerning the following question:

Hello Experts. I am trying to get an program to reach a number with minimum number of iteration. what I wrote is given below. Is there a better way? <\p>

eg: I want to reach 1000 starting from 30. script output ------------- start with 30 Find 1000 ASCENT 130 230 330 430 530 630 730 830 930 1030 DESCENT 1442 1186 1058 994 1026 1010 1002 998 1000 GOT IT...$newScale == $dest --> 1000 == 1000 Total Iteration taken is 21
my $dest = 1000; my $start = 30; my $steps = 100; my $newScale = $start; my $ascent = 1; my $descent = 0; my $n = 9; # n is power of 2 to reach $steps my $i=1; print "start with $start\n"; print "Find $dest\n"; print "\n\nASCENT\n"; while ($ascent) { if ($newScale < $dest) { $i++; $newScale = $newScale + $steps; print "$newScale\n"; } else { $ascent = 0; $descent = 1; $newScale = $newScale - $steps; $i++; } } print "\n\nDESCENT\n"; while ($descent) { if ( $n < 0 ) { last; } if ($newScale > $dest) { $newScale = $newScale - 2**$n; print "$newScale\n"; $i++; } else { $newScale = $newScale + 2**$n; $i++; print "$newScale\n"; } if ($newScale == $dest) { print "\n\nGOT IT...\$newScale == \$dest --> $newScale == $des +t \nTotal Iteration taken is $i \n"; last; } $n--; }

Replies are listed 'Best First'.
Re: search algo to reach a number
by Laurent_R (Canon) on Sep 27, 2013 at 17:39 UTC

    Make a Google search on the following words: dichotomic search algorithm, binary search algorithm or half-interval search algorithm. This is likely to be your more efficient solution.

Re: search algo to reach a number
by davido (Archbishop) on Sep 27, 2013 at 15:18 UTC

    What is this for?


      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?

        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.


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1055995]
Approved by marinersk
LanX it's an imaginary list ...
LanX ... reflecting root problems
choroba uses real lists so he can easily insert as many items in between as needed
LanX questions the integerity of this approach. ..
LanX doesn't sound natural
[LanX]: welcome to a new episode of Big Perl Theory...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (10)
As of 2018-03-20 10:30 GMT
Find Nodes?
    Voting Booth?
    When I think of a mole I think of:

    Results (250 votes). Check out past polls.