4 ms·
Any measurement of "code complexity" is relative to some particular computational basis; which one do we choose? In APL sorting the array P in ascending order
by kragen 5y ago
Any measurement of "code complexity" is relative to some particular computational basis; which one do we choose?
In APL sorting the array P in ascending order is just
P[⍋P]
which result you can optionally assign back to P by prepending "P←". So, by the APL measure, none of these algorithms is "as simple as" invoking the builtin sort operator. (Which is probably also faster.) APL doesn't actually have any 'syntax that's basically "for i = x to y".'
If we take Perl golf as our measure of "code complexity" you can't use a for-loop for dumbsort, because zeroing the ostensible loop counter doesn't reset the loop; there's a hidden loop counter you can't alter. You have to use an explicit while loop, which makes the cantbelievesort much simpler. Smalltalk and Python are the same way. But of course the shortest way to sort in all three languages is to invoke the built-in sort function: sort @p, p asSortedCollection, p.sort().
(You're right about FORTRAN and BASIC, though. You can futz with loop counters in those languages, just like in C.)
That's why I chose C and machine code as my metric. Smalltalk and Python maintain this hidden loop counter in the implementation, and also do garbage collection behind the scenes (which you might think was irrelevant, but the write barrier can significantly slow down heavily mutating algorithms like this one) and bounds checking. Numpy and APL additionally do implicit array broadcasting. All of these languages (except FORTRAN and BASIC) have built-in sort routines that are simpler to invoke than writing your own sort function. So I was looking for the language that would keep me as honest as possible.
But of course in a different machine language the answer might be different. For example, I haven't seen an instruction set with dedicated looping instructions that support nested loops, but make it inconvenient to clobber the loop counter in the middle of the loop, but it would be easy to design one, and there might be some advantage to doing so. (Code density, maybe, or unrolling iterations of the loop into a pipeline.) Then dumbsort would lose, because as in Python, it would have to be written as a regular while loop, which usually costs four instructions: an increment, a compare, a conditional jump, and an unconditional jump.
I think the i-=2 tweak you suggest converts dumbsort into gnomesort, which is just a sort of pessimized insertion sort. As your "saturating" comment suggests, gnomesort needs an additional operation to avoid running off the beginning of the array; some instruction sets do provide saturating arithmetic (it's often useful for DSP and graphics, even if it's not as often useful for indexing arrays), and many others provide a binary "max" operation (SSE's PMAXSW and friends, as well as, say, APL ⌈) which could convert an ordinary subtraction into a saturating subtraction.
- Dylan16807 5y agoI don't have a rigorous method here, but I'd say a builtin sort is cheating a complexity count while "for each" is fine. > If we take Perl golf as our measure of "code complexity" you can't use a for-loop for dumbsort, because zeroing the ostensible loop counter doesn't reset the loop; there's a hidden loop counter you can't alter. You have to use an explicit while loop, which makes the cantbelievesort much simpler. Smalltalk and Python are the same way. I think it can be reasonable to say that manipulating a loop counter is more complex than a strict loop over elements. Though you can get around that issue by using tail recursion for dumbsort instead of setting i to 0. > But of course in a different machine language the answer might be different. For example, I haven't seen an instruction set with dedicated looping instructions that support nested loops, but make it inconvenient to clobber the loop counter in the middle of the loop, but it would be easy to design one, and there might be some advantage to doing so. Maybe not nestable ones, but that's just a quirk of trying to have an especially compact instruction encoding. If the common case can be a single opcode like LOOP, or only a couple opcodes in a RISC architecture, I think it's reasonable to call it "one line of code". > I think the i-=2 tweak you suggest converts dumbsort into gnomesort, which is just a sort of pessimized insertion sort. As your "saturating" comment suggests, gnomesort needs an additional operation to avoid running off the beginning of the array; some instruction sets do provide saturating arithmetic (it's often useful for DSP and graphics, even if it's not as often useful for indexing arrays), and many others provide a binary "max" operation (SSE's PMAXSW and friends, as well as, say, APL ⌈) which could convert an ordinary subtraction into a saturating subtraction. Is there a way to write gnomesort that only has two simple conditionals? You're right that my suggestion brings it a lot closer to gnomesort, but I'm definitely not suggesting anything that checks if you're at zero.
- kragen 5y agoI hadn't thought of writing a tail-recursive dumbsort, though I'm not sure this is really simpler (untested): void dumbsort(int *p, size_t n) { dumbsort2(p, n, 1); } int dumbsort2(int *p, size_t n, size_t i) { int tmp; return i == n ? 0 : p[i] < p[i-1] ? (tmp = p[i], p[i] = p[i-1], p[i-1] = tmp, dumbsort2(p, n, 1)) : dumbsort2(p, n, i+1); } > If the common case can be a single opcode like LOOP The thing about the 8086 LOOP instruction is that it does expose the loop counter conveniently; it's just CX (or ECX on i386, RCX on amd64). So restarting it is just a MOV (not an XOR, because it counts down to 0). Forth offers an instructive example of a set of operations (usually implemented in software rather than hardware) that support nested loops. Forth DO pushes both the loop counter and the upper bound on the "return stack" as what the ANSI standard calls a "do-sys"; there are words I, J, and K which get the innermost, second-innermost, and third-innermost loop counters, but cannot be used to set them. You can even save the contents of the return stack and restore it, but ANSI doesn't give you a way to restart the loop counter (which is certainly bad practice). But that's just a matter of portability; any concrete Forth necessarily has to have a reliable way to set the loop counter so that LOOP can increment it. For CPUs, that circuitry wouldn't have to be accessible as an instruction, but general-purpose CPUs have a different concern: they need to have some way to save and restore all their architectural registers for preemptive context switching, which would include that loop counter — even if it wasn't exposed as a GPR like the i386 ECX. You could imagine providing that ability only via something like i386 PUSHAD, which would be a pretty inconvenient and slow way to restart the loop counter. But I'm not familiar with any instruction sets that work that way. > Is there a way to write gnomesort that only has two simple conditionals? You're right that my suggestion brings it a lot closer to gnomesort, but I'm definitely not suggesting anything that checks if you're at zero. I think that if you have a signed max() instruction that doesn't count as a conditional, this produces gnomesort with only two simple conditionals (untested): void browniesort(int *p, size_t n) { int tmp; for (size_t i = 1; i < n; i++) { if (p[i] < p[i-1]) tmp = p[i], p[i] = p[i-1], p[i-1] = tmp, i = max(i-2, 0); } } I was thinking that maybe the "standard" gnome sort avoids redundantly comparing the first two entries again after swapping them, instead immediately stepping forward, but in fact both Dick Grune's C at https://dickgrune.com/Programs/gnomesort.html https://dickgrune.com/Programs/gnomesort.html and the pseudocode in https://en.wikipedia.org/wiki/Gnome_sort https://en.wikipedia.org/wiki/Gnome_sort do the same redundant comparison of the two items they just swapped. (Hamid Sarbazi-Azad's original "stupid sort" does not do this, but Grune considers it "the same algorithm".) I think not counting max() as a conditional may be reasonable because, as I said, a number of CPU instruction sets provide it as a fundamental operation. At the hardware level it's no more conditional than the multiplexers used to read an operand from a source register in the register file.