[
https://issues.apache.org/jira/browse/MATH-169?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12722348#action_12722348
]
Eugene Kirpichov commented on MATH-169:
---------------------------------------
Rolling percentiles seems like an interesting and useful thing to do; however,
the implementation looks to me like it might have poor performance under some
circumstances.
Namely, the SortedDeque class uses a LinkedList for storing items in order, and
does a Collections.binarySearch on it.
However, Collections.binarySearch is very inefficient for the LinkedList:
actually, so inefficient that a linear search is much faster.
If you are maintaining a fixed-size sorted queue, I'd suggest you to use a
binary heap; when it is full and a new item goes in, insert the new item and
delete the minimum from the heap. One might simply use a PriorityQueue, or
implement a heap of double's for greater efficiency.
> Rolling statistics
> ------------------
>
> Key: MATH-169
> URL: https://issues.apache.org/jira/browse/MATH-169
> Project: Commons Math
> Issue Type: Improvement
> Reporter: Bradford N. Cross
> Assignee: Phil Steitz
> Fix For: 2.1
>
> Attachments: FirstRollingPatch, RankRollingPatch
>
>
> Rolling statistics with optimized calculation algorithms.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
