Forget about this one, you don’t want to compute a matrix
when sorting. And this wouldn’t actually leverage rank for
getting the “looping” done.
Shame on me.
Still I think it’s possible. But I’ll now stop rushing
to an answer before my thinking is done.
Am 05.10.21 um 20:00 schrieb Hauke Rehr:
Now I understand what you’re talking about.
And I think it is possible.
This is quick and dirty but you may get the idea:
] 'first second' =: 1 5 7 8 12 ; 2 3 9 11 14 15
┌──────────┬──────────────┐
│1 5 7 8 12│2 3 9 11 14 15│
└──────────┴──────────────┘
first </ second
1 1 1 1 1 1
0 0 1 1 1 1
0 0 1 1 1 1
0 0 1 1 1 1
0 0 0 0 1 1
+/"1 first </ second
6 4 4 4 2
2 -/\ +/"1 first </ second
2 0 0 2
; ({. first) ; (2 {. second) ; ((>: # 0 0) {. }. first) ; (2 {. 2 }.
second) ; ((1 + (>: # 0 0)) }. first) ; ((2 + 2) }. second)
1 2 3 5 7 8 9 11 12 14 15
Now go find an elegant way to derive the last one from the 2 0 0 2
and some extra information (first entry in first </ second).
Maybe someone else on this forum knows of a better approach?
Am 05.10.21 um 19:40 schrieb Adrien Mathieu:
Yes, I understood that. I had the impression sometimes you can create
data that will allow you to operate on them as if you were operating
on the original data sequentially. An example I have in mind is, if
you have a sequence of booleans, finding the beginning of the
sequences of 1s. Of course, you could do that with a loop, and you
can't directly solve this with rank (because of the dependence of
chunks of data with other chunks of data). However, by duplicating the
array, shifting one of the copy, and applying the right function to
the two arrays, one can obtain the wanted effect, using no
loop/recursion. This is what I meant by translating a temporal problem
to a space problem.
However, there might be a fundamental difference that I don't see
between merging two sorted arrays, and the example I gave, that makes
it impossible to find a pure-rank solution to the merging problem,
whereas it is possible for my example.
Adrien Mathieu
On 05/10/2021 19:13, Hauke Rehr wrote:
I didn’t express that very well, sorry for that.
Rank helps when you want data parallelism.
Apply to /this/ data, after chopping it into chunks.
Not to different data computed from this one.
In merge sort, the data changes in each loop iteration
so you can’t use that. Usually, you resort to using ^:
or the fold family F: etc
I hope this is both more accutare and easier to understand.
Am 05.10.21 um 19:06 schrieb Adrien Mathieu:
Yes, indeed, that was the main issue I met when trying to solve this
puzzle, ie. when you solve a problem "using rank", it usually means
your operation could be parallelized (because the J specs do not
specify the order of operations), so there should be no time
relation between each appliance.
However, I had the impression that sometimes it is possible to
translate a time problem into a space problem, to use your words,
for instance using the \ and \. adverbs (if I had to translate this
to Caml, I would put it this way: if you could either solve you
problem with recursion, or with a big fold) — which, to me, counts
as a "rank solution".
If what I say is a bit vague, it's because I'm not sure exactly to
grasp completely the limits between what can be solved "using rank",
and what can be solved "using recursion/loop". I don't even know if
the two are completely equivalent (ie. if you can get a solution
with the same complexity using both for every problem).
Adrien Mathieu
On 05/10/2021 19:00, Hauke Rehr wrote:
I don’t quite understand.
Rank always applies to data (space). Recursion to program flow (time).
Am 05.10.21 um 18:58 schrieb Adrien Mathieu:
Well, technically this answers the question, but it doesn't answer
/my/ question, since this is the functional-language approach of a
loop. Maybe I have to be more specific:
the answer you are giving is, to me, what you would code if you
were asked to translate, say, the Caml version of mergesort. So
the loop is transformed into recursion.
What I wanted to know if there is a way in which loop is
translated into rank (if you get what I mean).
Adrien Mathieu
On 05/10/2021 18:53, Gilles Kirouac wrote:
Does this page help?
https://code.jsoftware.com/wiki/NYCJUG/2012-05-08
See Merge-Sort Examples.
~ Gilles
Le 2021-10-05 à 12:03, Adrien Mathieu a écrit :
Hello,
I am a beginner, and I would like to know if there is a way to
write mergesort without using loops, or an ugly translation of
loops using the ^: conjunction.
In particular, I have the impression that the merge part is hard
to achieve.
Thanks in advance,
Adrien Mathieu
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
--
----------------------
mail written using NEO
neo-layout.org
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
