I should probably have gone straight to Knuth, but here's what I
managed with
Fredman's account of the algorithm. The tacit version is surprisingly
easy!!!
Note that this algorithm does not in general produce the same
subsequence as
the Wikipedia alternative, but it is of equal length, and is a bit
quicker.
Also, the subsquence's indices are not available, so it is deficient
compared
to longascseq etc; the latter are /: -like while lisf and taclisf
(below) are
not.
Advertising
NB. Fredman/Knuth algorithm as in
NB. https://dx.doi.org/10.1016%2F0012-365X%2875%2990103-X
lisf =: 3 : 0
x =. y
if. 2>#x do. x return. end.
T =. {.x
for_xj. }.x do.
if. xj > {:T do.
T =. T, xj
else.
m =. T I. xj
NB. if. xj < m { T do. Slight impairment with this test
T =. xj m } T
NB. end.
end.
end.
T
)
NB. see how to do tacit amend/append xi in T
NB. 10 ([ I.~ } ]`(,~)@.(>{:) ) 7 9 11 NB. 10 <: 11, so insert
NB. 7 9 10
NB. 20 ([ I.~ } ]`(,~)@.(>{:) ) 7 9 11 NB. 20 > 11, so append
NB. 7 9 11 20
doxj =: ([ I.~ } ]`(,~)@.(>{:) ) NB. amend T (rha) with xj (lha)
taclisf =: doxj / @ |. NB. closed form on array
q =: ?.~ 1000000
timer'(#; 10&{.) longascseq1 q'
+-+----+------------------------------------------------+
|8|1971|647 1210 1309 1399 1450 1688 1993 2006 2349 2729|
+-+----+------------------------------------------------+
timer'(#; 10&{.) lisf q'
+-----+----+------------------------+
|4.238|1971|0 2 4 7 9 12 13 20 28 37|
+-----+----+------------------------+
timer'(#; 10&{.) taclisf q'
+-----+----+------------------------+
|4.742|1971|0 2 4 7 9 12 13 20 28 37|
+-----+----+------------------------+
Space requirements are similar for all 3, at ~ 8.4 Mb,
with lisf <~ taclisf <~ longascseq1 , in this case.
Mike
Please note that I've snipped earlier history (below)
from this correspondence.
On 15/09/2016 09:28, Erling Hellenäs wrote:
The Knuth reference can be downloaded here:
http://www.mediafire.com/download/3btahsyzax4w7xp/Vol%2C3+SortingAndSearching-Donald+Knuth.pdf
Youngs tableau is on page 47.
/Erling
On 2016-09-14 23:27, 'Mike Day' via Programming wrote:
I suspect it's pretty near optimal. The wikipedia article points at
Fredman's paper:
http://www.sciencedirect.com/science/article/pii/0012365X7590103X
analysing an algorithm of Knuth's. He shows that it performs better
than
n log2(n) - n log2 log2 (n) + O(n)
rather than the O(n logn) cited for the function we've been looking at.
I might have a play at tacit for the algorithm already discussed.
Mike
On 14/09/2016 14:57, Erling Hellenäs wrote:
Any ideas about how you could make a substantially faster tacit
solution to this problem or how you could make this solution
substantially faster? /Erling
[ sorry, but I've snipped the rest - Mike]
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
