LakshSingla commented on a change in pull request #11987:
URL: https://github.com/apache/druid/pull/11987#discussion_r756636906
##########
File path: core/src/main/java/org/apache/druid/math/expr/Function.java
##########
@@ -3422,6 +3422,100 @@ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
}
}
+ class ArrayContainsContiguousSubarrayFunction extends ArraysFunction
+ {
+ @Override
+ public String name()
+ {
+ return "array_contains_contiguous_subarray";
+ }
+
+ @Override
+ public boolean hasArrayOutput()
+ {
+ return true;
+ }
+
+ @Nullable
+ @Override
+ public ExpressionType getOutputType(Expr.InputBindingInspector inputTypes,
List<Expr> args)
+ {
+ return ExpressionType.LONG;
+ }
+
+ @Override
+ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
Review comment:
The implementation seems to have complexity of O(length1 * length2),
which seems suboptimal if we used something like
[KMP](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm).
Maybe something like
[Collections#indexOfSublist](https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#indexOfSubList%28java.util.List,%20java.util.List%29)
can be better, but it seems that it might be using the same algorithm
underneath. In any case, I think it could be optimized further, and we might
not wanna go with the naive implementation [String
searching](https://en.wikipedia.org/wiki/String-searching_algorithm#Examples_of_search_algorithms)
--
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]
