Sorting things out

[The Beez]

Hi 4tH-ers!

You know I got something with pseudorandom algorithms and sorting algorithms. So, for a long time I wondered "what about an algorithm that is optimized to sort an almost sorted list"?

I mean - it happens often. You just made some minute changes and the whole thing is turned upside down because of some overly aggressive algorithm.

So I looked at the "in place merge sort" which (in theory) merges two datasets with little overhead. Let's examine a thing like:

  128967 (data)

  012345 (address)

Now, that algorithm want you to give:

1. the address of the left most element of the list to merge with;
2. the address of the left most element of the list to merge;
3. the address of the right most element of the list to merge.

In this case, that would be: 0, 4, 5

It would run like: 1-6, 1-7, 2-6, 2-7, 8-6 => SWITCH!!

Now, the list turns to 126987 - which would go haywire in a minute, because the algorithm expects BOTH sides to be sorted. So, what we have to end up with is:

  126978 (data)

  012345 (address)

Of course, 9-7 triggers another switch, which ultimately results in 126789. Job done. Now, for one reason or another, I could get the standard "in place merge sort" to work, so I designed my own. In one version 4tH moves the data in the rightmost part, in the slightly optimized version SMOVE does the moving. However, the difference is not dramatic..

As usual, code in SVN.

BTW, I'm benchmarking the slowest sorting routines. The comparisons are more accurate now - it doesn't mean they've actually become slower. It's means I'm less lazy ;-)

Hans Bezemer

[David Meyer]

Hello Hans and fellow 4tH-ers.

I was installing 4tH on a Linux system and noticed that the notes in the 4tH manual section 3.1.4.2 /etc/magic related to 64-bit operating systems do not go into much detail.

The /etc/magic lines for a 64-bit system are indeed different from the ones shown in the manual. The following lines are what works on my Linux kernel 6.1.0-30-amd64 system and another Linux 6.1.0-22-amd64 system where I double-checked:

0       belong      0x01020800       4tH eXecutable

>0x0d   leshort x   \b, version %x

It is maybe not a feature that many users care about, but since 64-bit systems are now the norm, it might be worth an update the next time the manual is revised.

-- 

David Meyer

Takarazuka, Japan

pa...@sdf.org

[The Beez]

Hi David!

Thank you for your remark! I have tested it straight away - and I can confirm it works:

~/4th$ file cassini.hx
cassini.hx: 4tH 64bit eXecutable, version 364

So I've added it to the manual. It will be in the next version, I can assure you:

LyX Document 0.0.0.1 /etc/magic

If you want Linux to recognize your 4tH files, you have to add the following lines to your /etc/magic file:

# From The.Bee...@gmail.com

# These are the magic numbers for 4tH HX files

 

0       belong          0x01020400      4tH 32bit eXecutable

>9      leshort x       \b, version %x

0       belong          0x01020800      4tH 64bit eXecutable

>0x0d   leshort x       \b, version %x

So, thanks again! It's been added!

Hans Bezemer

[The Beez]

BTW, for those interested, here is the test program for the algorithm.

Hans Bezemer