Talk:Mian-Chowla sequence: Difference between revisions
→Basic Algorithm: Perhaps one of the procedural Python compressions costs more than it saves ?
m (→Basic Algorithm: updated link) |
(→Basic Algorithm: Perhaps one of the procedural Python compressions costs more than it saves ?) |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 30:
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 under 100 ms. [https://tio.run/##jVHLbsMgELzzFStfAq0T5XFqJZ/6GW6EKMYKKi8BVhSp/@5icFS77SEcEOzM7szuulu8WHMax95bDTIKH61VAaR21kfgdjCxBhmU5KIGfmHSoBmLUguEOtGDlsxQfrFXxTB5RZCO5tBAezjnz00K1aVQu50DLgw6JEIQEbfHM8lBI67L8BztrYfoJVMgTbGDj7PGHTYZmqxhzWtoM/28IE0nlU6VDTyXaitM9hlOVbKxdeLC2o4rwTwmf/APL9gn@i@DdR1Oj58UoYJYC5RhfDX3HPSosuY75pwwHc4trcEy89IrSg1SapgWlELTwIZSnaZF6aY4CTGNZlrnbrpmFedlmrWSIeKyfrxacw2nPSEPUl/2NRz2v/jVu3mz2g2RRWlN1ocrC1UNeOFlGyKBpyk71ah0qMg4fgM (Here is a link)] I was somewhat surprised to find that the revised code goes around 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)
:I took a look at your Python code but did not run it. I must admit that I stopped development after getting what I thought were correct results and did not look to optimise.
:If your code is correct then it seems best if you replace my proceedural code, and maybe amend the comparative timings above the following, more functional version, (where the functional is now ~3x slower when run on the Tio.run site), as there is no need to keep my original proceedural code.
: Thanks. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 07:17, 21 March 2019 (UTC)
:: You're welcome, I will do what you suggest. --[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 13:38, 21 March 2019 (UTC)<br/>
:Thanks for pointing out that the 2nd Go version contains some redundant code - probably a hangover from an earlier version I wrote. Anyway, I've removed it now and achieved the ~40% performance boost you mentioned :) --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 09:32, 21 March 2019 (UTC)
:: You're welcome. --[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 13:38, 21 March 2019 (UTC)
Tidying and simplifying the functional Python, it occurred to me that one of the speed optimisations in your procedural version could possibly be losing more on the swings than it's gaining on the roundabouts. Most of the integers tested will not turn out to be Mian-Chowlas, so perhaps the cost of constructing a new set, saving all sums from the test, and then (in most cases) just clearing that set, is an uncertain investment ? (The current functional draft doesn't bother, and still seems fast). Of course, both versions are now at a few dozen milliseconds, so nothing much turns on it :-) [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 15:40, 4 April 2019 (UTC)
| |||