Sparse Array for Group By
- Dominant language
- C++
- Stars
- 1.9k
- Forks
- 225
- PR merge metrics
- No merged PRs in 30d
Description
This is just a thought, but we should consider making a sparse array similar to `hana::detail::hash_table` for the purpose of making a fast "group by" algorithm. One problem would be that it would have to use `fold_left` to construct the lookup which I recall was an expensive up front cost.
The result could even be a `hana::map` as it appears that everything except `make_map` is agnostic to the use of `hana::hash`.
I kind of got a start on something. The following is ripped from `hana::detail::hash`:
```cpp
namespace sparse_array
{
template
struct group { };
template
struct lookup_table
: Groups...
{ };
// find indices
template
std::index_sequence find_indices_impl(group const&);
template
std::index_sequence<> find_indices_impl(...);
template
struct find_indices {
using type = decltype(find_indices_impl(Lookup{}));
};
// update_group
template
struct update_group {
using type = Group;
};
template
struct update_group, Key, Index> {
using type = group;
};
// group_insert
template ::type::size() > 0)
>
struct group_insert;
template
struct group_insert, Node, Index, true> {
// There is a group for that Key; append the new index to it.
using type = lookup_table<
typename update_group::type...
>;
};
template
struct group_insert, Node, Index, false> {
// There is no group for that Key; insert a new group.
using type = lookup_table>;
};
template
struct make {
using type = typename decltype(
hana::fold_left(
std::declval(),
hana::type_c>,
hana::template_
)
)::type;
};
}
```
See the following for background information:
http://stackoverflow.com/questions/42541148/how-do-i-speed-up-many-different-hanafilters-on-the-same-input-data
Contributor guide
Research direction
No target file or test is identified. Start by reviewing hana::detail::hash, fold_left, and the linked background discussion to assess the proposed sparse lookup for group-by operations. The issue does not define an API, implementation location, or completion criteria, so those would need agreement before work can begin.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100