Jefffrey commented on code in PR #23460:
URL: https://github.com/apache/datafusion/pull/23460#discussion_r3578270631
##########
datafusion/functions/src/unicode/find_in_set.rs:
##########
@@ -329,16 +334,34 @@ where
let nulls = string_array.nulls().cloned();
let zero = T::Native::from_usize(0).unwrap();
+ // The set (`str_list`) is constant across all rows. For a large set, the
+ // per-row `position` linear scan is O(set_len). Building a lookup from
each
+ // distinct entry to its 1-based position once turns each row into an O(1)
+ // probe (first occurrence wins, exactly matching `position`). Below the
+ // threshold the linear scan's small constant factor is faster, so the map
is
+ // built at most once here rather than per row.
+ let map: Option<HashMap<&str, usize>> =
+ (str_list.len() >= FIND_IN_SET_LOOKUP_THRESHOLD).then(|| {
+ let mut map = HashMap::with_capacity(str_list.len());
+ for (idx, entry) in str_list.iter().enumerate() {
+ map.entry(*entry).or_insert(idx + 1);
+ }
+ map
+ });
+
let values: Vec<T::Native> = (0..len)
.map(|i| {
if nulls.as_ref().is_some_and(|n| n.is_null(i)) {
return zero;
}
let string = string_array.value(i);
- let position = str_list
- .iter()
- .position(|s| *s == string)
- .map_or(0, |idx| idx + 1);
+ let position = match &map {
Review Comment:
should we pull the match on the map outside the loop or doesnt make too much
of a difference?
--
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]
