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
