home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1809 next >
Encoding:
Text File  |  1992-08-23  |  2.7 KB  |  79 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!wupost!cs.utexas.edu!torn!watserv2.uwaterloo.ca!watdragon.uwaterloo.ca!abrodnik
  3. From: abrodnik@watdragon.uwaterloo.ca
  4. Subject: Re: Generic sorting functions
  5. Message-ID: <BtGtup.F55@watdragon.uwaterloo.ca>
  6. Organization: University of Waterloo
  7. References: <9208212151.AA44579@cs90code.csv-tgsc.amex-trs.com>
  8. Date: Mon, 24 Aug 1992 02:06:24 GMT
  9. Lines: 68
  10.  
  11. In article <9208212151.AA44579@cs90code.csv-tgsc.amex-trs.com> gonzalod@amex-trs.com (Gonzalo Diethelm) writes:
  12. >
  13. >A very generic question. Given a set S of n strings (the `|' characters
  14. >are used as delimiters):
  15. >
  16. >  s1   |dunno|
  17. >  s2   |I'd rather have a bottle in front of me than a frontal lobotomy|
  18. >  s3   |eschew clever rules|
  19. >  ... ...
  20. >  sn   |bzzzzt!|
  21. >
  22. >and an ordering sequence O:
  23. >
  24. >  {s4, s1, s6, s2, sn, s3, ... s7}
  25. >
  26. >is there any way to determine a fixed, hopefully cheap function
  27. >
  28. >  f(): SxS -> integers
  29. >
  30. >with the property that
  31. >
  32. >  if si comes before sj in O, f(si, sj) < 0
  33. >  if si comes after  sj in O, f(si, sj) > 0
  34. >
  35. >that is, could be used to sort the strings in the given sequence?
  36.  
  37. If I understnd this correctly, you are asking the following question:
  38.  
  39.     o you are given a total ordering (not known how to efectively
  40.       compute relations among elements)
  41.     o make a comparison function for this ordering.
  42.  
  43. If your function can use O(S) space, your total running time is 
  44.  
  45.                 O(S*c + n*c),
  46.  
  47. where n is the number of queries to it. The c represents the time to
  48. fetch the internal table.
  49.  
  50. At first query f simply runs through the sequence O until it finds the
  51. right key (it can't do better -- apply a simple adversay argument,
  52. because you don't know efective function to describe it). As it
  53. searches for the right key, it assigns proper indices to the internal
  54. table. This table will be later used to map from key --> itsOrder. The
  55. assumption here is that the set of keys {s_i} is known in advance.
  56.  
  57. Each searching for the index in the table takes O(c) time (you can
  58. take here O(log S) for tree or binary search, or O(1) for perfect
  59. hashing).
  60.  
  61. The first search takes O(S*c) time, but each subsequent search will
  62. take then O(c) time what gives us the above bound.
  63.  
  64. Even more, because of the adversary argument the lower bound on the
  65. first search is also _O_(S*c) and simple reasoning will also show that
  66. the mentioned upper bound matches the lower bound.
  67.  
  68. The overall assumption here is that the set {s_i | i=1..S} is known in
  69. advance. I think that it is feasible especially because the only way
  70. to order elements is through the sequence O. It's an interresting
  71. question if the space can be decreased. Again (because of the
  72. adversary argument) it seems that the time will increase immediately.
  73.  
  74. This are my 2 pence.
  75.  
  76. Best regards,
  77.  
  78. Andrej
  79.