Path: csiph.com!weretis.net!feeder8.news.weretis.net!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: Thu, 11 Apr 2024 21:55:22 -0700 Organization: A noiseless patient Spider Lines: 31 Message-ID: <86v84nyybp.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> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Fri, 12 Apr 2024 06:55:24 +0200 (CEST) Injection-Info: dont-email.me; posting-host="c97bd3546ab5d223656b076d0b7c627f"; logging-data="2297268"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19moMDjCjrwlHvtbE+WeaAxK5jSCzZWYEA=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:61eIOIzGZ9DRMfSWirfPMpH5dV0= sha1:8KnB/0oiNasFObOjneO4bWGVOM4= Xref: csiph.com comp.lang.c:384297 Michael S writes: > On Wed, 10 Apr 2024 19:47:11 -0700 > Tim Rentsch wrote: > >> Michael S writes: >>> 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. Thank you for the implied compliment. At this point I think the probability that I will figure it out anytime soon is pretty low.