High resolution performance.now() works if you set specific headers as described here. You can't do that on GitHub Pages, but you can on Netlify

@Bubbler thanks. that's good to know.

(This is the Netlify config file for the headers, in case anyone wants to move to Netlify too for similar reasons)

@ktye is \t not good enough?

@ktye btw i tried implementing the half-copying version of mergesort and there was only a small improvement. i'm not sure it's worth it.

i also tried non-recursive bottom-up mergesort and it ended up a little worse

next: mergesort-insertionsort hybrid ("tim")

@ktye you mean "\t:100" instead of "\t100"?

@ngn i'm puzzled about my mergsort. I do need that memcopy to initialize both arrays, (due to swapping depending on the input size). Other versions seem to get away without (but maybe copy elsewhere)?

@ktye i got a "reference error" too, it just doesn't show up in the interface

@ktye i think you can get away with no copying, but then the output array changes or something

@dzaima this is about gradeing. First i create ⍳N than a working copy. the original array is not modified and i'm interested only in one of the two index-arrays.

@ktye swept under the carpet :)

@ktye in the simplest version of mergesort you have an input array and a tmp array. one level of the recursion swaps those. when the recusion is over your output should be either the input array or the tmp array, depending on the parity of the depth of the recursion. this way you don't need to initialize tmp.

@dzaima oh, i guess it's not that simple. You probably need to have consistent depth that the merge sort runs at, know the parity in advance, and swap the input & output arrays depending on that

@ngn ok. that means i miss a check at the end.

in the half-copying algorithm (my current impl) you have two versions of the sorting function - one that puts the output in the input array, and a "copying" version that puts it in a separate array. this way too you don't need to initialize the tmp array.

@ngn did you try not to recurse until length 2 but switch to another (simple/quadratic) algorithm before?

@ktye not yet, i wanted to test some variations on pure mergesort first

@ktye i'd expect the optimal threshold to be higher than 2

how can I adjust this hanoi solution to output unnested moves? ngn.bitbucket.io/k/…

@Traws like this?

@ngn yeah, thanks. it was really simple.

@Traws this sequence of moves looks wrong: .. 1 3; 3 1; 1 3 ..

@ngn thanks, i hadn't noticed. the correct should be ngn.bitbucket.io/k/…

@Traws btw, there must be an elegant non-recursive version too, as the i-th move seems to depend on the binary representation of i

@Traws nicer (i think) recursive version:

move:{$[x;3!(-o x-1),(,!2),2-o x-1;()]}
1 3 2@move 4

or: move:{$[x;(3!-u),(,!2),2-u:o x-1;()]}

here's a non-recursive one, unfortunately longer: {1_+3!x-:/0 2-2/'(&':'b;|':'b:!x#2)}

@ngn I quite liked this solution. very clever trick for doing the swaps, although it took me a while to decipher.

it always delights me that while functional programmers view recursive procedures as portraits of elegance, the vector programming community sees them as merely a first jab at a problem

@JohnE potentially because of the lack of optimisation for recursion in array langs + the lack of optimisation for vector stuff in fp langs

Recursive algorithms typically mean recursive data: nibbling at things in tiny bites, lots of interpretive overhead, and horrific cache coherency. Just as vector languages eschew explicit loops, explicit recursion should be viewed as boilerplate. Abstract recursion is better whenever you can get away with it

vector programming feels like those perspective drawings (or at least something conjuring long parallel lines). not sure what a more recursion-oriented approach is in that metaphor

@JohnE what's 'abstract recursion'? not heard that term before

doing for recursion the same things adverbs do to iteration

do you have an example?

hypercubed.github.io/joy/html/j05cmp.html

ah right combinators and stuff, interesting

I also wrote this paper: vector.org.uk/conquering-recursion

this looks familiar, must have read it at some point

the challenging part is that there is a vast zoo of "topologies", if you will, for recursive programs, and it can be exceedingly difficult to carve apart an arbitrary program into a set of combinators

in that paper I describe a pentad which describes a variety of interesting cases and if you project it down you get several less general yet also less daunting looking combinators

just as over and scan capture a very small number of possible for loops, rec captures a very small number of possible recursive bodies

neat

need to look into it more

never thought about generalising recursion the same way adverbs generalise iteration

many of joy's recursive combinators are covered by adverbs one way or another; if you don't have any "fanout" it's easy enough to rethink a procedure as a loop

and even with recursive structure you may not need explicit recursion e.g. adding a scalar to a tree leverages the abstract recursion built into conforming

you know sometimes I think I'm sorta getting the hang of this array language thing and then I see things like this and realise I still don't have a clue lol

nonrecursive representation of trees are also very interesting

like aaron hsu's stuff?

so far as I have explored, you end up with something much easier and more elegant to query, but perhaps much clumsier to change in place

yes

and even simpler stuff like having a vector of values and a vector of "index to parent node"

the idea of being able to separate values from their hierarchical structure is very powerful

try doing that with sexprs