home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / lisp / 3155 < prev    next >
Encoding:
Internet Message Format  |  1992-12-30  |  1.5 KB
  1. Path: sparky!uunet!think.com!barmar
  2. From: barmar@think.com (Barry Margolin)
  3. Newsgroups: comp.lang.lisp
  4. Subject: Re: sorting arrays
  5. Date: 30 Dec 1992 05:12:38 GMT
  6. Organization: Thinking Machines Corporation, Cambridge MA, USA
  7. Lines: 26
  8. Message-ID: <1hrb46INNjgf@early-bird.think.com>
  9. References: <C01pCC.MFK@acsu.buffalo.edu>
  10. NNTP-Posting-Host: gandalf.think.com
  11.  
  12. In article <C01pCC.MFK@acsu.buffalo.edu> lewocz@acsu.buffalo.edu (John S. Lewocz) writes:
  13. >What would be the most effiecient way to sort a two-dimensional
  14. >array using an arbitrary column
  15. >as a key?
  16.  
  17. I can't vouch for it being "the most efficient way", but here's a
  18. reasonably simple way that seems like it shouldn't be too inefficient.
  19. Make a list or vector of displaced arrays, where each elements is a vector
  20. displaced to a row of the original array.  Sort this using :KEY #'(LAMBDA
  21. (X) (AREF X COLUMN-NUMBER)), and then combine the results into a new 2-D
  22. array.
  23.  
  24. Some of the sources of inefficiency in this may be all the references to
  25. displaced arrays and the copying of the elements into the result.  You can
  26. avoid the former (at the cost of more consing and copying) by copying the
  27. rows into new vectors at the beginning instead of using displaced arrays.
  28.  
  29. If you need to avoid all copying, then you'll have to do the sorting in
  30. place, and there's nothing built into Lisp (Common Lisp, at least) to do
  31. this, so you'll have to write your own sort routine.
  32.  
  33. -- 
  34. Barry Margolin
  35. System Manager, Thinking Machines Corp.
  36.  
  37. barmar@think.com          {uunet,harvard}!think!barmar
  38.