Binary trees in gawk 
Author Message
 Binary trees in gawk

I've been thinking about this enhancement to gawk & would like to get
opinions.

I would like to see an option to gawk to store associative arrays in a
binary tree so that they could be read out in sorted order, rather than
by hashed order - which is essentially random.

There are, of course, tradeoffs involved - a binary tree is likely to be
slower than a hash table in access, but the programmer can decide
whether the tradeoff is worth it.

Gawk has so many enhancements to standard awk already that adding a new
feature to gawk that is incompatible with awk shouldn't be a problem.

What do y'all think?

Jim Mellander
System Administrator
Lawrence Livermore National Laboratory



Sun, 15 Apr 2001 03:00:00 GMT  
 Binary trees in gawk

Quote:

> I've been thinking about this enhancement to gawk & would like to get
> opinions.

> I would like to see an option to gawk to store associative arrays in a
> binary tree so that they could be read out in sorted order, rather than
> by hashed order - which is essentially random.

> There are, of course, tradeoffs involved - a binary tree is likely to be
> slower than a hash table in access, but the programmer can decide
> whether the tradeoff is worth it.

Jim,

This issue has been discussed in comp.lang.awk in the past. In particular,
there was a thread with the subject "Looking for Unix-based AWK that does
Array sorting" initiated on 09/19/1996 by Jeremy Mathers

threads on the topic.

Here's a brief synopsis of what I know about this topic:

    o  TAWK from Thompson Automation Software
       <http://www.tasoft.com/~thompson/tawk.html> has this feature
       already. It uses a built-in variable named SORTTYPE to control the
       behavior of the expression 'for (index in array)'. Strangely,
       the default behavior is to sort array indexes; it must be turned
       off for TAWK to behave as other awks behave. I believe I read
       that the manner in which the indexes are sorted (ASCIIbetically,
       numerically, etc.) is user-definable.

    o  Brian Kernighan added this feature to awk, then immediately
       removed it. Here is his explanation in the FIXES file of his
       awk distribution <http://cm.bell-labs.com/who/bwk/awk.shar>:

         May 6, 1991:

           changed for (i in array) to access elements in sorted order.
           then unchanged it -- it really does run slower in too many
           cases. left the code in place, commented out.

    o  This issue stirs passions and starts flame wars. Purists are
       opposed to introducing anything into awk that bloats the
       language and reduces execution speed (i.e, makes it more like
       Perl). Others, like you, see it as a useful extension that, if
       implemented as a user-selectable option, can do no harm to the
       language. Among those in the latter camp, there's no concensus
       on how best to implement this option.

Quote:
> Gawk has so many enhancements to standard awk already that adding a new
> feature to gawk that is incompatible with awk shouldn't be a problem.

Exactly.

Quote:
> What do y'all think?

My opinion, in a nutshell: Add it.

--
Jim Monty

Tempe, Arizona USA



Sun, 15 Apr 2001 03:00:00 GMT  
 Binary trees in gawk

Quote:

> I would like to see an option to gawk to store associative arrays in a
> binary tree so that they could be read out in sorted order, rather than
> by hashed order - which is essentially random.

> There are, of course, tradeoffs involved - a binary tree is likely to be
> slower than a hash table in access, but the programmer can decide
> whether the tradeoff is worth it.

> Gawk has so many enhancements to standard awk already that adding a new
> feature to gawk that is incompatible with awk shouldn't be a problem.

There's certainly folks who want this feature, and others who think
that awk doesn't need the extra code.  If I recall correctly, there
are some awk's with this feature.  Jeremy Mathers

   As I mentioned in another thread, I modified mawk to do "array sorting"
   (a controversial "feature" of AWK, the merits of which we will not
   discuss here)

Arnold Robbins does not necessarily see these posts.  If you want
your addition to become part of gawk, you will need to write to

features.

--



Sun, 15 Apr 2001 03:00:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Self-Adjusting Binary Search Trees (Splay Trees)

2. Self-Adjusting Binary Search Trees (Splay Trees)

3. AVL Tree,Binary Tree,Sorting..

4. gawk win32 binary & single quote invalid char

5. looking for windows NT/2000 binary for gawk 3.1.1 (or better)

6. GAWK 3.0.4 DOS binary WHERE ?

7. Binary Data in (m/gawk)

8. Gawk for win32 slower than Gawk for Dos_32?

9. Gawk bug, gawk won't nawk.

10. gawk 3.0.95, beta for gawk 3.1.0, now available

11. Pointers and Binary Trees!

12. Binary tree

 

 
Powered by phpBB® Forum Software