Re: filling area by color atack safety - worst memory size

Liste des GroupesRevenir à cl c 
Sujet : Re: filling area by color atack safety - worst memory size
De : already5chosen (at) *nospam* yahoo.com (Michael S)
Groupes : comp.lang.c
Date : 05. Apr 2024, 16:30:33
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <20240405173033.00006145@yahoo.com>
References : 1 2 3 4 5 6 7 8 9
User-Agent : Claws Mail 4.1.1 (GTK 3.24.34; x86_64-w64-mingw32)
On Sun, 24 Mar 2024 10:24:45 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:
 
On Wed, 20 Mar 2024 10:01:10 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
 
Michael S <already5chosen@yahoo.com> writes: 
 
[...]
 
Generally, I like your algorithm.
It was surprising for me that queue can work better than stack, my
intuition suggested otherwise, but facts are facts. 
>
Using a stack is like a depth-first search, and a queue is like a
breadth-first search.  For a pixel field of size N x N, doing a
depth-first search can lead to memory usage of order N**2,
whereas a breadth-first search has a "frontier" at most O(N).
Another way to think of it is that breadth-first gets rid of
visited nodes as fast as it can, but depth-first keeps them
around for a long time when everything is reachable from anywhere
(as will be the case in large simple reasons). 
>
For my test cases the FIFO depth of your algorithm never exceeds
min(width,height)*2+2.  I wonder if existence of this or similar
limit can be proven theoretically. 
 
I believe it is possible to prove the strict FIFO algorithm is
O(N) for an N x N pixel field, but I haven't tried to do so in
any rigorous way, nor do I know what the constant is.  It does
seem to be larger than 2.
>

It seems that in worst case the strict FIFO algorithm is the same as
the rest of them, i.e. O(NN) where NN is the number of re-colored
points. Below is an example of the shape for which I measured memory
consumption for 3840x2160 image almost exactly 4x as much as for
1920x1080.

static void make_fractal_tree_recursive(
  unsigned char* image,
  int            width,
  int            nx,
  int            ny,
  unsigned char  pen_c)
{
  if (nx < 3 && ny < 3) {
    // small rectangle - solid fill
    for (int y = 0; y < ny; ++y)
      for (int x = 0; x < nx; ++x)
        image[width*y+x] = pen_c;
    return;
  }
  if (nx >= ny) {
    int xc = (nx-1)/2;
    if (xc - 1 > 0) { // left sub-plot
      make_fractal_tree_recursive(image, width, xc - 1, ny, pen_c);
    }
    if (xc + 2 < nx) { // right sub-plot
      make_fractal_tree_recursive(&image[xc+2], width,
        nx - (xc + 2), ny, pen_c);
    }
    // draw vertical cross
    for (int y = 0; y < ny; ++y)
      image[width*y+xc] = pen_c;
    int yc = (ny-1)/2;
    image[width*yc+xc-1] = pen_c;
    image[width*yc+xc+1] = pen_c;
  } else {
    int yc = (ny-1)/2;
    if (yc - 1 > 0) { // upper sub-plot
      make_fractal_tree_recursive(image, width, nx, yc - 1, pen_c);
    }
    if (yc + 2 < ny) { // lower sub-plot
      make_fractal_tree_recursive(&image[(yc+2)*width], width, nx,
          ny -(yc + 2), pen_c);
    }
    // draw horizontal cross
    for (int x = 0; x < nx; ++x)
      image[width*yc+x] = pen_c;
    int xc = (nx-1)/2;
    image[width*(yc-1)+xc] = pen_c;
    image[width*(yc+1)+xc] = pen_c;
  }
}

static void make_fractal_tree(
  unsigned char* image,
  int            width,
  int            height,
  unsigned char  background_c,
  unsigned char  pen_c)
{
  memset(image, background_c, width*height);
  make_fractal_tree_recursive(image, width, width, height, pen_c);
}



Date Sujet#  Auteur
16 Mar 24 * filling area by color atack safety163fir
16 Mar 24 +* Re: filling area by color atack safety86Malcolm McLean
16 Mar 24 i+* Re: filling area by color atack safety25Ben Bacarisse
16 Mar 24 ii+* Re: filling area by color atack safety11bart
17 Mar 24 iii+- Re: filling area by color atack safety1Ben Bacarisse
18 Mar 24 iii+* Re: filling area by color atack safety8Tim Rentsch
18 Mar 24 iiii`* Re: filling area by color atack safety7Michael S
18 Mar 24 iiii +- Re: filling area by color atack safety1Tim Rentsch
19 Mar 24 iiii `* Re: filling area by color atack safety5fir
19 Mar 24 iiii  `* Re: filling area by color atack safety4bart
19 Mar 24 iiii   +- Re: filling area by color atack safety1bart
20 Mar 24 iiii   +- Re: filling area by color atack safety1fir
20 Mar 24 iiii   `- Re: filling area by color atack safety1David Brown
18 Mar 24 iii`- Re: filling area by color atack safety1Tim Rentsch
16 Mar 24 ii`* Re: filling area by color atack safety13Malcolm McLean
16 Mar 24 ii +* Re: filling area by color atack safety5Malcolm McLean
16 Mar 24 ii i+* Re: filling area by color atack safety3Chris M. Thomasson
17 Mar 24 ii ii`* Re: filling area by color atack safety2Chris M. Thomasson
18 Mar 24 ii ii `- Re: filling area by color atack safety1Michael S
20 Mar 24 ii i`- Re: filling area by color atack safety1fir
17 Mar 24 ii +* Re: filling area by color atack safety6Ben Bacarisse
17 Mar 24 ii i`* Re: filling area by color atack safety5Malcolm McLean
17 Mar 24 ii i +- Re: filling area by color atack safety1Kaz Kylheku
23 Mar 24 ii i +- Re: filling area by color atack safety1Ben Bacarisse
23 Mar 24 ii i `* Re: filling area by color atack safety2Tim Rentsch
29 Mar 24 ii i  `- Re: filling area by color atack safety1Tim Rentsch
17 Mar 24 ii `- Re: filling area by color atack safety1Michael S
16 Mar 24 i+* Re: filling area by color atack safety38David Brown
16 Mar 24 ii+* Re: filling area by color atack safety31Malcolm McLean
17 Mar 24 iii+* Re: filling area by color atack safety16Malcolm McLean
17 Mar 24 iiii+- Re: filling area by color atack safety1Michael S
17 Mar 24 iiii+* Re: filling area by color atack safety13Michael S
17 Mar 24 iiiii+* Re: filling area by color atack safety5Michael S
18 Mar 24 iiiiii`* Re: filling area by color atack safety4Tim Rentsch
18 Mar 24 iiiiii `* Re: filling area by color atack safety3Malcolm McLean
19 Mar 24 iiiiii  `* Re: filling area by color atack safety2Tim Rentsch
19 Mar 24 iiiiii   `- Re: filling area by color atack safety1Malcolm McLean
20 Mar 24 iiiii`* Re: filling area by color atack safety7fir
20 Mar 24 iiiii `* Re: filling area by color atack safety6Michael S
20 Mar 24 iiiii  `* Re: filling area by color atack safety5fir
20 Mar 24 iiiii   `* Re: filling area by color atack safety4Michael S
20 Mar 24 iiiii    `* Re: filling area by color atack safety3fir
20 Mar 24 iiiii     `* Re: filling area by color atack safety2Michael S
20 Mar 24 iiiii      `- Re: filling area by color atack safety1fir
20 Mar 24 iiii`- Re: filling area by color atack safety1fir
17 Mar 24 iii`* Re: filling area by color atack safety14David Brown
17 Mar 24 iii `* Re: filling area by color atack safety13Malcolm McLean
18 Mar 24 iii  `* Re: filling area by color atack safety12David Brown
18 Mar 24 iii   `* Re: filling area by color atack safety11Malcolm McLean
18 Mar 24 iii    `* Re: filling area by color atack safety10David Brown
18 Mar 24 iii     `* Re: filling area by color atack safety9Malcolm McLean
18 Mar 24 iii      +* Re: filling area by color atack safety3Keith Thompson
19 Mar 24 iii      i+- Keith-world (Was: filling area by color atack safety)1Kenny McCormack
19 Mar 24 iii      i`- Re: filling area by color atack safety1David Brown
18 Mar 24 iii      +- Re: filling area by color atack safety1bart
19 Mar 24 iii      +- Re: filling area by color atack safety1Chris M. Thomasson
19 Mar 24 iii      +- Re: filling area by color atack safety1David Brown
19 Mar 24 iii      `* Re: filling area by color atack safety2David Brown
19 Mar 24 iii       `- Re: filling area by color atack safety1Richard Harnden
17 Mar 24 ii+* Re: filling area by color atack safety4Ben Bacarisse
17 Mar 24 iii+* Re: filling area by color atack safety2Malcolm McLean
17 Mar 24 iiii`- Re: filling area by color atack safety1bart
17 Mar 24 iii`- Re: filling area by color atack safety1David Brown
20 Mar 24 ii`* Re: filling area by color atack safety2fir
20 Mar 24 ii `- Re: filling area by color atack safety1fir
17 Mar 24 i+* Re: filling area by color atack safety18Michael S
17 Mar 24 ii+* Re: filling area by color atack safety9bart
17 Mar 24 iii`* Re: filling area by color atack safety8Michael S
17 Mar 24 iii `* Re: filling area by color atack safety7bart
17 Mar 24 iii  +* Re: filling area by color atack safety2Michael S
17 Mar 24 iii  i`- Re: filling area by color atack safety1David Brown
17 Mar 24 iii  `* Re: filling area by color atack safety4Ben Bacarisse
17 Mar 24 iii   `* Re: filling area by color atack safety3Spiros Bousbouras
18 Mar 24 iii    `* Re: filling area by color atack safety2Ben Bacarisse
18 Mar 24 iii     `- Re: filling area by color atack safety1bart
18 Mar 24 ii+* Re: filling area by color atack safety5Tim Rentsch
18 Mar 24 iii`* Re: filling area by color atack safety4Malcolm McLean
19 Mar 24 iii `* Re: filling area by color atack safety3Tim Rentsch
19 Mar 24 iii  `* Re: filling area by color atack safety2Malcolm McLean
20 Mar 24 iii   `- Re: filling area by color atack safety1Tim Rentsch
20 Mar 24 ii`* Re: filling area by color atack safety3fir
20 Mar 24 ii `* Re: filling area by color atack safety2Michael S
20 Mar 24 ii  `- Re: filling area by color atack safety1fir
17 Mar 24 i`* Re: filling area by color atack safety4Lew Pitcher
17 Mar 24 i +- Re: filling area by color atack safety1bart
19 Mar 24 i `* Re: filling area by color atack safety2Peter 'Shaggy' Haywood
20 Mar 24 i  `- Re: filling area by color atack safety1fir
16 Mar 24 +* Re: filling area by color atack safety8bart
16 Mar 24 i+* Re: filling area by color atack safety2bart
16 Mar 24 ii`- Re: filling area by color atack safety1Malcolm McLean
20 Mar 24 i`* Re: filling area by color atack safety5fir
22 Mar 24 i `* Re: filling area by color atack safety4Peter 'Shaggy' Haywood
22 Mar 24 i  +* Re: filling area by color atack safety2Michael S
22 Mar 24 i  i`- Re: filling area by color atack safety1Michael S
23 Mar 24 i  `- Re: filling area by color atack safety1fir
17 Mar 24 +- Re: filling area by color atack safety1Peter 'Shaggy' Haywood
18 Mar 24 `* Re: filling area by color atack safety67Tim Rentsch
19 Mar 24  `* Re: filling area by color atack safety66Tim Rentsch
19 Mar 24   `* Re: filling area by color atack safety65Michael S
19 Mar 24    +* Re: filling area by color atack safety29Malcolm McLean
19 Mar 24    i+* Re: filling area by color atack safety4Michael S
19 Mar 24    i`* Re: filling area by color atack safety24Michael S
20 Mar 24    `* Re: filling area by color atack safety35Tim Rentsch

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal