Cleanup: correct misspelling of occurrence
This commit is contained in:
parent
cc6bdac921
commit
2b914a2ecb
|
@ -132,7 +132,7 @@ class AtomicDisjointSet {
|
|||
|
||||
/**
|
||||
* Get an identifier for each id. This is deterministic and does not depend on the order of
|
||||
* joins. The ids are ordered by their first occurence. Consequently, `result[0]` is always zero
|
||||
* joins. The ids are ordered by their first occurrence. Consequently, `result[0]` is always zero
|
||||
* (unless there are no elements).
|
||||
*/
|
||||
void calc_reduced_ids(MutableSpan<int> result) const;
|
||||
|
|
|
@ -17,14 +17,14 @@ AtomicDisjointSet::AtomicDisjointSet(const int size) : items_(size)
|
|||
});
|
||||
}
|
||||
|
||||
static void update_first_occurence(Map<int, int> &map, const int root, const int index)
|
||||
static void update_first_occurrence(Map<int, int> &map, const int root, const int index)
|
||||
{
|
||||
map.add_or_modify(
|
||||
root,
|
||||
[&](int *first_occurence) { *first_occurence = index; },
|
||||
[&](int *first_occurence) {
|
||||
if (index < *first_occurence) {
|
||||
*first_occurence = index;
|
||||
[&](int *first_occurrence) { *first_occurrence = index; },
|
||||
[&](int *first_occurrence) {
|
||||
if (index < *first_occurrence) {
|
||||
*first_occurrence = index;
|
||||
}
|
||||
});
|
||||
}
|
||||
|
@ -37,49 +37,49 @@ void AtomicDisjointSet::calc_reduced_ids(MutableSpan<int> result) const
|
|||
|
||||
/* Find the root for element. With multi-threading, this root is not deterministic. So
|
||||
* some postprocessing has to be done to make it deterministic. */
|
||||
threading::EnumerableThreadSpecific<Map<int, int>> first_occurence_by_root_per_thread;
|
||||
threading::EnumerableThreadSpecific<Map<int, int>> first_occurrence_by_root_per_thread;
|
||||
threading::parallel_for(IndexRange(size), 1024, [&](const IndexRange range) {
|
||||
Map<int, int> &first_occurence_by_root = first_occurence_by_root_per_thread.local();
|
||||
Map<int, int> &first_occurrence_by_root = first_occurrence_by_root_per_thread.local();
|
||||
for (const int i : range) {
|
||||
const int root = this->find_root(i);
|
||||
result[i] = root;
|
||||
update_first_occurence(first_occurence_by_root, root, i);
|
||||
update_first_occurrence(first_occurrence_by_root, root, i);
|
||||
}
|
||||
});
|
||||
|
||||
/* Build a map that contains the first element index that has a certain root. */
|
||||
Map<int, int> &combined_map = first_occurence_by_root_per_thread.local();
|
||||
for (const Map<int, int> &other_map : first_occurence_by_root_per_thread) {
|
||||
Map<int, int> &combined_map = first_occurrence_by_root_per_thread.local();
|
||||
for (const Map<int, int> &other_map : first_occurrence_by_root_per_thread) {
|
||||
if (&combined_map == &other_map) {
|
||||
continue;
|
||||
}
|
||||
for (const auto item : other_map.items()) {
|
||||
update_first_occurence(combined_map, item.key, item.value);
|
||||
update_first_occurrence(combined_map, item.key, item.value);
|
||||
}
|
||||
}
|
||||
|
||||
struct RootOccurence {
|
||||
int root;
|
||||
int first_occurence;
|
||||
int first_occurrence;
|
||||
};
|
||||
|
||||
/* Sort roots by first occurence. This removes the non-determinism above. */
|
||||
Vector<RootOccurence, 16> root_occurences;
|
||||
root_occurences.reserve(combined_map.size());
|
||||
/* Sort roots by first occurrence. This removes the non-determinism above. */
|
||||
Vector<RootOccurence, 16> root_occurrences;
|
||||
root_occurrences.reserve(combined_map.size());
|
||||
for (const auto item : combined_map.items()) {
|
||||
root_occurences.append({item.key, item.value});
|
||||
root_occurrences.append({item.key, item.value});
|
||||
}
|
||||
parallel_sort(root_occurences.begin(),
|
||||
root_occurences.end(),
|
||||
parallel_sort(root_occurrences.begin(),
|
||||
root_occurrences.end(),
|
||||
[](const RootOccurence &a, const RootOccurence &b) {
|
||||
return a.first_occurence < b.first_occurence;
|
||||
return a.first_occurrence < b.first_occurrence;
|
||||
});
|
||||
|
||||
/* Remap original root values with deterministic values. */
|
||||
Map<int, int> id_by_root;
|
||||
id_by_root.reserve(root_occurences.size());
|
||||
for (const int i : root_occurences.index_range()) {
|
||||
id_by_root.add_new(root_occurences[i].root, i);
|
||||
id_by_root.reserve(root_occurrences.size());
|
||||
for (const int i : root_occurrences.index_range()) {
|
||||
id_by_root.add_new(root_occurrences[i].root, i);
|
||||
}
|
||||
threading::parallel_for(IndexRange(size), 1024, [&](const IndexRange range) {
|
||||
for (const int i : range) {
|
||||
|
|
Loading…
Reference in New Issue