Wat is er met Speeltuinzoeker gebeurd?

Geregeld krijg ik nog de vraag hoe het met mijn speeltuinen-website gaat. Het antwoord is: hij bestaat nog, maar eerlijk gezegd doe ik er weinig meer mee. Waarom dan? Het concept bleek toch niet zo aan te slaan als ik had gehoopt. Het was moeilijk om een “community” van ouders van de grond te krijgen die informatie over speeltuinen met elkaar gingen delen. Facebook-advertenties, in combinatie met winacties, zijn een goede manier om (tijdelijke) activiteit te genereren, maar zodra je ze stopzet, houdt dat ook op. Waarschijnlijk had ik er met heel veel tijd energie wel een levendige site van kunnen maken, maar die beide factoren zijn bij een vader van drie jonge kinderen, met een fulltime baan, niet bepaald voorradig. Het was in ieder geval een leerzame ervaring en ik heb de domeinnaam nog 🙂 De hosting vindt nu echter hier, op erikroos.org, plaats. Wie weet wordt Speeltuinzoeker nog eens (her)ontdekt en gaat het nog een grootse toekomst tegemoet!

Zie www.speeltuinzoeker.nl oftewel erikroos.org/speeltuinzoeker

Sorting algorithms III – 9 years later

And so I’m back! I haven’t been here for quite some time, and a lot has happened in the meantime. I’ve worked as a Customer Support Manager at Eezeebee (a small software company for fashion B2B’s and B2C’s) for quite some time, but recently I made a career change by becoming something I never thought I’d become (mostly because my father was one): a teacher! I’ve recently begun as an IT teacher at the Hanzehogeschool (University of Applied Sciences). It’s hard work but it’s fun and it’s rewarding. And it brought me back to that old passion o’mine: sorting algorithms 🙂 One of the courses I teach, together with the esteemed Bas Heijne, is Algorithms and Data Structures, wherein sorting is used as an example case for developing efficient algorithms. Reading back on what I wrote 9 years ago, it seems to me that the infamous H Sort is nothing more than Selection Sort (although the keeping-in-memory part could be a small improvement). But… the other day I thought of yet another sorting algorithm: Index Sort, or maybe Hash Sort. It has to do with storing items in an array using their value (or a hash of it) as the index. Theoretically, this could give you a Big O of N (N times O(1)). I’m still developing and testing it using good old Java, and the results seem promising, but I have no final results yet. So, again, stay tuned for more on Sorting!

Today I learned…

PHP has a nice library to work with zip archives: ZipArchive. However, you cannot open zip files that are hosted on some website. First you have to download the zip file, and then you can open it using ZipArchive. An example:

$file = 'http://www.somesite.com/file.zip';
file_put_contents('file.zip', fopen($file, 'r'));
$zip = new ZipArchive();
if ($zip->open('file.zip') === true) {
    for ($i = 0; $i < $zip->numFiles; $i++) { 
         $stat = $zip->statIndex($i);
         if (strpos($stat['name'], 'partoffilename') !== false) {
             $fileContents = $zip->getFromIndex($i);
             // Do something here...

Also note something interesting here: if you don’t know the exact name of the file inside the zip archive that you want to open, you cannot use getFromName(), so you have to take another approach. In the above example, I iterate through the files in the archive using an index, checking every file for the part of the filename that I do know. When there’s a match, I can use the current index and getFromIndex() to open the file.

Today I learned…

In PHP, if you sort -or better: do not sort- an array, using a custom function that happens to return 0 every time, the resulting order is undefined as opposed to the original order as you might expect.

So, if you do something like this and X is never set:

usort($arr_content['content']['results'], function($a, $b) {
    if (isset($a['X']) && isset($b['X'])) {
       if ($a['X'] == $b['X']) {
            return 0;
        if ($a['X'] < $b['X']) {
            return -1;
        return 1;
    if (isset($a['X'])) {
        return -1;
    if (isset($b['X'])) {
        return 1;
    return 0; // this is returned for every element since $a['X'] and $b['X'] are never set

you end up with an array that’s sorted in an unexpected way, in my case even perfectly reversed!

I had to work around this “feature” of PHP by checking the number of undefined X’es in the array and skipping the usort() of their number is equal to the number of elements in the array.

Sorting algorithms II

As posted a few days ago, I experimented a bit with a new sorting algorithm called H Sort. I built a simple testing framework in Java to see how well it performs compared to traditional Q Sort.

First I steadily increased the number of runs. I noticed that the average time it takes to do a sorting run decreases with the total number of runs. At first this seemed strange because the runs are unconnected, a new array of random numbers generated each run. Then I realized that this effect is probably due to more processing power and cores being allocated to the process when the number of runs increases. The average sorting times of the two algorithms begin to settle at 1,000 runs and become really stable at 100,000 runs.

  • Times: 100 Orderedness: 0% Size: 100 Average time Q: 99,32 micros Average time H: 152,88 micros Factor H vs. Q: 1,54
  • Times: 1000 Orderedness: 0% Size: 100 Average time Q: 9,40 micros Average time H: 37,18 micros Factor H vs. Q: 3,95
  • Times: 10000 Orderedness: 0% Size: 100 Average time Q: 8,92 micros Average time H: 35,15 micros Factor H vs. Q: 3,94
  • Times: 50000 Orderedness: 0% Size: 100 Average time Q: 8,81 micros Average time H: 33,52 micros Factor H vs. Q: 3,81
  • Times: 100000 Orderedness: 0% Size: 100 Average time Q: 8,72 micros Average time H: 32,94 micros Factor H vs. Q: 3,78
  • Times: 500000 Orderedness: 0% Size: 100 Average time Q: 8,87 micros Average time H: 33,52 micros Factor H vs. Q: 3,78
  • Times: 1000000 Orderedness: 0% Size: 100 Average time Q: 8,77 micros Average time H: 33,15 micros Factor H vs. Q: 3,78
Having found the optimal number of runs, I then varied the ‘orderedness’ of the generated sort lists. Orderedness corresponds to the chance that the number at index i is equal to i. If not, it is a random number. So an array with 0% orderedness is a completely random array, whereas one with 100% orderedness goes like 1, 2, 3, …, 100. I read that Q Sort doesn’t perform well on already quite ordered lists. I can verify that, except that when comparing to H Sort that moment is reached only around 98% orderedness, which is an almost completely ordered array. So no great advantage of H Sort so far…
  • Times: 100000 Orderedness: 0% Size: 100 Average time Q: 8,88 micros Average time H: 33,60 micros Factor H vs. Q: 3,78
  • Times: 100000 Orderedness: 10% Size: 100 Average time Q: 8,70 micros Average time H: 33,43 micros Factor H vs. Q: 3,84
  • Times: 100000 Orderedness: 20% Size: 100 Average time Q: 8,50 micros Average time H: 33,31 micros Factor H vs. Q: 3,92
  • Times: 100000 Orderedness: 30% Size: 100 Average time Q: 8,28 micros Average time H: 33,07 micros Factor H vs. Q: 4,00
  • Times: 100000 Orderedness: 40% Size: 100 Average time Q: 8,00 micros Average time H: 32,45 micros Factor H vs. Q: 4,05
  • Times: 100000 Orderedness: 50% Size: 100 Average time Q: 7,76 micros Average time H: 31,75 micros Factor H vs. Q: 4,09
  • Times: 100000 Orderedness: 60% Size: 100 Average time Q: 7,52 micros Average time H: 31,05 micros Factor H vs. Q: 4,13
  • Times: 100000 Orderedness: 70% Size: 100 Average time Q: 7,29 micros Average time H: 30,12 micros Factor H vs. Q: 4,13
  • Times: 100000 Orderedness: 80% Size: 100 Average time Q: 7,06 micros Average time H: 28,45 micros Factor H vs. Q: 4,03
  • Times: 100000 Orderedness: 90% Size: 100 Average time Q: 7,07 micros Average time H: 23,88 micros Factor H vs. Q: 3,38
  • Times: 100000 Orderedness: 95% Size: 100 Average time Q: 7,42 micros Average time H: 16,93 micros Factor H vs. Q: 2,28
  • Times: 100000 Orderedness: 98% Size: 100 Average time Q: 8,15 micros Average time H: 8,85 micros Factor H vs. Q: 1,09
  • Times: 100000 Orderedness: 99% Size: 100 Average time Q: 8,55 micros Average time H: 5,05 micros Factor H vs. Q: 0,59
  • Times: 100000 Orderedness: 100% Size: 100 Average time Q: 9,08 micros Average time H: 0,50 micros Factor H vs. Q: 0,06
Maybe better luck for H Sort when varying the array size? Indeed, H sort performs almost as well as Q Sort on arrays of size… 10. When increasing the array size, Q Sort quickly takes the lead. And then we run into the limitations of my Core i7 2.8 GHz laptop: sorting arrays of 10,000 numbers for 100,000 times took so much time I eventually gave up and killed the process.
  • Times: 100000 Orderedness: 50% Size: 10 Average time Q: 0,48 micros Average time H: 0,51 micros Factor H vs. Q: 1,08
  • Times: 100000 Orderedness: 50% Size: 100 Average time Q: 7,74 micros Average time H: 31,75 micros Factor H vs. Q: 4,10
  • Times: 100000 Orderedness: 50% Size: 500 Average time Q: 58,33 micros Average time H: 359,31 micros Factor H vs. Q: 6,16
  • Times: 100000 Orderedness: 50% Size: 1000 Average time Q: 127,35 micros Average time H: 1323,50 micros Factor H vs. Q: 10,39

All in all we can say that H Sort is not a very good algorithm, which in no useful situation is able to outperform good old Q Sort. It was fun developing and testing it, but I’ll leave it at this. The project can be found on GitHub for those who want to try themselves and maybe improve the algorithm.

Sorting algorithms

Some time ago I suddenly got an idea for a new sorting algorithm. What if you walked through an unsorted list of numbers, doing so until the next number was no longer greater than its predecessor, moved that number to the front and started again? I soon realized that this was a very brute and therefore somewhat inefficient approach. Performance could drastically improve if you don’t move the smaller number to the fron but keep it in memory during your next walk-through and insert it into the right spot when you pass it.

I wanted to test this so I made a Java program to implement my new sorting algorithm, which I dubbed ‘H sort’. Of course I needed a benchmark to test against, and I recalled the famous Q sort algorithm from my freshman year. I dusted off my old Pascal book (never thought I’d ever do that again!) and used it to implement Q sort in Java. Strangely enough Q sort does not seem to be in any standard Java library.

As I’d thought, brute H sort performed tragically badly. Its speed also seems highly dependent on the degree of ‘unsortedness’ of the sort list. Sorting an array of 10 integers ranging from 1 through 100 takes approximately 45 microsecs for Q sort, while brute H sort needs 80 up to 600 micros! Improved H sort takes around 50 micros, so that’s indeed quite acceptable.

Further comparing Q and (improved) H sort:

  • Array size 50: 125 vs. 520 micros
  • Array size 100: 260 vs. 1800 micros
  • Array size 1000: 4,000 vs. 18,000 micros

OK, so it’s quite good but not nearly as good as the old Q sort! Of course I need to test this further, running tests automatically for many times and averaging the results. I also want to vary the degree of ‘sortedness’ of the arrays, using partly-sorted ones for testing. I hope to work on this in my spare time the coming days and I’ll keep you posted! I’ll also look into whether this ‘H sort’ algorithm of mine is indeed new or if someone already came up with this (which seems very likely).

Verkiezingen: democratie als legitimatie van de staat?

Gisteren mochten we stemmen. Een democratisch recht dat ons een héél klein beetje invloed geeft op waar het in dit land naartoe gaat. We stemmen met om en nabij de 10 miljoen mensen om 150 Tweede Kamer-zetels te verdelen over enkele politieke partijen. Na een moeizaam formatieproces gaan een paar van deze partijen die al dan niet een meerderheid van zetels hebben en het enigszins met elkaar kunnen vinden, een regering vormen. Deze regering gaat vervolgens beleid maken en uitvoeren, en de door ons gekozen Tweede Kamer legt zich toe op zijn eigenlijke taak: het controleren van de regering. Beleid ligt overigens al voor minstens zo’n 80 procent vast; op de rest kan de regering enige invloed uitoefenen.

Je invloed in dit spel is natuurlijk miniem. Jouw ene stem maakt feitelijk niet uit. Maar als niemand zou gaan stemmen, werkt het systeem ook weer niet.

Het gaat met name om trends, om wat grote groepen mensen vinden, onder invloed van groepsprocessen en natuurlijk de media. Als er op een gegeven moment het groepsgevoel ontstaat dat Samsom het best goed doet, dan heeft dat enorme invloed omdat heel veel mensen daar hun stemgedrag op aanpassen. En dan is Roemer ineens zijn extra zetels kwijt.

Democratie gaat dus om groepsdynamiek en niet om individuele stemmen. Is het daarmee een slecht systeem? Ik weet het eerlijk waar niet; ik kan me momenteel nog geen beter systeem indenken. Misschien is het wel waar wat ze zeggen, dat democratie de minst slechte staatsvorm is.

Het waarom van de staat

Feit is dat we een staat nodig hebben. Voor mij als klassiek liberaal het liefst voor zo min mogelijk taken, maar in ieder geval politie, justitie en defensie. De eigendomsrechten van de burgers op hun eigen lichaam, persoon en de vruchten van hun arbeid moeten bewaakt worden. Niemand mag zich daaraan onttrekken, anders dreigt wetteloosheid en wanorde. We moeten dus iets van een staat boven (naast?) ons dulden om ons tegen de rotte appels onder ons te beschermen. En deze staat moet op enige wijze gelegitimeerd worden, zodat de mensen deze situatie accepteren. Vroeger deed een door God zelf aangewezen koning of keizer het erg goed. Daar geloven we nu toch niet meer zo in. Het ritueel van de democratie is nu feitelijk de legitimatie van de staat geworden. Je hebt invloed op het beleid van de staat, zij het minimaal, en daarmee is de staat ook een beetje van jou.

Ik vind persoonlijk dat dit mechanisme niet volledig voldoet. De staat groeit maar door en trekt steeds meer taken naar zich toe. En de meeste burgers vinden dit nog prima ook! Het verdelen van belastinggeld over bepaalde groepen helpt hier natuurlijk bij. Maar goed, nu wijk ik wat te ver af van het thema van deze post, democratie als legitimatie van de staat. Thema’s als belastingen kunnen later mooi nog eens aan bod komen.

Feit is dat ik op dit moment nog geen goed alternatief voor democratie zie, waarbij burgers meer invloed hebben op de staat en deze beter in toom kunnen houden. Daar kan ik de komende tijd dus nog eens flink over lezen en nadenken, terwijl ondertussen in Den Haag de heren Samsom en Rutte hun formatiedans dansen!

OpenID geactiveerd

Je kunt nu ook inloggen op deze site met OpenID, dus bijvoorbeeld via Google of Yahoo. Met de openid-plugin voor WordPress was dit zo gepiept. Door nog een extra plugin te installeren, kun je bij het inloggen nu ook op het icoon klikken van je OpenID-provider in plaats van dat je de hele url in moet tikken. Handig!

En ja, nu zou het handig zijn als er ook zo’n plugin was voor mijn Piwigo-webalbum! Maar goed, dat is open source dus dat zou ik natuurlijk ook zelf kunnen doen. Leuk hobbyproject?