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 :)

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.

"My major gripe with haskell was that I could never tell the space/time complexity of the my code without serious analysis (that among other things involves second-guessing the compiler's ability to optimize). This makes writing good quality code harder than it needs to be."

This problem is significantly worse in Haskell than in most other languages. Usually you lose at most a constant factor in performance if the compiler doesn't optimize as much as you expected, but the lazy evaluation can actually change the asymptotic memory complexity. I have been bitten by lazy evaluation several times by writing code that I expect to run in constant space and then finding it require linear amount of memory because of the evaluation order.

> My major gripe with haskell was that I could never tell the space/time complexity of the my code without serious analysis

This is really a serious issue. The only other language where I ever had this issue was SQL. I had a project where we have lots of nested Views. We had to rephrase the SQL in sometimes very non-obvious ways, introducing intermediate Array results, CTEs, switching between sub SELECTs and JOINs -- all this just to convince the Query Planner to use a different Query Plan. That made a difference between < 1 second or a few minutes.

In the end, this is why I prefer languages OCaml or SML over Haskell. (Rust on the horizon)

Roughly speaking, in Haskell you can prove "just" correctness, while in OCaml you can prove correctness as well as performance.

"My major gripe with haskell was that I could never tell the space/time complexity of the my code without serious analysis (that among other things involves second-guessing the compiler's ability to optimize). This makes writing good quality code harder than it needs to be."

It seems to me that there is some connection/analogy with garbage collection. Garbage collection also makes reasoning about space usage of programs difficult, since it happens in some future, yet unspecified, time. Yet GC is almost always regarded as good (although historically there was a lot of fight against it), yet lazy evaluation is regarded as bad by many. Maybe the issue really is "good enough compilers"?

It's really easy to fuck up what will be evaluated, when, and wind up with disastrous performance ramifications.

As an example, I wanted to accumulate a list of summary data as I iterated through a recursive function. Through a coding error, the elements of the list (although not the list itself) were not evaluated until all the iterations were complete. This meant that, instead of a list of structs, which I thought I had, I had a list of zero-argument functions that, when called, would yield structs, _each of which contained a reference to a large array computed at an earlier iteration of the computation_.

So, I hemorrhaged space. This was a fuck-up, not a missed optimization.

It is similar to garbage collection, but maybe an order of magnitude worse. The benefits of lazy evaluation are also very nice, though.

Of course they do. The point here is exactly that all of those things apply to Haskell, simultaneously.

And yet, most of us posting these things still choose Haskell.

I think this shows that the tooling is just as important, if not more important, when choosing a language. Good debugging tools are a must simply because things always go wrong, and if I don't have an IDE that can highlight the line for me and allow to mouse hover over variable values, then the whole experience becomes a lesson in frustration.

Additionally if you expect me to 'write, build, run, repeat' just to test my code, then you better hope you have a fast compiler else I'm going to start associating using your language with the same amount of interest as watching paint dry.

> if I don't have an IDE that can highlight the line for me and allow to mouse hover over variable values, then the whole experience becomes a lesson in frustration.

What does that even mean in a language with no explicit model for code sequencing?

Well Haskell has a well defined execution order. I think the large problem is that compiled Haskell doesn't represent the original source at all making this tricky if not impossible.

The execution order is only defined on the IO monad or when there is data dependency. Independent chunks of pure code can be executed in any order.

The key word being independent. There is still a natural baked in dependency ordering. That is all that I meant. I realize I could of phrased it better.