On 12/02/2015 06:26 AM, Timon Gehr wrote:
Assume the initial array is sorted from largest to smallest. This will
be the worst case for this construction algorithm, as each element will
be sifted all the way down to leaf level of the last heap.
[...]
Ω(n^(3/2)).
Thanks. My math-fu is not good
On 12/03/2015 11:44 PM, Andrei Alexandrescu wrote:
On 12/02/2015 06:26 AM, Timon Gehr wrote:
Assume the initial array is sorted from largest to smallest. This will
be the worst case for this construction algorithm, as each element will
be sifted all the way down to leaf level of the last heap.
On 12/02/2015 12:26 PM, Timon Gehr wrote:
...
∑ᵢ[2≤i≤m]·log(i)·∑ₖ[0≤k≤⌊i/2⌋-1]·(2·k+1)
=
∑ᵢ[2≤i≤m]·log(i)·⌊i/2⌋²
It should actually be (⌊i/2⌋-1)² here, but this does not change the
asymptotics.
On 12/02/2015 06:26 AM, Timon Gehr wrote:
The linear search can have way better locality, so it is likely that
actually the binary search dominates for some data sets.
Galloping search ftw (good locality, log complexity). -- Andrei
On 12/02/2015 03:29 PM, Timon Gehr wrote:
On 12/02/2015 12:26 PM, Timon Gehr wrote:
...
∑ᵢ[2≤i≤m]·log(i)·∑ₖ[0≤k≤⌊i/2⌋-1]·(2·k+1)
=
∑ᵢ[2≤i≤m]·log(i)·⌊i/2⌋²
It should actually be (⌊i/2⌋-1)² here, but this does not change the
asymptotics.
Oops. No, it was actually right. Sorry for the noise.
On Wed, 02 Dec 2015 05:58:24 +, Navin wrote:
> Nice to see this interesting post and learn.
>
> I have a few questions.
>
> 1) This is offline datastructure since you don't know how the elements
> of the future are going to be ie dynamic. ie later elements from n to 2n
> can break or
On 12/01/2015 11:48 PM, Andrei Alexandrescu wrote:
On 12/01/2015 12:13 AM, Andrei Alexandrescu wrote:
On 11/30/15 9:47 PM, Timon Gehr wrote:
On 12/01/2015 03:33 AM, Timon Gehr wrote:
On 11/30/2015 09:57 PM, Andrei Alexandrescu wrote:
So now consider my square heaps. We have O(n) build time
On 12/01/2015 12:13 AM, Andrei Alexandrescu wrote:
On 11/30/15 9:47 PM, Timon Gehr wrote:
On 12/01/2015 03:33 AM, Timon Gehr wrote:
On 11/30/2015 09:57 PM, Andrei Alexandrescu wrote:
So now consider my square heaps. We have O(n) build time (just a bunch
of heapifications) and O(sqrt n)
On 12/01/2015 04:50 AM, Emil Kirschner wrote:
On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu wrote:
Okasaki's book is a continued inspiration of data structures and
algorithms.
Start with a simple array of data. Then mentally decompose that array
into a concatenation of
On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu
wrote:
Okasaki's book is a continued inspiration of data structures
and algorithms.
[...]
Sort of reminds me of a modified Hashed Array Tree — not keen on
the name, I think "Bucket Array" would have been better.
On Tuesday, 1 December 2015 at 22:48:56 UTC, Andrei Alexandrescu
wrote:
On 12/01/2015 12:13 AM, Andrei Alexandrescu wrote:
On 11/30/15 9:47 PM, Timon Gehr wrote:
On 12/01/2015 03:33 AM, Timon Gehr wrote:
On 11/30/2015 09:57 PM, Andrei Alexandrescu wrote:
So now consider my square heaps. We
On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu
wrote:
Okasaki's book is a continued inspiration of data structures
and algorithms.
Start with a simple array of data. Then mentally decompose that
array into a concatenation of smaller arrays: first has size 1,
second has size
On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu
wrote:
Okasaki's book is a continued inspiration of data structures
and algorithms.
[...]
Hi,
You might find relevant ideas in
https://cs.uwaterloo.ca/research/tr/1979/CS-79-31.pdf and
On 12/1/15 5:19 AM, Marko Mikulicic wrote:
On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu wrote:
Okasaki's book is a continued inspiration of data structures and
algorithms.
[...]
Hi,
You might find relevant ideas in
https://cs.uwaterloo.ca/research/tr/1979/CS-79-31.pdf
On Mon, Nov 30, 2015 at 03:57:24PM -0500, Andrei Alexandrescu via Digitalmars-d
wrote:
> On 11/30/15 3:20 PM, H. S. Teoh via Digitalmars-d wrote:
> >On Mon, Nov 30, 2015 at 03:13:11PM -0500, Andrei Alexandrescu via
> >Digitalmars-d wrote:
> >>Okasaki's book is a continued inspiration of data
Okasaki's book is a continued inspiration of data structures and algorithms.
I was thinking along the following lines: typical collections are
searchable in linear time. Then we have highly structured collections
that feature logarithmic search time. But there seems to be nothing in
between.
On Mon, Nov 30, 2015 at 03:13:11PM -0500, Andrei Alexandrescu via Digitalmars-d
wrote:
> Okasaki's book is a continued inspiration of data structures and
> algorithms.
>
> I was thinking along the following lines: typical collections are
> searchable in linear time. Then we have highly
On 30-Nov-2015 23:13, Andrei Alexandrescu wrote:
Okasaki's book is a continued inspiration of data structures and
algorithms.
I was thinking along the following lines: typical collections are
searchable in linear time. Then we have highly structured collections
that feature logarithmic search
On 11/30/15 3:29 PM, Dmitry Olshansky wrote:
Reminds me of Van Emde Boas layout which is however fractal in nature:
sqrt(N) pieces each having sqrt(N) element are subdivided again into
sqrt(sqrt(N)) pieces and so on.
Not sure if you have seen, but see also cache-oblivious data-structures:
On 11/30/15 3:20 PM, H. S. Teoh via Digitalmars-d wrote:
On Mon, Nov 30, 2015 at 03:13:11PM -0500, Andrei Alexandrescu via Digitalmars-d
wrote:
Okasaki's book is a continued inspiration of data structures and
algorithms.
I was thinking along the following lines: typical collections are
The key search phrase is "cache oblivious data structures". One
of the cache-friendly layouts is the van Emde Boas tree.
On 11/30/2015 09:57 PM, Andrei Alexandrescu wrote:
So now consider my square heaps. We have O(n) build time (just a bunch
of heapifications) and O(sqrt n) search.
How do you build in O(n)? (The initial array is assumed to be completely
unordered, afaict.)
On 12/01/2015 03:33 AM, Timon Gehr wrote:
On 11/30/2015 09:57 PM, Andrei Alexandrescu wrote:
So now consider my square heaps. We have O(n) build time (just a bunch
of heapifications) and O(sqrt n) search.
How do you build in O(n)? (The initial array is assumed to be completely
unordered,
On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu
wrote:
Now each of these arrays we organize as a max heap. Moreover,
we arrange data such that the maximums of these heaps are in
INCREASING order. That means the smallest element of the entire
(initial) array is at the first
On 11/30/2015 09:13 PM, Andrei Alexandrescu wrote:
I haven't worked out the math for insertion and deletion yet, but they
seem to also be around O(sqrt n) or O(log(n) * sqrt(n)).
(Assuming the bucket sizes actually grow linearly.) It seems to me that
for insertion O(√n̅ log n) is very easy to
On 11/30/2015 06:19 PM, Titus Nicolae wrote:
On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu wrote:
...
smallest organized in a max heap, ... etc. There are a total of O(sqrt
n) heaps, and each has O(sqrt n) elements.
...
Hi Andrei,
If I'm not mistaken, the number of heaps is
On 11/30/2015 06:32 PM, Titus Nicolae wrote:
On Monday, 30 November 2015 at 23:19:44 UTC, Titus Nicolae wrote:
On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu wrote:
...
smallest organized in a max heap, ... etc. There are a total of
O(sqrt n) heaps, and each has O(sqrt n)
On Monday, 30 November 2015 at 23:19:44 UTC, Titus Nicolae wrote:
On Monday, 30 November 2015 at 20:13:15 UTC, Andrei
Alexandrescu wrote:
...
smallest organized in a max heap, ... etc. There are a total
of O(sqrt n) heaps, and each has O(sqrt n) elements.
...
Hi Andrei,
If I'm not mistaken,
On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu
wrote:
...
smallest organized in a max heap, ... etc. There are a total of
O(sqrt n) heaps, and each has O(sqrt n) elements.
...
Hi Andrei,
If I'm not mistaken, the number of heaps is proportional to
n^(1/3) not n^(1/2)
On Monday, 30 November 2015 at 23:19:44 UTC, Titus Nicolae wrote:
On Monday, 30 November 2015 at 20:13:15 UTC, Andrei
Alexandrescu wrote:
...
smallest organized in a max heap, ... etc. There are a total
of O(sqrt n) heaps, and each has O(sqrt n) elements.
...
Hi Andrei,
If I'm not mistaken,
On 11/30/15 9:47 PM, Timon Gehr wrote:
On 12/01/2015 03:33 AM, Timon Gehr wrote:
On 11/30/2015 09:57 PM, Andrei Alexandrescu wrote:
So now consider my square heaps. We have O(n) build time (just a bunch
of heapifications) and O(sqrt n) search.
How do you build in O(n)? (The initial array is
31 matches
Mail list logo
