Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: filling area by color atack safety - worst memory size Date: Sat, 13 Apr 2024 08:30:03 -0700 Organization: A noiseless patient Spider Lines: 106 Message-ID: <86y19hxouc.fsf@linuxsc.com> References: <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> <86o7b9ms7d.fsf@linuxsc.com> <20240320115416.00001ab5@yahoo.com> <86zfusltwp.fsf@linuxsc.com> <20240324193352.000062e9@yahoo.com> <86jzlrk0f6.fsf@linuxsc.com> <20240405173033.00006145@yahoo.com> <868r1k1uq8.fsf@linuxsc.com> <20240411152033.00007173@yahoo.com> <86o7afyxnk.fsf@linuxsc.com> <20240412111305.00004bf2@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Sat, 13 Apr 2024 17:30:06 +0200 (CEST) Injection-Info: dont-email.me; posting-host="44a1207aeaadfda1483c7b96a3737e57"; logging-data="3234235"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+X8iJav99cSWXIOpvELf5rkM1OnuKkPwU=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:0E8rk8HT4HPmCPzui5w/deGrL9k= sha1:HXnEO+LurFtDc3kGsq5Nt2YyjVI= Bytes: 4590 Michael S writes: > On Thu, 11 Apr 2024 22:09:51 -0700 > Tim Rentsch wrote: [...] >> I do timings over these sizes: >> >> 25 x 19 >> 19 x 25 >> 200 x 200 >> 1280 x 760 >> 760 x 1280 >> 1920 x 1080 >> 1080 x 1920 >> 3840 x 2160 >> 2160 x 3840 >> 4096 x 4096 >> 38400 x 21600 >> 21600 x 38400 >> 32767 x 32767 >> 32768 x 32768 > > I didn't went that far up (ended at 4K) I test large sizes for three reasons. One, even if viewable area is smaller, virtual displays might be much larger. Two, to see how the algorithms scale. Three, larger areas have relatively less influence from edge effects. Also I have now added 275 x 25 25 x 275 400 x 300 300 x 400 640 x 480 480 x 640 1600 x 900 900 x 1600 16000 x 9000 9000 x 16000 > and I only test landscape sizes. May be, I'd add portrait option > to see anisotropic behaviors. I decided to do both, one, for symmetry (and there are still some applications for portrait mode), and two, to see whether that has an effect on behavior (indeed my latest algorithm is anisotropic, so it is good to test the flipped sizes). >> with these patterns: >> >> fractal >> slalom >> rotated slalom >> horizontal snake and vertical snake >> cross in cross >> donut aka ellipse with hole >> entire field starting from center >> >> If you have other patterns to suggest that would be great, >> I can try to incorporate them (especially if there is >> code to generate the pattern). >> >> Patterns are allowed to include a nominal start point, >> otherwise I can make an arbitrary choice and assign one. > > My suit is about the same with following exceptions: > 1. I didn't add donut yet > 2. + 3 greeds with cell size 2, 3 and 4 > 3. + fractal tree By "fractal" I meant fractal tree. Sorry if that was confusing. > 4. + entire field starting from corner I used to do that but took it out as redundant. I've added it back now. :) > It seems, neither of us tests the cases in which linear dimensions > of the shape are much smaller than those of the field. Shouldn't make a difference (for any of the algorithms shown) as long as there is at least a 1 pixel border around the pattern. Maybe I will add that variation (ick, a lot of work). By the way the donut pattern already has a 1 pixel border, ie, does not touch any edge. > static void make_grid( > unsigned char *image, > int width, int height, > unsigned char background_c, > unsigned char pen_c, int cell_sz) > { > for (int y = 0; y < height; ++y) { > unsigned char* p = &image[y*width]; > if (y % cell_sz == 0) { > memset(p, pen_c, width); > } else { > for (int x = 0; x < width; ++x) > p[x] = x % cell_sz ? background_c : pen_c; > } > } > } Ahh, this is what you meant by greed. A nice set of patterns. I wrote a variation where the "line width" as well as the "hole width" is variable, and added a bunch of those to my tests (so a full timing suite now runs for several hours).