Talk:Mian-Chowla sequence: Difference between revisions

I am a novice at python programming, and I was looking the ''Python Procedural'' version, using tio.run and found it takes about 2 seconds to execute. I made a few changes to it and got the execution time down to aboutunder 100 ms. [https://tio.run/##jVLJasMwEL3rKwZfIrdOyHJqIadjVHLbsMgELzzFStfAq0T5XFqJZ/6GW6EKMYKKi8BVhSp/@hmuEqshkqDYkhRDov7uyrFC77SE6GPSWmTcju1s8W3MYht5bDRilj9aqAKid9RGEvZjYAAaFQjYgzhwNKVxELQk5yR40csPE2V4Vp5icFS77SEcEOzM7szuulu8WHMax95bDTIKH61VAaR21kfgdjCxBhmU5KIGfmHSoBmLUguEOtGDlsxQfrFXxTB5RZCO5tBAezjnz00K1aVQu50DLgw6JEIQEbfHM8lBI67L8BztrYfoJVMgTbGDj7PGHTYZmqxhzWtoM/UrgXS0gCO0uy5fbijVKUHtugAuXHRIgiAjbfddnUEjr3O4oL31ED1yBWimOHRfetxpk6kxGtWigTbLu5loPKl0qmzgeaq24LDPdKqSgy2Ns2gboST3tP7Df3jJP8k28IE0nlU6VDTyXaitM9hlOVbKxdeLC2o4rwTwmf/Dvgq06RL9APL9gn@OTKshlF3dXFyN5tL0WGi@6cNCea51qS0@KngUmakjHDtWQMjkdYMabTyhhbTUlCTPsZ33QzfkoX5zEtXGGIdPoH6OKtGzhs6DdR1Oj58UoYJYC5RhfDX3HPSosuY75pwwHc4trcEy89IrSg1SapgWlELTwIZSnaZF6aY4CTGNZlrnbrpmFedlmrWSIeKyfrxacw2nPSEPUl/pB6cu2gd32l756N29Wu0vkEa3J2NRz2v/eHKQ9UAnWVZh1jD0@hONSodqnoYvgEjVu3mz2g2RRWlN1ocrC1UNeOFlGyKBpyk71ah0qMg4fgM (Here is a link)] I was somewhat surprised to find that the revised code goes aboutaround 20 times faster.<br/><br/>The thing I noticed about what I was able to change was that the test against the existing sums can be simplified, that is, rather than maintaining a list of all the sums and testing each new trial against the whole list, one can test the trials against only the previous iterations list of sums, and build an incremental list (without checking the incremental list). If the trial succeeds, the incremental list is combined with the main sums list. If you think about it, it is mathematically impossible for each new iteration's trials to collide with it's own iteration. Each new iteration's trials can only collide with the sums from previous iterations.<br/><br/>Another thing to point out is that, in the modified code (linked above), I clear the incremental list after combining it with the main sums list. This seems like it would slow things down, but the time spent clearing it is offset by the odds that it will be quickly cleared when there is a sums collision in the block above. Also, since the Sets are being union-ed, instead of appended, any attempted duplication is disregarded. If that line is omitted, (the "newsums.clear()" in the else block), the program execution time remains about the same. So perhaps it is redundant.<br/><br/> The quickest run at (tio.run) so far is the 2nd Go version which is about 10ms. However, it can be increased slightly to ~6ms by removing the unnecessary removal of the "isx" items from the "is" set (because they never get put in there in the first place). --[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 05:07, 21 March 2019 (UTC)