1#ifndef TATAMI_DELAYED_SUBSET_UNIQUE_HPP
2#define TATAMI_DELAYED_SUBSET_UNIQUE_HPP
23namespace DelayedSubsetUnique_internal {
25template<
typename Index_>
26struct DenseParallelResults {
27 std::vector<Index_> sorted;
28 std::vector<Index_> permutation;
31template<
typename Index_,
class SubsetStorage_,
class ToIndex_>
32DenseParallelResults<Index_> format_dense_parallel(
const SubsetStorage_& subset,
const Index_ len,
const ToIndex_ to_index) {
33 std::vector<std::pair<Index_, Index_> > collected;
34 collected.reserve(len);
35 for (Index_ i = 0; i < len; ++i) {
36 collected.emplace_back(subset[to_index(i)], i);
38 std::sort(collected.begin(), collected.end());
40 DenseParallelResults<Index_> output;
41 output.sorted.reserve(len);
42 output.permutation.reserve(len);
43 for (
const auto& pp : collected) {
44 output.sorted.push_back(pp.first);
45 output.permutation.push_back(pp.second);
51template<
bool oracle_,
typename Value_,
typename Index_>
52class ParallelDense final :
public DenseExtractor<oracle_, Value_, Index_> {
54 template<
class SubsetStorage_>
56 const Matrix<Value_, Index_>& matrix,
57 const SubsetStorage_& subset,
59 MaybeOracle<oracle_, Index_> oracle,
62 auto processed = format_dense_parallel<Index_>(subset, subset.size(), [&](Index_ i) -> Index_ { return i; });
63 initialize(matrix, std::move(processed), row, std::move(oracle), opt);
66 template<
class SubsetStorage_>
68 const Matrix<Value_, Index_>& matrix,
69 const SubsetStorage_& subset,
71 MaybeOracle<oracle_, Index_> oracle,
72 const Index_ block_start,
73 const Index_ block_length,
76 auto processed = format_dense_parallel<Index_>(subset, block_length, [&](Index_ i) -> Index_ {
return i + block_start; });
77 initialize(matrix, std::move(processed), row, std::move(oracle), opt);
80 template<
class SubsetStorage_>
82 const Matrix<Value_, Index_>& matrix,
83 const SubsetStorage_& subset,
85 MaybeOracle<oracle_, Index_> oracle,
86 VectorPtr<Index_> indices_ptr,
89 const auto& indices = *indices_ptr;
90 auto processed = format_dense_parallel<Index_>(subset, indices.size(), [&](Index_ i) -> Index_ { return indices[i]; });
91 initialize(matrix, std::move(processed), row, std::move(oracle), opt);
96 const Matrix<Value_, Index_>& matrix,
97 DenseParallelResults<Index_> processed,
99 MaybeOracle<oracle_, Index_> oracle,
103 my_ext = new_extractor<false, oracle_>(matrix, row, std::move(oracle), std::move(processed.sorted), opt);
104 my_permutation = std::move(processed.permutation);
108 const Value_* fetch(
const Index_ i, Value_*
const buffer) {
109 auto src = my_ext->fetch(i, my_holding_vbuffer.data());
114 for (
const auto p : my_permutation) {
123 std::unique_ptr<DenseExtractor<oracle_, Value_, Index_> > my_ext;
124 std::vector<Value_> my_holding_vbuffer;
125 std::vector<Index_> my_permutation;
128template<
typename Index_,
class SubsetStorage_,
class ToIndex_>
129std::vector<Index_> format_sparse_parallel(
const SubsetStorage_& subset,
const Index_ len,
const ToIndex_ to_index) {
130 std::vector<Index_> collected;
131 collected.reserve(len);
132 for (Index_ i = 0; i < len; ++i) {
133 collected.emplace_back(subset[to_index(i)]);
135 std::sort(collected.begin(), collected.end());
139template<
bool oracle_,
typename Value_,
typename Index_>
140class ParallelSparse final :
public SparseExtractor<oracle_, Value_, Index_> {
142 template<
class SubsetStorage_>
144 const Matrix<Value_, Index_>& matrix,
145 const SubsetStorage_& subset,
146 const std::vector<Index_>& remap,
148 MaybeOracle<oracle_, Index_> oracle,
153 auto processed = format_sparse_parallel<Index_>(subset, subset.size(), [](Index_ i) -> Index_ { return i; });
154 initialize(matrix, std::move(processed), row, std::move(oracle), opt);
157 template<
class SubsetStorage_>
159 const Matrix<Value_, Index_>& matrix,
160 const SubsetStorage_& subset,
161 const std::vector<Index_>& remap,
163 MaybeOracle<oracle_, Index_> oracle,
164 const Index_ block_start,
165 const Index_ block_length,
170 auto processed = format_sparse_parallel<Index_>(subset, block_length, [&](Index_ i) -> Index_ {
return i + block_start; });
171 initialize(matrix, std::move(processed), row, std::move(oracle), opt);
174 template<
class SubsetStorage_>
176 const Matrix<Value_, Index_>& matrix,
177 const SubsetStorage_& subset,
178 const std::vector<Index_>& remap,
180 MaybeOracle<oracle_, Index_> oracle,
181 VectorPtr<Index_> indices_ptr,
186 const auto& indices = *indices_ptr;
187 auto processed = format_sparse_parallel<Index_>(subset, indices.size(), [&](Index_ i) -> Index_ { return indices[i]; });
188 initialize(matrix, std::move(processed), row, std::move(oracle), opt);
192 void initialize(
const Matrix<Value_, Index_>& matrix, std::vector<Index_> sorted,
const bool row, MaybeOracle<oracle_, Index_> oracle, Options opt) {
193 my_needs_value = opt.sparse_extract_value;
194 my_needs_index = opt.sparse_extract_index;
195 my_needs_sort = opt.sparse_ordered_index;
199 if (!my_needs_sort) {
200 if (my_needs_index) {
204 }
else if (my_needs_value) {
205 opt.sparse_extract_index =
true;
206 my_sortspace.reserve(sorted.size());
207 if (my_needs_index) {
214 }
else if (my_needs_index) {
218 my_ext = new_extractor<true, oracle_>(matrix, row, std::move(oracle), std::move(sorted), opt);
222 SparseRange<Value_, Index_> fetch(
const Index_ i, Value_*
const value_buffer, Index_*
const index_buffer) {
223 auto input = my_ext->fetch(i, value_buffer, (my_holding_ibuffer.empty() ? index_buffer : my_holding_ibuffer.data()));
227 if (!my_needs_sort) {
228 if (my_needs_index) {
229 for (Index_ i = 0; i < input.number; ++i) {
230 index_buffer[i] = my_remapping[input.index[i]];
232 input.index = index_buffer;
235 }
else if (my_needs_value) {
238 my_sortspace.clear();
239 for (Index_ i = 0; i < input.number; ++i) {
240 my_sortspace.emplace_back(my_remapping[input.index[i]], input.value[i]);
242 std::sort(my_sortspace.begin(), my_sortspace.end());
244 auto vcopy = value_buffer;
245 for (
const auto& ss : my_sortspace) {
249 input.value = value_buffer;
251 if (my_needs_index) {
252 auto icopy = index_buffer;
253 for (
const auto& ss : my_sortspace) {
257 input.index = index_buffer;
262 }
else if (my_needs_index) {
263 for (Index_ i = 0; i < input.number; ++i) {
264 index_buffer[i] = my_remapping[input.index[i]];
266 std::sort(index_buffer, index_buffer + input.number);
267 input.index = index_buffer;
274 const std::vector<Index_>& my_remapping;
275 std::unique_ptr<SparseExtractor<oracle_, Value_, Index_> > my_ext;
276 bool my_needs_value, my_needs_index, my_needs_sort;
277 std::vector<std::pair<Index_, Value_> > my_sortspace;
278 std::vector<Index_> my_holding_ibuffer;
297template<
typename Value_,
typename Index_,
class SubsetStorage_>
310 SubsetStorage_ subset,
312 const bool check =
true
314 my_matrix(std::move(matrix)),
315 my_subset(std::move(subset)),
318 const Index_ fulldim = my_by_row ? my_matrix->nrow() : my_matrix->ncol();
319 const auto nsub = my_subset.size();
323 for (I<
decltype(nsub)> i = 0; i < nsub; ++i) {
324 auto& found = checks[my_subset[i]];
326 throw std::runtime_error(
"my_subset should be unique");
333 for (I<
decltype(nsub)> i = 0; i < nsub; ++i) {
334 my_mapping_single[my_subset[i]] = i;
339 std::shared_ptr<const Matrix<Value_, Index_> > my_matrix;
340 SubsetStorage_ my_subset;
342 std::vector<Index_> my_mapping_single;
347 return my_subset.size();
349 return my_matrix->nrow();
355 return my_matrix->ncol();
357 return my_subset.size();
362 return my_matrix->is_sparse();
366 return my_matrix->is_sparse_proportion();
370 return my_matrix->prefer_rows();
374 return my_matrix->prefer_rows_proportion();
378 return my_matrix->uses_oracle(row);
393 template<
typename ... Args_>
394 std::unique_ptr<MyopicDenseExtractor<Value_, Index_> > populate_myopic_dense(
398 if (row == my_by_row) {
399 return std::make_unique<subset_utils::MyopicPerpendicularDense<Value_, Index_, SubsetStorage_> >(
403 std::forward<Args_>(args)...
406 return std::make_unique<DelayedSubsetUnique_internal::ParallelDense<false, Value_, Index_> >(
411 std::forward<Args_>(args)...
417 std::unique_ptr<MyopicDenseExtractor<Value_, Index_> >
dense(
421 return populate_myopic_dense(row, opt);
424 std::unique_ptr<MyopicDenseExtractor<Value_, Index_> >
dense(
426 const Index_ block_start,
427 const Index_ block_length,
430 return populate_myopic_dense(row, block_start, block_length, opt);
433 std::unique_ptr<MyopicDenseExtractor<Value_, Index_> >
dense(
438 return populate_myopic_dense(row, std::move(indices_ptr), opt);
445 template<
typename ... Args_>
446 std::unique_ptr<MyopicSparseExtractor<Value_, Index_> > populate_myopic_sparse(
450 if (row == my_by_row) {
451 return std::make_unique<subset_utils::MyopicPerpendicularSparse<Value_, Index_, SubsetStorage_> >(
455 std::forward<Args_>(args)...
458 return std::make_unique<DelayedSubsetUnique_internal::ParallelSparse<false, Value_, Index_> >(
464 std::forward<Args_>(args)...
470 std::unique_ptr<MyopicSparseExtractor<Value_, Index_> >
sparse(
474 return populate_myopic_sparse(row, opt);
477 std::unique_ptr<MyopicSparseExtractor<Value_, Index_> >
sparse(
479 const Index_ block_start,
480 const Index_ block_length,
483 return populate_myopic_sparse(row, block_start, block_length, opt);
486 std::unique_ptr<MyopicSparseExtractor<Value_, Index_> >
sparse(
491 return populate_myopic_sparse(row, std::move(indices_ptr), opt);
498 template<
typename ... Args_>
499 std::unique_ptr<OracularDenseExtractor<Value_, Index_> > populate_oracular_dense(
504 if (row == my_by_row) {
505 return std::make_unique<subset_utils::OracularPerpendicularDense<Value_, Index_> >(
510 std::forward<Args_>(args)...
513 return std::make_unique<DelayedSubsetUnique_internal::ParallelDense<true, Value_, Index_> >(
518 std::forward<Args_>(args)...
524 std::unique_ptr<OracularDenseExtractor<Value_, Index_> >
dense(
529 return populate_oracular_dense(row, std::move(oracle), opt);
532 std::unique_ptr<OracularDenseExtractor<Value_, Index_> >
dense(
535 const Index_ block_start,
536 const Index_ block_length,
539 return populate_oracular_dense(row, std::move(oracle), block_start, block_length, opt);
542 std::unique_ptr<OracularDenseExtractor<Value_, Index_> >
dense(
548 return populate_oracular_dense(row, std::move(oracle), std::move(indices_ptr), opt);
555 template<
typename ... Args_>
556 std::unique_ptr<OracularSparseExtractor<Value_, Index_> > populate_oracular_sparse(
561 if (row == my_by_row) {
562 return std::make_unique<subset_utils::OracularPerpendicularSparse<Value_, Index_> >(
567 std::forward<Args_>(args)...
570 return std::make_unique<DelayedSubsetUnique_internal::ParallelSparse<true, Value_, Index_> >(
576 std::forward<Args_>(args)...
582 std::unique_ptr<OracularSparseExtractor<Value_, Index_> >
sparse(
587 return populate_oracular_sparse(row, std::move(oracle), opt);
590 std::unique_ptr<OracularSparseExtractor<Value_, Index_> >
sparse(
593 const Index_ block_start,
594 const Index_ block_length,
597 return populate_oracular_sparse(row, std::move(oracle), block_start, block_length, opt);
600 std::unique_ptr<OracularSparseExtractor<Value_, Index_> >
sparse(
606 return populate_oracular_sparse(row, std::move(oracle), std::move(indices_ptr), opt);
Virtual class for a matrix of some numeric type.
Delayed subsetting of a matrix with unique indices.
Definition DelayedSubsetUnique.hpp:298
bool prefer_rows() const
Definition DelayedSubsetUnique.hpp:369
Index_ ncol() const
Definition DelayedSubsetUnique.hpp:353
double is_sparse_proportion() const
Definition DelayedSubsetUnique.hpp:365
bool is_sparse() const
Definition DelayedSubsetUnique.hpp:361
std::unique_ptr< MyopicSparseExtractor< Value_, Index_ > > sparse(const bool row, const Index_ block_start, const Index_ block_length, const Options &opt) const
Definition DelayedSubsetUnique.hpp:477
double prefer_rows_proportion() const
Definition DelayedSubsetUnique.hpp:373
std::unique_ptr< OracularSparseExtractor< Value_, Index_ > > sparse(const bool row, std::shared_ptr< const Oracle< Index_ > > oracle, const Options &opt) const
Definition DelayedSubsetUnique.hpp:582
std::unique_ptr< OracularDenseExtractor< Value_, Index_ > > dense(const bool row, std::shared_ptr< const Oracle< Index_ > > oracle, const Index_ block_start, const Index_ block_length, const Options &opt) const
Definition DelayedSubsetUnique.hpp:532
std::unique_ptr< MyopicDenseExtractor< Value_, Index_ > > dense(const bool row, const Index_ block_start, const Index_ block_length, const Options &opt) const
Definition DelayedSubsetUnique.hpp:424
std::unique_ptr< MyopicDenseExtractor< Value_, Index_ > > dense(const bool row, const Options &opt) const
Definition DelayedSubsetUnique.hpp:417
bool uses_oracle(const bool row) const
Definition DelayedSubsetUnique.hpp:377
std::unique_ptr< OracularSparseExtractor< Value_, Index_ > > sparse(const bool row, std::shared_ptr< const Oracle< Index_ > > oracle, VectorPtr< Index_ > indices_ptr, const Options &opt) const
Definition DelayedSubsetUnique.hpp:600
std::unique_ptr< OracularDenseExtractor< Value_, Index_ > > dense(const bool row, std::shared_ptr< const Oracle< Index_ > > oracle, const Options &opt) const
Definition DelayedSubsetUnique.hpp:524
std::unique_ptr< OracularDenseExtractor< Value_, Index_ > > dense(const bool row, std::shared_ptr< const Oracle< Index_ > > oracle, VectorPtr< Index_ > indices_ptr, const Options &opt) const
Definition DelayedSubsetUnique.hpp:542
std::unique_ptr< MyopicDenseExtractor< Value_, Index_ > > dense(const bool row, VectorPtr< Index_ > indices_ptr, const Options &opt) const
Definition DelayedSubsetUnique.hpp:433
std::unique_ptr< MyopicSparseExtractor< Value_, Index_ > > sparse(const bool row, VectorPtr< Index_ > indices_ptr, const Options &opt) const
Definition DelayedSubsetUnique.hpp:486
Index_ nrow() const
Definition DelayedSubsetUnique.hpp:345
DelayedSubsetUnique(std::shared_ptr< const Matrix< Value_, Index_ > > matrix, SubsetStorage_ subset, const bool by_row, const bool check=true)
Definition DelayedSubsetUnique.hpp:308
std::unique_ptr< OracularSparseExtractor< Value_, Index_ > > sparse(const bool row, std::shared_ptr< const Oracle< Index_ > > oracle, const Index_ block_start, const Index_ block_length, const Options &opt) const
Definition DelayedSubsetUnique.hpp:590
std::unique_ptr< MyopicSparseExtractor< Value_, Index_ > > sparse(const bool row, const Options &opt) const
Definition DelayedSubsetUnique.hpp:470
Virtual class for a matrix.
Definition Matrix.hpp:59
std::unique_ptr< MyopicDenseExtractor< Value_, Index_ > > dense_row() const
Definition Matrix.hpp:295
std::unique_ptr< MyopicDenseExtractor< Value_, Index_ > > dense_column() const
Definition Matrix.hpp:336
std::unique_ptr< MyopicSparseExtractor< Value_, Index_ > > sparse_column() const
Definition Matrix.hpp:545
std::unique_ptr< MyopicSparseExtractor< Value_, Index_ > > sparse_row() const
Definition Matrix.hpp:504
Predict future access requests on the target dimension.
Definition Oracle.hpp:29
Copy data from one buffer to another.
Flexible representations for matrix data.
Definition Extractor.hpp:15
std::shared_ptr< const std::vector< Index_ > > VectorPtr
Definition Matrix.hpp:26
void resize_container_to_Index_size(Container_ &container, const Index_ x, Args_ &&... args)
Definition Index_to_container.hpp:92
typename std::conditional< oracle_, OracularDenseExtractor< Value_, Index_ >, MyopicDenseExtractor< Value_, Index_ > >::type DenseExtractor
Definition Extractor.hpp:273
Container_ create_container_of_Index_size(const Index_ x, Args_ &&... args)
Definition Index_to_container.hpp:73
Options for accessing data from a Matrix instance.
Definition Options.hpp:30