Exponential tree implementation

Discussion in 'C++' started by Alec Taylor, Apr 17, 2012.

  1. Alec Taylor

    Alec Taylor Guest

    I have become obsessed with improving the bounds for integer sorting after reading; Arne Andersson's 1995 paper: "Faster Deterministic Sorting and Searching in Linear Space"[1], Mikkel Thorup's 1998 paper: "Faster deterministic sorting and priority queues in linear space"[2], Yijie Han's 2002paper: "Deterministic sorting in O(n log log n) time and linear space"[3] and Han & Thorup's 2002 paper: "Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space"[4].

    Unfortunately when I got down to implementing the "Exponential search tree"data-structure of Andersson I ran into some trouble.

    I think I mis-implemented the insert function.

    Where did I go wrong? - http://ideone.com/F1T1f

    Thanks for all suggestions,

    Alec Taylor

    [1]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7109
    [2]: http://dl.acm.org/citation.cfm?id=314844
    [3]: http://dl.acm.org/citation.cfm?id=975984
    [4]: http://dl.acm.org/citation.cfm?id=645413.652131
     
    Alec Taylor, Apr 17, 2012
    #1
    1. Advertising

  2. Alec Taylor

    Alec Taylor Guest

    Arghh, ended up making a very n00bish mistake;
    `tree.insert(i);`, instead of: `tree.insert(inputVector);`

    On Tuesday, April 17, 2012 5:24:38 PM UTC+10, Alec Taylor wrote:
    > I have become obsessed with improving the bounds for integer sorting after reading; Arne Andersson's 1995 paper: "Faster Deterministic Sorting and Searching in Linear Space"[1], Mikkel Thorup's 1998 paper: "Faster deterministic sorting and priority queues in linear space"[2], Yijie Han's 2002 paper: "Deterministic sorting in O(n log log n) time and linear space"[3] and Han & Thorup's 2002 paper: "Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space"[4].
    >
    > Unfortunately when I got down to implementing the "Exponential search tree" data-structure of Andersson I ran into some trouble.
    >
    > I think I mis-implemented the insert function.
    >
    > Where did I go wrong? - http://ideone.com/F1T1f
    >
    > Thanks for all suggestions,
    >
    > Alec Taylor
    >
    > [1]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7109
    > [2]: http://dl.acm.org/citation.cfm?id=314844
    > [3]: http://dl.acm.org/citation.cfm?id=975984
    > [4]: http://dl.acm.org/citation.cfm?id=645413.652131
     
    Alec Taylor, Apr 17, 2012
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Eric Lawrence [MSFT]

    Re: See data in exponential format

    Eric Lawrence [MSFT], Mar 1, 2004, in forum: ASP .Net
    Replies:
    3
    Views:
    575
    =?Utf-8?B?Sm9yZ2UgTWFnYW50bw==?=
    Mar 2, 2004
  2. Exponential

    , Feb 10, 2005, in forum: C++
    Replies:
    1
    Views:
    986
    Victor Bazarov
    Feb 11, 2005
  3. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,136
  4. Timothy Fitz

    Exponential Notation and integers

    Timothy Fitz, Nov 18, 2004, in forum: Python
    Replies:
    4
    Views:
    1,072
    =?ISO-8859-1?Q?F=E1bio?= Mendes
    Nov 19, 2004
  5. Neal Becker

    unusual exponential formatting puzzle

    Neal Becker, Sep 21, 2005, in forum: Python
    Replies:
    5
    Views:
    517
    Neal Becker
    Sep 22, 2005
Loading...

Share This Page