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

On Wed, 10 Apr 2024 19:47:11 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:
 

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. 

 
Before I do anything else I should correct a bug in my earlier
FIFO algorithm.  The initialization of the variable jx should
read
 
    Index const jx =  used*3 < open  ? k  : j+open/3 &m;
>

I lost track, sorry. I can not find your code that contains line
similar to this.
Can you point to specific post?

rather than what it used to.  (The type may have changed but that
is incidental;  what matters is the value of the initializing
expression.)  I don't know what I was thinking when I wrote the
previous version, it's just completely wrong.
 

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. 

 
I agree, the empirical evidence here and in my own tests is quite
compelling.
>

BTW, I am no longer agree with myself about "the rest of them".
By now, I know at least one method that is O(W*log(H)). It is even
quite fast for majority of my test shapes. Unfortunately, [in its
current form] it is abysmally slow (100x) for minority of tests.
[In it's current form] it has other disadvantages as well like
consuming non-trivial amount of memory when handling small spot in the
big image. But that can be improved. I am less sure that worst-case
speed can be improved enough to make it generally acceptable.

I think, I said enough for you to figure out a general principle of
this algorithm. I don't want to post code here before I try few
improvements.

That said, the constant factor for the FIFO algorithm is lower
than the stack-based algorithms, even taking into account the
difference in sizes for queue and stack elements.  Moreover cases
where FIFO algorithms are O( NxN ) are unusual and sparse,
whereas the stack-based algorithms tend to use a lot of memory
in lots of common and routine cases.  On the average FIFO
algorithms typically use a lot less memory (or so I conjecture).
 

[code to generate fractal tree pattern] 

 
Thank you for this.  I incorporated it into my set of test
patterns more or less as soon as it was posted.
 
Now that I have taken some time to play around with different
algorithms and have been more systematic in doing speed
comparisons between different algorithms, on different patterns,
and with a good range of sizes, I have some general thoughts
to offer.
 
Stack-based methods tend to do well on long skinny patterns and
tend to do not as well on fatter patterns such as circles or
squares.  The fractal pattern is ideal for a stack-based method.
Conversely, patterns that are mostly solid shapes don't fare as
well under stack-based methods, at least not the ones that have
been posted in this thread, and also they tend to use more memory
in those cases.
>

Indeed, with solid shapes it uses more memory. But at least in my tests
on my hardware with this sort of shapes it is easily faster than
anything else. The difference vs the best of the rest is especially big
at 4K images on AMD Zen3 based hardware, but even on Intel Skylake which
generally serves as equalizer between different algorithms, the speed
advantage of 2x2 stack is significant.

I've been playing around with a more elaborate, mostly FIFO
method, in hopes of getting something that offers the best
of both worlds.  The results so far are encouraging, but a
fair amount of tuning has been necessary (and perhaps more
still is), and comparisons have been done on just the one
test server I have available.  So I don't know how well it
would hold up on other hardware, including especially more
recent hardware.  Under these circumstances I feel it is
premature to post actual code, especially since the code
is still in flux.
 
This topic has been more interesting that I was expecting, and
also more challenging.

That's not the first time in my practice where problems with simple
formulation begots interesting challenges.
Didn't Donald Knuth wrote 300 or 400 pages about sorting and still
ended up quite far away from exhausting the topic?

I have a strong rule against writing
functions more than about 60 lines long.  For the problem of
writing an acceptably quick flood-fill algorithm, I think it would
at the very least be a lot of work to write code to do that while
still observing a limit on function length of even 100 lines, let
alone 60.

So why not break it down to smaller pieces ?
Myself, I have no rules. In my real work I am quite happy with
dispatchers of network messages that are 250-300 lines long. But if I
had this sort of rules, I'd certainly decompose.