awk, scheme, tcl, and/or perl (was: Why you should not use Tcl) 
Author Message
 awk, scheme, tcl, and/or perl (was: Why you should not use Tcl)



:   ... when considered as a user-visible scripting language, tcl
:   consistently kills 80% of the birds with 20% of the stones, ...
:
:When asked why I often use Scheme for scripts rather than AWK, I gave
:the example of needing a trie structure to store the data I was
:processing.  I couldn't work out how to do this easily in AWK, so I
:used Scheme.  Is there an easy way to implement a trie in TCL or do I
:have to implement it in C?  If it can be done in TCL, it would go a
:long way to convincing me that TCL can deal with 80% of the type of
:scripts *I* write.

I suspect that while it's hard to do in awk, you can problably do it in
TCL.  Hopefully someone else will post that.

There are alternatives to awk or Scheme, though, Stephan.  Here's a
(slightly modified for integer keys) package for a Patricia trie
implemented in Perl.  

I'm showing you this here, and crossposting as I have, not to incite a
flame war, but just to show folks something they might not have realized
was not only feasible, but in fact, quite straightforward in execution.

The algorithm I copied it right out of Sedgewick's Algorithms in C, added
dollar signs, and it worked just fine.  This was very nice, because it
makes translations from C into Perl a nearly mechanical process.  (Except
I wanted it to be class, so added some classy things.) It retains its C
structure though, which adds to the code busy-ness.

Suppported class methods are

    $tree = new Patricia

    insert $tree (SOME_NUMERIC_KEY, ANY_DATA)

    $data = search $tree (NUMERIC_KEY)

Other methods are included for debugging.

Do not assume that what you read here is the best you can do in terms
of speed, memory use, or reliability:  

    I could make it faster by enabling the integer pragma or using a
    list instead of a hash table represention.

    I could also use much less memory with different structure
    representation:  I could use lists ( [] ) instead of tables ( {} )
    for one thing, or I could use a packed binary structure using just 4
    words of memory plus however much data you're keeping.

    On reliability, I developed the code in a much more austere environment
    than the one you see here.  I had pragmata enabled for strict variables,
    references, and subroutines.  I had the run-time lint monitor in place
    (-w).  I used argument checking code for type and count.  I could have
    trapped undefined structure field reference if I wanted to.

I would probably change it to use string instead of integer keys.  It
would probably not perform better thoguh than Perl's internal hashing
algorithm, except perhaps on very long keys.

--tom

package Patricia;
use English;
$MAXB = 9999999;

sub new {
    my $node = bless {};

    %$node = (
        LEFT  => $node,
        RIGHT => $node,
        KEY   => 0,
        INFO  => "",
        BITS  => $MAXB,
    );

    return $node;

Quote:
}


    my $p = $head;
    my $x = $head->{LEFT};

    while ($p->{BITS} > $x->{BITS}) {
        $p = $x;
        $x = $x->{ bits($v, $x->{BITS}, 1) ? RIGHT : LEFT };
    }
    if ($v == $x->{KEY}) {
        return $x->{INFO};
    } else {
        return undef;
    }

Quote:
}


    my ($p, $t, $x);

    my $i = $Patricia::MAXB;
    $p = $head;
    $t = $head->{LEFT};

    while ( $p->{BITS} > $t->{BITS} ) {
        $p = $t;
        $t = $t->{bits($v, $t->{BITS}, 1) ? RIGHT : LEFT};
    }

    if ($v == $t->{KEY}) { return }

    while (bits($t->{KEY}, $i, 1) == bits($v, $i, 1)) { $i--; }

    $p = $head;
    $x = $head->{LEFT};
    while ($p->{BITS} > $x->{BITS} && $x->{BITS} > $i) {
        $p = $x;
        $x = bits($v, $x->{BITS}, 1) ? $x->{RIGHT} : $x->{LEFT};
    }
    $t = new();
    $t->{KEY} = $v; $t->{INFO} = $info; $t->{BITS} = $i;
    $t->{LEFT}  = (bits($v, $t->{BITS}, 1)) ? $x : $t;
    $t->{RIGHT} = (bits($v, $t->{BITS}, 1)) ? $t : $x;
    $p->{ bits($v, $p->{BITS}, 1) ? RIGHT : LEFT } = $t;

Quote:
}

sub bits {

    ($x >> $k) & ~(~0 << $j);

Quote:
}


    print <<EOF;
Node is $node
        BITS    $node->{BITS}        
        KEY     $node->{KEY}        
        INFO    $node->{INFO}        
        LEFT    $node->{LEFT}
        RIGHT   $node->{RIGHT}      
EOF

Quote:
}

sub dtree {
    local %seen;
    &rdumpdree;

Quote:
}

sub rdumpdree {

    $node->{LEFT}->rdumpdree()  unless $seen{$node}++;
    $node->print();
    $node->{RIGHT}->rdumpdree() unless $seen{$node}++;
Quote:
}



Tue, 08 Apr 1997 06:35:29 GMT  
 awk, scheme, tcl, and/or perl (was: Why you should not use Tcl)

   :... When asked why I often use Scheme for scripts rather than AWK, I gave
   :the example of needing a trie structure to store the data I was
   :processing.  I couldn't work out how to do this easily in AWK, so I
   :used Scheme.  ...

   ... There are alternatives to awk or Scheme, though, Stephan. ...

Indeed.  I thought this implication was clear in my message, but since
you followed up extolling the virtues of Perl, perhaps it was not.

   ... I would probably change it to use string instead of integer keys.  It
   would probably not perform better thoguh than Perl's internal hashing
   algorithm, except perhaps on very long keys.

If you are going to change the code, I'd suggest changing the key from
an integer to any object for which a compare operation can be defined.
I needed this flexibility in the trie I used.  I also found that an
O(log n) insert rather than O(n) insert was more efficient for my
application (I don't know Perl and don't have Sedgewick so I can't
tell if the posted insert is O(log n) or not).



Mon, 14 Apr 1997 00:47:55 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Tcl and Tcl::Tk w/ Tcl 7.5, 7.6 and Tk 4.1, 4.2

2. Why you should not use Tcl

3. Why you should not use Tcl

4. Tcl::Tk and Tcl modules are available to provide Tk GUI to perl

5. Tcl/2K : The 7th USENIX Tcl/Tk Conference Call for Papers

6. ANNOUNCE: Tcl and Tcl::Tk extensions to Perl5

7. Tcl/2K : The 7th USENIX Tcl/Tk Conference Call for Papers

8. Tcl/2k : The 7th USENIX Tcl/Tk Conference Call for Papers

9. Tcl/2k : The 7th USENIX Tcl/Tk Conference Call for Papers

10. Unix tower of babble tcl/awk/perl -- why not just lisp?

11. Why Tcl instead of Perl?

12. Why is perl faster then Tcl

 

 
Powered by phpBB® Forum Software