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.

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

Reply via email to