This graph shows the results of a tradeoff study on different procedures to shuffle a list into random sequence.The abscissa shows the length of the list, and the ordinate the time taken (on a 550 MHz PIII) to shuffle it.The curves correspond to the ''shuffle0'', ''shuffle1'', ''shuffle1a'', ''shuffle2'', ''shuffle3'' and ''shuffle4'', ''shuffle5'', ''shuffle5a'', and ''shuffle6'' procedures, all of which appear on the page entitled [Shuffle a list]. ([KBK] Note that the vertical scale needed to be changed to accommodate [[shuffle6]].) Please look below the image for the code that generated it.Thanks to DKF for making the image available! [MG] wonders if the image-creation code could be redone using something like package require Img set graph [image create photo -data .c -format window] $graph write shufflegraph.gif -format gif to make it work in a few more places? (NOTE: The image is missing the curve for [[shuffle6]].) [http://www.man.ac.uk/~zzcgudf/tcl/wikipix/shufflegraph.gif] ---- # Graph the results of a tradeoff study on list shuffle procedures grid [canvas .c -width 640 -height 480 -bg white] array set color { 0 black 1 blue 1a forestgreen 2 red 3 magenta 4 darkcyan 5 gray50 5a brown 6 orange } set yscale [expr { 400 / ( log( 1000000 ) - log ( 1 ) ) }] set xscale [expr { 560 / ( log( 10000 ) - log ( 1 ) ) }] .c create line 60 440 620 440 .c create line 60 440 60 40 for { set n 1 } { $n <= 10000 } { set n [expr { $n * 10 }] } { set x [expr { 60 + $xscale * log ( $n ) }] .c create text $x 450 -text $n -anchor n -font {Helvetica -10} for { set nn $n } { $nn < 10*$n && $nn <= 10000 } { incr nn $n } { set x [expr { 60 + $xscale * log ( $nn ) }] .c create line $x 440 $x 450 } } for { set t 1 } { $t <= 1000000 } { set t [expr { $t * 10 }] } { puts "t = $t" set y [expr { 440 - $yscale * log ($t ) }] .c create text 50 $y -text [expr { 0.000001 * $t}] -anchor e \ -font {Helvetica -10} for { set tt $t } { $tt < 10*$t && $tt <= 1000000 } { incr tt $t } { set y [expr { 440 - $yscale * log ($tt ) }] .c create line 60 $y 50 $y } } # default font is {Helvetica -12} .c create text 320 5 -text "Comparison of list shuffle methods" -anchor n \ -font {Helvetica -12 bold} .c create text 330 475 -text "List size" -anchor s -font {Helvetica -10} .c create text 5 210 -text "Time (s)" -anchor w -font {Helvetica -10} set y0 42 set dy [font metrics {Helvetica -12} -linespace] .c create text 75 $y0 -anchor nw -text "Key:" -fill black -tag key \ -font {Helvetica -12 bold} incr y0 $dy foreach { method tm(1) tm(10) tm(100) tm(1000) tm(10000) } { shuffle0 33 118 997 11045 183446 shuffle1 28 169 2055 105000 ------ shuffle1a 33 187 1717 17243 176520 shuffle2 39 203 1852 19034 229225 shuffle3 28 128 1097 12195 267413 shuffle4 30 138 1182 11808 121336 shuffle5 20 95 1023 35988 ------ shuffle5a 24 108 908 10266 250796 shuffle6 8 74 633 6409 66740 } { set ab [string range $method 7 end] set y1 [expr {$y0+$dy/2}] .c create line 75 $y1 95 $y1 -fill $color($ab) -tag key .c create text 100 $y0 -anchor nw -text $method -fill $color($ab) \ -tag key incr y0 $dy foreach n { 1 10 100 1000 10000 } { set t $tm($n) if { [string compare ------ $t] } { set x [expr { 60 + $xscale * log ( $n ) }] set y [expr { 440 - $yscale * log ($t ) }] .c create text $x $y -text $ab -anchor center \ -fill $color($ab) -font {Helvetica -10} if { [info exists lastx($ab)] } { .c create line $lastx($ab) $lasty($ab) $x $y \ -fill $color($ab) } set lastx($ab) $x set lasty($ab) $y } } } foreach {x1 y1 x2 y2} [.c bbox key] {} .c create rectangle [incr x1 -2] [incr y1 -2] [incr x2 2] [incr y2 2] \ -fill grey95 -outline black -tags {key keybg} .c lower keybg if {[tk_messageBox -type yesno -title "Snapshot?" -icon question \ -message "Take snapshot of graph?"] == "yes"} { # Need *two* updates update update # DKF - And Now a little code to convert this graph to a GIF # image file. Obviously, this doesn't work everywhere and the # filename is hardcoded... exec xwd -id [winfo id .c] | xwdtopnm 2>@stderr | \ ppmtogif >shufflegraph.gif 2>@stderr exit } ----[AMG]: See also [Shuffling a list] and [unsort]. ---- !!!!!! %| [Category Mathematics] | [Category Plotting] |% !!!!!!