Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Sort Algorithm (recursive?)

by bertigo (Novice)
on Oct 14, 2005 at 14:44 UTC ( [id://500240]=perlquestion: print w/replies, xml ) Need Help??

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

Following a previous post Best way to sort these strings ? recursive way ? use Parse::RecDescent?, i want to obtain this output with the right order :

TEX1J desc 'Job Start' MEX1J desc 'Job 2' Pred TEX1J MEX2J desc 'Job end' Pred MEX1J, MEX2J # MEX1J must appear after TEX1J because it depend on TEX1J # MEX2J must appear after TEX1J and MEX1J from a hash defined like this: %hash={ 'MEX1J' => { 'desc' => 'Job 2' 'pred' => [TEX1J], }, 'MEX2J' => { 'desc' => 'Job end' 'pred' => [TEX1J,MEX1J], }, 'TEX1J' => { 'desc' => 'Job start' 'pred' => [], } }

I think I must use a recursive algorithm but I don't really see how to do it...

Thanks for the answer

Edited by planetscape - removed <pre> tags; replaced with <code>

Replies are listed 'Best First'.
Re: Sort Algorithm (recursive?)
by merlyn (Sage) on Oct 14, 2005 at 15:19 UTC
Re: Sort Algorithm (recursive?)
by Roy Johnson (Monsignor) on Oct 14, 2005 at 15:23 UTC
    For the general case, you'd need a recursive solution to traverse the pred lists. For this particular case, you don't have to worry about something being a pred-of-a-pred. I believe I have fixed the recursive section, as well.
    my %hash=( 'MEX1J' => { desc => 'Job 2' , pred => ['TEX1J'], }, 'MEX2J' => { desc => 'Job end', pred => ['TROUBLE'], }, 'TEX1J' => { desc => 'Job start', pred => [], }, 'TROUBLE' => { desc => 'who cares', pred => ['MEX1J'] } ); sub pred_cmp { my ($i1, $i2) = @_; # Anybody with no preds is first if (@{$hash{$i1}{pred}} == 0) { return -1; } elsif (@{$hash{$i2}{pred}} == 0) { return 1; } # If one is a pred of the other, it's first elsif (grep {$_ eq $i2} @{$hash{$i1}{pred}}) { return 1; } elsif (grep {$_ eq $i1} @{$hash{$i2}{pred}}) { return -1; } else { # Check recursively my ($rec) = grep $_, map {pred_cmp($_, $i2)} @{$hash{$i1}{pred +}}; if ($rec) { print "Returning $rec\n"; return $rec } ($rec) = grep $_, map {pred_cmp($i1, $_)} @{$hash{$i2}{pred}}; if ($rec) { print "Returning $rec\n"; return $rec } return 0; } } for (sort {pred_cmp($a,$b)} keys %hash) { print "$_\n"; }

    Caution: Contents may have been coded under pressure.
Re: Sort Algorithm (recursive?)
by Perl Mouse (Chaplain) on Oct 14, 2005 at 15:17 UTC
    Ah, a topological sort. Which you can be reduced to sorting if there are no conflicting requirements. (Sometimes you can do a topological sort faster than an ordinary sort, but you never need more time than a regular sort).

    I'd preprocess the 'pred' arrays so I can faster search in them, after that, I'd do a regular sort:

    #!/usr/bin/perl use strict; use warnings; my %hash = ( MEX1J => { desc => 'Job 2', pred => [qw /TEX1J/], }, MEX2J => { desc => 'Job End', pred => [qw /TEX1J MEX1J/], }, TEX1J => { desc => 'Job start', pred => [], }, ); # # Preprocess, transform the 'pred' arrays into hashes. # while (my ($key, $value) = each %hash) { $value->{pred_h} = {map {($_, 1)} @{$value->{pred}}}; } # # Sort keys. # my @keys = sort {$hash{$b}{pred_h}{$a} ? -1 : $hash{$a}{pred_h}{$b} ? 1 : 0} keys %hash; # # Print keys. # print "$_\n" for @keys; __END__ TEX1J MEX1J MEX2J
    Note that you can write the sort block as:
    {$hash{$a}{pred_h}{$b} - $hash{$b}{pred_h}{$a}}
    but that's rather obscure, and you'd need to turn off warnings.
    Perl --((8:>*
      Doesn't work on
      my %hash=( 'MEX1J' => { desc => 'Job 2' , pred => ['TEX1J'], }, 'MEX2J' => { desc => 'Job end', pred => ['TROUBLE'], }, 'TEX1J' => { desc => 'Job start', pred => [], }, 'TROUBLE' => { desc => 'who cares', pred => ['MEX1J'] } );

      Caution: Contents may have been coded under pressure.
Re: Sort Algorithm (recursive?)
by dragonchild (Archbishop) on Oct 14, 2005 at 15:36 UTC
    Convert your HoH into an AoH. To do that, you need to create a second entry in your HoH that contains successors. So, your datastructure needs to look like:
    $hash={ 'MEX1J' => { 'desc' => 'Job 2' 'pred' => [TEX1J], 'succ' => [MEX2J], }, 'MEX2J' => { 'desc' => 'Job end' 'pred' => [TEX1J,MEX1J], 'succ' => [], }, 'TEX1J' => { 'desc' => 'Job start' 'pred' => [], 'succ' => [MEX2J], } }
    That way, you can start to build your job execution tree.

    Of course, I would build this using some sort of directed graph instead of a HoH. That way, predecessors and successors would be handled for you.


    My criteria for good software:
    1. Does it work?
    2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
Re: Sort Algorithm (recursive?)
by BrowserUk (Patriarch) on Oct 14, 2005 at 15:22 UTC

    This does the job for your simple case with the only recursion necessary is that embedded inside Perl's builtin sort.

    UpdateHowever, if your structure could have circular dependancies that are indirect--ie. A depends on B depends on C depends on A.--then this will not detect that.

    Making it more efficient is the next challenge, but maybe that doesn't matter if your hash is smallish.

    Updated to use @{} instead of $#{}. With thanks to Roy Johnson

    A somewhat more efficient version curtesy of the Orcish Manouver(?) and List::Util::first that avoids modifying your datastructure.

Log In?
Username:
Password:

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

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

    No recent polls found