xtensor
Loading...
Searching...
No Matches
xsort.hpp
1/***************************************************************************
2 * Copyright (c) Johan Mabille, Sylvain Corlay and Wolf Vollprecht *
3 * Copyright (c) QuantStack *
4 * *
5 * Distributed under the terms of the BSD 3-Clause License. *
6 * *
7 * The full license is in the file LICENSE, distributed with this software. *
8 ****************************************************************************/
9
10#ifndef XTENSOR_SORT_HPP
11#define XTENSOR_SORT_HPP
12
13#include <algorithm>
14#include <cmath>
15#include <iterator>
16#include <utility>
17
18#include <xtl/xcompare.hpp>
19
20#include "../containers/xadapt.hpp"
21#include "../containers/xarray.hpp"
22#include "../containers/xtensor.hpp"
23#include "../core/xeval.hpp"
24#include "../core/xmath.hpp"
25#include "../core/xtensor_config.hpp"
26#include "../core/xtensor_forward.hpp"
27#include "../misc/xmanipulation.hpp"
28#include "../views/xindex_view.hpp"
29#include "../views/xslice.hpp" // for xnone
30#include "../views/xview.hpp"
31
32namespace xt
33{
40
41 namespace detail
42 {
43 template <class T>
44 std::ptrdiff_t adjust_secondary_stride(std::ptrdiff_t stride, T shape)
45 {
46 return stride != 0 ? stride : static_cast<std::ptrdiff_t>(shape);
47 }
48
49 template <class E>
50 inline std::ptrdiff_t get_secondary_stride(const E& ev)
51 {
52 if (ev.layout() == layout_type::row_major)
53 {
54 return adjust_secondary_stride(ev.strides()[ev.dimension() - 2], *(ev.shape().end() - 1));
55 }
56
57 return adjust_secondary_stride(ev.strides()[1], *(ev.shape().begin()));
58 }
59
60 template <class E>
61 inline std::size_t leading_axis_n_iters(const E& ev)
62 {
63 if (ev.layout() == layout_type::row_major)
64 {
65 return std::accumulate(
66 ev.shape().begin(),
67 ev.shape().end() - 1,
68 std::size_t(1),
69 std::multiplies<>()
70 );
71 }
72 return std::accumulate(ev.shape().begin() + 1, ev.shape().end(), std::size_t(1), std::multiplies<>());
73 }
74
75 template <class E, class F>
76 inline void call_over_leading_axis(E& ev, F&& fct)
77 {
78 XTENSOR_ASSERT(ev.dimension() >= 2);
79
80 // Pointer arithmetic needs a signed count. n_iters * secondary_stride is the
81 // size of the container (or the stride is 0 and n_iters does not matter),
82 // so n_iters fits in a ptrdiff_t.
83 const auto n_iters = static_cast<std::ptrdiff_t>(leading_axis_n_iters(ev));
84 const std::ptrdiff_t secondary_stride = get_secondary_stride(ev);
85
86 const auto begin = ev.data();
87 const auto end = begin + n_iters * secondary_stride;
88 for (auto iter = begin; iter != end; iter += secondary_stride)
89 {
90 fct(iter, iter + secondary_stride);
91 }
92 }
93
94 template <class E1, class E2, class F>
95 inline void call_over_leading_axis(E1& e1, E2& e2, F&& fct)
96 {
97 XTENSOR_ASSERT(e1.dimension() >= 2);
98 XTENSOR_ASSERT(e1.dimension() == e2.dimension());
99
100 // See above, n_iters fits in a ptrdiff_t.
101 const auto n_iters = static_cast<std::ptrdiff_t>(leading_axis_n_iters(e1));
102 const std::ptrdiff_t secondary_stride1 = get_secondary_stride(e1);
103 const std::ptrdiff_t secondary_stride2 = get_secondary_stride(e2);
104 XTENSOR_ASSERT(secondary_stride1 == secondary_stride2);
105
106 const auto begin1 = e1.data();
107 const auto end1 = begin1 + n_iters * secondary_stride1;
108 const auto begin2 = e2.data();
109 const auto end2 = begin2 + n_iters * secondary_stride2;
110 auto iter1 = begin1;
111 auto iter2 = begin2;
112 for (; (iter1 != end1) && (iter2 != end2); iter1 += secondary_stride1, iter2 += secondary_stride2)
113 {
114 fct(iter1, iter1 + secondary_stride1, iter2, iter2 + secondary_stride2);
115 }
116 }
117
118 template <class E>
119 inline std::size_t leading_axis(const E& e)
120 {
121 if (e.layout() == layout_type::row_major)
122 {
123 return e.dimension() - 1;
124 }
125 else if (e.layout() == layout_type::column_major)
126 {
127 return 0;
128 }
129 XTENSOR_THROW(std::runtime_error, "Layout not supported.");
130 }
131
132 // get permutations to transpose and reverse-transpose array
133 inline std::pair<dynamic_shape<std::size_t>, dynamic_shape<std::size_t>>
134 get_permutations(std::size_t dim, std::size_t ax, layout_type layout)
135 {
136 dynamic_shape<std::size_t> permutation(dim);
137 std::iota(permutation.begin(), permutation.end(), std::size_t(0));
138 permutation.erase(permutation.begin() + std::ptrdiff_t(ax));
139
140 if (layout == layout_type::row_major)
141 {
142 permutation.push_back(ax);
143 }
144 else
145 {
146 permutation.insert(permutation.begin(), ax);
147 }
148
149 // TODO find a more clever way to get reverse permutation?
150 dynamic_shape<std::size_t> reverse_permutation;
151 for (std::size_t i = 0; i < dim; ++i)
152 {
153 auto it = std::find(permutation.begin(), permutation.end(), i);
154 reverse_permutation.push_back(std::size_t(std::distance(permutation.begin(), it)));
155 }
156
157 return std::make_pair(std::move(permutation), std::move(reverse_permutation));
158 }
159
160 template <class R, class E, class F>
161 inline R map_axis(const E& e, std::ptrdiff_t axis, F&& lambda)
162 {
163 if (e.dimension() == 1)
164 {
165 R res = e;
166 lambda(res.begin(), res.end());
167 return res;
168 }
169
170 const std::size_t ax = normalize_axis(e.dimension(), axis);
171 if (ax == detail::leading_axis(e))
172 {
173 R res = e;
174 detail::call_over_leading_axis(res, std::forward<F>(lambda));
175 return res;
176 }
177
178 dynamic_shape<std::size_t> permutation, reverse_permutation;
179 std::tie(permutation, reverse_permutation) = get_permutations(e.dimension(), ax, e.layout());
180 R res = transpose(e, permutation);
181 detail::call_over_leading_axis(res, std::forward<F>(lambda));
182 res = transpose(res, reverse_permutation);
183 return res;
184 }
185
186 template <class VT>
187 struct flatten_sort_result_type_impl
188 {
189 using type = VT;
190 };
191
192 template <class VT, std::size_t N, layout_type L>
193 struct flatten_sort_result_type_impl<xtensor<VT, N, L>>
194 {
195 using type = xtensor<VT, 1, L>;
196 };
197
198 template <class VT, class S, layout_type L>
199 struct flatten_sort_result_type_impl<xtensor_fixed<VT, S, L>>
200 {
201 using type = xtensor_fixed<VT, xshape<fixed_compute_size<S>::value>, L>;
202 };
203
204 template <class VT>
205 struct flatten_sort_result_type : flatten_sort_result_type_impl<common_tensor_type_t<VT>>
206 {
207 };
208
209 template <class VT>
210 using flatten_sort_result_type_t = typename flatten_sort_result_type<VT>::type;
211
212 template <class E, class R = flatten_sort_result_type_t<E>>
213 inline auto flat_sort_impl(const xexpression<E>& e)
214 {
215 const auto& de = e.derived_cast();
216 R ev;
217 ev.resize({static_cast<typename R::shape_type::value_type>(de.size())});
218
219 std::copy(de.cbegin(), de.cend(), ev.begin());
220 std::sort(ev.begin(), ev.end());
221
222 return ev;
223 }
224 }
225
226 template <class E>
227 inline auto sort(const xexpression<E>& e, placeholders::xtuph /*t*/)
228 {
229 return detail::flat_sort_impl(e);
230 }
231
232 namespace detail
233 {
234 template <class T>
235 struct sort_eval_type
236 {
237 using type = typename T::temporary_type;
238 };
239
240 template <class T, std::size_t... I, layout_type L>
241 struct sort_eval_type<xtensor_fixed<T, fixed_shape<I...>, L>>
242 {
243 using type = xtensor<T, sizeof...(I), L>;
244 };
245 }
246
258 template <class E>
259 inline auto sort(const xexpression<E>& e, std::ptrdiff_t axis = -1)
260 {
261 using eval_type = typename detail::sort_eval_type<E>::type;
262
263 return detail::map_axis<eval_type>(
264 e.derived_cast(),
265 axis,
266 [](auto begin, auto end)
267 {
268 std::sort(begin, end);
269 }
270 );
271 }
272
273 /*****************************
274 * Implementation of argsort *
275 *****************************/
276
282 enum class sorting_method
283 {
294 };
295
296 namespace detail
297 {
298 template <class ConstRandomIt, class RandomIt, class Compare, class Method>
299 inline void argsort_iter(
300 ConstRandomIt data_begin,
301 [[maybe_unused]] ConstRandomIt data_end,
302 RandomIt idx_begin,
303 RandomIt idx_end,
304 Compare comp,
305 Method method
306 )
307 {
308 XTENSOR_ASSERT(std::distance(data_begin, data_end) >= 0);
309 XTENSOR_ASSERT(std::distance(idx_begin, idx_end) == std::distance(data_begin, data_end));
310
311 std::iota(idx_begin, idx_end, 0);
312 // The indices are in [0, std::distance(data_begin, data_end)), so they fit in
313 // the difference type of the data iterator.
314 using difference_type = typename std::iterator_traits<ConstRandomIt>::difference_type;
315 auto index_comp = [&](const auto i, const auto j)
316 {
317 return comp(
318 *(data_begin + static_cast<difference_type>(i)),
319 *(data_begin + static_cast<difference_type>(j))
320 );
321 };
322 switch (method)
323 {
325 {
326 std::sort(idx_begin, idx_end, index_comp);
327 }
329 {
330 std::stable_sort(idx_begin, idx_end, index_comp);
331 }
332 }
333 }
334
335 template <class ConstRandomIt, class RandomIt, class Method>
336 inline void
337 argsort_iter(ConstRandomIt data_begin, ConstRandomIt data_end, RandomIt idx_begin, RandomIt idx_end, Method method)
338 {
339 return argsort_iter(
340 std::move(data_begin),
341 std::move(data_end),
342 std::move(idx_begin),
343 std::move(idx_end),
344 [](const auto& x, const auto& y) -> bool
345 {
346 return x < y;
347 },
348 method
349 );
350 }
351
352 template <class VT, class T>
353 struct rebind_value_type
354 {
356 };
357
358 template <class VT, class EC, layout_type L>
359 struct rebind_value_type<VT, xarray<EC, L>>
360 {
361 using type = xarray<VT, L>;
362 };
363
364 template <class VT, class EC, std::size_t N, layout_type L>
365 struct rebind_value_type<VT, xtensor<EC, N, L>>
366 {
367 using type = xtensor<VT, N, L>;
368 };
369
370 template <class VT, class ET, class S, layout_type L>
371 struct rebind_value_type<VT, xtensor_fixed<ET, S, L>>
372 {
373 using type = xtensor_fixed<VT, S, L>;
374 };
375
376 template <class VT, class T>
377 struct flatten_rebind_value_type
378 {
379 using type = typename rebind_value_type<VT, T>::type;
380 };
381
382 template <class VT, class EC, std::size_t N, layout_type L>
383 struct flatten_rebind_value_type<VT, xtensor<EC, N, L>>
384 {
385 using type = xtensor<VT, 1, L>;
386 };
387
388 template <class VT, class ET, class S, layout_type L>
389 struct flatten_rebind_value_type<VT, xtensor_fixed<ET, S, L>>
390 {
391 using type = xtensor_fixed<VT, xshape<fixed_compute_size<S>::value>, L>;
392 };
393
394 template <class T>
395 struct argsort_result_type
396 {
397 using type = typename rebind_value_type<typename T::temporary_type::size_type, typename T::temporary_type>::type;
398 };
399
400 template <class T>
401 struct linear_argsort_result_type
402 {
403 using type = typename flatten_rebind_value_type<
404 typename T::temporary_type::size_type,
405 typename T::temporary_type>::type;
406 };
407
408 template <class E, class R = typename detail::linear_argsort_result_type<E>::type, class Method>
409 inline auto flatten_argsort_impl(const xexpression<E>& e, Method method)
410 {
411 const auto& de = e.derived_cast();
412
413 auto cit = de.template begin<layout_type::row_major>();
414 using const_iterator = decltype(cit);
415 auto ad = xiterator_adaptor<const_iterator, const_iterator>(cit, cit, de.size());
416
417 using result_type = R;
418 result_type result;
419 result.resize({de.size()});
420
421 detail::argsort_iter(de.cbegin(), de.cend(), result.begin(), result.end(), method);
422
423 return result;
424 }
425 }
426
427 template <class E>
428 inline auto
430 {
431 return detail::flatten_argsort_impl(e, method);
432 }
433
449 template <class E>
450 inline auto
451 argsort(const xexpression<E>& e, std::ptrdiff_t axis = -1, sorting_method method = sorting_method::quick)
452 {
453 using eval_type = typename detail::sort_eval_type<E>::type;
454 using result_type = typename detail::argsort_result_type<eval_type>::type;
455
456 const auto& de = e.derived_cast();
457
458 std::size_t ax = normalize_axis(de.dimension(), axis);
459
460 if (de.dimension() == 1)
461 {
462 return detail::flatten_argsort_impl<E, result_type>(e, method);
463 }
464
465 const auto argsort = [&method](auto res_begin, auto res_end, auto ev_begin, auto ev_end)
466 {
467 detail::argsort_iter(ev_begin, ev_end, res_begin, res_end, method);
468 };
469
470 if (ax == detail::leading_axis(de))
471 {
472 result_type res = result_type::from_shape(de.shape());
473 detail::call_over_leading_axis(res, de, argsort);
474 return res;
475 }
476
477 dynamic_shape<std::size_t> permutation, reverse_permutation;
478 std::tie(permutation, reverse_permutation) = detail::get_permutations(de.dimension(), ax, de.layout());
479 eval_type ev = transpose(de, permutation);
480 result_type res = result_type::from_shape(ev.shape());
481 detail::call_over_leading_axis(res, ev, argsort);
482 res = transpose(res, reverse_permutation);
483 return res;
484 }
485
486 /************************************************
487 * Implementation of partition and argpartition *
488 ************************************************/
489
490 namespace detail
491 {
503 template <class RandomIt, class Iter, class Compare>
504 inline void
505 partition_iter(RandomIt data_begin, RandomIt data_end, Iter kth_begin, Iter kth_end, Compare comp)
506 {
507 XTENSOR_ASSERT(std::distance(data_begin, data_end) >= 0);
508 XTENSOR_ASSERT(std::distance(kth_begin, kth_end) >= 0);
509
510 using idx_type = typename std::iterator_traits<Iter>::value_type;
511
512 idx_type k_last = static_cast<idx_type>(std::distance(data_begin, data_end));
513 for (; kth_begin != kth_end; ++kth_begin)
514 {
515 std::nth_element(data_begin, data_begin + *kth_begin, data_begin + k_last, std::move(comp));
516 k_last = *kth_begin;
517 }
518 }
519
520 template <class RandomIt, class Iter>
521 inline void partition_iter(RandomIt data_begin, RandomIt data_end, Iter kth_begin, Iter kth_end)
522 {
523 return partition_iter(
524 std::move(data_begin),
525 std::move(data_end),
526 std::move(kth_begin),
527 std::move(kth_end),
528 [](const auto& x, const auto& y) -> bool
529 {
530 return x < y;
531 }
532 );
533 }
534 }
535
563 template <class E, xtl::non_integral_concept C, class R = detail::flatten_sort_result_type_t<E>>
564 inline R partition(const xexpression<E>& e, C kth_container, placeholders::xtuph /*ax*/)
565 {
566 const auto& de = e.derived_cast();
567
568 R ev = R::from_shape({de.size()});
569 std::sort(kth_container.begin(), kth_container.end());
570
571 std::copy(de.linear_cbegin(), de.linear_cend(), ev.linear_begin()); // flatten
572
573 detail::partition_iter(ev.linear_begin(), ev.linear_end(), kth_container.rbegin(), kth_container.rend());
574
575 return ev;
576 }
577
578 template <class E, class I, std::size_t N, class R = detail::flatten_sort_result_type_t<E>>
579 inline R partition(const xexpression<E>& e, const I (&kth_container)[N], placeholders::xtuph tag)
580 {
581 return partition(
582 e,
583 xtl::forward_sequence<std::array<std::size_t, N>, decltype(kth_container)>(kth_container),
584 tag
585 );
586 }
587
588 template <class E, class R = detail::flatten_sort_result_type_t<E>>
589 inline R partition(const xexpression<E>& e, std::size_t kth, placeholders::xtuph tag)
590 {
591 return partition(e, std::array<std::size_t, 1>({kth}), tag);
592 }
593
594 template <class E, xtl::non_integral_concept C>
595 inline auto partition(const xexpression<E>& e, C kth_container, std::ptrdiff_t axis = -1)
596 {
597 using eval_type = typename detail::sort_eval_type<E>::type;
598
599 std::sort(kth_container.begin(), kth_container.end());
600
601 return detail::map_axis<eval_type>(
602 e.derived_cast(),
603 axis,
604 [&kth_container](auto begin, auto end)
605 {
606 detail::partition_iter(begin, end, kth_container.rbegin(), kth_container.rend());
607 }
608 );
609 }
610
611 template <class E, class T, std::size_t N>
612 inline auto partition(const xexpression<E>& e, const T (&kth_container)[N], std::ptrdiff_t axis = -1)
613 {
614 return partition(
615 e,
616 xtl::forward_sequence<std::array<std::size_t, N>, decltype(kth_container)>(kth_container),
617 axis
618 );
619 }
620
621 template <class E>
622 inline auto partition(const xexpression<E>& e, std::size_t kth, std::ptrdiff_t axis = -1)
623 {
624 return partition(e, std::array<std::size_t, 1>({kth}), axis);
625 }
626
654 template <
655 class E,
656 xtl::non_integral_concept C,
657 class R = typename detail::linear_argsort_result_type<typename detail::sort_eval_type<E>::type>::type>
658 inline R argpartition(const xexpression<E>& e, C kth_container, placeholders::xtuph)
659 {
660 using eval_type = typename detail::sort_eval_type<E>::type;
661 using result_type = typename detail::linear_argsort_result_type<eval_type>::type;
662
663 const auto& de = e.derived_cast();
664
665 result_type res = result_type::from_shape({de.size()});
666
667 std::sort(kth_container.begin(), kth_container.end());
668
669 std::iota(res.linear_begin(), res.linear_end(), 0);
670
671 detail::partition_iter(
672 res.linear_begin(),
673 res.linear_end(),
674 kth_container.rbegin(),
675 kth_container.rend(),
676 [&de](std::size_t a, std::size_t b)
677 {
678 return de[a] < de[b];
679 }
680 );
681
682 return res;
683 }
684
685 template <class E, class I, std::size_t N>
686 inline auto argpartition(const xexpression<E>& e, const I (&kth_container)[N], placeholders::xtuph tag)
687 {
688 return argpartition(
689 e,
690 xtl::forward_sequence<std::array<std::size_t, N>, decltype(kth_container)>(kth_container),
691 tag
692 );
693 }
694
695 template <class E>
696 inline auto argpartition(const xexpression<E>& e, std::size_t kth, placeholders::xtuph tag)
697 {
698 return argpartition(e, std::array<std::size_t, 1>({kth}), tag);
699 }
700
701 template <class E, xtl::non_integral_concept C>
702 inline auto argpartition(const xexpression<E>& e, C kth_container, std::ptrdiff_t axis = -1)
703 {
704 using eval_type = typename detail::sort_eval_type<E>::type;
705 using result_type = typename detail::argsort_result_type<eval_type>::type;
706
707 const auto& de = e.derived_cast();
708
709 if (de.dimension() == 1)
710 {
711 return argpartition<E, C, result_type>(e, std::forward<C>(kth_container), xnone());
712 }
713
714 std::sort(kth_container.begin(), kth_container.end());
715 const auto argpartition_w_kth =
716 [&kth_container](auto res_begin, auto res_end, auto ev_begin, auto /*ev_end*/)
717 {
718 std::iota(res_begin, res_end, 0);
719 detail::partition_iter(
720 res_begin,
721 res_end,
722 kth_container.rbegin(),
723 kth_container.rend(),
724 [&ev_begin](auto const& i, auto const& j)
725 {
726 return *(ev_begin + i) < *(ev_begin + j);
727 }
728 );
729 };
730
731 const std::size_t ax = normalize_axis(de.dimension(), axis);
732 if (ax == detail::leading_axis(de))
733 {
734 result_type res = result_type::from_shape(de.shape());
735 detail::call_over_leading_axis(res, de, argpartition_w_kth);
736 return res;
737 }
738
739 dynamic_shape<std::size_t> permutation, reverse_permutation;
740 std::tie(permutation, reverse_permutation) = detail::get_permutations(de.dimension(), ax, de.layout());
741 eval_type ev = transpose(de, permutation);
742 result_type res = result_type::from_shape(ev.shape());
743 detail::call_over_leading_axis(res, ev, argpartition_w_kth);
744 res = transpose(res, reverse_permutation);
745 return res;
746 }
747
748 template <class E, class I, std::size_t N>
749 inline auto argpartition(const xexpression<E>& e, const I (&kth_container)[N], std::ptrdiff_t axis = -1)
750 {
751 return argpartition(
752 e,
753 xtl::forward_sequence<std::array<std::size_t, N>, decltype(kth_container)>(kth_container),
754 axis
755 );
756 }
757
758 template <class E>
759 inline auto argpartition(const xexpression<E>& e, std::size_t kth, std::ptrdiff_t axis = -1)
760 {
761 return argpartition(e, std::array<std::size_t, 1>({kth}), axis);
762 }
763
764 /******************
765 * xt::quantile *
766 ******************/
767
768 namespace detail
769 {
770 template <class S, class I, class K, class O>
771 inline void select_indices_impl(
772 const S& shape,
773 const I& indices,
774 std::size_t axis,
775 std::size_t current_dim,
776 const K& current_index,
777 O& out
778 )
779 {
780 using id_t = typename K::value_type;
781 if ((current_dim < shape.size() - 1) && (current_dim == axis))
782 {
783 for (auto i : indices)
784 {
785 auto idx = current_index;
786 idx[current_dim] = i;
787 select_indices_impl(shape, indices, axis, current_dim + 1, idx, out);
788 }
789 }
790 else if ((current_dim < shape.size() - 1) && (current_dim != axis))
791 {
792 for (id_t i = 0; xtl::cmp_less(i, shape[current_dim]); ++i)
793 {
794 auto idx = current_index;
795 idx[current_dim] = i;
796 select_indices_impl(shape, indices, axis, current_dim + 1, idx, out);
797 }
798 }
799 else if ((current_dim == shape.size() - 1) && (current_dim == axis))
800 {
801 for (auto i : indices)
802 {
803 auto idx = current_index;
804 idx[current_dim] = i;
805 out.push_back(std::move(idx));
806 }
807 }
808 else if ((current_dim == shape.size() - 1) && (current_dim != axis))
809 {
810 for (id_t i = 0; xtl::cmp_less(i, shape[current_dim]); ++i)
811 {
812 auto idx = current_index;
813 idx[current_dim] = i;
814 out.push_back(std::move(idx));
815 }
816 }
817 }
818
819 template <class S, class I>
820 inline auto select_indices(const S& shape, const I& indices, std::size_t axis)
821 {
822 using index_type = xindex_type_t<S>;
823 auto out = std::vector<index_type>();
824 select_indices_impl(shape, indices, axis, 0, xtl::make_sequence<index_type>(shape.size()), out);
825 return out;
826 }
827
828 // TODO remove when fancy index views are implemented
829 // Poor man's indexing along a single axis as in NumPy a[:, [1, 3, 4]]
830 template <class E, class I>
831 inline auto fancy_indexing(E&& e, const I& indices, std::ptrdiff_t axis)
832 {
833 const std::size_t ax = normalize_axis(e.dimension(), axis);
834 using shape_t = xindex_type_t<typename std::decay_t<E>::shape_type>;
835 auto shape = xtl::forward_sequence<shape_t, decltype(e.shape())>(e.shape());
836 shape[ax] = indices.size();
837 return reshape_view(
838 index_view(std::forward<E>(e), select_indices(e.shape(), indices, ax)),
839 std::move(shape)
840 );
841 }
842
843 template <class T, class I, class P>
844 inline auto quantile_kth_gamma(std::size_t n, const P& probas, T alpha, T beta)
845 {
846 const auto m = alpha + probas * (T(1) - alpha - beta);
847 // Evaluting since reused a lot
848 const auto p_n_m = eval(probas * static_cast<T>(n) + m - 1);
849 // Previous (virtual) index, may be out of bounds
850 const auto j = floor(p_n_m);
851 const auto j_jp1 = concatenate(xtuple(j, j + 1));
852 // Both interpolation indices, k and k+1
853 const auto k_kp1 = xt::cast<std::size_t>(clip(j_jp1, T(0), T(n - 1)));
854 // Both interpolation coefficients, 1-gamma and gamma
855 const auto omg_g = concatenate(xtuple(T(1) - (p_n_m - j), p_n_m - j));
856 return std::make_pair(eval(k_kp1), eval(omg_g));
857 }
858
859 // TODO should implement unsqueeze rather
860 template <class S>
861 inline auto unsqueeze_shape(const S& shape, std::size_t axis)
862 {
863 XTENSOR_ASSERT(axis <= shape.size());
864 auto new_shape = xtl::forward_sequence<xt::svector<std::size_t>, decltype(shape)>(shape);
865 new_shape.insert(new_shape.begin() + axis, 1);
866 return new_shape;
867 }
868 }
869
899 template <class T = double, class E, class P>
900 inline auto quantile(E&& e, const P& probas, std::ptrdiff_t axis, T alpha, T beta)
901 {
902 XTENSOR_ASSERT(all(0. <= probas));
903 XTENSOR_ASSERT(all(probas <= 1.));
904 XTENSOR_ASSERT(0. <= alpha);
905 XTENSOR_ASSERT(alpha <= 1.);
906 XTENSOR_ASSERT(0. <= beta);
907 XTENSOR_ASSERT(beta <= 1.);
908
909 using tmp_shape_t = xindex_type_t<typename std::decay_t<E>::shape_type>;
910 using id_t = typename tmp_shape_t::value_type;
911
912 const std::size_t ax = normalize_axis(e.dimension(), axis);
913 const std::size_t n = e.shape()[ax];
914 auto kth_gamma = detail::quantile_kth_gamma<T, id_t, P>(n, probas, alpha, beta);
915
916 // Select relevant values for computing interpolating quantiles
917 auto e_partition = xt::partition(std::forward<E>(e), kth_gamma.first, axis);
918 auto e_kth = detail::fancy_indexing(std::move(e_partition), std::move(kth_gamma.first), axis);
919
920 // Reshape interpolation coefficients
921 auto gm1_g_shape = xtl::make_sequence<tmp_shape_t>(e.dimension(), 1);
922 gm1_g_shape[ax] = kth_gamma.second.size();
923 auto gm1_g_reshaped = reshape_view(std::move(kth_gamma.second), std::move(gm1_g_shape));
924
925 // Compute interpolation
926 // TODO(C++20) use (and create) xt::lerp in C++
927 auto e_kth_g = std::move(e_kth) * std::move(gm1_g_reshaped);
928 // Reshape pairwise interpolate for suming along new axis
929 auto e_kth_g_shape = detail::unsqueeze_shape(e_kth_g.shape(), ax);
930 e_kth_g_shape[ax] = 2;
931 e_kth_g_shape[ax + 1] /= 2;
932 auto quantiles = xt::sum(reshape_view(std::move(e_kth_g), std::move(e_kth_g_shape)), ax);
933 // Cannot do a transpose on a non-strided expression so we have to eval.
934 // quantiles has as many dimensions as e, so axis designates the same axis.
935 return moveaxis(eval(std::move(quantiles)), axis, 0);
936 }
937
938 // Static proba array overload
939 template <class T = double, class E, std::size_t N>
940 inline auto quantile(E&& e, const T (&probas)[N], std::ptrdiff_t axis, T alpha, T beta)
941 {
942 return quantile(std::forward<E>(e), adapt(probas, {N}), axis, alpha, beta);
943 }
944
954 template <class T = double, class E, class P>
955 inline auto quantile(E&& e, const P& probas, T alpha, T beta)
956 {
957 return quantile(xt::ravel(std::forward<E>(e)), probas, 0, alpha, beta);
958 }
959
960 // Static proba array overload
961 template <class T = double, class E, std::size_t N>
962 inline auto quantile(E&& e, const T (&probas)[N], T alpha, T beta)
963 {
964 return quantile(std::forward<E>(e), adapt(probas, {N}), alpha, beta);
965 }
966
993
1003 template <class T = double, class E, class P>
1004 inline auto
1005 quantile(E&& e, const P& probas, std::ptrdiff_t axis, quantile_method method = quantile_method::linear)
1006 {
1007 T alpha = 0.;
1008 T beta = 0.;
1009 switch (method)
1010 {
1012 {
1013 alpha = 0.;
1014 beta = 1.;
1015 break;
1016 }
1018 {
1019 alpha = 0.5;
1020 beta = 0.5;
1021 break;
1022 }
1024 {
1025 alpha = 0.;
1026 beta = 0.;
1027 break;
1028 }
1030 {
1031 alpha = 1.;
1032 beta = 1.;
1033 break;
1034 }
1036 {
1037 alpha = 1. / 3.;
1038 beta = 1. / 3.;
1039 break;
1040 }
1042 {
1043 alpha = 3. / 8.;
1044 beta = 3. / 8.;
1045 break;
1046 }
1047 }
1048 return quantile(std::forward<E>(e), probas, axis, alpha, beta);
1049 }
1050
1051 // Static proba array overload
1052 template <class T = double, class E, std::size_t N>
1053 inline auto
1054 quantile(E&& e, const T (&probas)[N], std::ptrdiff_t axis, quantile_method method = quantile_method::linear)
1055 {
1056 return quantile(std::forward<E>(e), adapt(probas, {N}), axis, method);
1057 }
1058
1070 template <class T = double, class E, class P>
1071 inline auto quantile(E&& e, const P& probas, quantile_method method = quantile_method::linear)
1072 {
1073 return quantile(xt::ravel(std::forward<E>(e)), probas, 0, method);
1074 }
1075
1076 // Static proba array overload
1077 template <class T = double, class E, std::size_t N>
1078 inline auto quantile(E&& e, const T (&probas)[N], quantile_method method = quantile_method::linear)
1079 {
1080 return quantile(std::forward<E>(e), adapt(probas, {N}), method);
1081 }
1082
1083 /****************
1084 * xt::median *
1085 ****************/
1086
1087 template <class E>
1088 inline typename std::decay_t<E>::value_type median(E&& e)
1089 {
1090 using value_type = typename std::decay_t<E>::value_type;
1091 auto sz = e.size();
1092 if (sz % 2 == 0)
1093 {
1094 std::size_t szh = sz / 2; // integer floor div
1095 std::array<std::size_t, 2> kth = {szh - 1, szh};
1096 auto values = xt::partition(xt::flatten(e), kth);
1097 return (values[kth[0]] + values[kth[1]]) / value_type(2);
1098 }
1099 else
1100 {
1101 std::array<std::size_t, 1> kth = {(sz - 1) / 2};
1102 auto values = xt::partition(xt::flatten(e), kth);
1103 return values[kth[0]];
1104 }
1105 }
1106
1120 template <class E>
1121 inline auto median(E&& e, std::ptrdiff_t axis)
1122 {
1123 std::size_t ax = normalize_axis(e.dimension(), axis);
1124 std::size_t sz = e.shape()[ax];
1125 xstrided_slice_vector sv(e.dimension(), xt::all());
1126
1127 if (sz % 2 == 0)
1128 {
1129 std::size_t szh = sz / 2; // integer floor div
1130 std::array<std::size_t, 2> kth = {szh - 1, szh};
1131 auto values = xt::partition(std::forward<E>(e), kth, static_cast<ptrdiff_t>(ax));
1132 sv[ax] = xt::range(szh - 1, szh + 1);
1133 return xt::mean(xt::strided_view(std::move(values), std::move(sv)), {ax});
1134 }
1135 else
1136 {
1137 std::size_t szh = (sz - 1) / 2;
1138 std::array<std::size_t, 1> kth = {(sz - 1) / 2};
1139 auto values = xt::partition(std::forward<E>(e), kth, static_cast<ptrdiff_t>(ax));
1140 sv[ax] = xt::range(szh, szh + 1);
1141 return xt::mean(xt::strided_view(std::move(values), std::move(sv)), {ax});
1142 }
1143 }
1144
1145 namespace detail
1146 {
1147 template <class T>
1148 struct argfunc_result_type
1149 {
1150 using type = xarray<std::size_t>;
1151 };
1152
1153 template <class T, std::size_t N>
1154 struct argfunc_result_type<xtensor<T, N>>
1155 {
1156 using type = xtensor<std::size_t, N - 1>;
1157 };
1158
1159 template <layout_type L, class E, class F>
1160 inline typename argfunc_result_type<E>::type arg_func_impl(const E& e, std::size_t axis, F&& cmp)
1161 {
1162 using eval_type = typename detail::sort_eval_type<E>::type;
1163 using value_type = typename E::value_type;
1164 using result_type = typename argfunc_result_type<E>::type;
1165 using result_shape_type = typename result_type::shape_type;
1166
1167 if (e.dimension() == 1)
1168 {
1169 auto begin = e.template begin<L>();
1170 auto end = e.template end<L>();
1171 // todo C++17 : constexpr
1172 if (std::is_same<F, std::less<value_type>>::value)
1173 {
1174 std::size_t i = static_cast<std::size_t>(std::distance(begin, std::min_element(begin, end)));
1175 return xtensor<size_t, 0>{i};
1176 }
1177 else
1178 {
1179 std::size_t i = static_cast<std::size_t>(std::distance(begin, std::max_element(begin, end)));
1180 return xtensor<size_t, 0>{i};
1181 }
1182 }
1183
1184 result_shape_type alt_shape;
1185 xt::resize_container(alt_shape, e.dimension() - 1);
1186
1187 // Excluding copy, copy all of shape except for axis
1188 std::copy(e.shape().cbegin(), e.shape().cbegin() + std::ptrdiff_t(axis), alt_shape.begin());
1189 std::copy(
1190 e.shape().cbegin() + std::ptrdiff_t(axis) + 1,
1191 e.shape().cend(),
1192 alt_shape.begin() + std::ptrdiff_t(axis)
1193 );
1194
1195 result_type result = result_type::from_shape(std::move(alt_shape));
1196 auto result_iter = result.template begin<L>();
1197
1198 auto arg_func_lambda = [&result_iter, &cmp](auto begin, auto end)
1199 {
1200 std::size_t idx = 0;
1201 value_type val = *begin;
1202 ++begin;
1203 for (std::size_t i = 1; begin != end; ++begin, ++i)
1204 {
1205 if (cmp(*begin, val))
1206 {
1207 val = *begin;
1208 idx = i;
1209 }
1210 }
1211 *result_iter = idx;
1212 ++result_iter;
1213 };
1214
1215 if (axis != detail::leading_axis(e))
1216 {
1217 dynamic_shape<std::size_t> permutation, reverse_permutation;
1218 std::tie(
1219 permutation,
1220 reverse_permutation
1221 ) = detail::get_permutations(e.dimension(), axis, e.layout());
1222
1223 // note: creating copy
1224 eval_type input = transpose(e, permutation);
1225 detail::call_over_leading_axis(input, arg_func_lambda);
1226 return result;
1227 }
1228 else
1229 {
1230 auto&& input = eval(e);
1231 detail::call_over_leading_axis(input, arg_func_lambda);
1232 return result;
1233 }
1234 }
1235 }
1236
1237 template <layout_type L = XTENSOR_DEFAULT_TRAVERSAL, class E>
1238 inline auto argmin(const xexpression<E>& e)
1239 {
1240 auto&& ed = eval(e.derived_cast());
1241 auto begin = ed.template begin<L>();
1242 auto end = ed.template end<L>();
1243 std::size_t i = static_cast<std::size_t>(std::distance(begin, std::min_element(begin, end)));
1244 return xtensor<size_t, 0>{i};
1245 }
1246
1257 template <layout_type L = XTENSOR_DEFAULT_TRAVERSAL, class E>
1258 inline auto argmin(const xexpression<E>& e, std::ptrdiff_t axis)
1259 {
1260 using value_type = typename E::value_type;
1261 auto&& ed = eval(e.derived_cast());
1262 std::size_t ax = normalize_axis(ed.dimension(), axis);
1263 return detail::arg_func_impl<L>(ed, ax, std::less<value_type>());
1264 }
1265
1266 template <layout_type L = XTENSOR_DEFAULT_TRAVERSAL, class E>
1267 inline auto argmax(const xexpression<E>& e)
1268 {
1269 auto&& ed = eval(e.derived_cast());
1270 auto begin = ed.template begin<L>();
1271 auto end = ed.template end<L>();
1272 std::size_t i = static_cast<std::size_t>(std::distance(begin, std::max_element(begin, end)));
1273 return xtensor<size_t, 0>{i};
1274 }
1275
1287 template <layout_type L = XTENSOR_DEFAULT_TRAVERSAL, class E>
1288 inline auto argmax(const xexpression<E>& e, std::ptrdiff_t axis)
1289 {
1290 using value_type = typename E::value_type;
1291 auto&& ed = eval(e.derived_cast());
1292 std::size_t ax = normalize_axis(ed.dimension(), axis);
1293 return detail::arg_func_impl<L>(ed, ax, std::greater<value_type>());
1294 }
1295
1303 template <class E>
1304 inline auto unique(const xexpression<E>& e)
1305 {
1306 auto sorted = sort(e, xnone());
1307 auto end = std::unique(sorted.begin(), sorted.end());
1308 std::size_t sz = static_cast<std::size_t>(std::distance(sorted.begin(), end));
1309 // TODO check if we can shrink the vector without reallocation
1310 using value_type = typename E::value_type;
1311 auto result = xtensor<value_type, 1>::from_shape({sz});
1312 std::copy(sorted.begin(), end, result.begin());
1313 return result;
1314 }
1315
1324 template <class E1, class E2>
1325 inline auto setdiff1d(const xexpression<E1>& ar1, const xexpression<E2>& ar2)
1326 {
1327 using value_type = typename E1::value_type;
1328
1329 auto unique1 = unique(ar1);
1330 auto unique2 = unique(ar2);
1331
1332 auto tmp = xtensor<value_type, 1>::from_shape({unique1.size()});
1333
1334 auto end = std::set_difference(unique1.begin(), unique1.end(), unique2.begin(), unique2.end(), tmp.begin());
1335
1336 std::size_t sz = static_cast<std::size_t>(std::distance(tmp.begin(), end));
1337
1338 auto result = xtensor<value_type, 1>::from_shape({sz});
1339
1340 std::copy(tmp.begin(), end, result.begin());
1341
1342 return result;
1343 }
1344}
1345
1346#endif
select_iterator< L > begin() noexcept
Returns an iterator to the first element of the expression.
Base class for xexpressions.
derived_type & derived_cast() &noexcept
Returns a reference to the actual derived type of the xexpression.
auto clip(E1 &&e1, E2 &&lo, E3 &&hi) noexcept -> detail::xfunction_type_t< math::clamp_fun, E1, E2, E3 >
Clip values between hi and lo.
Definition xmath.hpp:816
auto cast(E &&e) noexcept -> detail::xfunction_type_t< typename detail::cast< R >::functor, E >
Element-wise static_cast.
bool all(E &&e)
Any.
auto floor(E &&e) noexcept -> detail::xfunction_type_t< math::floor_fun, E >
floor function.
Definition xmath.hpp:1555
auto sum(E &&e, X &&axes, EVS es=EVS())
Sum of elements over given axes.
Definition xmath.hpp:1804
auto mean(E &&e, X &&axes, EVS es=EVS())
Mean of elements over given axes.
Definition xmath.hpp:1898
auto adapt(C &&container, const SC &shape, layout_type l=L)
Constructs:
auto eval(T &&t) -> std::enable_if_t< detail::is_container< std::decay_t< T > >::value, T && >
Force evaluation of xexpression.
Definition xeval.hpp:46
auto flatten(E &&e)
Return a flatten view of the given expression.
auto moveaxis(E &&e, std::ptrdiff_t src, std::ptrdiff_t dest)
Return a new expression with an axis move to a new position.
auto ravel(E &&e)
Return a flatten view of the given expression.
auto transpose(E &&e) noexcept
Returns a transpose view by reversing the dimensions of xexpression e.
quantile_method
Quantile interpolation method.
Definition xsort.hpp:979
auto unique(const xexpression< E > &e)
Find unique elements of a xexpression.
Definition xsort.hpp:1304
R partition(const xexpression< E > &e, C kth_container, placeholders::xtuph)
Partially sort xexpression.
Definition xsort.hpp:564
auto quantile(E &&e, const P &probas, std::ptrdiff_t axis, T alpha, T beta)
Compute quantiles over the given axis.
Definition xsort.hpp:900
auto setdiff1d(const xexpression< E1 > &ar1, const xexpression< E2 > &ar2)
Find the set difference of two xexpressions.
Definition xsort.hpp:1325
R argpartition(const xexpression< E > &e, C kth_container, placeholders::xtuph)
Partially sort arguments.
Definition xsort.hpp:658
@ weibull
Method 6 of (Hyndman and Fan, 1996) with alpha=0 and beta=0.
Definition xsort.hpp:985
@ interpolated_inverted_cdf
Method 4 of (Hyndman and Fan, 1996) with alpha=0 and beta=1.
Definition xsort.hpp:981
@ linear
Method 7 of (Hyndman and Fan, 1996) with alpha=1 and beta=1.
Definition xsort.hpp:987
@ normal_unbiased
Method 9 of (Hyndman and Fan, 1996) with alpha=3/8 and beta=3/8.
Definition xsort.hpp:991
@ median_unbiased
Method 8 of (Hyndman and Fan, 1996) with alpha=1/3 and beta=1/3.
Definition xsort.hpp:989
@ hazen
Method 5 of (Hyndman and Fan, 1996) with alpha=1/2 and beta=1/2.
Definition xsort.hpp:983
standard mathematical functions for xexpressions
auto range(A start_val, B stop_val)
Select a range from start_val to stop_val (excluded).
Definition xslice.hpp:737
std::vector< xstrided_slice< std::ptrdiff_t > > xstrided_slice_vector
vector of slices used to build a xstrided_view
xarray_container< uvector< T, A >, L, xt::svector< typename uvector< T, A >::size_type, 4, SA, true > > xarray
Alias template on xarray_container with default parameters for data container type and shape / stride...
auto concatenate(std::tuple< CT... > &&t, std::size_t axis=0)
Concatenates xexpressions along axis.
Definition xbuilder.hpp:830
layout_type
Definition xlayout.hpp:24
xfixed_container< T, FSH, L, Sharable > xtensor_fixed
Alias template on xfixed_container with default parameters for layout type.
xtensor_container< uvector< T, A >, N, L > xtensor
Alias template on xtensor_container with default parameters for data container type.
auto index_view(E &&e, I &&indices) noexcept
creates an indexview from a container of indices.
sorting_method
Sorting method.
Definition xsort.hpp:283
@ quick
Faster method but with no guarantee on preservation of order of equal elements https://en....
Definition xsort.hpp:288
@ stable
Slower method but with guarantee on preservation of order of equal elements https://en....
Definition xsort.hpp:293
auto strided_view(E &&e, S &&shape, X &&stride, std::size_t offset=0, layout_type layout=L) noexcept
Construct a strided view from an xexpression, shape, strides and offset.
auto xtuple(Types &&... args)
Creates tuples from arguments for concatenate and stack.
Definition xbuilder.hpp:707