<div dir="ltr"><div dir="ltr"><font face="monospace">On Oct 11, 2023 at 2:42 AM Rob Landley <rob at <a href="http://landley.net">landley.net</a>> wrote:<br>> On 10/10/23 17:46, Ray Gardner wrote:<br>> > After seeing your comments about tsort in your blog, I thought about trying<br>> > to implement Knuth's algorithm,<br>> <br>> Is that the recommended algorithm here?<br></font><span style="font-family:monospace"><br></span></div><div dir="ltr"><span style="font-family:monospace"><a href="https://man.openbsd.org/tsort">https://man.openbsd.org/tsort</a> mentions Knuth's TAOCP Vol 1, and under</span><font face="monospace"><br></font></div><font face="monospace">"History" says: "This tsort command was completely rewritten by Marc Espie for<br>OpenBSD, to finally use the well-known optimal algorithms for topological<br>sorting." So I think that's a reasonable guess. Not sure why it says<br>algorithms (plural), TAOCP has only one. (That's also the most informative</font><div><font face="monospace">tsort man page I've seen.)<br></font><div dir="ltr"><font face="monospace"><br></font></div><div dir="ltr"><span style="font-family:monospace">Taking your response out of order a bit:</span><br></div><div dir="ltr"><br><font face="monospace">> > I can post here about how I tested, if you're interested.</font><br><font face="monospace">> </font><br><font face="monospace">> How you tested what? That it's shorter? ...</font><br><br><font face="monospace">How I tested that your tsort measures roughly O(N^2). And that it did </font>a correct<br><font face="monospace">sort, for the cases I tested.</font><br><br><font face="monospace">> (I might still be just a little bit cheesed about this. </font>Normal<font face="monospace"> I vent the above</font><br><font face="monospace">> sort of thing into the blog instead of here, but you asked. :)</font><br><br><font face="monospace">I don't recall asking. I only mentioned Knuth because you were talking about</font><br><font face="monospace">implementing tsort on your blog and I thought I might try to do it myself, to</font><br><font face="monospace">see if I could come up with anything useful. I put it aside when you got yours</font><br><font face="monospace">working. I mentioned the N^2 thing because you mentioned O(N^2) in your Sept 7</font><br><font face="monospace">blog so I thought you were hoping to avoid it.</font><br><br><font face="monospace">> How big an input have you fed it? Being N^2 over 10 elements is fine by me.</font><br><font face="monospace">...</font><br><font face="monospace">> up to a million A->B pairs. ...</font><br><br><font face="monospace">I had to </font>use pretty<font face="monospace"> large input to see the N^2 effect. I used 100,000,</font><br><font face="monospace">200,000, and 400,000 pairs, seeing that doubling the input quadrupled the time.</font><br><font face="monospace">I'm not trying to criticize; your tsort is quite small and I'm sure a </font><br><font face="monospace">Knuth-based algo would be lots longer. Just thought you'd like to know.</font><br><font face="monospace">The Knuth algo is roughly linear time.</font><br><br><font face="monospace">GNU tsort took (on 400,000 pairs):</font><br><font face="monospace">real    0m1.362s user    0m0.469s sys     0m0.048s </font><br><font face="monospace">Your tsort takes </font><br><font face="monospace">real    0m50.051s user    0m50.027s sys     0m0.011s</font><br><br><font face="monospace">On 1,000,000 pairs, GNU tsort takes 3.458s, yours takes 7m29.647s (real).</font><br><br><font face="monospace">> But sure, if you've got an easily explicable better algorithm I'm all ears.</font><br><br><font face="monospace">I was really not trying to make a big deal about the algo or the run time! I</font><br><font face="monospace">just thought you might find it interesting. And I can still take a shot at a</font></div><div dir="ltr"><font face="monospace">Knuth-</font><font face="monospace">based version if you're interested.</font><br><br><font face="monospace">What my post was trying to do was suggest what I thought was a clearer</font><br><font face="monospace">way to handle the "search the second element of array by first element of key"</font><br><font face="monospace">thing without resorting to a "trick".</font><br><br><font face="monospace">> Yes, I considered declaring "char *sadness[3], **keep = sadness+1" but the</font><br><font face="monospace">> reason I _didn't_ is the compiler is WRONG.</font><br><br><font face="monospace">At the risk of annoying you further, I'll mention that forcing a pointer to</font><br><font face="monospace">point below the base of an array is undefined behavior, and has been</font><br><font face="monospace">since ANSI C89. Even if it's not dereferenced. Modern compilers can do weird</font><br><font face="monospace">things with UB, as you know.</font><br><br><font face="monospace">Of course the LP64 trick works. I like the sadness thing better, but I think</font><br><font face="monospace">the additional </font>keepfake<font face="monospace">[] array is better yet, because IMO it's clearer, and</font><br><font face="monospace">with the **keep=sadness+1 you have to change all the sizeof(keep) instances.</font><br><font face="monospace">So I just tossed that out there to see if you had considered it to avoid the</font><br><font face="monospace">"trick".</font><br><br><font face="monospace">Ray</font></div></div></div>