As I understand it, the algorithm employed is as follows:
set
is a set of numbers, all of which are in the sequence
arrOfResult
is set
in order
- Invariant: the first
nextInvoker + 1
elements of arrOfResult
are complete: i.e. they form a prefix of the sequence with no gaps
- We loop, extending
set
/arrOfResult
by two elements each time until we have n
elements, so the prefix is of length n/2
(plus or minus a couple: I haven't worked through the exact details)
- We then form the closure under the two operations \$x \to 2x+1\$ and \$x \to 3x+1\$ and claim that the prefix of that closure contains the first
n
elements with no gaps.
The claim of that last point seems to me to need a comment showing why it's true.
But more importantly, the way in which the algorithm works seems to repeat a lot of work.
arrOfResult = Array.from(set).sort((a, b) => a - b);
sorts the same elements as the previous time round the loop, plus two more, with a full \$\Omega(n \lg n)\$ sort.
An easy way to get an asymptotic improvement would be to use a suitable priority queue. A standard binary heap would probably be sufficient. It would also simplify the main method: just three variables (the heap, a counter, and the previous element in order to detect duplicates) and a single loop.
In fact, if you really optimise that loop it's not even necessary to fully implement the binary heap.
function dbl_linear(n) {
var prev = 0,
heap = [1];
while (true) {
if (heap[0] === prev) {
// Standard heap pop: move last element to replace first and downheap
heap[0] = heap.pop();
}
else {
if (n-- === 0) return heap[0];
// We want to pop x and then insert 2x+1 and 3x+1
// Since 3x+1 is guaranteed to be larger than anything in the heap,
// we can optimise its insertion. Then we can combine the pop and the
// other insertion into one assignment and a downheap.
prev = heap[0];
heap.push(3 * prev + 1);
heap[0] = 2 * prev + 1;
}
// Push heap[0] down until we restore the heap property
downheap(heap);
}
}
downheap
not included.
The clever way of tackling a problem about a sequence of integers if you're allowed access to the Internet is to use the Online Encyclopedia of Integer Sequences to see what's known about it. Searching for the prefix given in the problem statement gives two results: the desired sequence with and without duplicates. Since you clearly interpret the (IMO ambiguous) problem statement as being without duplicates, look at the notes on the sequence without duplicates:
...
a(n+1) = A007448(a(n)); giving also the record values of A007448 and their positions. - Reinhard Zumkeller, Jul 14 2010
...
A007448 is
Knuth's sequence (or Knuth numbers): a(n+1) = 1 + min( 2*a(floor(n/2)), 3*a(floor(n/3)) )
I would be happy to leave it there, but since some commentators doubted my observation that this gave a simple and efficient solution, two implementations.
A naïve implementation (ignoring everything from Zumkeller's comment after the semicolon) would be
function dbl_linear(n) {
var cache = {0 : 1},
a = 1,
knuth = function(n) {
return cache[n] = cache[n] || 1 + Math.min(2 * knuth(Math.floor((n - 1) / 2)),
3 * knuth(Math.floor((n - 1) / 3)));
}
while (n--) a = knuth(a);
return a;
}
But taking into account the observations made after the semicolon we can optimise quite heavily. This is slightly less simple (although a binary search is still simpler than a heap), but more efficient, and easily argued to run in \$O(n \lg n)\$ time:
function dbl_linear(n) {
// a(n+1) = A007448(a(n)); giving also the record values of A007448 and their positions.
// - Reinhard Zumkeller, Jul 14 2010
// A007448(n+1) = 1 + min(2 * A007448(n/2), 3 * A007448(n/3))
var A002977 = [1],
i,
ai = 1;
function A007448(x) {
// Find the smallest element of A002977 which is larger than x by binary chop
// Invariant: A002977[lb] <= x < A002977[ub]
// To ensure the invariant we need a special case
if (x === 0) return 1;
var lb = 0,
ub = A002977.length - 1,
mid;
while (ub - lb > 1) {
mid = lb + ((ub - lb) >> 1);
if (A002977[mid] > x) ub = mid;
else lb = mid;
}
return A002977[ub];
}
for (i = 1; i <= n; i++) {
ai = 1 + Math.min(2 * A007448(Math.floor((ai - 1) / 2)),
3 * A007448(Math.floor((ai - 1) / 3)));
A002977[i] = ai;
}
return ai;
}
Performance measured on tio.run using Spidermonkey. Times based on a single run, so take with a pinch of salt. They are at least illustrative.
n | original code | sineemore's code | heap | naïve Knuth | optimised Knuth
100 | 0.034s | 0.038s | 0.028s | 0.026s | 0.029s
10^3 | 0.185s | 0.031s | 0.028s | 0.032s | 0.031s
10^4 | 15.2s | 0.147s | 0.031s | 0.042s | 0.040s
10^5 | timeout | 8.3s | 0.042s | 0.268s | 0.051s
10^6 | timeout | timeout | 0.195s | 4.4s | 0.155s
10^7 | not tested | not tested | 2.4s | segfault | 1.9s
}
but anyway, sorting inside thewhile
loop is unnecessary and incredibly slow (not to mention that you're building anArray
from aSet
, each time): directly insert items in the right position and dropset
all together. \$\endgroup\$ – Adriano Repetti Jun 4 '18 at 8:48}
to make clear where things start/ends but the point is the you do not need sorting at all. When inserting you already know where to (binary search for the greatest number smaller than the one you want to insert). Also note that the final size of the array is known in advance then you do not need to create/destroy/copy arrays (and you can preallocate arraynew Array(the_size_you_need)
. With slightly more complicate code you don't even need to search but even doing it you'll greatly gain in performance compared to now. \$\endgroup\$ – Adriano Repetti Jun 4 '18 at 9:24> n
and you can simplycontinue
plus I have the gut feeling that algorithm itself should be rewritten to be even simpler but I'm kind of lazy then... \$\endgroup\$ – Adriano Repetti Jun 4 '18 at 9:28