in reply to constructing large hashes

I have a simple question, what on earth are you doing that could require a 4 million entry hash? the collisions on that in a 32bit space are not going to be pretty, and the build time will be silly. Unless you're doing a shitload of lookups its not going to be more efficient than calculating the entries on the fly, especially if your system is low on ram.

More details on the actual problem would help :)

Replies are listed 'Best First'.
Re: Big Picture
by duelafn (Parson) on Oct 01, 2002 at 00:39 UTC

    Why, I'm classifying codimension two hyperplane arrangements in C2. What else would I be doing?

    Basically, I need to create all of the permutations of 1 to n, then for each one, apply a set of three rules which will give me a list of different permutations which shall be deemed "equivalent" to the current one. I give each of these a common tag and then move on.

    I do perform quite a few lookups to determine whether I have already applied the set of rules to a particular permutation through one of its equivalent representations. This is important since each of the rules can give me many equivalent permutations.

    At the end I perform one final clean up since sets of equivalent permutations may have been labeled with different tags. I make note of these occurrances during the first pass through though, so the final cleanup is trivial.

    Thanks for asking! (but I bet you're sorry you did)

    Update: Sorry, we're in C2 not C4

    If we didn't reinvent the wheel, we wouldn't have rollerblades.

      Thanks for asking! (but I bet you're sorry you did)

      You're not wrong there :) :)

      Its situations like this where MathML or equivalent would be really nice, since you could just give me the forumlae :)

      In essence, what I understood was the following:

      For every permutation 1->n check every permutation 1->n to see if it is equivalent according to the rules. If it is, mark it as such.

      Results: a set of groups of permutations who are deemed equivalent.

      Are the rules transitive?

      My head generated psuedocode something like this (no efficiency or anything, just a general algorithm):

      foreach $p_1 (permutation(1..n)) { if ($tags{$p_1}) { next; } $tags{$p_1} = $p_1; foreach $p_2 (permutation(1..n)) { if (rule1($p_1, $p_2) && rule2($p_1,$p_2) && rule3($p_1, $p_2)) + { $tags{$p_2} = $p_1; } } }

      But that only works if the rules are both transitive and symmetric (you hint that they are but I may be reading it wrong)

      I would be interested in the contents of the rules 1->3 if they're not going to make my head ache :)

        Actually, I (fortunately) do not need two for loops. The main loop of my code is this:
        $i = 'A'; # the class label for $n (@temp) { next if defined $arrangements{$n}; # already classified it. @n = split /,/, $n; @classmates = ( $n, join(',', reverse @n) ); # n and its mirror @classmates = (@classmates, &M1(@n)); # Maz 1 @classmates = (@classmates, &M2(@n)); # Maz 2 @classmates = (@classmates, &M3(@n)); # Maz 3 &ClassReunion( $i, \@classmates ); $i++; }

        M1, M2, and M3 are the three moves (literally, the permutations represent lines in space) which return a new list of permutations. &ClassReunion just does some magic with the label $i.

        M1 is easy, it is just the cyclic permutations of the list Ex: M1(12345) -> 51234, 45123, 34512, 23451. sub M1 { map join(',', @_[$_..$#_], @_[0..$_-1]), 1..$#_ }

        M2 is the inverse permutation. The permutation 4132 is equivalent to tr/1234/4132/. The inverse would then be tr/4132/1234/.

        sub M2 { my %temp; @temp{(1..@_)} = @_; %temp = reverse %temp; return join(',', @temp{(1..@_)}); }

        M3 is, unfortunately much harder to explain, and has much longer code. I've posted a working version of the code on my sratchpad. If you /msg me I will post a better explanation of M3 there as well.

        Good Day,

        If we didn't reinvent the wheel, we wouldn't have rollerblades.