From: Dan S. <dv...@ea...> - 2004-10-30 14:03:50
|
Concerning set-difference ... If it is known that both sets are sorted, the calculation can proceed very quickly indeed. Consider, apart from hashing, to write #'sorted-set-diff, which presumes sorting, and then use this on sorted sets. Intuitively, since decent sorting takes place in (* n (log n) time, and #'sorted-set-diff is one-pass, this could be a favorable solution for larger sets. Might compete favorably with hashing. It would require,however, two predicates: A :test parameter and a :pecedes parameter, so you might wind up inferring #'< from #'= and so forth. That could get sticky. Just a thought. Devious Dan |
From: Sam S. <sd...@gn...> - 2004-10-30 15:00:39
|
> * Dan Starr <qi...@rn...g> [2004-10-30 10:05:39 -0400]: > > If it is known that both sets are sorted, the calculation can proceed > very quickly indeed. this is already outside ANSI CL. see CLOCC/CLLIB/sorted.lisp -- Sam Steingold (http://www.podval.org/~sds) running w2k <http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/> <http://www.mideasttruth.com/> <http://www.honestreporting.com> There is Truth, and its value is T. Or just non-NIL. So 0 is True! |