Anonymous user
Talk:Nonogram solver: Difference between revisions
→Python Entry
Line 4:
:: OK, I have updated the Python entry. But we are often collaborating on RosettaCode, so it's very good to be civil and friendly :-) I don't want to step on your toes. -[[User:Bearophile|bearophile]] ([[User talk:Bearophile|talk]])
:: Most of the run time of the D entry is used by genRow function. (And generating unsigned bytes instead of ints reduces the memory a lot, but leaves the run-time unchanged). So is is possible to use a 32/64 unsigned integer to represent the inner arrays (the possible configurations for each row), something like [2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] => 81fff? And if a more compact representation is possible, is it leading to a faster program? (if you use 64 bits you can't have rows longer than 64) -[[User:Bearophile|bearophile]] ([[User talk:Bearophile|talk]])
::: It really depends on what operations are the slowest in the program. Row/col runs could initially generate a lot of possible patterns, so reducing memory footprint can reduce cache/page misses, which may help, but it really depends. Also keep in mind that whatever you use to track allowed cell values must have 4 states: must be filled, must be empty, can be either, and can be neither, which means it must have at least 2 bits per cell, so 64 bit likely will only represent up to 32 cells.
::: If I were to write it in C, I'd probably first try to find some other way to manage allowable patterns instead of generating all of them at once, which could be cleaner for a lower level language. But that's just a hunch. --[[User:Ledrug|Ledrug]] ([[User talk:Ledrug|talk]]) 01:48, 7 April 2014 (UTC)
| |||