Rosetta Code

Talk:Cut a rectangle: Difference between revisions

Page Discussion

Talk:Cut a rectangle (view source)

Revision as of 12:55, 14 October 2011

565 bytes removed ,  12 years ago
→‎J implementation
(→‎J implementation: wrong timing)
 
Line 118:
::: Tracking the path can still be done with your bit matrix, albeit its size should be (m+1) x (n+1) now. The advantage is it will never produce duplicate solutions, and due to symmetry, you'll only need to search in half or a quarter (if m = n) of the solution space. --[[User:Ledrug|Ledrug]] 14:41, 13 October 2011 (UTC)
:::: I've implemented your suggestion of asymmetric neighbor pruning at each step. I am not quite sure how I would implement the division path approach -- the data structures for that all seem more complex than the bit matrix (and neighbor location) approach I currently use. --[[User:Rdm|Rdm]] 03:22, 14 October 2011 (UTC)
:::: P.S. I know that we do not do timings on this site, but .... --[[User:Rdm|Rdm]] 11:01, 14 October 2011 (UTC)
:::: P.S. I know that we do not do timings on this site, but I thought I should point out that the current C solution seems significantly slower than the J solution. On my machine, the first of the current C solutions takes 6.390 seconds of user time for the 3 4 rectangle case (though I do not know how to interpret its results). For comparison purposes, the J solution takes less than a millisecond on the same machine. Even if we allow for a factor of 2 timing inaccuracy between runs, I think that that's still a significant difference -- and since J is implemented in C, I think these timings might even have some validity? Granted, though, the second C implementation took only 15 milliseconds, which is probably fast enough. --[[User:Rdm|Rdm]] 11:01, 14 October 2011 (UTC)
::::: Er what? I guess you missed the fact that the first C program doesn't take arguments. You were looking at the time needed to calculate all size combos below 10. I changed it here to run 4x3 for a million times, and the run took .4 seconds. --[[User:Ledrug|Ledrug]] 11:13, 14 October 2011 (UTC)
:::::: Oh, oops, yes -- that would explain it. Thanks. --[[User:Rdm|Rdm]] 12:55, 14 October 2011 (UTC)
Rdm
6,951

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/202594"