polars_core/frame/group_by/
into_groups.rs1use arrow::legacy::kernels::sort_partition::{
2 create_clean_partitions, partition_to_groups, partition_to_groups_amortized_varsize,
3};
4use polars_error::signals::try_raise_keyboard_interrupt;
5use polars_utils::total_ord::{ToTotalOrd, TotalHash};
6
7use super::*;
8use crate::chunked_array::cast::CastOptions;
9use crate::chunked_array::ops::row_encode::_get_rows_encoded_ca_unordered;
10use crate::config::verbose;
11use crate::series::BitRepr;
12use crate::utils::Container;
13use crate::utils::flatten::flatten_par;
14
15pub trait IntoGroupsType {
17 fn group_tuples(&self, _multithreaded: bool, _sorted: bool) -> PolarsResult<GroupsType> {
21 unimplemented!()
22 }
23}
24
25fn group_multithreaded<T: PolarsDataType>(ca: &ChunkedArray<T>) -> bool {
26 ca.len() > 1000 && POOL.current_num_threads() > 1
28}
29
30fn num_groups_proxy<T>(ca: &ChunkedArray<T>, multithreaded: bool, sorted: bool) -> GroupsType
31where
32 T: PolarsNumericType,
33 T::Native: TotalHash + TotalEq + DirtyHash + ToTotalOrd,
34 <T::Native as ToTotalOrd>::TotalOrdItem: Send + Sync + Copy + Hash + Eq + DirtyHash,
35{
36 if multithreaded && group_multithreaded(ca) {
37 let n_partitions = _set_partition_size();
38
39 if ca.null_count() == 0 {
41 let keys = ca
42 .downcast_iter()
43 .map(|arr| arr.values().as_slice())
44 .collect::<Vec<_>>();
45 group_by_threaded_slice(keys, n_partitions, sorted)
46 } else {
47 let keys = ca
48 .downcast_iter()
49 .map(|arr| arr.iter().map(|o| o.copied()))
50 .collect::<Vec<_>>();
51 group_by_threaded_iter(&keys, n_partitions, sorted)
52 }
53 } else if !ca.has_nulls() {
54 group_by(ca.into_no_null_iter(), sorted)
55 } else {
56 group_by(ca.iter(), sorted)
57 }
58}
59
60impl<T> ChunkedArray<T>
61where
62 T: PolarsNumericType,
63 T::Native: NumCast,
64{
65 fn create_groups_from_sorted(&self, multithreaded: bool) -> GroupsSlice {
66 if verbose() {
67 eprintln!("group_by keys are sorted; running sorted key fast path");
68 }
69 let arr = self.downcast_iter().next().unwrap();
70 if arr.is_empty() {
71 return GroupsSlice::default();
72 }
73 let mut values = arr.values().as_slice();
74 let null_count = arr.null_count();
75 let length = values.len();
76
77 if null_count == length {
79 return vec![[0, length as IdxSize]];
80 }
81
82 let mut nulls_first = false;
83 if null_count > 0 {
84 nulls_first = arr.get(0).is_none()
85 }
86
87 if nulls_first {
88 values = &values[null_count..];
89 } else {
90 values = &values[..length - null_count];
91 };
92
93 let n_threads = POOL.current_num_threads();
94 if multithreaded && n_threads > 1 {
95 let parts =
96 create_clean_partitions(values, n_threads, self.is_sorted_descending_flag());
97 let n_parts = parts.len();
98
99 let first_ptr = &values[0] as *const T::Native as usize;
100 let groups = parts.par_iter().enumerate().map(|(i, part)| {
101 let first_ptr = first_ptr as *const T::Native;
103
104 let part_first_ptr = &part[0] as *const T::Native;
105 let mut offset = unsafe { part_first_ptr.offset_from(first_ptr) } as IdxSize;
106
107 if nulls_first && i == 0 {
109 partition_to_groups(part, null_count as IdxSize, true, offset)
110 }
111 else if !nulls_first && i == n_parts - 1 {
113 partition_to_groups(part, null_count as IdxSize, false, offset)
114 }
115 else {
117 if nulls_first {
118 offset += null_count as IdxSize;
119 };
120
121 partition_to_groups(part, 0, false, offset)
122 }
123 });
124 let groups = POOL.install(|| groups.collect::<Vec<_>>());
125 flatten_par(&groups)
126 } else {
127 partition_to_groups(values, null_count as IdxSize, nulls_first, 0)
128 }
129 }
130}
131
132#[cfg(all(feature = "dtype-categorical", feature = "performant"))]
133impl<T: PolarsCategoricalType> IntoGroupsType for CategoricalChunked<T>
134where
135 ChunkedArray<T::PolarsPhysical>: IntoGroupsType,
136{
137 fn group_tuples(&self, multithreaded: bool, sorted: bool) -> PolarsResult<GroupsType> {
138 self.phys.group_tuples(multithreaded, sorted)
139 }
140}
141
142impl<T> IntoGroupsType for ChunkedArray<T>
143where
144 T: PolarsNumericType,
145 T::Native: TotalHash + TotalEq + DirtyHash + ToTotalOrd,
146 <T::Native as ToTotalOrd>::TotalOrdItem: Send + Sync + Copy + Hash + Eq + DirtyHash,
147{
148 fn group_tuples(&self, multithreaded: bool, sorted: bool) -> PolarsResult<GroupsType> {
149 if self.is_sorted_ascending_flag() || self.is_sorted_descending_flag() {
151 return Ok(GroupsType::Slice {
153 groups: self.rechunk().create_groups_from_sorted(multithreaded),
154 rolling: false,
155 });
156 }
157
158 let out = match self.dtype() {
159 DataType::Float32 => {
160 let ca: &Float32Chunked = unsafe {
162 &*(self as *const ChunkedArray<T> as *const ChunkedArray<Float32Type>)
163 };
164 num_groups_proxy(ca, multithreaded, sorted)
165 },
166 DataType::Float64 => {
167 let ca: &Float64Chunked = unsafe {
169 &*(self as *const ChunkedArray<T> as *const ChunkedArray<Float64Type>)
170 };
171 num_groups_proxy(ca, multithreaded, sorted)
172 },
173 _ => match self.to_bit_repr() {
174 BitRepr::U8(ca) => num_groups_proxy(&ca, multithreaded, sorted),
175 BitRepr::U16(ca) => num_groups_proxy(&ca, multithreaded, sorted),
176 BitRepr::U32(ca) => num_groups_proxy(&ca, multithreaded, sorted),
177 BitRepr::U64(ca) => num_groups_proxy(&ca, multithreaded, sorted),
178 #[cfg(feature = "dtype-i128")]
179 BitRepr::I128(ca) => num_groups_proxy(&ca, multithreaded, sorted),
180 },
181 };
182 try_raise_keyboard_interrupt();
183 Ok(out)
184 }
185}
186impl IntoGroupsType for BooleanChunked {
187 fn group_tuples(&self, mut multithreaded: bool, sorted: bool) -> PolarsResult<GroupsType> {
188 multithreaded &= POOL.current_num_threads() > 1;
189
190 #[cfg(feature = "performant")]
191 {
192 let ca = self
193 .cast_with_options(&DataType::UInt8, CastOptions::Overflowing)
194 .unwrap();
195 let ca = ca.u8().unwrap();
196 ca.group_tuples(multithreaded, sorted)
197 }
198 #[cfg(not(feature = "performant"))]
199 {
200 let ca = self
201 .cast_with_options(&DataType::UInt32, CastOptions::Overflowing)
202 .unwrap();
203 let ca = ca.u32().unwrap();
204 ca.group_tuples(multithreaded, sorted)
205 }
206 }
207}
208
209impl IntoGroupsType for StringChunked {
210 #[allow(clippy::needless_lifetimes)]
211 fn group_tuples<'a>(&'a self, multithreaded: bool, sorted: bool) -> PolarsResult<GroupsType> {
212 self.as_binary().group_tuples(multithreaded, sorted)
213 }
214}
215
216impl IntoGroupsType for BinaryChunked {
217 #[allow(clippy::needless_lifetimes)]
218 fn group_tuples<'a>(
219 &'a self,
220 mut multithreaded: bool,
221 sorted: bool,
222 ) -> PolarsResult<GroupsType> {
223 if self.is_sorted_any() && !self.has_nulls() && self.n_chunks() == 1 {
224 let arr = self.downcast_get(0).unwrap();
225 let values = arr.values_iter();
226 let mut out = Vec::with_capacity(values.len() / 30);
227 partition_to_groups_amortized_varsize(values, arr.len() as _, 0, false, 0, &mut out);
228 return Ok(GroupsType::Slice {
229 groups: out,
230 rolling: false,
231 });
232 }
233
234 multithreaded &= POOL.current_num_threads() > 1;
235 let bh = self.to_bytes_hashes(multithreaded, Default::default());
236
237 let out = if multithreaded {
238 let n_partitions = bh.len();
239 let bh = bh.iter().map(|v| v.as_slice()).collect::<Vec<_>>();
241 group_by_threaded_slice(bh, n_partitions, sorted)
242 } else {
243 group_by(bh[0].iter(), sorted)
244 };
245 try_raise_keyboard_interrupt();
246 Ok(out)
247 }
248}
249
250impl IntoGroupsType for BinaryOffsetChunked {
251 #[allow(clippy::needless_lifetimes)]
252 fn group_tuples<'a>(
253 &'a self,
254 mut multithreaded: bool,
255 sorted: bool,
256 ) -> PolarsResult<GroupsType> {
257 if self.is_sorted_any() && !self.has_nulls() && self.n_chunks() == 1 {
258 let arr = self.downcast_get(0).unwrap();
259 let values = arr.values_iter();
260 let mut out = Vec::with_capacity(values.len() / 30);
261 partition_to_groups_amortized_varsize(values, arr.len() as _, 0, false, 0, &mut out);
262 return Ok(GroupsType::Slice {
263 groups: out,
264 rolling: false,
265 });
266 }
267 multithreaded &= POOL.current_num_threads() > 1;
268 let bh = self.to_bytes_hashes(multithreaded, Default::default());
269
270 let out = if multithreaded {
271 let n_partitions = bh.len();
272 let bh = bh.iter().map(|v| v.as_slice()).collect::<Vec<_>>();
274 group_by_threaded_slice(bh, n_partitions, sorted)
275 } else {
276 group_by(bh[0].iter(), sorted)
277 };
278 Ok(out)
279 }
280}
281
282impl IntoGroupsType for ListChunked {
283 #[allow(clippy::needless_lifetimes)]
284 #[allow(unused_variables)]
285 fn group_tuples<'a>(
286 &'a self,
287 mut multithreaded: bool,
288 sorted: bool,
289 ) -> PolarsResult<GroupsType> {
290 multithreaded &= POOL.current_num_threads() > 1;
291 let by = &[self.clone().into_column()];
292 let ca = if multithreaded {
293 encode_rows_vertical_par_unordered(by).unwrap()
294 } else {
295 _get_rows_encoded_ca_unordered(PlSmallStr::EMPTY, by).unwrap()
296 };
297
298 ca.group_tuples(multithreaded, sorted)
299 }
300}
301
302#[cfg(feature = "dtype-array")]
303impl IntoGroupsType for ArrayChunked {
304 #[allow(clippy::needless_lifetimes)]
305 #[allow(unused_variables)]
306 fn group_tuples<'a>(
307 &'a self,
308 mut multithreaded: bool,
309 sorted: bool,
310 ) -> PolarsResult<GroupsType> {
311 multithreaded &= POOL.current_num_threads() > 1;
312 let by = &[self.clone().into_column()];
313 let ca = if multithreaded {
314 encode_rows_vertical_par_unordered(by).unwrap()
315 } else {
316 _get_rows_encoded_ca_unordered(PlSmallStr::EMPTY, by).unwrap()
317 };
318 ca.group_tuples(multithreaded, sorted)
319 }
320}
321
322#[cfg(feature = "object")]
323impl<T> IntoGroupsType for ObjectChunked<T>
324where
325 T: PolarsObject,
326{
327 fn group_tuples(&self, _multithreaded: bool, sorted: bool) -> PolarsResult<GroupsType> {
328 Ok(group_by(self.into_iter(), sorted))
329 }
330}