home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / lang / prolog / 1672 < prev    next >
Encoding:
Text File  |  1992-09-08  |  4.4 KB  |  112 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!munnari.oz.au!cs.mu.OZ.AU!mundil.cs.mu.OZ.AU!fjh
  3. From: fjh@mundil.cs.mu.OZ.AU (Fergus James HENDERSON)
  4. Subject: Re: AVL trees - improving an implementation of:
  5. Message-ID: <9225217.13465@mulga.cs.mu.OZ.AU>
  6. Sender: news@cs.mu.OZ.AU
  7. Organization: Computer Science, University of Melbourne, Australia
  8. References: <Bu6w2w.IBF@matilda.vut.edu.au>
  9. Date: Tue, 8 Sep 1992 07:12:37 GMT
  10. Lines: 100
  11.  
  12. awenn@matilda.vut.edu.au (Andrew Wenn) writes:
  13.  
  14. >I have implemented (almost entirely thanks to Ivan Bratko's book) 
  15. >a program for AVL trees. However, it has a problem, which I 
  16. >suspect is mainly due to the lack of tail recursion optimisation 
  17. >in the prolog that I am using in that if I try to insert a large 
  18. >number of items into it I run out of local stack space. For 
  19. >various reasons, I cannot increase the size of the stack and 
  20. >besides I feel this is the incorrect approach. By the way if I 
  21. >use a simple binary dictionary, I can insert all the records I 
  22. >wish into it.
  23.  
  24. A good reference which covers this sort of thing is "The Craft of Prolog"
  25. by Richard O'Keefe, in particular chapter 3, "Where Does All The Space Go?".
  26.  
  27. >----------------------------------------------------------
  28. >%%%   A program for constructing and searching an avl tree.
  29. >
  30. >/* Based on Bratko pp 244ff. */
  31. >
  32. >/* Build the tree. */
  33. >
  34. >% The root of the tree is Key.
  35. >
  36. >addavl( nil/0, Key, avl(nil/0, Key, nil/0)/1 ).    
  37.  
  38. Using '/' in this way is convenient, but most Prolog compilers
  39. are not smart enough to avoid using extra space if you do so.
  40. The following is likely to be more space-efficient:
  41.  
  42.     addavl( nil(0), Key, avl(nil(0), Key, nil(0), 1) ).    
  43.  
  44. Ie. replace nil/H with nil(H) and avl(L,K,R)/H with avl(L,K,R,H).
  45. [You will need to change all the rest of the code too :-( ]
  46.  
  47. >addavl( avl(Left, Y, Right)/Hy, Key, NewTree):-
  48. >    eq(Y, Key), 
  49. >    !,
  50. >    NewTree = avl(Left, Y, Right)/Hy.
  51. >
  52. >addavl( avl(Left, Y, Right)/Hy, Key, NewTree):-
  53. >    gt(Y, Key),
  54. >    addavl(Left, Key, avl(Left1, Z, Left2)/_ ),
  55. >    combine(Left1, Z, Left2, Y, Right, NewTree).  
  56. >
  57. >addavl( avl(Left, Y, Right)/Hy, Key, NewTree):- 
  58. >    gt(Key, Y),
  59. >    addavl(Right, Key, avl(Right1, Z, Right2)/_ ),
  60. >    combine(Left, Y, Right1, Z, Right2, NewTree).  
  61.  
  62. The basic problem is likely to be that although the above code
  63. is deterministic, most Prolog compilers are not going to be smart
  64. enough to detect this, and you are going to get unnecessary choice
  65. points on the stack. You could improve things by putting a cut after the 
  66. call gt(Y, Key), which would remove the choice point from the stack,
  67. but it is better to avoid pushing the choice point in the first place.
  68.  
  69. Most Prolog compilers "index" clauses on the top-level functor of the
  70. first argument, and will detect determinism if the top-level functors
  71. of the first argument of each clause are different (and avoid pushing
  72. choice points).  Thus the following code may be much more efficient:
  73.  
  74.         % top-lvl functors of 1st arg are nil/1 and avl/4.
  75.     addavl( nil(0), Key, avl(nil(0), Key, nil(0), 1)).    
  76.     addavl( avl(Left, Y, Right, Hy), Key, NewTree):-
  77.         termCompare(Y, Key, Result),
  78.         addavl_2(Result, Left, Y, Right, Hy, Key, NewTree).
  79.  
  80.         % Using termCompare/3 above allows us to index on 1st arg here,
  81.         % thus avoiding creating choice points
  82.     addavl_2(=, Left, Y, Right, Hy, _Key, avl(Left, Y, Right, Hy)):-
  83.         write(Y),    % don't hide these writes in eq/2 - put them
  84.                 % here in addavl so they're obvious.
  85.                 % eq/2 might be used for other purposes.
  86.         write(' Item already in tree\n').
  87.     addavl_2(>, Left, Y, Right, Hy, Key, NewTree):-
  88.         addavl(Left, Key, avl(Left1, Z, Left2, _),
  89.         combine(Left1, Z, Left2, Y, Right, NewTree).
  90.     addavl_2(<, Left, Y, Right, Hy, Key, NewTree):-
  91.         addavl(Right, Key, avl(Right1, Z, Right2, _),
  92.         combine(Left, Y, Right1, Z, Right2, NewTree).
  93.  
  94. You should use the same trick with termCompare and an auxiliary predicate
  95. for searching the AVL tree.
  96.  
  97. >combine(T1/H1, A, avl(T21, B, T22)/H2 , C, T3/H3,
  98. >        avl(avl(T1/H1, A, T21)/Ha, B, avl(T22, C, T3/H3)/Hc)/Hb ):-
  99.  
  100. As far as I know, most Prolog compilers don't seem to do common subexpression
  101. elimination, so repeating the terms T1/H1 and T3/H3 will cost you both time
  102. and heap space. (Another reason to avoid using '/'/2 in this way.)
  103.  
  104. Hope all this helps,
  105.     Fergus.
  106.  
  107. -- 
  108. Fergus Henderson             fjh@munta.cs.mu.OZ.AU      
  109. This .signature virus is a self-referential statement that is true - but 
  110. you will only be able to consistently believe it if you copy it to your own
  111. .signature file!
  112.