Support and General Use > Audio Playback, Database and Playlists
Glitchy audio after resume playback (split from: New USB mode questions)
dreamlayers:
This bug already had its own entry in the tracker. I just submitted a patch: http://www.rockbox.org/tracker/task/9949#comment28863
Chronon:
--- Quote from: AstroBoy on March 05, 2009, 07:01:25 PM ---Your math is beyond me. :(
--- End quote ---
You are looking at the worst case scenario, which actually seems apt for this instance of it. Usually, it's assumed that when the test returns a member of the set that you're searching you know if it's correct or not. In this case it isn't known unless you search for pairs of consecutive builds. (Testing one build at a time cannot tell you if a broken build is the first one or not.) For that reason, it's likely that you won't know until the very end of the test that you have gotten the right result. So, your analysis is good for this situation. However, it seems that you are shifted by one with your initial case. In this case (though not in general) we can assume that the object of our search exists in the set we're searching. So, a set with only one member needs to be searched zero times to find a particular member (there's only one!). A single search on a 2 member set will return the correct result -- it's either successful and you have picked the right one, or it wasn't and you can choose the other member of the set without running the test again.
So, after further consideration, it seems that my off-the-cuff answer of 10 for 1024 was correct, but not for the reasons that I initially thought. Wikipedia has a good explanation for why, in the ideal case, the number tends to correspond to the formula that I used in my previous comment.
Anyway, I don't care to quibble over the exact value. It's really not a big deal and my initial answer was really a back of the envelope approximation, not intended to be a rigorous answer. And it appears this may now be moot, anyway. ;D
dreamlayers:
Here are r20211 builds for testing:
* 5G 30GB iPod
* Sansa E200
These builds also include the pause unpause loop function for testing. You can use it from the debug menu and you can get out of the loop by holding stop. If you don't use it, its presence makes no difference.
You should also find that when unpaused, playback continues exactly from the point where it was paused. When this bug did not cause noise, it sometimes caused small changes in playback position.
Edit: Never mind, I didn't fix this correctly. No, it didn't show up as noise; the buffer is not advanced in some cases when pausing.
AstroBoy:
--- Quote from: Chronon on March 05, 2009, 08:23:28 PM ---In this case (though not in general) we can assume that the object of our search exists in the set we're searching. So, a set with only one member needs to be searched zero times to find a particular member (there's only one!).
--- End quote ---
Even if you only gave me 1 version of RockBox to test, I would not know if it had the bug or not until I tested it.
I was a programmer for years (but not now). I don't recall ever knowing that the opject I was looking for would be in the tree or not. Maybe you have a list of names, or checking account numbers. If you only have a set of 1 you still need to test it to see if you have a match or not. If not, maybe you would create a second object on the tree. Anyway, I will look at the Wikipedia link. Been fun, ty.
Chronon:
:-[
I have been sloppy again. Now that I have been through this once again I see the resolution. The number of iterations they discuss in that article is for the number required to reduce the set to one candidate. It does not include the final test for whether the test, as a whole, fails or succeeds (i.e. whether or not the object of the search in the set). So, log2N iterations gets you down to one candidate but doesn't tell you whether the candidate is the one that you want. Given the stated problem your calculation was spot on. In order to gain the speed up from early truncation, the problem needs to be posed in a way that satisfies those conditions. If pairs of code revisions are tested then you can positively identify a given pair as the correct one and on average you will find your desired result one iteration early (provided the object of the search is in the set). To set things up so this is the case you would also want to ensure that the endpoints are not the desired result. This situation seems less like a set of account numbers which may or may not contain a given account number. It's a sequential set of code revisions whose open boundary (in a mathematical sense) on the lower side lacks a bug and whose open boundary on the upper side contains a bug. In this sense, it's more akin to an analog to digital converter in which, given an in-range voltage, you search for the nearest digital number that does not exceed the target -- there will always be such a number unless the initial voltage is out of range.
Anyway, thanks for pointing out my mistakes. It's good to find a proper resolution in these cases. :)
*Apologies for getting off topic. If anyone feels this exchange should be trimmed, I'm fine with that.
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version