Re: better algorithm: bitwise reordering

I tried the idea of converting the args into a 2D array of 0/1s with unpack, then inverting it. That way you can perform the swapping of bits on all the rows in one go (swapping anonymous arrays around). You then reinvert and pack back to ints before finally sorting and returning.

It works, but it's certainly not quicker.

I also built a lookup table for the specific case. 3-bits gives an table with 7 elements (x-column value if 0..6. 7 is impossible because it leaves no place for the 'x'). Each of the 7 first level elements has the potential for 3 sets of swaps (one for each combination of x-column value * position of the x).

Of the 21 possible combinations, 9 are impossible and 2 require no swaps (they are correctly ordered on input). For each of the 10 remaining you need either 1 or 2 pairs of column indexes that require swapping, that need to be applied to each of the args.

## 3-bit case only.
my %reorder = (
    0 => [ undef        , [[0,1]], [[0,1],[1,2]] ],
    1 => [ undef        , [[0,1]], [[0,2]]       ],
    2 => [ [[0,1]]      , undef  , [[0,1],[1,2]] ],
    3 => [ undef        , undef  , undef         ],
    4 => [ [[1,2],[0,1]], [[0,2]], []            ],
    5 => [ undef        , [[1,2]], undef         ],
    6 => [ [[0,1],[1,2]], undef  , undef         ],
);

sub reorder {
    my( $dim, $height, $v, $args ) = @_;
    my $xforms = $reorder{ $args->[ $v ] }[ $height ];
    return $args unless $xforms;
    
    for my $arg ( @$args ) {
        swapBits( $arg, @$_ ) for @$xforms;
    }
    return $args
}
[download]

That's not working code (swapBits() is undefined) but it gives feel for the notion. The problem then would be building the lookup tables, would become quite large depending upon the maximum dimensions you are hoping to handle. But if speed is the issue, and your current sub works, then using it to build the lookup once and storing it would allow runtime to be a bit quicker I think.

ADDENDUM: Having typed that in, I realise that there is no need to store the pairs of indexes. You may as well store the xformed values instead. It saves one level of depth in the lookup at the expense of the lower level having 2**n-bits values. Which is probably much of a muchness space-wise, but it avoids the need for swapBits().

You just lookup the correct array of xforms, then lookup each args value in that and replace it with the contents indexed. That would be much quicker. At the cost of the memory.

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon

Comment on Re: better algorithm: bitwise reordering Download Code

Replies are listed 'Best First'.
Re^2: better algorithm: bitwise reordering by hv (Prior) on Aug 26, 2004 at 02:26 UTC
Yes, the lookup certainly would be an improvement: since the memoization is also `$dim`-dependent, I've written the rest of the code to assume a series of calculations with `$dim` fixed, so I'd only need to set up the table once per run. In general (though I haven't benchmarked it recently[0]) I believe that `@$args[ @mapping ]` should be very fast, so I think either calculating the mapping array from the lookup table or (memory permitting) replacing the lookup-of-bitswaps with a lookup-of-mappings would be preferable to doing sequences of individual swaps within the array. (I hadn't mentioned it, but the `$args` arrayref needs to be preserved, so serial swapping would need to be preceded by a copy.) Hmm, of course each bitswap could be replaced by a mapping array - that way only `$dim * ($dim + 1) / 2` mappings would need to be stored, rather than `O($dim * (2 ^ $dim) / 2)`, at the cost of applying multiple mappings in some cases. Hugo [0] bad optimizer, no cookie	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^2: better algorithm: bitwise reordering
by hv (Prior) on Aug 26, 2004 at 02:26 UTC

Yes, the lookup certainly would be an improvement: since the memoization is also $dim-dependent, I've written the rest of the code to assume a series of calculations with $dim fixed, so I'd only need to set up the table once per run.

In general (though I haven't benchmarked it recently[0]) I believe that @$args[ @mapping ] should be very fast, so I think either calculating the mapping array from the lookup table or (memory permitting) replacing the lookup-of-bitswaps with a lookup-of-mappings would be preferable to doing sequences of individual swaps within the array.

(I hadn't mentioned it, but the $args arrayref needs to be preserved, so serial swapping would need to be preceded by a copy.)

Hmm, of course each bitswap could be replaced by a mapping array - that way only $dim * ($dim + 1) / 2 mappings would need to be stored, rather than O($dim * (2 ^ $dim) / 2), at the cost of applying multiple mappings in some cases.

Hugo

[0] bad optimizer, no cookie

[reply]
[d/l]
[select]