On Parallel Binary Search #1384
Conversation
|
Hello @Kostero and welcome! Thanks for joining the project and thanks for the contribution! Here's some quick initial feedback: Consider putting text in online grammar/spell checker. I noticed than 'Specifically' was misspelled. Also, I'd personally prefer more descriptive variable names rather than Also, consider compiling the given code. What is Also, I think we use snake case for functions and it may make sense to have |
|
Thanks for the feedback. I have fixed some issues. Comments for the remaining ones below.
A and X are mostly there to keep things simple and to not repeat long variables names (especially in the table explaining what we actually do). I would prefer to keep it that way.
I have a problem of changing the variables over and over, after doing all the checks (including compilation). It should work now. I will try to add tests in the follow-up, just wanted to get the first review asap.
I kinda disagree here, as they directly refer to |
| | query | \( X_1 = 8 \) | \( X_2 = 11 \) | \( X_3 = 4 \) | \( X_4 = 5 \) | | ||
| |--------|------------------------|------------------------|-----------------------|-----------------------| | ||
| | **step 1** | answer in \([0,8)\) | answer in \([0,8)\) | answer in \([0,8)\) | answer in \([0,8)\) | | ||
| | | check \( A_4 \) | check \( A_4 \) | check \( A_4 \) | check \( A_4 \) | | ||
| | | \( X_1 < A_4 = 9 \) | \( X_2 \geq A_4 = 9 \) | \( X_3 < A_4 = 9 \) | \( X_4 < A_4 = 9 \) | | ||
| | **step 2** | answer in \([0,4)\) | answer in \([4,8)\) | answer in \([0,4)\) | answer in \([0,4)\) | | ||
| | | check \( A_2 \) | check \( A_6 \) | check \( A_2 \) | check \( A_2 \) | | ||
| | | \( X_1 \geq A_2 = 5 \) | \( X_2 < A_6 = 13 \) | \( X_3 < A_2 = 5 \) | \( X_4 \geq A_2 = 5 \) | | ||
| | **step 3** | answer in \([2,4)\) | answer in \([4,6)\) | answer in \([0,2)\) | answer in \([2,4)\) | | ||
| | | check \( A_3 \) | check \( A_5 \) | check \( A_1 \) | check \( A_3 \) | | ||
| | | \( X_1 \geq A_3 = 7 \) | \( X_2 \geq A_5 = 9 \) | \( X_3 \geq A_1 = 3 \) | \( X_4 < A_3 = 7 \) | | ||
| | **step 4** | answer in \([3,4)\) | answer in \([5,6)\) | answer in \([1,2)\) | answer in \([2,3)\) | | ||
| | | \( index = 3 \) | \( index = 5 \) | \( index = 1 \) | \( index = 2 \) | |
There was a problem hiding this comment.
| | query | \( X_1 = 8 \) | \( X_2 = 11 \) | \( X_3 = 4 \) | \( X_4 = 5 \) | | |
| |--------|------------------------|------------------------|-----------------------|-----------------------| | |
| | **step 1** | answer in \([0,8)\) | answer in \([0,8)\) | answer in \([0,8)\) | answer in \([0,8)\) | | |
| | | check \( A_4 \) | check \( A_4 \) | check \( A_4 \) | check \( A_4 \) | | |
| | | \( X_1 < A_4 = 9 \) | \( X_2 \geq A_4 = 9 \) | \( X_3 < A_4 = 9 \) | \( X_4 < A_4 = 9 \) | | |
| | **step 2** | answer in \([0,4)\) | answer in \([4,8)\) | answer in \([0,4)\) | answer in \([0,4)\) | | |
| | | check \( A_2 \) | check \( A_6 \) | check \( A_2 \) | check \( A_2 \) | | |
| | | \( X_1 \geq A_2 = 5 \) | \( X_2 < A_6 = 13 \) | \( X_3 < A_2 = 5 \) | \( X_4 \geq A_2 = 5 \) | | |
| | **step 3** | answer in \([2,4)\) | answer in \([4,6)\) | answer in \([0,2)\) | answer in \([2,4)\) | | |
| | | check \( A_3 \) | check \( A_5 \) | check \( A_1 \) | check \( A_3 \) | | |
| | | \( X_1 \geq A_3 = 7 \) | \( X_2 \geq A_5 = 9 \) | \( X_3 \geq A_1 = 3 \) | \( X_4 < A_3 = 7 \) | | |
| | **step 4** | answer in \([3,4)\) | answer in \([5,6)\) | answer in \([1,2)\) | answer in \([2,3)\) | | |
| | | \( index = 3 \) | \( index = 5 \) | \( index = 1 \) | \( index = 2 \) | | |
| | Query | \( X_1 = 8 \) | \( X_2 = 11 \) | \( X_3 = 4 \) | \( X_4 = 5 \) | | |
| |--------|:----------------------------------------:|:-----------------------------------------:|:------------------------------------------:|:------------------------------------------:| | |
| | **Step 1** | Answer in \([0,8)\) <br> Check \( A_4 \) <br> \( X_1 < A_4 = 9 \) | Answer in \([0,8)\) <br> Check \( A_4 \) <br> \( X_2 \geq A_4 = 9 \) | Answer in \([0,8)\) <br> Check \( A_4 \) <br> \( X_3 < A_4 = 9 \) | Answer in \([0,8)\) <br> Check \( A_4 \) <br> \( X_4 < A_4 = 9 \) | | |
| | **Step 2** | Answer in \([0,4)\) <br> Check \( A_2 \) <br> \( X_1 \geq A_2 = 5 \) | Answer in \([4,8)\) <br> Check \( A_6 \) <br> \( X_2 < A_6 = 13 \) | Answer in \([0,4)\) <br> Check \( A_2 \) <br> \( X_3 < A_2 = 5 \) | Answer in \([0,4)\) <br> Check \( A_2 \) <br> \( X_4 \geq A_2 = 5 \) | | |
| | **Step 3** | Answer in \([2,4)\) <br> Check \( A_3 \) <br> \( X_1 \geq A_3 = 7 \) | Answer in \([4,6)\) <br> Check \( A_5 \) <br> \( X_2 \geq A_5 = 9 \) | Answer in \([0,2)\) <br> Check \( A_1 \) <br> \( X_3 \geq A_1 = 3 \) | Answer in \([2,4)\) <br> Check \( A_3 \) <br> \( X_4 < A_3 = 7 \) | | |
| | **Step 4** | Answer in \([3,4)\) <br> \( index = 3 \) | Answer in \([5,6)\) <br> \( index = 5 \) | Answer in \([1,2)\) <br> \( index = 1 \) | Answer in \([2,3)\) <br> \( index = 2 \) | |
Let's join rows for each step and align by center in columns.
|
|
||
| for (int step = 1; step <= ceil(log2(N)); ++step) { | ||
| // Map to store indices of queries asking for this value. | ||
| unordered_map<int, vector<int>> m_to_queries; |
There was a problem hiding this comment.
Using std::unordered_map is generally considered an anti-pattern in modern CP, given that it's constantly getting hacked by certain enthusiasts in CF rounds, unless proper randomization is used, and even when it is used properly, it rarely provides significant practical benefits over std::map.
Also in this formulation it should be sufficient to e.g. have an array of M vectors?
| | **step 4** | answer in \([3,4)\) | answer in \([5,6)\) | answer in \([1,2)\) | answer in \([2,3)\) | | ||
| | | \( index = 3 \) | \( index = 5 \) | \( index = 1 \) | \( index = 2 \) | | ||
|
|
||
| We generally process this table by columns (queries), but notice that in each row we often repeat access to certain values of the array. To limit access to these values, we can process the table by rows (steps). This does not make huge difference in our small example problem (as we can access all elements in $\mathcal{O}(1)$), but in more complex problems, where computing these values is more complicated, this might be essential to solve these problems efficiently. Moreover, note that we can arbitrarily choose the order in which we answer questions in a single row. Let us look at the code implementing this approach. |
There was a problem hiding this comment.
I'd really prefer to add a bit more of the following:
- Motivation to ever consider doing it in the first place;
- Some specific examples on how using this reduces the complexity.
I think for the latter there are some very simple applications like finding order of key on segment in
| | **step 4** | answer in \([3,4)\) | answer in \([5,6)\) | answer in \([1,2)\) | answer in \([2,3)\) | | ||
| | | \( index = 3 \) | \( index = 5 \) | \( index = 1 \) | \( index = 2 \) | | ||
|
|
||
| We generally process this table by columns (queries), but notice that in each row we often repeat access to certain values of the array. To limit access to these values, we can process the table by rows (steps). This does not make huge difference in our small example problem (as we can access all elements in $\mathcal{O}(1)$), but in more complex problems, where computing these values is more complicated, this might be essential to solve these problems efficiently. Moreover, note that we can arbitrarily choose the order in which we answer questions in a single row. Let us look at the code implementing this approach. |
There was a problem hiding this comment.
| We generally process this table by columns (queries), but notice that in each row we often repeat access to certain values of the array. To limit access to these values, we can process the table by rows (steps). This does not make huge difference in our small example problem (as we can access all elements in $\mathcal{O}(1)$), but in more complex problems, where computing these values is more complicated, this might be essential to solve these problems efficiently. Moreover, note that we can arbitrarily choose the order in which we answer questions in a single row. Let us look at the code implementing this approach. | |
| We generally process this table by columns (queries), but notice that in each row we often repeat access to certain values of the array. To limit access to these values, we can process the table by rows (steps). This does not make huge difference in our small example problem (as we can access all elements in $O(1)$), but in more complex problems, where computing these values is more complicated, this might be essential to solve these problems efficiently. Moreover, note that we can arbitrarily choose the order in which we answer questions in a single row. Let us look at the code implementing this approach. |
Other parts of the article don't use mathcal with O.
|
|
||
| <small>Note that this section follows the description in [Sports programming in practice](https://kostka.dev/sp/).</small> | ||
|
|
||
| Imagine that we want to answer $Z$ queries about the index of the largest value less than or equal to some $X_i$ (for $i=1,2,\ldots,Z$) in a sorted 0-indexed array $A$. Naturally, each query can be answered using binary search. |
There was a problem hiding this comment.
It is
| @@ -138,6 +138,63 @@ Another noteworthy way to do binary search is, instead of maintaining an active | |||
|
|
|||
| This paradigm is widely used in tasks around trees, such as finding lowest common ancestor of two vertices or finding an ancestor of a specific vertex that has a certain height. It could also be adapted to e.g. find the $k$-th non-zero element in a Fenwick tree. | |||
|
|
|||
| ## Parallel Binary Search | |||
|
|
|||
| <small>Note that this section follows the description in [Sports programming in practice](https://kostka.dev/sp/).</small> | |||
There was a problem hiding this comment.
Is the intention here to provide a reference for further reading, or an attribution? I think it is more common to integrate references in the text (see e.g. how this is linked above in the article) or put them in some kind of further reading section at the end.
Also, to make sure, you understand that by putting the text from the book here you also make it licensed under CC BY-SA 4.0?
| | **step 4** | answer in \([3,4)\) | answer in \([5,6)\) | answer in \([1,2)\) | answer in \([2,3)\) | | ||
| | | \( index = 3 \) | \( index = 5 \) | \( index = 1 \) | \( index = 2 \) | | ||
|
|
||
| We generally process this table by columns (queries), but notice that in each row we often repeat access to certain values of the array. To limit access to these values, we can process the table by rows (steps). This does not make huge difference in our small example problem (as we can access all elements in $\mathcal{O}(1)$), but in more complex problems, where computing these values is more complicated, this might be essential to solve these problems efficiently. Moreover, note that we can arbitrarily choose the order in which we answer questions in a single row. Let us look at the code implementing this approach. |
There was a problem hiding this comment.
Moreover, note that we can arbitrarily choose the order in which we answer questions in a single row.
Don't we actually really care about doing it in increasing order of
|
Any update here? |
No description provided.