[AMG] Please bear with my silly mood and my overlong narrative. We'll fix it later. :^) I think I'll move the "story" elements to a new page, leave the sort algorithms here, and move the array-based set stuff to a page on sets. '''Argument''' I needed a ''set'' data type with the following properties, above and beyond those of basic lists: * Order is unimportant. {bravo delta charlie alpha} == {alpha delta bravo charlie}. * An element is either in the set, or it isn't. The frequency of any given element is either zero or one. I needed the following operations: insertion: After inserting an element, all that is guaranteed is that it will be present in the set. It won't necessarily be at the end of the set, and if it was already present then the set will not be modified. In my program I expected that relatively few insertions would result in new elements being added. membership: This operation returns true if and only if the element was previously inserted, i.e. is present in the set. iteration: I'm not sure this is the name I should be using, but here I mean the ability to get a list of all elements suitable for use with [[[foreach]]]. I didn't need to worry about removing elements, doing operations involving multiple sets (union, intersection, symmetric difference, subtraction, comparison, etc.), or generating power sets or anything like that. '''Book 1 - Lists, or, the Author goes on at Length''' So I thought the best way of doing it was with a list that always remained sorted. Why? Because this made the membership check very fast. And by the way, I used the variable name ''lst'' rather than ''set'' to avoid [Vim] erroneously highlighting it as a keyword. Also it is the name of a variable in the caller's stack frame, not the set itself. proc scontains {lst elem} { upvar 1 $lst var return [expr {[lsearch -exact -sorted $var $elem] != -1}] } This gives a nice logarithmic-time means of checking whether or not an element is in a set. For example, determining whether or not a 1000-element set contains any given element takes at most 10 checks. For comparison's sake, using an unsorted list to represent a set can require up to 1000 checks for this same situation. And I might as well cover "iteration" while I'm laying the groundwork. A set, being represented as a list, can be used directly as a list so long as the operation is read-only. But nevertheless I'll wrap it as a proc. proc slist {lst} { upvar 1 $lst var return $var } This returns a list of every element present in the set. '''Chapter 1 - In which Insertion is Developed''' Next, insertion. But first I'll state that an empty set is represented as {}. I'll wrap it in a proc for the sake of completeness. proc screate {lst} { upvar 1 $lst var set var {} } Nonempty sets can be built up from there using insertions. Here's the simplest possible implementation: proc sinsert_simple {lst elem} { upvar 1 $lst var set var [lsort -unique [lappend var $elem]] } This works by first appending $elem to the end of the set list, then re-sorting the list while removing any duplicates. But this is rather wasteful because there is at most one duplicate (the newly-inserted $elem), yet this fact isn't communicated to [[[lsort]]] so it has no choice but to check the whole list for duplicates. Before going any further, let's set up a benchmarking system to prepare performance. I'll be running these tests on a 486 running at 50MHz. If your computer is slower than this, don't worry, Tcl will still run. :^) proc test {func} { screate lst puts [time {$func lst [expr {int(rand() * 1000)}]} 1000] } This inserts 1000 random numbers into a set and prints the average insertion time. The numbers are themselves in the range 0 ... 999, so there will be a fair number of duplicates. (It might be an interesting probability problem to determine the distribution of the lengths of the sets after such a test...) Now let's try it with [[sinsert_simple]]. % test sinsert_simple 20445 microseconds per iteration Yes, it really did take 20 seconds to run that test. Maybe it might go faster on computers of the future. Why, in another decade we might even be able to get it down to 10 seconds! :^) '''Chapter 2 - Insertion gains in Sophistication''' Next revision: Armed with the knowledge that the list representation need not change if $elem is already in the set, and that adding a new element never creates a duplicate, I can write: proc sinsert_checkmemb {lst elem} { upvar 1 $lst var if {![scontains var $elem]} { set var [lsort [lappend var $elem]] } return $var } I'm guessing that in my test about 40% of the insertions are duplicates, so the time should go down to 12267 microseconds or so. Let's check. % test sinsert_checkmemb 12098 microseconds per iteration That's a pretty big improvement. Consistent with by 40% guess (okay, it wasn't a guess, I checked [[[llength] $lst]]), it takes 40.8% less time to run [[sinsert_checkmemb]] than [[sinsert_simple]]. '''Chapter 3 - In which the Author milks Insertion for all it's Worth''' But there are more possibilities in store. Since there's at most one element to insert into a list that's already sorted, why re-sort the entire list? This next proc ditches [[lsort]] in favor of a binary search to determine at which point in the list the new element needs to be inserted (or if it is already present). proc sinsert_bsearch {lst elem} { upvar 1 $lst var set left 0 set right [llength $var] while {$left < $right} { set idx [expr {($left + $right) / 2}] set dat [lindex $var $idx] switch -- [string compare $dat $elem] { -1 {set left [expr {$idx + 1}]} 0 {return $var } 1 {set right $idx } } } set var [linsert $var $left $elem] return $var } I was initially hesitant about coding so much in Tcl, since the [C]-implemented [[lsort]] "should" be faster due to being compiled machine code, but the benchmark shows that algorithmic improvements give better results than switching from [bytecode] to machine code. % test sinsert_bsearch 7011 microseconds per iteration See, rather than wait a decade (okay, okay, 18 months) for hardware technology to double my program's speed, I could just drop in a better algorithm and get the same effect in no time at all. '''Chapter 4 - In which the Author admits his Lie''' But I've been rather irresponsible in my benchmarks. Going to a higher-performance class of algorithm (i.e. quadratic time to linear time to logarithmic time to constant time) always gives a speed boost for high ''n''. (The ''n'' refers to the letter in [Big O] notation: O(n log n) for example.) But it also tends to increase coding complexity and setup time. In fact, it's quite common for an unsophisticated algorithm to outperform a fancy algorithm given that the actual data used has low values of ''n''. So to even things out, first let's redo the benchmarks for various values of ''n'' rather than just 1000 as was done above. foreach n {1 5 10 25 50 100 250 500 1000} { puts "n = $n" foreach func {sinsert_simple sinsert_checkmemb sinsert_bsearch} { puts -nonewline " $func: "; flush stdout set sum 0 for {set i 0} {$i < 5} {incr i} { screate lst set dur [time {$func lst [expr {int(rand() * $n)}]} $n] incr sum [lindex $dur 0] } puts [expr {$sum / 5}] } } And here's the result, manually generated from the output of the above [[foreach]] loop: n simple checkmemb bsearch 1 1611 2442 1428 5 1662 2282 2327 10 1736 2330 2743 25 1938 2578 3314 50 2337 2653 3844 100 3076 3070 4476 250 5771 4439 5481 500 10487 7234 6317 1000 20820 12650 7283 As you can see, [[sinsert_bsearch]] loses all the way up to around n=300, but from there on out its increased overhead pays for itself. [[sinsert_simple]] works fine until n=100, at which point [[sinsert_checkmemb]] starts to work better. The finished [[sinsert]] proc can determine which algorithm to use based on the list length, but first verify that the overhead of the [[[if]]] doesn't overwhelm your optimization. I should also mention that the above table entries and the tradeoff points are all dependent on the nature of the data, specifically the ratio of unique insertions to duplicate insertions. So if you want to use any of this code in your own application, you should benchmark using actual data rather than blindly trusting the above. Important rule of thumb: ''n'' is always small. Look before you optimize! I didn't. Which brings me to the next book in my tale of coding and woe. '''Book 2 - Arrays, or, in which the Author realizes he is an Idiot''' You may have noticed the use of past tense in the above narrative. I have since repented, deciding that a sorted list is '''not''', in fact, the best way to represent a set. Per [Joe English]'s casual suggestion (I hope I have that attribution correct), I tried using [array]s. The results were both astonishing and humbling. Mostly humbling! '''Chapter 1 - In which the Paradigm is Shifted''' So I switched from using lists to arrays to represent my sets. For the sake of this Narrative we don't care about the value associated with any particular key in the array, so we'll just use "". But know that in your own program you're free to abuse arrays any way you wish. Any given element can either be or not be in any given set. Any given key can either be or not be in any given array. See the parallel? The properties of sets map much more closely to arrays than they do to lists, wherein we have to do special things to avoid duplicate elements and discourage dependence on order. First we need a way of creating a new, empty set. The following will do: proc screate {arr} { upvar 1 $arr var array set var {} } And here's the array version of [[scontains]]. I'm changing from ''lst'' to ''arr'' as my set variable name. Again, I'd just say ''set'' directly if not for [Vim]. proc scontains {arr elem} { upvar 1 $arr var return [info exists var($elem)] } Notice how easy that was. All the searching has moved from my script to inside the Tcl core, so this code will automatically take advantage of all future algorithmic breakthroughs in the field of fast array lookup and subsequent improvements to the Tcl array implementation. It's a little more tricky to get a list of all elements in a set, now that the set is no longer itself a list. But it's definitely doable: proc slist {arr} { upvar 1 $arr var return [array names $var] } The returned list is by no means sorted, but sort order's not supposed to matter anyway. If you need it to be sorted, just use [[lsort]] afterwards. Of course this particular proc is less efficient than its list-only method from Book 1, but it's still workable. '''Chapter 2 - In which the Difficult becomes Easy (and fast, too!)''' Now for set insertion. If you will recall, this occupied the bulk of the above discussion, which is actually a good thing because this page is supposed to be about sorted ''lists'', not arrays, and therefore I'll leave all that claptrap where it is just in case somebody decides he wants a sorted list. proc sinsert {arr elem} { upvar 1 $arr var set var($elem) "" } Don't blink or you'll miss it! This code is now very short and simple. And as it turns out, very fast. Here's proof: foreach n {1 5 10 25 50 100 250 500 1000} { set sum 0 for {set i 0} {$i < 5} {incr i} { screate arr set dur [time {sinsert arr [expr {int(rand() * $n)}]} $n] incr sum [lindex $dur 0] } puts "n = $n : [expr {$sum / 5}]" } Adding the results to the previous table yields absolutely marvelous results: n simple checkmemb bsearch array 1 1611 2442 1428 1561 5 1662 2282 2327 1158 10 1736 2330 2743 1158 25 1938 2578 3314 1162 50 2337 2653 3844 1160 100 3076 3070 4476 1196 250 5771 4439 5481 1164 500 10487 7234 6317 1163 1000 20820 12650 7283 1168 We appear to have gone to constant time. Stunning. I'm sure there's a hidden cost. Most likely the array representation of sets uses more memory than the list representation of sets. I don't have what I need to check the memory usage, though, so I'll leave that for someone else. Honestly, I don't really even care. If memory usage was crucial then I'd just use a slower algorithm. ''Fin.'' [AMG] I just discovered a shortcoming of the array-based set procedures. With them it is impossible to store sets inside arrays. This is fatal for the program I'm writing now. But that's not so bad since said program has ''n'' of up to, uhm, 50, and at that point performance is quite acceptable using the basic [[lappend]]/[[lsort -unique]] method. ---- [AM] Beware of code outside procedures: such code is ''not'' compiled and hence messes up the timings. I suspect that with the various versions inside a procedure the timing results will be very different! [AMG] Okay, I redid the benchmarks using a proc. (Whereas above I did the table formatting manually this time I got smart and used [MAK]'s [[listToTable]], found in [Additional list functions]. I modified it a bit to do right justification.) n simple checkmemb bsearch array 1 1467 4322 1541 1890 5 2136 2202 2678 1345 10 2095 2679 3306 1298 25 2526 2275 4172 1272 50 3014 2041 4116 1047 100 4762 2196 4856 1122 250 10774 2931 5793 1051 500 21721 4263 6348 1063 1000 44843 7075 7122 1056 Yeah, that is different. Thanks for the tip. I can see more clearly now that using Tcl's built-in binary search (inside the implementation of [[[lsearch]]]) wins over my script-based binary search. But I think that if insertions were more frequent then [[sinsert_bsearch]] would outperform [[sinsert_checkmemb]]. Again, relative performance of different algorithms is often very data-dependent. If the [[lsearch -sorted]] command could be made to return the index where an element ''should'' be even if not actually present in the list, that would give the best performance of all. ---- [schlenk]: [tcllib], [prioqueue] and [skiplist] have some 'sorted list' kind of functionality. [NEM]: With regard to the drawback of the array-based implementation, have you tried using [dict]s? They're in 8.5 and there is a package available which provides them for 8.4 too. [AMG]: If all set access is performed through procedures ([[screate]], [[sinsert]], [[slist]], etc.), it's quite possible for the set implementation to store the set data in an internal namespace. For example: namespace eval ::set { variable next_id 0 } proc ::set::create {} { set id $::set::next_id array set ::set::set_$id {} incr ::set::next_id return $id } proc ::set::include {id args} { foreach elem $args { set ::set::set_$id\($elem) "" } } proc ::set::contents {id} { return [array names ::set::set_$id] } % set quux [set::create] % set::include $quux alpha bravo charlie delta % set::contents $quux charlie delta bravo alpha This allows client code to treat sets as ordinary (if opaque) strings yet still takes advantage of Tcl's array system. ---- [AK]: Regarding [tcllib], it has set operations, under [struct]. Called [struct::set]. [AMG]: I see [[struct::set]] makes no attempt at sorting or any other such "optimization" of dubious benefit. This is probably for the best because, since it has no clue about the nature of the data it is given, it cannot hope to select the proper algorithm. Therefore, it falls back on [simple]. <> Algorithm | Data Structure | Performance I'm half-tempted to also put this in Category Book. :^)