Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork1.8k
On Parallel Binary Search#1384
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
base:main
Are you sure you want to change the base?
Uh oh!
There was an error while loading.Please reload this page.
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 |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Thanks for the pull request! I have a few comments that I think should be addressed before this is merged.
| | 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.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| | 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.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Usingstd::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 overstd::map.
Also in this formulation it should be sufficient to e.g. have an array ofM 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.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
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 onhow 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.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| 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.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
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.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
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. howthis 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.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
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.