Hacker News Reader

Comment by YeGoblynQueenne | Hacker News Reader

For those who, like me, wondered what wolf-fencing is:

"Wolf fence" algorithm: Edward Gauss described this simple but very useful and now famous algorithm in a 1982 article for communications of the ACM as follows: "There's one wolf in Alaska; how do you find it? First build a fence down the middle of the state, wait for the wolf to howl, determine which side of the fence it is on. Repeat process on that side only, until you get to the point where you can see the wolf."[10] This is implemented e.g. in the Git version control system as the command git bisect, which uses the above algorithm to determine which commit introduced a particular bug.

[https://en.wikipedia.org/wiki/Debugging]

So now you know what that thing you always end up doing is called :)

View on HN

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

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?

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.

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?

You can search N objects in less than O(N) time if you have a way of testing multiple objects at once. Pre-sorting is one way to obtain this capability, but it's only one of many. Often the capability comes from the problem domain itself (or, more accurately, how you model time in your problem domain). In debugging, "one run of the program" often decently approximates a constant unit of time, and you can (theoretically) bisect once per run, giving you the ability to search without an explicit presort. In the wolf analogy, your ability to roughly determine which direction the wolf call is coming from does the same thing.

In both cases you could argue that you are "cheating" because there is a computational process of some kind doing at least O(N) work each time (the computer in the debugging example, the universe in the wolf example), giving O(NlnN)+ overall, strictly worse than an O(N) linear search. However, you have to ask yourself in this case if it makes sense to equate the time taken by the computer/universe to run one unit of its computation with the time taken to run one unit of your* search, and in many cases it doesn't. In the end it's just a model and it's up to you to choose what to measure, approximate, and exclude.

If someone tries to argue that there is fundamental philosophical truth that makes one model better than the other, start digging down into the physics of the CPU -- how much O(N^N) quantum computation did the universe have to do in order to bring you a single CPU cycle? God only knows, but the time it takes is nearly constant, so it makes sense to ignore. Even the most hard-core theoretical algorithms expert is just as "guilty" of this kind of approximation as you are :-)

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.

I like this explanation ;)

So apply a binary search to an effect instead of a value.

There's this thing called a BSP tree which just uses a plane instead of a line as in the case above. There ya go, binary search.

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 ;).

*> 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.

> 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.

> 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.

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

What's with capturing large predators? My book on complex analysis euphemizes building a descending sequence of sets which converge to a point by

> If R is the continent of Africa and we select R_n as that subregion which contains the biggest lion in Africa, we have an algorithm for capturing a big lion—we simply build a cage around point z_0.

Reply on news.ycombinator.com