Path: ...!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Michael S Newsgroups: comp.lang.c Subject: Re: filling area by color atack safety - worst memory size Date: Fri, 3 May 2024 18:33:05 +0300 Organization: A noiseless patient Spider Lines: 339 Message-ID: <20240503183305.000079e0@yahoo.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> <86bk6ez9te.fsf@linuxsc.com> <20240417004609.000010aa@yahoo.com> <86plunyj82.fsf@linuxsc.com> <20240417224126.0000727a@yahoo.com> <86a5lpxbd3.fsf@linuxsc.com> <20240420211023.000067cc@yahoo.com> <20240425175606.000059d5@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Injection-Date: Fri, 03 May 2024 17:33:10 +0200 (CEST) Injection-Info: dont-email.me; posting-host="24f79386f11d1cfdbf24e001dc1c4c6c"; logging-data="624660"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX193zUa1HjNcbVXhorbmoQhJaI9ijqiqXGY=" Cancel-Lock: sha1:HwgZ+6vq7JAbmx51yMug/uCaUP8= X-Newsreader: Claws Mail 4.1.1 (GTK 3.24.34; x86_64-w64-mingw32) Bytes: 12487 On Thu, 25 Apr 2024 17:56:06 +0300 Michael S wrote: > On Sat, 20 Apr 2024 21:10:23 +0300 > Michael S wrote: > > > On Fri, 19 Apr 2024 14:59:20 -0700 > > Tim Rentsch wrote: > > > > > > > > Did you mean you some algorithms whose worst case memory > > > behavior is strictly less than O( total number of pixels )? > > > > > > I think it would be helpful to adopt a standard terminology > > > where the pixel field is of size M x N, otherwise I'm not > > > sure what O(N) refers to. > > > > > > > No, I mean O(max(M,N)) plus possibly some logarithmic component that > > loses significance when images grow bigger. > > More so, if bounding rectangle of the shape is A x B then I'd like > > memory requirements to be O(max(A,B)), but so far it does not appear > > to be possible, or at least not possible without significant > > complications and further slowdown. So, as an intermediate goal I am > > willing to accept that allocation would be O(max(M,N)). but amount > > of touched memory is O(max(A,B)). > > > > > > but so > > > > far they are all unreasonably slow - ~5 times slower than > > > > the best. > > > > > > I'm no longer working on the problem but I'm interested to > > > hear what you come up with. > > > > > > Here is what I had in mind. > I tried to optimize as little as I can in order to make it as simple > as I can. Unfortunately, I am not particularly good at it, so, code > still contains few unnecessary "tricks" that make understanding a > little harder. > The code uses VLA and recursion for the same purpose of making it less > tricky. > If desired, the memory footprint could be easily reduced by factor of > 8 through use of packed bit arrays instead arrays of _Bool. > > Even in this relatively crude form for majority of shapes this code is > blazingly fast. > Unfortunately, in the worst case (both 'slalom' shapes) an execution > time is O(max(A,B)**3) which makes it unfit as general-purpose > routine. At the moment I don't see a solution for this problem. > Overall, it's probably a dead end. > A solution (sort of) is in line with the famous quite of David Wheeler - to turn todo lists from bit maps into arrays of abscesses-or-ordinates of contact points. The cost is a memory footprint - 4x bigger than the previous version, 32 times bigger than above-mentioned "packed" variant of the previous version. But in BigO sense it's the same. In my tests it reduced the worst case time from O(max(A,B)**3) to O(A*B*log(max(A,B)). Which is non-ideal, but probably acceptable, because the bad cases should be very rare in practice. The real trouble is different - I don't know if my "worst case" is really the worst. The code below is for presentation of algorithm in both clear and compact manner, with emphasis on symmetry between x and y directions. It is not optimal in any sense and can be made no-trivially faster both by algorithm enhancements an by specialization of critical loops. #include #include typedef unsigned char Color; enum coordinate_axes { x_i = 0, y_i, // index of pos[], ld[], 1st index of limits[][], todo[][] }; enum from_to { from_i = 0, to_i // 2nd index of limits[][], todo[][], I use 0 and 1 more commonly }; enum { // indices of todo[] lists le_i = x_i*2+from_i, ri_i = x_i*2+to_i, up_i = y_i*2+from_i, dn_i = y_i*2+to_i, }; #define IDX2INC(ft_idx) ((int)(ft_idx)*2 - 1) #define X2Y(axis) ((axis) ^ 1) typedef struct { Color* image; Color old_color, new_color; ptrdiff_t ld[2]; // {1, width} int limits[2][2]; // {{0, width-1}, {0, height-1} } floodfill4_param; typedef struct { int *todo[4]; // {left,right, up, down} - first item holds the # of active entries int limits[2][2]; // {{x0, x1}, {y0, y1}}; int pos[2]; // {x, y} } floodfill4_state; static void floodfill4_core( const floodfill4_param* prm, const floodfill4_state* arg); static _Bool floodfill4_expand( const floodfill4_param* prm, floodfill4_state* s, enum coordinate_axes axis, enum from_to ft_idx); int floodfill4( Color* image, int width, int height, int x, int y, Color old_color, Color new_color) { if (width <= 0 || height <= 0) return 0; if (x < 0 || x >= width || y < 0 || y >= height) return 0; if (image[(size_t)width*y+x] != old_color) return 0; int lr_todo[2][height+1]; int ud_todo[2][width+1]; floodfill4_param prm = { .image = image, .ld[x_i] = 1, .ld[y_i] = width, .limits = {{ 0, width-1}, {0, height-1}}, .old_color = old_color, .new_color = new_color, }; floodfill4_state s = { .todo[le_i] = lr_todo[0], .todo[ri_i] = lr_todo[1], .todo[up_i] = ud_todo[0], .todo[dn_i] = ud_todo[1], .limits[x_i] = {x, x}, .limits[y_i] = {y, y}, .pos[x_i] = x, .pos[y_i] = y, }; for (int i = 0; i < 4; ++i) *s.todo[i] = 0; // process central 1x1 rectangle floodfill4_core(&prm, &s); // expansion loop for (unsigned idx = 0; idx < 4;) { if (floodfill4_expand(&prm, &s, idx/2, idx % 2)) { // try to expand idx = 0; // expansion succeed - restart from beginning continue; } ++idx; } ========== REMAINDER OF ARTICLE TRUNCATED ==========