Path: ...!feeds.phibee-telecom.net!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Malcolm McLean <malcolm.arthur.mclean@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Mon, 18 Mar 2024 09:26:12 +0000
Organization: A noiseless patient Spider
Lines: 78
Message-ID: <ut91bm$3m2q$1@dont-email.me>
References: <ut3669$21eur$1@i2pn2.org> <ut4020$2s8ov$1@dont-email.me>
 <ut4b09$2uhpm$1@dont-email.me> <ut4cnc$2ut2t$1@dont-email.me>
 <ut76ms$3kal7$1@dont-email.me> <ut7co3$3lmeo$1@dont-email.me>
 <ut8on5$200c$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 18 Mar 2024 09:26:14 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="0909a5289999e8e117f7896cdedb74a6";
	logging-data="120922"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+Dvtm0zIau3BeOeYh2T3ij9rBekTJmXUQ="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:hBApdVdImlJOpSgGRYhMqQQ3tbc=
Content-Language: en-GB
In-Reply-To: <ut8on5$200c$1@dont-email.me>
Bytes: 5094

On 18/03/2024 06:58, David Brown wrote:
> On 17/03/2024 19:28, Malcolm McLean wrote:
>> On 17/03/2024 16:45, David Brown wrote:
>>> On 16/03/2024 16:09, Malcolm McLean wrote:
>>>>
>>> The OP's code is simple and obvious, as is its correctness (assuming 
>>> reasonable definitions of the pixel access and setting functions) and 
>>> its time and space requirements.  Yours is not.
>>>
>> Except it is not. You didn't give the right answer for the space 
>> requirements.
> 
> Unfortunately, I am still fallible - /easier/ does not mean I'll get it 
> right :-(  And I apologise for unhelpfully rushing that and getting it 
> wrong.
> 
> However, I stand by my claim that the recursive version is much easier 
> to analyse.
> 
I this case it s very short code and easy to see that it is right, so a 
win for recursion. Except that it is only right if the stack is bigger 
than N/2 calls deep, where N is the number fo pixels in the image. Now a 
100x100 woked fine an my machine  - I just checked the main stack, and 
it's 8MB by default. BUt of cuuurse the bigger than machine, the bigger 
the image th euser might want to load.


>> It's better to have one function. Subroutines have a way of getting 
>> lost.>
> 
> Seriously?  "Subroutines get lost" ?  So your answer is to put all your 
> ideas in a mixer and scrunch them up until any semblance of logic and 
> structure is lost, and the code works (if it does) by trial and error? 
> And then the whole mess is cut-and-paste duplicated - along with any 
> subtle bugs it might have - for 8-connected version.  And that's better, 
> in your eyes, than re-using code?
> 
Exactly. If a routine ia leaf, you can cut and paste it and use it where 
you will. If you have to take subroutines, you've got to explore the 
code to understand what you neeed to take, then you have to out them 
somewhere. So it's better to keep routines leaf is possible and fold a 
few trivial operations into the code body, even if ideally they would be 
subroutines. And I understand these trade offs. >
> I have been most interested in being able to be sure the algorithm is 
> correct, rather than considering its absolute (rather than "big O") 
> efficiency in different systems.  It is certainly the case that cache 
> considerations are more relevant now than they used to be on many 
> systems.  And for working on PC's, you would likely dispense with your 
> growing stack entirely and simply allocate a queue big enough for every 
> pixel in the image.
> 
That is an idea. But a bit extravanagant. I'd like to try to work out 
how much quue s actually used in typical as well as worst case.
 >
> I suggested separating the code into functions - that is /definitely/ 
> constructive.  I suggested using sensible names for parameters and 
> variables (well, the suggestion was implied by my criticism).
> 
> And I am also suggesting now that you allocate a queue that is big 
> enough for every pixel in the image.  Much of what you don't touch of 
> that space, will probably never be physically allocated by the OS, 
> depending on page sizes and free memory.
> 
> And I would also suggest you drop the requirement for coding in an 
> ancient tongue, and instead switch to reasonably modern C.  Make 
> abstractions for the types and the access functions - it will make the 
> code far easier to follow, easier to show correct, and easier to modify 
> and reuse, without affecting efficiency at run-time.
> 
> 
And of course the entire binary image library has a consistent style. 
And we don't want the user mee=ssing about with writing his own getpixel 
/ setpixel functions, thouhg there would be a case for that for a 
geneeral purpose flood fill.
-- 
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm