computer science

I checked the effect of list element size on my implementation of mergesort of a linked list.

It occurred to me that benchmarking traversing very long linked lists end-to-end might provide some clues.

Based on the effects of linked list re-use, I checked if using a linked list with in-memory-address-order made a difference.

After I wrote a recursive merge sort, I reviewed it to ensure it wasn’t doing extra work. From that perspective, I noticed that for each of the 10 list sorts my benchmark program made for a given length linked list, it created a new linked list.

I thought that I could make the overall benchmark run faster by not creating a new, very large, linked list for every run, but rather re-using the existing list. I hoped to have the benchmark program use less time between the ten measured sort algorithm executions, not make the sorting faster. I surprised myself by getting the opposite effect.

I wrote a traditional, top-down, recursive merge sort. The idea was to see if a different implementation exhibited the same dramatic, abrupt slowdowns. If the different implementation showed the same jumps in timings, the problem is with the operating system, the language run time, or the memory hardware. I know I said I’d ruled out the underlying operating system previously, but I was still suspicious.

My July 2021 mergesort program, as the subject of an investigation, deserves some explanation.

One coding problem I encountered was to do a merge sort of a linked list. I wrote a merge sort in Go, but when I tried to verify it via timing sorting large linked lists, I got some strange behavior

Once upon a time, I wrote four programs that can play a game called squava with lesser or greater amounts of skill.

All four algorithmic players can win against each other, although there are definite differences in apparent skill. I wanted to know what their Elo rating might be.

I falsely believed that I had found a wordle state where an elaborate regular expression with alternations gives fewer possible answers than a simple regexp in a pipeline with extra greps.

I was wrong.