Timeline for GroupBy key a sequence of ordered key values
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 17, 2021 at 0:13 | vote | accept | EmmanuelMess | ||
| Jul 15, 2021 at 3:21 | comment | added | Sam Westrick | Yes, the whole algorithm runs in O(log n) parallel time, where n is number of input pairs. Finding the boundaries takes O(1) parallel time: in parallel for each i, if element at i is different from at i-1, then it is a boundary. And then you can filter out the non-boundaries in O(log n) parallel time. | |
| Jul 15, 2021 at 0:43 | comment | added | EmmanuelMess | how do I find the boundry in $O(1)$ if I have to check every entry until I find the entry where the keys didn't match? In other words, if the entire list has a single key, does the algorithm run in parallel in O(log n)? | |
| Jul 14, 2021 at 23:17 | history | answered | Sam Westrick | CC BY-SA 4.0 |