Opened 10 years ago

Closed 8 months ago

#710 closed enhancement (fixed)

speed up Kendall::score using NlogN algorithm

Reported by: Peter Owned by: Peter
Priority: major Milestone: yat 0.19
Component: statistics Version: trunk
Keywords: Cc:

Description

spin off from #494

Change History (19)

comment:1 Changed 22 months ago by Peter

Milestone: yat 0.x+yat 0.18
Status: newaccepted

comment:2 Changed 20 months ago by Peter

Milestone: yat 0.18yat 0.19

comment:3 Changed 20 months ago by Peter

In 4002:

Creating a private branch for refactoring of KendallScore? (refs #710)

comment:4 Changed 16 months ago by Peter

In 4037:

skeleton for new Ranking container. refs #710.

comment:5 Changed 10 months ago by Peter

In 4064:

first functioning version (tests pass) of Kendall class using the Ranking class. Split out the code in separate header and source files. Ranking class is still slow (linear) so Kendall::score is still quadratic. refs #710

comment:6 Changed 10 months ago by Peter

In 4065:

fix documentation; refs #710

comment:7 Changed 10 months ago by Peter

In 4070:

refs #710; add erase functions

comment:8 Changed 9 months ago by Peter

In 4071:

Add variables height_ and size_ in NodeBase?, which describes the longest distance to its leaves and the size of the subtree in which it is the root, respectively. Use these variables to calculate the ranking, which means the ranking now scales like the height rather than the number of nodes. refs #710

comment:9 Changed 9 months ago by Peter

In 4074:

add a destructor; refs #710

comment:10 Changed 9 months ago by Peter

In 4075:

fix some docs and get rid of function not used. refs #710

comment:11 Changed 9 months ago by Peter

In 4077:

implement insert with hint; refs #710

comment:12 Changed 9 months ago by Peter

In 4079:

store the right_most node, so it can be accessed in constant time (rather than logarithmic); refs #710

comment:13 Changed 9 months ago by Peter

In 4082:

add missing file; refs #710

comment:14 Changed 9 months ago by Peter

In 4083:

merge kendall-score branch into trunk. refs #710

comment:15 Changed 9 months ago by Peter

In 4084:

removing obsolete branch for kendall score (refs #710).

comment:16 Changed 9 months ago by Peter

Resolution: fixed
Status: acceptedclosed

In 4087:

extend docs; closes #710

comment:17 Changed 8 months ago by Peter

Resolution: fixed
Status: closedreopened

Some tests in kendall.test had been commented out and this ticket was closed prematurely.

comment:18 Changed 8 months ago by Peter

In 4100:

refs #710; activate tests and set XFAIL

comment:19 Changed 8 months ago by Peter

Resolution: fixed
Status: reopenedclosed

In 4103:

closes #710

Note: See TracTickets for help on using tickets.