On Tue, Nov 7, 2023 at 11:19 AM Rob Landley wrote:
>
> On 11/6/23 09:39, enh wrote:
> >> P.S. Yes I checked if posix/libc just had one I could use, like with
> >> qsort(),
> >> but man 3 hash says "This page documents interfaces provided in glibc up
> >> until
> >> version 2.1. Since version
On Sun, Nov 5, 2023 at 9:50 PM Rob Landley wrote:
>
> On 11/5/23 21:22, Ray Gardner wrote:
> > On 11/3/23 12:36:30, Rob Landley wrote:
> >> > As to the hash code, the only part I've taken from Python's
> >> > implementation is the probe sequence
> >>
> >> So... NOT the "linked lists descending
On 11/5/23 21:24, Ray Gardner wrote:
> On 11/3/23 12:36:30, Rob Landley wrote:
> ...
>> > One other thing: In an earlier post to the list, I pondered that I'd
>> > need to do something about duplicate input pairs to tsort. Knuth's
>> > approach doesn't need to be concerned about that, the
On 11/5/23 21:22, Ray Gardner wrote:
> On 11/3/23 12:36:30, Rob Landley wrote:
>> > As to the hash code, the only part I've taken from Python's
>> > implementation is the probe sequence
>>
>> So... NOT the "linked lists descending from each hash bucket" approach
>> then.
>>
>> > probe = (probe * 5
On 11/3/23 12:36:30, Rob Landley wrote:
...
> > One other thing: In an earlier post to the list, I pondered that I'd
> > need to do something about duplicate input pairs to tsort. Knuth's
> > approach doesn't need to be concerned about that, the duplicates sorta
> > come out in the wash.
>
> //
On 11/3/23 12:36:30, Rob Landley wrote:
> > As to the hash code, the only part I've taken from Python's
> > implementation is the probe sequence
>
> So... NOT the "linked lists descending from each hash bucket" approach
> then.
>
> > probe = (probe * 5 + 1 + (perturb >>= 5)) & hashmask
> > where
ut
stream, it's not deal but I'm ok wasting that much space on something a given
command should only have 2 or 3 of tops.)
> The remark about seekable input is not for toybox; I used your tsort
> code with readfd() which can handle input from terminal, pipe etc. and
> grows the buffer a
I wasn't going to write this, but I couldn't help myself. Had to see how
it would turn out.
This version passes the current tests/tsort.test. It also correctly prints
a loop, e.g. if the input is:
a b
b c
c a
c d
d e
it prints:
tsort: input contains a loop:
a ->
b ->
c ->
a
Note that c -> d
In the blog, Rob said
> I MOSTLY don't care because I don't know of a use case that big (he
> didn't send the test data, nor say how he created it)
I did say
> I can post here about how I tested, if you're interested.
No one said they were interested, so this will probably be my last attempt
to
> The topic at hand is whether I should redo it based on a different
> algorithm for better scalability up in the hundreds of thousands of
> entries range. (Answer: probably yes, the numbers seem convincing. I have
> to hack through a lot of math-speak from a book first published in 1968 to
>
On 10/11/23 15:57, scsijon wrote:
> I knew it from ibm mainframes and FEP's for aix, try this url for a
> simple explanation, it's pretty basic what it does.
>
> https://www.ibm.com/docs/da/aix/7.3?topic=t-tsort-command
I know what it does _now_. I wrote one from scratch that works.
The topic
On Thu, Oct 12, 2023 at 12:57 AM Rob Landley wrote:
>
> On 10/11/23 11:07, enh wrote:
> >> It's not HARD, I just consider the compiler's behavior to be obviously
> >> wrong
> >> here. My code never performs an illegal dereference. I don't see why the
> >> compiler should care what pointer values
On 10/11/23 11:07, enh wrote:
>> It's not HARD, I just consider the compiler's behavior to be obviously wrong
>> here. My code never performs an illegal dereference. I don't see why the
>> compiler should care what pointer values I'm passing around when they're not
>> being dereferenced: in C,
On Wed, Oct 11, 2023 at 2:26 PM Ray Gardner wrote:
>
> On Oct 11, 2023 at 2:42 AM Rob Landley wrote:
> > On 10/10/23 17:46, Ray Gardner wrote:
> > > After seeing your comments about tsort in your blog, I thought about
> > > trying
> > > to implement Knuth's algorithm,
> >
> > Is that the
On Oct 11, 2023 at 2:42 AM Rob Landley wrote:
> On 10/10/23 17:46, Ray Gardner wrote:
> > After seeing your comments about tsort in your blog, I thought about
trying
> > to implement Knuth's algorithm,
>
> Is that the recommended algorithm here?
https://man.openbsd.org/tsort mentions Knuth's
I knew it from ibm mainframes and FEP's for aix, try this url for a
simple explanation, it's pretty basic what it does.
https://www.ibm.com/docs/da/aix/7.3?topic=t-tsort-command
scsijon
___
Toybox mailing list
Toybox@lists.landley.net
On Wed, Oct 11, 2023 at 1:42 AM Rob Landley wrote:
>
> On 10/10/23 17:46, Ray Gardner wrote:
> > After seeing your comments about tsort in your blog, I thought about trying
> > to
> > implement Knuth's algorithm,
>
> Is that the recommended algorithm here?
>
> $ grep -i knuth
On 10/10/23 17:46, Ray Gardner wrote:
> After seeing your comments about tsort in your blog, I thought about trying to
> implement Knuth's algorithm,
Is that the recommended algorithm here?
$ grep -i knuth busybox/coreutils/tsort.c
$ grep -ir knuth busybox
After seeing your comments about tsort in your blog, I thought about trying
to implement Knuth's algorithm, but after I saw how far you'd got with your
version I decided not to for now. I haven't analyzed your version
carefully. It seems to be O(N^2) due to all the work to close up the list
with
19 matches
Mail list logo
