Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bifurcate the Problem Space

potetm.com

Post reply on HN
Print view View original

31–37 of 37 posts

Re: Bifurcate the Problem Space

#31

Post by Quekid5 »

bar94 wrote: post #23
joshjje wrote: post #22

Earlier quoted context omitted.

Am I missing something? How is that?

2^57 seconds is about 4.5 × 10^9 years, which is the age of the universe. They would only need that many stills because it would be possible to do a binary search on the footage, as each frame either has the bike in it or does not.

Maybe I'm just being dense, but I don't see how that would work. The bike's presence is not a monotonic property -- so you never know which half of the search space you need to descend into.

(In fact, you don't even know if a bike was ever there without already having identified a frame with the bike in it. After all, the physicist could be lying.)

Re: Bifurcate the Problem Space

#32

Post by bfung »

joatmon-snoo wrote: post #27
ithkuil wrote: post #14

Earlier quoted context omitted.

I more often heard and used "bisect". Is that subtly different or subtly the same?

It's the same, e.g. the git bisect command is just a binary search API for a commit history.

To finish the thought explicitly ~

If one has pretty good automated tests, it’s possible to automate and pinpoint which commit has the last working version and which commit had the test failure by using git bisect and using the test results as input.

Re: Bifurcate the Problem Space

#33

Post by Jtsummers »

Quekid5 wrote: post #31
bar94 wrote: post #23

Earlier quoted context omitted.

2^57 seconds is about 4.5 × 10^9 years, which is the age of the universe. They would only need that many stills because it would be possible to do a binary search on the footage, as each frame either has the bike in it or does not.

Maybe I'm just being dense, but I don't see how that would work. The bike's presence is not a monotonic property -- so you never know which half of the search space you need to descend into. (In fact, you don't even know if a bike was ever there without already having identified a frame with the bike in it. After all, the physicist could be lying.)

Probably exaggeration for effect, don't take it too literally. But if the bike had been there from the beginning of time, finding the second where it disappeared requires no more than 57 frames to be checked. So if searching billions of years of history only requires checking 57 frames, why is it so hard to check a day or a week or a few hours worth of data? (Of course, if this was before digital video records it could actually be tedious, but hardly impossible, to check even a few days worth of data since that may force a linear scan at least partially.)

Given that they knew when the bike was there (presumably the physicist knew when they locked it up or near enough) they could have found that point and looked forward, and it would have taken far fewer than 57 frames to identify where it disappeared if you're only interested in getting down to the second.

So if they knew the bike was present at 1pm, and it was gone by 3pm (hypothetical since not enough information is given) then they can do a binary search on that 2 hour window, that's only 7200 seconds worth of frames. Start at 2pm, is it present? Flip to 2:30, else 1:30. Repeat. Even a week is only 604k seconds, which would require no more than 20 frames to be checked.

Re: Bifurcate the Problem Space

#34

Post by Quekid5 »

Jtsummers wrote: post #33
Quekid5 wrote: post #31

Earlier quoted context omitted.

Maybe I'm just being dense, but I don't see how that would work. The bike's presence is not a monotonic property -- so you never know which half of the search space you need to descend into. (In fact, you don't even know if a bike was ever there without already having identified a frame with the bike in it. After all, the physicist could be lying.)

Probably exaggeration for effect, don't take it too literally. But if the bike had been there from the beginning of time, finding the second where it disappeared requires no more than 57 frames to be checked. So if searching billions of years of history only requires checking 57 frames, why is it so hard to check a day or a week or a few hours worth of data? (Of course, if this was before digital video records it cou…

The bike could have disappeared, then re-appeared and disappeared again, tho. So you might be finding the "wrong" thief.

(Btw, I realize it's just an anecdote, I'm just being extremely nitpicky.)

Re: Bifurcate the Problem Space

#35

Post by smilliken »

otikik wrote: post #16

The fact that the author is "commenting things out" makes me think that they don't have access to a debugger on their environment. When I find myself on that particular situation, I tend to: * Add lots of logs (e.g. "entered function X with parameters a, b, c", "exited function X, return value W"). * "Make things explode in a useful way". This is, cause an error on purpose, which halts the program. This is useful for…

"Commenting out" is often meant informally, not to be taken literally.

Your debugger may not work with a multithreaded program. Or it might cause the bug to disappear because it changes scheduling/execution order. Printf is more reliable in this context.

Or they may be debugging hardware, which the debugger can't step into. Or debugging object code without symbols.

Or they may be debugging a distributed system with remote code execution and asynchrony.

Or they may be debugging a language that doesn't have an execution stack.

Or they may be debugging an issue that only happens in production or customer machines that they can't access directly.

Or they may be debugging an issue that only happens very rarely, longer than the patience of a programmer to wait for a breakpoint.

Debuggers are one tool we have available, but hardly the only tool, and definitely not a complete tool.

Re: Bifurcate the Problem Space

#36

Post by otikik »

smilliken wrote: post #35
otikik wrote: post #16

The fact that the author is "commenting things out" makes me think that they don't have access to a debugger on their environment. When I find myself on that particular situation, I tend to: * Add lots of logs (e.g. "entered function X with parameters a, b, c", "exited function X, return value W"). * "Make things explode in a useful way". This is, cause an error on purpose, which halts the program. This is useful for…

"Commenting out" is often meant informally, not to be taken literally. Your debugger may not work with a multithreaded program. Or it might cause the bug to disappear because it changes scheduling/execution order. Printf is more reliable in this context. Or they may be debugging hardware, which the debugger can't step into. Or debugging object code without symbols. Or they may be debugging a distributed system with r…

Perhaps I didn’t explain myself correctly. My point is that when using a debugger is an option, they are preferable to print-based debugging. I am aware that they are not always an option. I don’t think my comment implied that.

Re: Bifurcate the Problem Space

#37

Post by joshjje »

bar94 wrote: post #23
joshjje wrote: post #22

Earlier quoted context omitted.

Am I missing something? How is that?

2^57 seconds is about 4.5 × 10^9 years, which is the age of the universe. They would only need that many stills because it would be possible to do a binary search on the footage, as each frame either has the bike in it or does not.

Ah I believe the confusion was thinking that 57 snapshots over said billion years would be enough to deduce the second. But instead they mean if you used binary search (or similar) across ALL of the images you could find it within 57 or so.
Post reply on HN