Indeed, this would blow up the complexity. However, I am as interested
in a working example as I am in the though process behind, including the
part where one stumbles, so it's actually useful if you post your ideas,
even if they turn out to be wrong. At least, I'll have an idea on how do
you solve a problem when you encounter one in J!
Adrien Mathieu
On 05/10/2021 20:14, Hauke Rehr wrote:
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
