Recently, one of the php lists I'm on was asked how to implement a stable sort using php's sort functions. But since all of php's sort functions eventually seem to land up in zend_qsort, the default sort is not stable. The query on list had this simple example which illustrates the problem clearly.
bash$ php -r '$a= array(1,1,1); asort($a); print_r($a);'
Array
(
[2] => 1
[1] => 1
[0] => 1
)
The basic problem here is to produce a stable sort which still operates in quicksort O(n*lg(n)) time. Essentially, falling back onto a bubble sort is ... well ... giving up :)
Schwartzian transform: The programming idiom, named after Randal L. Schwartz, is a carry-over of the decorate-sort-undecorate lisp memoization into perl. The real problem here however was putting it into a php syntactic form which was clean and as similar to the original as possible. For example, here's how the python version of the code would look like (despite the fact that the current python sort is stable).
a = [1,1,1] b = zip(a, range(len(a))) # decorate b.sort() # sort a = map(lambda x : x[0], b) # undecorate
array_walk() magic: Coming from a world of constant iterators, I had read the array_walk documentation and sort of read the "Users may not change array itself ..." as boilerplate. But as it turns out, the callback function is allowed to change the current value *in place* and for that purpose it gets a reference to the value. With that in mind, array_walk becomes a faux in-place map/transform function.
$a = array(1,1,1);
function dec(&$v, $k) { $v = array($v, $k);}
function undec(&$v, $k) { $v = $v[0]; }
array_walk($a, dec); // decorate
asort($a); // sort
array_walk($a, undec); // undecorate
And there you have it, a lispism made famous by perl, implemented nearly exactly in php.
--Whoever knows he is deep, strives for clarity;
Whoever would like to appear deep to the crowd, strives for obscurity.
-- Nietzsche
Been a while since I got back, but somehow it feels like a let-down to be back home. Add to that four interminably long hops, after which I've travelled from the northern most state of India, to nearly the southern most tip (tinymap). That doesn't make for a good mood. But still, as I sit here, most of what happened seems like a distant blurry day dream.
So, in short, I did a bunch of things, took a lot of interesting pictures (more to come) and had a lot of fun.
Still haven't gotten rid of the "your work is worthless" back-of-the-mind "why bother" voice (yes, the one which keeps saying "you'll get paid anyway" and "they don't pay you nearly enough for that") - eventually I'll have to shake off that coders' block & make work fun again.
Except for that extra bit, the rest of me is back, as expected :)
--Removing the straw that broke the camel's back does not necessarily allow the camel to walk again.