home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / pascal / 4516 < prev    next >
Encoding:
Text File  |  1992-07-22  |  1.9 KB  |  43 lines
  1. Newsgroups: comp.lang.pascal
  2. Path: sparky!uunet!gatech!usenet.ins.cwru.edu!po.CWRU.Edu!wct
  3. From: wct@po.CWRU.Edu (William C. Thompson)
  4. Subject: Re: Sparse matrices (comparison of methods)
  5. Message-ID: <1992Jul22.234424.3870@usenet.ins.cwru.edu>
  6. Sender: news@usenet.ins.cwru.edu
  7. Nntp-Posting-Host: cwns5.ins.cwru.edu
  8. Reply-To: wct@po.CWRU.Edu (William C. Thompson)
  9. Organization: Case Western Reserve University, Cleveland, OH (USA)
  10. References: <BrsxF5.DIw@news.cso.uiuc.edu> <1992Jul20.042405.6954@usenet.ins.cwru.edu>
  11. Date: Wed, 22 Jul 92 23:44:24 GMT
  12. Lines:       30
  13.  
  14.  
  15. Before I had proposed that each node contain four pointers, left, right,
  16. down, and up, and you enter each row/column through one of two doubly 
  17. linked lists.  Each node stores its position in the array.  This has
  18. the advantage of being able to process elements in either order, up
  19. or down, very quickly.  Unfortunately, each cell requires 20 bytes,
  20. which can add up quickly.  500 elements (not unheard od) would need
  21. 10K in pointers alone.  Not to mention the 10 bytes needed for each
  22. row and column.  At worst, this array would use 5K of pointers.  At
  23. best, a little more than 220 bytes.  15K isn't catastrophic for 500
  24. elements.  Any non-trivial application probably has data that dwarves
  25. the 15K.  The main problem is speed.  If you are accessing elements
  26. at the end of lists, it could take a while.
  27.  
  28. Another suggestion has been to use doubly-linked lists for each row
  29. and have a list pointers into the rows.  This uses half as much memory
  30. (potentially), but you lose the ability to go in each direction with
  31. ease and speed.
  32.  
  33. You could also use trees instead of linked lists.  The speed is there,
  34. but going from element to a nearby element can be awkward.  Going in
  35. both directions isn't there either.
  36.  
  37. As usual, it depends on your application what you decide.
  38. -- 
  39.  
  40.                         [currently under construction]
  41.  
  42.  
  43.