sorting a list of key value pairs 
Author Message
 sorting a list of key value pairs

i want to sort a key-value pairs. i was thinking of modifying the
heap sort algorithm in AWK book such that A[i] is used for
comparisons, but when we swap, we swap A[i] and A[i+1] (i stores
the key, i+1 the value).

but this seems a little awk-ward (:-)). is there an obvious better way?

--
        Dr. Tim Menzies     rm EE339 | "I appreciate the fact that

/     \ AI Dept, School of Computer  | but some of the sentences that
\_,-._* Science& Engineering,Uni NSW | you are sending out in the
     v  Sydney, Australia, 2052      | world to do your work for you
        +61-2-93854034(p)93855995(f) | are loitering in taverns or
    http://www.*-*-*.com/ ~timm | asleep beside the highway."
                                     | -- Dr. Dwight Van de Vate,
                                     |    Professor of Philosophy,
                                     |    Uni Tennessee, Knoxville



Thu, 18 Nov 1999 03:00:00 GMT  
 sorting a list of key value pairs

Quote:

>i want to sort a key-value pairs. i was thinking of modifying the
>heap sort algorithm in AWK book such that A[i] is used for
>comparisons, but when we swap, we swap A[i] and A[i+1] (i stores
>the key, i+1 the value).

Sorting in awk is painfully slow, because indexing into an array to
fetch or set the array element is a hash lookup instead of a pointer
offset.  I *never* sort in awk.  Better is to write the output to a
file, sort the file with sort(1), and read the file back.  I've timed
this many times, and it seems like about 50 elements or so is the
breakeven point at which it is better to suffer the intermediate I/O
than sort in awk, and even at only a few elements the time difference
is very small.

If you get a copy of Brian Kernighan's awk interpreter, the change log
indicates that at one point he had the "for (i in ...)" construct sort
the i's, but then took that feature out because it cost too much when
it wasn't needed; the code is still in the source, in comments.  Awk
is designed to work in conjunction with the other unix tools, providing
only the features not already provided elsewhere.

Phil
--



Thu, 18 Nov 1999 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Ada Package to read keyed attribute-value pairs

2. Split with Regular Expressions to get Key-Value Pair

3. Accessing hash values sorted by their keys

4. sort keyed lists

5. list to list of pairs

6. Sorting list of hex values

7. How to add a key:datum pair to the dictionary

8. (or (gethash key table) (setf (gethash key table) new-value))

9. plot pair of values in a XY graph

10. using putheader() to send name/value pairs

11. getting option-value pair data in Tktable

12. TCL Name/Value Pairs

 

 
Powered by phpBB® Forum Software