4 ms·

So, binary search? Why did a new name come up for this well known thing in CS?

vog 11y ago
Bisection is also a well-known term, in mathematics as well as computer science.
tedmiston 11y ago
Wolf fencing is new to me too. It seems to be used only in the context of debugging. While with git bisect, we are also repeatedly ~halving the remaining search space, the list of commits isn't "sorted" like the precondition for binary search. You could argue that commits are sorted against time. But I would say that's different because we don't know which commit hash we're looking for -- we just want to find the point in time when our code stopped working, not that I've ever had to use it before ;).
- vog 11y ago
  *> the list of commits isn't "sorted" like the precondition for binary search. Good point. One may think that in some sense, it is sorted: The history is sorted into "good" commits (before the bug was introduced), which are followed by "bad" commits (after the bug was introduced). However, the bisection algorithm also works if "good" and "bad" commits are mixed. Even then it will find one commit where the bug was introduced (although there may be other places where it had been fixed and later reintroduced). This works because bisection doesn't require a sorted list, it just needs a continuous function. And any sequence is just a special case of that.
  - x1798DE 11y ago
    > However, the bisection algorithm also works if "good" and "bad" commits are mixed. Even then it will find one commit where the bug was introduced (although there may be other places where it had been fixed and later reintroduced). I don't understand this comment. Need for sorting the list is essentially the same in both cases, because "the bug was reintroduced" is essentially equivalent to "a lower number showed up later". A binary search makes the assumption of sorting because it's premised on the idea, "Whatever number I find, every number that comes after it will be larger". Same with bug-finding in a git history, it assumes "If I find a point in the history where the problematic behavior exists, it exists at all points after that for the same reason." If you had an "unsorted" history where a bug was fixed and then reintroduced in another way, your binary search may fail to find the immediate cause of your problems in the same way that an "unsorted" binary search would fail to find what it's looking for.
    - vog 11y ago
      > because "the bug was reintroduced" is essentially equivalent to "a lower number showed up later" Yes, and this is perfectly okay for "git bisect". > Need for sorting the list is essentially the same in both cases. No, bisection does not require sorting, it just needs a continuous range whose endpoints have different signs. Then, it will always find one point where the signs on both sides differ. (In real analysis, this means finding a zero. In discrete maths, it means find the introduction of a sign change.) In other words, when starting with a range from an old "good" commit to the current "bad" commit, it will always find a "good" commit directly followed by a "bad" commit. This is why "bisection" is a good term for this Git algorithm, while "binary search" would be misleading. (Even though bisection and binary search are almost identical algorithms. They mostly differ in their input assumptions and output guarantees.) Bisection makes no assumtion on any sort order, but guarantees to find one point of bug introduction in logarithmic time. It does not give any guarantee to find the lastest point of bug introduction -- unless, of course, your history does have just one such point.
brianwawok 11y ago
Binary search sounds kind of 2D. Wolf fence also lets you work with unsorted data. I.e. if I asked you to find a squeaky noise coming from somewhere in your house. Does it make sense to "binary search" your 3D 3-story house? Wolf fencing makes more sense.. stand on floor 2, see if it is on your floor. Or is it coming from the stairwell to floor 3, or the starwell to floor 1? You just used 1 step to narrow your search space down by 1/3. How would you sort your house so you can binary sort it?
- mrkgnao 11y ago
  Well, what you are doing is a "generalized" binary search. Suppose you have a four-stor(e)y house. You can start from the second floor and proceed a la standard binary search. You're putting an implicit ordering on the parts of your house, essentially, and then doing a search. And the bit about cutting the search space to a third (which is what I believe you meant, instead of cutting it /by/ a third) is something you can also do when searching a list, but IIRC halving is preferred because it has better worst-case time-complexity. You can always split a list into 1/3 + 2/3 instead of 1/2 + 1/2, but you risk having to search the 2/3 every time, etc.
- formula1 11y ago
  How can wolf fencing work on unsorted if you have to find out where it happens? Wouldnt that involve iterating on each item to find out where the wolf is?
  - true_religion 11y ago
    Binary search is looking for a value. Wolf-fencing is looking for a side-effect of that value. As per analogy, you're not checking an animal in Alaska to see if it is a wolf, you are waiting till the wolf howls (side effect of wolf-existence) then focusing your efforts in that area. So you can't really use wolf-fencing to say... find a number in an array; it makes no sense.
    - brianwawok 11y ago
      I like this explanation ;) So apply a binary search to an effect instead of a value.
js8 11y ago
I think it's called "divide and conquer".

vog 11y ago

Bisection is also a well-known term, in mathematics as well as computer science.

Wolf fencing is new to me too. It seems to be used only in the context of debugging. While with git bisect, we are also repeatedly ~halving the remaining search space, the list of commits isn't "sorted" like the precondition for binary search. You could argue that commits are sorted against time. But I would say that's different because we don't know which commit hash we're looking for -- we just want to find the point in time when our code stopped working, not that I've ever had to use it before ;).

vog 11y ago
*> the list of commits isn't "sorted" like the precondition for binary search. Good point. One may think that in some sense, it is sorted: The history is sorted into "good" commits (before the bug was introduced), which are followed by "bad" commits (after the bug was introduced). However, the bisection algorithm also works if "good" and "bad" commits are mixed. Even then it will find one commit where the bug was introduced (although there may be other places where it had been fixed and later reintroduced). This works because bisection doesn't require a sorted list, it just needs a continuous function. And any sequence is just a special case of that.
- x1798DE 11y ago
  > However, the bisection algorithm also works if "good" and "bad" commits are mixed. Even then it will find one commit where the bug was introduced (although there may be other places where it had been fixed and later reintroduced). I don't understand this comment. Need for sorting the list is essentially the same in both cases, because "the bug was reintroduced" is essentially equivalent to "a lower number showed up later". A binary search makes the assumption of sorting because it's premised on the idea, "Whatever number I find, every number that comes after it will be larger". Same with bug-finding in a git history, it assumes "If I find a point in the history where the problematic behavior exists, it exists at all points after that for the same reason." If you had an "unsorted" history where a bug was fixed and then reintroduced in another way, your binary search may fail to find the immediate cause of your problems in the same way that an "unsorted" binary search would fail to find what it's looking for.
  - vog 11y ago
    > because "the bug was reintroduced" is essentially equivalent to "a lower number showed up later" Yes, and this is perfectly okay for "git bisect". > Need for sorting the list is essentially the same in both cases. No, bisection does not require sorting, it just needs a continuous range whose endpoints have different signs. Then, it will always find one point where the signs on both sides differ. (In real analysis, this means finding a zero. In discrete maths, it means find the introduction of a sign change.) In other words, when starting with a range from an old "good" commit to the current "bad" commit, it will always find a "good" commit directly followed by a "bad" commit. This is why "bisection" is a good term for this Git algorithm, while "binary search" would be misleading. (Even though bisection and binary search are almost identical algorithms. They mostly differ in their input assumptions and output guarantees.) Bisection makes no assumtion on any sort order, but guarantees to find one point of bug introduction in logarithmic time. It does not give any guarantee to find the lastest point of bug introduction -- unless, of course, your history does have just one such point.

brianwawok 11y ago

Binary search sounds kind of 2D. Wolf fence also lets you work with unsorted data. I.e. if I asked you to find a squeaky noise coming from somewhere in your house. Does it make sense to "binary search" your 3D 3-story house? Wolf fencing makes more sense.. stand on floor 2, see if it is on your floor. Or is it coming from the stairwell to floor 3, or the starwell to floor 1? You just used 1 step to narrow your search space down by 1/3. How would you sort your house so you can binary sort it?

mrkgnao 11y ago
Well, what you are doing is a "generalized" binary search. Suppose you have a four-stor(e)y house. You can start from the second floor and proceed a la standard binary search. You're putting an implicit ordering on the parts of your house, essentially, and then doing a search. And the bit about cutting the search space to a third (which is what I believe you meant, instead of cutting it /by/ a third) is something you can also do when searching a list, but IIRC halving is preferred because it has better worst-case time-complexity. You can always split a list into 1/3 + 2/3 instead of 1/2 + 1/2, but you risk having to search the 2/3 every time, etc.
formula1 11y ago
How can wolf fencing work on unsorted if you have to find out where it happens? Wouldnt that involve iterating on each item to find out where the wolf is?
- true_religion 11y ago
  Binary search is looking for a value. Wolf-fencing is looking for a side-effect of that value. As per analogy, you're not checking an animal in Alaska to see if it is a wolf, you are waiting till the wolf howls (side effect of wolf-existence) then focusing your efforts in that area. So you can't really use wolf-fencing to say... find a number in an array; it makes no sense.
  - brianwawok 11y ago
    I like this explanation ;) So apply a binary search to an effect instead of a value.

js8 11y ago

I think it's called "divide and conquer".