tag:blogger.com,1999:blog-8513438391157777465.post7636244152790343134..comments2023-04-07T05:56:45.278-07:00Comments on Re: Factor: Fast "shuffle"mrjbq7http://www.blogger.com/profile/06842721076008035602noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-8513438391157777465.post-47902175762633416932013-03-01T07:42:26.165-08:002013-03-01T07:42:26.165-08:00For python, you not need to implement it. It's...For python, you not need to implement it. It's already implemented under random.shuffle (http://docs.python.org/2/library/random.html#random.shuffle)<br /><br />And you can use range instead of xrange and then go through and build an array (it's faster)<br />https://gist.github.com/ehmo/5065450<br /><br />On my laptoon (2 years old MacBook air) and python 2.7.1 the result is:<br /><b>took 13.629 seconds</b>xsshttps://www.blogger.com/profile/08031265009505650737noreply@blogger.comtag:blogger.com,1999:blog-8513438391157777465.post-31251189708216848952013-02-28T08:10:33.999-08:002013-02-28T08:10:33.999-08:00@Redline6561: Your Lisp code is broken, you need t...@Redline6561: Your Lisp code is broken, you need to use (random (1+ i)) instead of (random i) to get an index in the right interval.<br /><br />Also, please do not use ELT instead of AREF, the idea of using this algorithm on lists is disgusting.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8513438391157777465.post-54409279476307321482013-02-27T06:21:29.787-08:002013-02-27T06:21:29.787-08:00@Redline6561: Nice examples!
@halex: I forgot abo...@Redline6561: Nice examples!<br /><br />@halex: I forgot about builtin shuffle, that would make a nice comparison with the builtin Ruby version.<br /><br />@AndrewDalke: Great points! I wasn't trying to make Python look bad at all, just to show how performance is all over the place. I know there's many versions of optimizations you could do in Python (similar to how I try and speed up the Factor version) including writing it in C to be "fastest".<br /><br />It's fun that you can usually write C in any language, but it's refreshing to see PyPy and LuaJit allowing C-like performance with more simple looking code.<br /><br />Thanks!mrjbq7https://www.blogger.com/profile/06842721076008035602noreply@blogger.comtag:blogger.com,1999:blog-8513438391157777465.post-14898131543983138432013-02-27T05:44:20.901-08:002013-02-27T05:44:20.901-08:00CPython uses a dictionary lookup for module variab...CPython uses a dictionary lookup for module variables. Local variables have an optimized O(1) lookup because it's impossible to add new variables to local scope after a function has been declared.<br /><br />If I wrap the code in a "def main():" and call it with "main()", then I get a drop from 20 seconds to 17.<br /><br />Two other minor optimizations are to use range(n) instead of list(xrange(n)), and to make randrange be a local variable ("import random" then before the main loop "randrange = random.randrange"). This turns a large number of module lookup+attribute lookup calls into a single fast local lookup call.<br /><br />Pypy does this last optimization automatically.<br /><br />Using the suggestion of halex, random.shuffle on the array takes about 8 seconds in CPython.Andrew Dalkehttps://www.blogger.com/profile/17091314849699854287noreply@blogger.comtag:blogger.com,1999:blog-8513438391157777465.post-34017392349949809182013-02-27T01:20:41.228-08:002013-02-27T01:20:41.228-08:00You really should mention the python builtin funct...You really should mention the python builtin function <a href="http://docs.python.org/2/library/random.html#random.shuffle" rel="nofollow">shuffle</a> when writing about the ruby builtin too. In my case the runtime went down a factor of 3 when using this bultin shuffle function compared to your naive one (with plain Python 2.7.3).halexhttps://www.blogger.com/profile/12233112742056082750noreply@blogger.comtag:blogger.com,1999:blog-8513438391157777465.post-65311444645751220342013-02-26T21:04:23.224-08:002013-02-26T21:04:23.224-08:00Adding (declaim (ftype (function ((simple-vector))...Adding (declaim (ftype (function ((simple-vector))) shuffle)) gets my lisp version down to ~0.6 seconds.<br /><br />A luajit 2.0 version with no type declarations performs in about 0.63 seconds.<br /><br />math = require("math")<br />os = require("os")<br /><br />local toy = {}<br />for i=1, 10000000 do<br /> toy[i] = math.random(10000000)<br />end<br /><br />function shuffle(seq)<br /> for i=(#seq-1), 1, -1 do<br /> j = math.random(i)<br /> seq[i], seq[j] = seq[j], seq[i]<br /> end<br />endRedline6561https://www.blogger.com/profile/05037070664173001374noreply@blogger.comtag:blogger.com,1999:blog-8513438391157777465.post-76615419510119330092013-02-26T20:07:14.762-08:002013-02-26T20:07:14.762-08:00Just for giggles, I got the following results in m...Just for giggles, I got the following results in my Debian64 VM with SBCL 1.14*:<br />[*] PRE and CODE tags were rejected. Sorry if this looks like garbage.<br /><br /><br />(defun shuffle (arr)<br /> (loop for i from (1- (length arr)) downto 1<br /> do (rotatef (aref arr (random i)) (aref arr i))))<br /><br />CL-USER> (time (shuffle *toy*))<br />Evaluation took:<br /> 1.065 seconds of real time<br /> 1.524095 seconds of total run time (1.524095 user, 0.000000 system)<br /> 143.10% CPU<br /> 3,161,941,417 processor cycles<br /> 0 bytes consed<br /><br />Taking away the specialization on arrays with AREF, we get a slightly slower version:<br /><br />(defun shuffle2 (seq)<br /> (loop for i from (1- (length seq)) downto 1<br /> do (rotatef (elt seq (random i)) (elt seq i))))<br /><br />CL-USER> (time (shuffle2 *toy*))<br />Evaluation took:<br /> 1.405 seconds of real time<br /> 2.032127 seconds of total run time (2.032127 user, 0.000000 system)<br /> 144.63% CPU<br /> 4,165,084,903 processor cycles<br /> 28,128 bytes consedRedline6561https://www.blogger.com/profile/05037070664173001374noreply@blogger.com