home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / lang / misc / 2843 < prev    next >
Encoding:
Text File  |  1992-09-01  |  2.4 KB  |  58 lines
  1. Newsgroups: comp.lang.misc
  2. Path: sparky!uunet!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!usenet.coe.montana.edu!oususalg
  3. From: oususalg@cs.montana.edu (Glassy)
  4. Subject: Mutating Data Organization:  Practical?
  5. Message-ID: <1992Sep1.142643.3061@coe.montana.edu>
  6. Sender: usenet@coe.montana.edu (USENET News System)
  7. Organization: Montana State University, Bozeman Montana USA
  8. Date: Tue, 1 Sep 1992 14:26:43 GMT
  9. Lines: 47
  10.  
  11. A small idea yesterday:
  12.  
  13. Suppose the machine representation of one's data could transparently
  14. mutate in response to the way one uses it.
  15.  
  16. For example, say I start out with a mythical data structure called a
  17. 'u-list' (universal list?).  I append a lot of data, one element at a
  18. time, to it.  So at first I'd like the u-list simply to have a
  19. singly-linked list representation in the machine.
  20.  
  21. Then for a while, I do a bunch of random accesses.  Now I'd like the
  22. u-list to turn into an array.
  23.  
  24. Then I access the data with another (say, clumpy) pattern, like a[1],
  25. a[21], a[2], a[22]... Now I'd like the data to somehow change its
  26. organization to maximize locality of reference (wrt the specific
  27. machine I'm on).
  28.  
  29. How often would the data's organization have to mutate?  Say, once
  30. every few runs of the program.  Data on reference/use patterns would be
  31. stored for each run, accumulated, analyzed, and possibly a new
  32. organization applied every so often (e.g., once every 5 runs?).
  33.  
  34. Is this nuts?  Has it been done?  If so, in what contexts?
  35.  
  36. It may be tempting to reply:  well, just use a XYZ representation,
  37. where XYZ is one of:
  38.    skip-list, avl-tree, threaded-splay-tree, etc., etc.
  39.  
  40. but I think this misses the point.  (I think.)  There is no single
  41. existing data structure that does *everything* well, i.e. use minimal
  42. storage, and perform sequential access, random access, prepend, append,
  43. arbitrary insertions, etc, all in constant order.  (at least, I haven't
  44. run across such a data structure yet!)  so:  if my use of the data has
  45. a pattern to it that changes (relatively) slowly over time (e.g.  over
  46. a 5-run period), then having the data change its internal
  47. representation to best suit what i seem to be doing with it *now*,
  48. might make sense.
  49.  
  50. i mentioned that i'd like to do this mutation 'transparently', because
  51. as a user of the data, i don't care what its internal representation
  52. is, as long as i can efficiently monkey with the data right *now* :-).
  53.  
  54. thoughts?
  55.  
  56. -- 
  57. Lou Glassy (oususalg@cs.montana.edu)                  C Delenda Est
  58.