in reply to In-place sort with order assignment

# untested!

my %h = (...);

my @k;
while (keys %h) {
  my $k = each %h;
  push @k, $k;
  delete $h{$k};
}

@k = sort @k;

my $ix = 0;
while (@k) {
  $h{shift @k} = $ix++;
}

[download]

Replies are listed 'Best First'.
Re^2: In-place sort with order assignment
by BrowserUk (Patriarch) on Sep 19, 2010 at 16:17 UTC

    I tried that, and I think it might work, but it takes an extraordinary amount of time. So much so that I never actually saw it complete. To counter that, I tried extracting and deleting the keys in batches of 1000: 

    my @ordered;
while( my $n = keys %hash ) {
    my @temp;
    for ( 1 ..  $n < 1000 ? $n : 1000 ) {
        push @temp, scalar each %hash;
    }
    delete @hash{ @temp };
    push @ordered, @temp;
}

    [download]

    But it still takes an extraordinary amount of time.

    Update: The above has a precedence problem with the ternary expression! And results in for loop operating from 1 to 1.

    Add a set of parens and things go much more quickly: 

    my @ordered;
while( my $n = keys %hash ) {
    my @temp;
    for ( 1 ..  ( $n < 1000 ? $n : 1000 ) ) {
        push @temp, scalar each %hash;
    }
    delete @hash{ @temp };
    push @ordered, @temp;
}

    [download]

    BTW: If I ever manage to get the keys out of the hash and into an array without blowing memory, then I intend to use your Sort::Key to sort them in-place. But, there doesn't seem to be a an in-place version of keysort that doesn't take a callback?

    I can use keysort_inplace{ $_ } @ordered;, but doesn't the callback slow things down?

    I can use rsort_inplace @array and just assign the numbers reversed, but it seems there should be a sort_inplace() version?

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
[select]
      BTW: If I ever manage to get the keys out of the hash and into an array without blowing memory, then I intend to use your Sort::Key to sort them in-place. But, there doesn't seem to be a an in-place version of keysort that doesn't take a callback?

      It seems the interface is not very consistent... actually, the function exists, it is Sort::Key::_sort_inplace.

      In any case, perl builtin sort will perform equally faster as @k = sort @k gets optimized by the interpreter into an inplace operation.

      BTW, using the quicksort algorithm instead of the default merge sort will also help to reduce memory usage.

[reply]
[d/l]
[select]
        @k = sort @k gets optimized by the interpreter into an inplace operation.

        When did that make it into the release? Cos everytime it comes up here, I try it out and it doesn't seem to work. (And my attempt to search for the release info fail.)

        For now, Sort::Key::_sort_inplace() will do me fine.

[reply]
[d/l]

In Section Seekers of Perl Wisdom