Thanks, I'll have a look. M Please reply to [email protected]. Sent from my iPad
> On 14 Mar 2017, at 23:52, 'Jon Hough' via Programming > <[email protected]> wrote: > > I haven't attempted that Project Euler Question. But I did implement a > priority queue a while back. > I just put it here: > https://gist.github.com/jonghough/e3566dcfea95e4dbc5b23f9295388df6 > > It can handle arbitrary comparators, i.e. any verb returning 0 or 1. However, > I doubt it is of much use, because it isn't particularly fast. > But may be interesting as a reference. > > Jon > > -------------------------------------------- > On Wed, 3/15/17, 'Mike Day' via Programming <[email protected]> wrote: > > Subject: [Jprogramming] Moving median - any good methods? > To: [email protected] > Date: Wednesday, March 15, 2017, 4:50 AM > > This has arisen in > solving Euler Project problem 593. > https://projecteuler.net/problem=593 > It is basically quite easy, especially for the > examples with given > answers, ie > for F(100,10) and even for F(100000, 10000) but > as usual with these > problems, > there's a sting in the tail, in the > computing requirement for F(10^7, 10^5) > > The data consist of what one can regard as a > random set of integers, > which I called > S2keep, drawn from a finite set with ~ 20000 > elements. > > F(n,k) is the sum > of medians on each window of k consecutive elements of > sample of n elements of S2keep. > > So F(10,100) is easily > constructed, hard-wired here: > > 10j1":-:+/10 (+/@:(4 > 5{/:~))\100{.S2keep > > 463628.5 > > > This is of course inefficient for larger n and > k. > > > However, the window size for the stated > problem is ~5 times larger than > the > universe > > of elements, and > we know that each successive window differs from the > previous one > > in at most two elements, so it's somewhat > more efficient, though more > tedious, > to > > maintain a count array > (cts) of size ~20000. For any window, this array > consists of > > effectively random zero or positive entries, > summing to k. The indices > of these > entries > > are the indices of > the elements of S2keep in a sorted list of nub > elements of S2keep. So > > locating the indices of the (k/2)th members of > the cumulative sum of cts > will reveal > the > > median elements of the > window. > > > But this is still quite slow. The answer > which I submitted had taken > about 14 > minutes > > with this method. > (in J805 pre avx!) > > > I thought it should be possible to do better, > and googled in stack > overflow and > elsewhere. > > The preferred > method appears to require "indexable skip lists", > said to > be better than binary > > trees. I had a look - > they're not too hard to construct, but it's > difficult to insert and delete > > elements in a J-like way. > > > I gave up on > this tack, and instead found some improvement in run-time > > with using > > heaps. So, instead of maintaining a count > array with one slot per nub > element, the > heaps > > count several > contiguous nub elements. The default of this approach is > > to have ~ %: 20000 > > heaps, ie ~ 140. > > > Best time so far is still > quite long - about 8 minutes. (And ~5 1/2 in > J806Beta using avx) > > > Question is - has anyone > achieved efficient solutions in J? Other > languages seem to have > > efficient implementations of heaps, binary > trees, skip lists and so > on, if only > one can > > understand how to > use them! > > > Not much use if it's just for solving Euler > Project problems, but > people do need > moving > > statistics on > occasion. > > > This is long enough without quoting my source > code. Available on request! > > > Thanks, > > > 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 > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
