thetumbled commented on code in PR #21085:
URL: https://github.com/apache/pulsar/pull/21085#discussion_r1310141718
##########
pulsar-broker/src/main/java/org/apache/pulsar/broker/loadbalance/extensions/models/TopKBundles.java:
##########
@@ -132,6 +133,42 @@ static void partitionSort(List<Map.Entry<String, ? extends
Comparable>> arr, int
Collections.sort(arr.subList(0, end), (a, b) ->
b.getValue().compareTo(a.getValue()));
}
+ public static <T> void partitionSort(List<Map.Entry<String, T>> arr, int
k, Comparator<T> comparator) {
+ int start = 0;
+ int end = arr.size() - 1;
+ int target = k - 1;
+ while (start < end) {
+ int lo = start;
+ int hi = end;
+ int mid = lo;
+ var pivot = arr.get(hi).getValue();
+ while (mid <= hi) {
+ int cmp = comparator.compare(pivot, arr.get(mid).getValue());
+ if (cmp < 0) {
+ var tmp = arr.get(lo);
+ arr.set(lo++, arr.get(mid));
+ arr.set(mid++, tmp);
+ } else if (cmp > 0) {
+ var tmp = arr.get(mid);
+ arr.set(mid, arr.get(hi));
+ arr.set(hi--, tmp);
+ } else {
+ mid++;
+ }
+ }
+ if (lo <= target && target < mid) {
+ end = lo;
+ break;
+ }
+ if (target < lo) {
+ end = lo - 1;
+ } else {
+ start = mid;
+ }
+ }
+ Collections.sort(arr.subList(0, end), (a, b) ->
comparator.compare(b.getValue(), a.getValue()));
Review Comment:
I imitate the logic implemented by
https://github.com/apache/pulsar/blob/ee5ac8607ebd7f90843789d4eead48de8600c1f0/pulsar-broker/src/main/java/org/apache/pulsar/broker/loadbalance/extensions/models/TopKBundles.java#L132-L132
I think we should make them consistent.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
