Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Find out missing floating value in an array

by manimarank (Novice)
on Dec 26, 2007 at 06:30 UTC ( #659004=perlquestion: print w/replies, xml ) Need Help??

manimarank has asked for the wisdom of the Perl Monks concerning the following question:

Greetings to all!!! Has someone help me the algorithm to find out the missing flatoing values in an array pls.. For example an array contains the value of 1.1 to 1.20 with the increment of 0.1 i.e (1.1,1.2,1.3 .... 1.20). How do i find out if 1.15 is missing in the list??? provide me some algorithm pls.. regards, Manimaran
  • Comment on Find out missing floating value in an array

Replies are listed 'Best First'.
Re: Find out missing floating value in an array
by Punitha (Priest) on Dec 26, 2007 at 07:20 UTC

    Hi

    I think your array contains the element from 1 to 20 with the preceeding of "1."

    You can find the missing element by generating the dummy array having all the elements with the increment value and the last element value, to compare with the original input array. Like

    use strict; use List::Compare::Functional qw(:originals :aliases); my @argen = (1..20); map{s/^/1./} @argen; #To create the dummy array having all the elem +ents with the increment value and the last element value my @arin=("1.1","1.2","1.3","1.4","1.5","1.7","1.10"); #Consider the e +lement in string, if not it will treat "1.10" as "1.1" my @ardif = get_unique( [ \@argen, \@arin ] ); #it gives the elemen +ts present in the first but not present in second if(@ardif){ $"=", "; print "The missing elements are: @ardif"; }

    Punitha

Re: Find out missing floating value in an array
by ysth (Canon) on Dec 26, 2007 at 06:55 UTC
    But that isn't an increment of 0.1. 1.2 is in your list twice, and 1.15 doesn't belong there at all. Are you really talking about floating values, or are you talking about some kind of version number or the like?

    Anyway, the algorithm is easy. Given the increment and the array, take the starting value in the array and add the increment to it to form your expected value. Then loop through the array from the second element on: for each element, while it's more than the expected value, put the expected value in your list of missing values and increment it. If the array element is equal to your expected value, increment the expected value and go on to the next array element.

    Where I say "more than" or "equal to", allow for floating point imprecision and rounding error.

    Alternatively, collect all values equal to the starting value plus some multiple of the increment that are between the starting and ending values (perhaps as hash keys), then remove all those that appear in your array. What's left are the missing values.

    If the increment isn't provided, you could initially take it as the difference between the first two elements in the array, then correct it if you find values that don't work with that increment.

Re: Find out missing floating value in an array
by apl (Monsignor) on Dec 26, 2007 at 12:38 UTC
    You need to specify what are permitted values in the array (how many decimal places of accuracy will be provided?), the maximum fineness of the search (will you ever want to check for three decimal places?) and the acceptable error margin (what if 1.14998 is in the list, or 1.15001?).

    In other words, I think you need to restate your problem.
Re: Find out missing floating value in an array
by roboticus (Chancellor) on Dec 26, 2007 at 15:32 UTC
    manimarank:

    Here's a hint on how to do it with floats:

    Sort the array, then check the intervals (adjacent values in the array). You'll either find the value, or you'll find an interval where it *should* be, but isn't.

    Note: Since many floating point values aren't representable in a binary format, you'll want to use the trick of selecting an arbitrary amount of error you'll accept when you try to determine whether two floats match. For example:

    #!/usr/bin/perl -w use warnings; use strict; my $epsilon=0.000005; my $desired=1.15; while (<DATA>) { chomp; if (abs($desired - $_) < $epsilon) { print "Match found: $_\n"; } } __DATA__ 1.149 1.1499 1.14999 1.149999 1.1499999 1.14999999 1.149999999
    Prints

    $ perl 659004.pl Match found: 1.149999 Match found: 1.1499999 Match found: 1.14999999 Match found: 1.149999999
    ...roboticus
Re: Find out missing floating value in an array
by ambrus (Abbot) on Dec 27, 2007 at 08:27 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://659004]
Approved by ysth
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (6)
As of 2020-07-09 12:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?