Mark Chu-Carroll writes about math, programming theory, distributed consensus, functional programming and debunking bad math.
HN links it for explainers on slide rules, category theory and constructivism, and for its takedown of a crank's claims about the field axioms.
> if the underlying buffer needs to reallocate after some edits the entire process slows to a crawl as you need to allocate a larger buffer and copy each byte into the new buffer and destroy the old one. It can turn an O(n) operation into O(n^2) randomly.
This would still only be a O(n) operation. The constant value might be higher, but the complexity is the same.
I don’t buy the argument that gap buffers “are bad for multiple cursors”. I get the argument on a theoretical level, but real hardware is not theoretical. There are several operations that are theoretical faster with a hashmap or b-tree than a vector, like insert and delete. But in reality the vector is usually faster in the real world except for very large inputs[1]. Gap buffers are basically vectors.
Another point with multiple cursors and gap buffers is that Chris Wellons animations show the gap moving back to the first cursor every time it needed to add a new character. But in reality you would just walk the cursors in reverse order each time, saving a trip.
I have actually written and benchmarked a very naive and unoptimized gap buffer, and the results showed that it was faster than highly optimized rope implantations on all real world benchmarks[2], including multiple cursors.
That being said, a gap buffer is still probably not the best data structure for a text editor because it has worse “worse case” performance than something like a rope or piece-tree. Even though it is faster overall, it’s the tail…
Thank you for the clarification. Following up on this, I found a blog post [0] that explains why you don't get bizarre consequences like the Banach-Tarski paradox this way:
> [The constructivist method] avoids the basic problem with the axiomatic problem. You can’t have something ridiculous like the set of all sets that don’t include themselves, because the only way to show that a set exists is to show a process to create it – and there’s no way to create a paradoxical set! You don’t get nonsense like [the Banach-Tarski paradox], because the division of the spherical topological space into the non-metric subspaces is impossible: you can’t show a process that produces it. In the world of intuitionism and constructivism, existence proofs that don’t produce concrete examples don’t exist!
[0]: http://www.goodmath.org/blog/2014/08/18/the-constructivist-roots-of-type-theory/
Another post I stumbled accross when looking for part one
http://www.goodmath.org/blog/category/bad-math/cantor-crankery/
A highlight I'd like HN to read, because it comes up every so often.
> There’s a common belief among crackpots of various sorts that scientists and mathematicians use symbols and formalisms just because we like them, or because we want to obscure things and make simple things seem complicated, so that we’ll look smart.
> That’s just not the case. We use formalisms and notation because they are absolutely essential. We can’t do math without the formalisms; we could do it without the notation, but the notation makes things clearer than natural language prose.
It's kinda fascinating how dominant LaTeX is, how nice its output is, how respected Knuth is as a computer scientist, and at the same time how totally awful it feels to use it. Hard to figure out how it can be so good and so bad at once.
Posts/discussion I found interesting:
- http://www.goodmath.org/blog/2008/01/10/the-genius-of-donald-knuth-typesetting-with-boxes-and-glue/
- https://tex.stackexchange.com/q/24671
- https://news.ycombinator.com/item?id=15733381
In particular it's interesting how people seem to think TeX itself is actually quite nice to use but its popularity and LaTeX packages created a huge mess of a system.
Wildberger has always been this way. Way back in 2007, Marc Chu-Carroll's "Good Math Bad Math" highlighted Wildberger: "This isn’t the typical wankish crackpottery, but rather a deep and interesting bit of crackpottery." In brief, Wildberger is clearly educated, but also clearly rejects axioms that mathematicians accepted a long time ago (infinite sets in this case):
"Dirty Rotten Infinite Sets and the Foundations of Math" http://www.goodmath.org/blog/2007/10/15/dirty-rotten-infinite-sets-and-the-foundations-of-math/
Wildberger also wrote a book on geometry with nothing allowed but rationals. (Or something like that.)
> I have been told I write better code than my CS grad peers but I have no clue about these algorithms and data structures.
For a programer in the industry, the ability to write simple "legible" code is very important. An ideal interview process should spend some time evaluating those skills of a candidate - but this is very very hard to measure.
But good familiarity with the basics of CS is also important to be able to perform many of these jobs. Here is a good blog post about this form of interview and the rationale behind it:
http://www.goodmath.org/blog/2015/11/19/technical-interviews-more-than-a-brain-teaser/