Beefy Boxes and Bandwidth Generously Provided by pair Networks
Come for the quick hacks, stay for the epiphanies.
 
PerlMonks  

Array: inserting what isn't there

by Anonymous Monk
on May 30, 2003 at 13:57 UTC ( [id://261850]=perlquestion: print w/replies, xml ) Need Help??

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

Dear Monks, Wondered if you could help - I have an array containing things that it has 'found' in a file. It is basically looking for consecutive numbers e.g. 1,2, upwards so it needs to work out which numbers haven't been found and insert them
@array = ("1.found","2.found", "4.found", "5.found");
How can I insert into the array things that are missing e.g. so the array looks like this:
@array = ("1.found","2.found","3.lost", "4.found", "5.found");
This list is potentially very long and I cant think of how to do it. Cheers

Replies are listed 'Best First'.
•Re: Array: inserting what isn't there
by merlyn (Sage) on May 30, 2003 at 14:11 UTC
    This smells like a good homework problem.

    At the risk of it being such, I'll answer anyway.

    I'd copy the array into a new array, picking out the initial number of each item, but inserting any items that weren't there.

    my @newarray; for (@array) { my ($prefix) = /^(\d+)/ or die "Missing leading integer in $_\n"; ## generate missing elements based on length of @newarray: push @newarray, (@newarray + 1) . ".lost" while @newarray < $prefix - 1; push @newarray, $_; } @array = @newarray; # copy the results back

    -- Randal L. Schwartz, Perl hacker
    Be sure to read my standard disclaimer if this is a reply.

      Merlyn, I'm quite the newbie, and have only dipped my monastic toe into the pond of REGEX and haven't touched reading files at all, so this looks like a great place for me to learn something. ;)

      A few weeks ago there was a math challenge posted (sorry I don't remember the node ID) about finding the shortest intiger that contained all the successive intigers from 0000 to 9999. In this particular problem, if the file contained only the number sequence "12345" would /^(\d+)/ pick up 12, 34, 45, 234, or even 12345 as .found elements? Why or why not? Coming from a programing language that isn't as text based as Perl (hey, I forgot to mention the language name!) I find regexes useful and a little difficult to wrap my brain around, even after RTFM a few times (okay, after reading the Indigo Perl version of the friendly manual!). Thanks for any insight.

      Looking to learn!
      Petras.
      Don't worry about people stealing your ideas. If your ideas are any good, you'll have to ram them down people's throats.

      -Howard Aiken
        A simple test shows that "12345" =~ /^(\d+)/ matches the entire string, as predicted. I'm not sure why you find that mysterious. {grin} I have a book that spends three chapters talking about regular expressions, if you need that level of instruction.

        -- Randal L. Schwartz, Perl hacker
        Be sure to read my standard disclaimer if this is a reply.

Re: Array: inserting what isn't there
by arthas (Hermit) on May 30, 2003 at 14:11 UTC
    Hi!

    The following code creates a second array which is the original one completed with the missing elements. You can then copy it back over the old one. Otherwise, you can try to work something out with splice() to work directly on the original array.
    use strict; my @array = ("1.found","2.found", "4.found", "5.found"); my @array2; my $i = 1; foreach my $a(@array) { my ($n) = split /\./, $a; while ($n > $i) { push @array2, "$i.lost"; $i++; } push @array2, $a; $i++; }
    Michele.
      do you realy need the final array with the negatives filled in?...when they can be inferred in any further access to the array, ie the negative element won't be there. also, since this looks like a binary problem (the result is either 1 or 0) you should realy think about expressing it as such, and save LOTS of space and time walking through it.
Re: Array: inserting what isn't there
by l2kashe (Deacon) on May 30, 2003 at 14:12 UTC
    I just finished working on a similar problem. What I needed was to preinitialize an array so that later if a value was 0 it would report correctly, you can do the same basic thing ala

    $max_size = 5; @array = (0) x $max_size; # put $max_size zeros in array # process file here.. for ( $i = 0; $i <= $#array; $i++ ) { # now set the value to lost if it is still zero $array[$i] = "$i.lost" unless ( $array[$i] ); }
    Now this assumes that you will never have a 0 in a particular field, but if you can then you can use a different sentinal value

    MMMMM... Chocolaty Perl Goodness.....

      Why not initialise to undef then use unless (defined $array[$i])?

        In my own code base I referenced, its actually reporting on metrics for some traffic. So instead of me needing to later loop over the array, and do something like
        # isnt actual code but displays idea my $f = $array[$i] || 0; $sql .= '"$f", ';
        I can now simply do
        $sql .= join('", "', @array) . '");';
        And I know my values are sane.

        I guess in the case of the OP this isnt a factor, but in my case I initialize to a number, because all my values are numbers, and I think it makes it slightly easier at run time on perl. If we simply created place holders in the array Im not sure what data type perl would use behind the scenes, or rather how much space would be allocated to each element, nor how much work Perl would have to do behind the scenes to go from undef -> val -> bigger val. I am also dealing with what I consider monster data sets. I process about 22Gb of data, then another 15Gb or so, and correlate info. If I can drop a few tests from loops, or make my run time a little quicker, then I do.

        Or I could just be lazy and didnt want to add another test inside of a loop later, when I could deal with it up front and just go :)

        Update: Heh, I think I miss interpreted the question asked so let me add this.

        I guess it honestly doesn't matter how you test. Looking at the requirements where I assume the info will always be digit.string, then using the value as a boolean is 'OK' to determine what we are gonna do. If the value could be zero then I would have used defined like you suggested.

        MMMMM... Chocolaty Perl Goodness.....
Re: Array: inserting what isn't there
by broquaint (Abbot) on May 30, 2003 at 14:15 UTC
    Here's how I'd do it
    use strict; use Data::Dumper; my @nums = map { chomp; $_ } <DATA>; for(local $_ = 0; $_ < $#nums; $_++) { splice @nums, $_, 1 => $nums[$_], ( $nums[$_] + 1 ). ".lost" unless $nums[$_] == ( $nums[$_ + 1] - 1 ); } print Dumper(\@nums); __DATA__ 1 2 3 6 7 9 10
    And that should spit out the desired results (minus the 'found'). Oh, and looky, a valid use of a C-style for loop!
    HTH

    _________
    broquaint

Re: Array: inserting what isn't there
by hardburn (Abbot) on May 30, 2003 at 14:22 UTC

    Instead of having "$i.found" or "$i.lost", why not just make the array value true or false and index it by $i. The 0th element will be useless, but don't worry about it:

    my @array; foreach my $i (1 .. $SOME_BIG_NUMBER) { $array[$i] = 1 if found($i); }

    ----
    I wanted to explore how Perl's closures can be manipulated, and ended up creating an object system by accident.
    -- Schemer

    Note: All code is untested, unless otherwise stated

Re: Array: inserting what isn't there
by boo_radley (Parson) on May 30, 2003 at 19:57 UTC
    grep hash fu!
    do you have a more useful dataset to check these against?
    my @array = ("12.found","1.found","2.found", "4.found", "5.found", "8. +found", "100.found"); my @e = sort {$a<=>$b} map {m/^(\d+)/ && $1}@array; my %hash; @hash{@e}= (@array); for ($e[0]..$e[-1]) {defined ($hash{$_})or$hash{$_} ="$_.missing"} print join " ", sort {$a<=>$b} values %hash;
Re: Array: inserting what isn't there
by ehdonhon (Curate) on May 30, 2003 at 21:47 UTC

    Sounds more like a hash problem than an array problem. This will give you the array you are looking for.

    my %found; while ( my $item = find_next_number() ) { $found{$item}=1; } @array = map { "$_.found" } sort {$a <=> $b} keys %found;
Re: Array: inserting what isn't there
by Anonymous Monk on May 30, 2003 at 14:50 UTC
    Here's my hacky solution that works:
    use strict; my @array = ( "1.found", "2.found", "4.found", "5.found", "6.found", "8.found", ); my $counter = substr($array[0], 0, 1); for (@array) { my ($num) = /^(\d+)/; if ($counter < $num) { print "$counter.lost\n"; $counter = $counter + 2; } else { $counter++; } }
      Doesn't work when the numbers get to two digits, or if there are two or more consecutive items missing, and doesn't put the data back into a summary array. At least, that's the first three defects I spotted.

      -- Randal L. Schwartz, Perl hacker
      Be sure to read my standard disclaimer if this is a reply.

Re: Array: inserting what isn't there
by bobn (Chaplain) on May 31, 2003 at 15:58 UTC
    Maybe this is aggogant, but I can't help thinking that the question is asked too late in the process.
    while(<DATA>) { # regex detects or doesn't detect number as $found in line m/magic_phrase:(\d+)/; next unless ( $found = $1 ); $max = ( $found >$max ? $found : $max ); $seen{$found}++; } sub isit { return exists $seen{$_[0]}; } # if you really need the output (or array) for ( 1..$max) { my $str = ( isit($_) ? "$_.found" : "$_.lost" ); print "$str\n"; push @array, $str; } print "\@array is @array\n"; __DATA__ magic_phrase:2 magic_phrase:5
    Produces:
    1.lost 2.found 3.lost 4.lost 5.found @array is 1.lost 2.found 3.lost 4.lost 5.found


    --Bob Niederman, http://bob-n.com
Re: Array: inserting what isn't there
by Anonymous Monk on Jun 02, 2003 at 15:12 UTC
    1) as you go through the data looking for numbers put the found numbers in a hash a remeber the largest one found. then at the end:
    my @array = map { $hash{$_} ? "$_.found" : "$_.lost" } 1 .. $max_found +;
    2) generate @array with:
    $array[$number] = "$number.found";
    when you're done:
    @array = map { $array[$_] ? $array[$_] : "$_.lost" } 1 .. $#array;

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://261850]
Approved by broquaint
Front-paged by broquaint
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others examining the Monastery: (7)
As of 2024-03-29 08:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found