belliottsmith commented on code in PR #207:
URL: https://github.com/apache/cassandra-accord/pull/207#discussion_r2185127951
##########
accord-core/src/main/java/accord/utils/SortedArrays.java:
##########
@@ -1793,4 +1794,29 @@ private static void swap(int[] values, int i, int j)
values[i] = values[j];
values[j] = t;
}
+
+ public static <T extends Comparable<? super T>> BitSet
toBitSet(SortedArrays.SortedArrayList<T> src,
+
SortedArrays.SortedArrayList<T> subset)
+ {
+ BitSet bitSet = new BitSet(src.size());
+ for (int i = 0; i < src.size(); i++)
+ {
+ if (subset.contains(src.get(i)))
Review Comment:
we should use `foldlIntersection` for O(n) versus O(n.lg(n)) complexity
e.g.
`return foldlIntersection(superset.array, 0, superset.array.length,
subset.array, 0, subset.array.length, (i, bs, li, ri) -> { bs.set(li); return
bs; }, new SimpleBitSet(superset.size()));`
This does require copying foldlIntersection to support operating over
objects rather than long:
```
@Inline
public static <T extends Comparable<? super T>, V> V
foldlIntersection(T[] as, int ai, int alim, T[] bs, int bi, int blim,
IndexedFoldIntersect<? super T, V> fold, V accumulate)
{
return foldlIntersection(1, Comparable::compareTo, as, ai, alim, bs,
bi, blim, fold, accumulate);
}
@Inline
public static <T, V> V foldlIntersection(int aiMatchIncrement,
AsymmetricComparator<? super T, ? super T> comparator, T[] as, int ai, int
alim, T[] bs, int bi, int blim, IndexedFoldIntersect<? super T, V> fold, V
accumulate)
{
while (true)
{
long abi = findNextIntersection(as, ai, alim, bs, bi, blim,
comparator);
if (abi < 0)
break;
ai = (int)(abi);
bi = (int)(abi >>> 32);
accumulate = fold.apply(as[ai], accumulate, ai, bi);
ai += aiMatchIncrement;
++bi;
}
return accumulate;
}
```
and copying IndexedFoldIntersectToLong to IndexedFoldIntersect:
```
package accord.utils;
public interface IndexedFoldIntersect<P1, Accumulate>
{
/**
* Apply some merge function accepting a constant object parameter p1,
and the prior output of this function
* or the initial value, to some element of a collection, with the index
of the element provided.
*
* This function is used for efficiently folding over some subset of a
collection.
*/
Accumulate apply(P1 p1, Accumulate p2, int leftIndex, int rightIndex);
}
```
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
