Shuffle a list: graph results

Difference between version 13 and 14 - Previous - Next
** Description **

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]

** See Also **

   * [AMG]: [Shuffling a list]
   * [AMG]: [unsort]

** Code **

======
#! /bin/env tclsh

package require Tk

# Graph the results of a tradeoff study on list shuffle procedures

grid [canvas .c -width 640 -height 480 -bg white]
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"} {
bind .c <Map> {
if {[tk_messageBox -type yesno -title "Snapshot?" -icon question \
-message "Take snapshot of graph?"] == "yes"} {
#[pyk] 2012-11-28: are these updates really needed?
## Need *two* updates
#update
#update
#[pyk] 2012-11-28: are these updates really needed?
## 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 | ppmquant 256 | \
ppmtogif >shufflegraph.gif 2>@stderr
exit
# 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 | ppmquant 256 | \
ppmtogif >shufflegraph.gif 2>@stderr
exit
}
}
grid .c
====== <<categories>> Mathematics | Plotting