Re^2: better algorithm: bitwise reordering

I'm not sure I fully understood your suggestions here, perhaps again because of my own difficulties explaining the problem in the first place.

First, I would assign each element a number corresponding to its row: 0,.., $dim-1. Then I would add $dim to each element if it was equal to 'x' and 2*$dim if it was equal to '*'.

Hmm, so something like:

  my @bits = (0 .. $dim - 1);
  for (0 .. $dim - 1) {
    $bits[$_] += 2 * $dim if $v & (1 << $_);
  }
  $bits[$height] += $dim;
  my @bitmap = map $_ % $dim, sort { $b <=> $a } @bits;
[download]

If I understand this correctly, this should produce the same @bitmap that my current code calculates. I'm not sure about the efficiency: the dominant order of my current code for that calculation is O($dim), but I suspect replacing many O($dim) perl opcodes with an O($dim log $dim) C-coded sort will probably win on the constants. And the resulting code is certainly a lot clearer than I had.

Now that you have the permutation, simply map all the other columns using the permutation. If you have many columns, I'd suggest creating a lookup table for the mapping. You are done.

This bit I don't understand. Having built the mapping of bits (rows), I then applied it with this code:

  # we now know what row should go where, so build and return the mapp
+ed result
  my @invmap = sort { $bitmap[$a] <=> $bitmap[$b] } 0 .. $dim - 1;
  my @vmap = (0);
  for (0 .. $dim - 1) { 
    my $mapped = 1 << $invmap[$_];
    push @vmap, map $_ + $mapped, @vmap;
  } 
  return ($bitmap[$height], [ @$args[ @vmap ] ]);
[download]

This first inverts the mapping with a sort, then uses the inverse mapping of bits to construct a mapping for each of the 2 ^ $dim bit patterns, then applies that map to the current $args arrayref. Is that significantly different from what you're suggesting here?

In the broader picture, your transformations induce an automorphism (permutation) on the array of bits, which by projection down to your $args array, induce an automorphism of the $args array itself. An interesting exercise would be to act directly on the $args array itself, skipping the bitwise sorting entirely.

I'm not sure I understand this either: are you suggesting removing the need for the rearrangement by recoding the rest of the program to work on the array in place, eg using an auxiliary array to describe the bit-order? That might be interesting, but the primary benefit of the rearrangement is to make logically equivalent arglists identical so that memoization can short-circuit the calculations. If I don't do the actual rearrangement, I still need to identify a signature for the arglist that encapsulates the same rearrangement for the memoization to work, and I suspect that means doing the work of the actual rearrangement in all but name.

Apologies if I've wildly misunderstood any of the things you were trying to say.

Hugo

Comment on Re^2: better algorithm: bitwise reordering Select or Download Code

Replies are listed 'Best First'.
Re^3: better algorithm: bitwise reordering by kvale (Monsignor) on Aug 26, 2004 at 04:33 UTC
I think we are mostly on the same page. The first code snippet in your post is precisely what I was suggesting: recode the elements of the bit array in the 'x' column to easily discover the set of transformations (resulting in a permutation of the rows)) needed to rearrange the 'x' column in the desired form. I think your second snippet of code executes what I was suggesting: take the permutation computed in the first snippet and apply it to every column of your bit array. I'm sorry for not making more effort to understand your code; my comments may very well be redundant. My 'broader picture' comment was just suggesting that explicit twiddling of the bit array might be able to be bypassed. If I understand your $args array correctly, a value z at index i means that you have z columns with bitstring i. The permutation converts each bitstring into another bitstring, which has the effect of shuffling the elements of $args. For instance transposing bit rows 1 and 2 would turn bit pattern '3' into bit pattern '5', so if $args3 = z, then after the transposition $args5 = z. In effect z has been permuted from the '3' postion in the $args array to the '5' position. The same thing happens for all the other elements of $args. Thus permuting the bit rows in the bit array is tantamount to permuting the elements of $args. Mathematically, one would say that the automorphism of the bit array induces an automorphism the $args. Whether manipulating the $args directly is faster than the bit twiddling depends on how slow the bit row copying is and, as you mention, speedups like memoization. I mostly made the comment for mathematical interest. -Mark	[reply]

Replies are listed 'Best First'.

Re^3: better algorithm: bitwise reordering
by kvale (Monsignor) on Aug 26, 2004 at 04:33 UTC

The first code snippet in your post is precisely what I was suggesting: recode the elements of the bit array in the 'x' column to easily discover the set of transformations (resulting in a permutation of the rows)) needed to rearrange the 'x' column in the desired form.

I think your second snippet of code executes what I was suggesting: take the permutation computed in the first snippet and apply it to every column of your bit array. I'm sorry for not making more effort to understand your code; my comments may very well be redundant.

My 'broader picture' comment was just suggesting that explicit twiddling of the bit array might be able to be bypassed. If I understand your $args array correctly, a value z at index i means that you have z columns with bitstring i. The permutation converts each bitstring into another bitstring, which has the effect of shuffling the elements of $args. For instance transposing bit rows 1 and 2 would turn bit pattern '3' into bit pattern '5', so if $args3 = z, then after the transposition $args5 = z. In effect z has been permuted from the '3' postion in the $args array to the '5' position. The same thing happens for all the other elements of $args. Thus permuting the bit rows in the bit array is tantamount to permuting the elements of $args. Mathematically, one would say that the automorphism of the bit array induces an automorphism the $args.

Whether manipulating the $args directly is faster than the bit twiddling depends on how slow the bit row copying is and, as you mention, speedups like memoization. I mostly made the comment for mathematical interest.

-Mark

[reply]