Github user jinxing64 commented on the issue:
https://github.com/apache/spark/pull/16867
@kayousterhout @squito
Thanks a lot for your comments, really helpful :)
I really think median heap is a good idea. `slice` is `O(n)` and is not
most efficient.
I'm doing implementation for `MedianHeap`, which provides `add`, `remove`
and `getMedian` methods.
Yes, for both `TreeSet` and `MedianHeap`, when `handleSuccessfulTask`, we
are doing insertion with `O(log n)`, I did a
test(https://github.com/apache/spark/pull/17112) to measure the *sum of time*
cost by `TreeSet.add`. There are 100k tasks in this test. Results are: 372ms,
362ms, 458ms, 429ms, 363ms. Thus I think the `O(log n)` time complexity will
not be a problem.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [email protected] or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
