Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #15421 > unrolled thread
| Started by | Alec Taylor <alec.taylor6@gmail.com> |
|---|---|
| First post | 2012-04-17 00:24 -0700 |
| Last post | 2012-04-17 00:47 -0700 |
| Articles | 2 — 1 participant |
Back to article view | Back to comp.lang.c++
Exponential tree implementation Alec Taylor <alec.taylor6@gmail.com> - 2012-04-17 00:24 -0700
Re: Exponential tree implementation Alec Taylor <alec.taylor6@gmail.com> - 2012-04-17 00:47 -0700
| From | Alec Taylor <alec.taylor6@gmail.com> |
|---|---|
| Date | 2012-04-17 00:24 -0700 |
| Subject | Exponential tree implementation |
| Message-ID | <16199152.641.1334647478254.JavaMail.geo-discussion-forums@pbjk8> |
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
[toc] | [next] | [standalone]
| From | Alec Taylor <alec.taylor6@gmail.com> |
|---|---|
| Date | 2012-04-17 00:47 -0700 |
| Message-ID | <31918865.1485.1334648858306.JavaMail.geo-discussion-forums@pbcpw7> |
| In reply to | #15421 |
Arghh, ended up making a very n00bish mistake; `tree.insert(i);`, instead of: `tree.insert(inputVector[i]);` 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
[toc] | [prev] | [standalone]
Back to top | Article view | comp.lang.c++
csiph-web