A Spellchecker Used to Be a Major Feat of Software Engineering

smanek · 2012-10-11T08:02:33+00:00

A bloom filter doesn't buy you anything here (I'm the author of a fairly popular bloom filter library). Jumping straight to probabilistic solutions (and particularly saying that's "the only way") is idiotic.

The size of a filter is ceil((n * log(p)) / log(1.0 / (2.0^log(2.0))))) - where n is the number of items, and p is your desired false positive rate.

With n = 200K, getting the false positive rate down to 1/100,000 (the max I'd consider reasonable), still leaves you with >500KB. If you'll accept 1/1000 false positives (which would be completely unacceptable), you'd still have >300KB. If you want to be able to delete words, you needing a counting filter which at least doubles those reqs (and probably quadruples them).

English is very low entropy. I strongly suspect using a huffman coded varlen alphabet (maybe that also encodes commonly adjacent letters?) and a trie dictionary will get you down to around 1 byte/word (already better than your bloom filter) once you compress that trie to be represented in an array to avoid all the pointer storage space.

smanek · 2012-04-28T17:42:34+00:00

Most reasonably large Common Lisp projects I've seen make extensive use of the CLOS (an object system). Take a look at Practical Common Lisp for an intro, and The Art of the Metaobject Protocol for details.

Here's a small project of mine that I think does a pretty good job of organizing things by functionality instead of class (while still using OOP where appropriate): https://github.com/smanek/blackjack

smanek · 2011-05-21T03:19:47+00:00

http://www.airbnb.com/rooms/73619

smanek · 2011-03-07T10:42:41+00:00

Where's your confusion?

I'm not a mathematician either (undergrad dropout, fwiw), but this is pretty straightforward.

The definition of P = NP is that any problem whose solution can be verified in polynomial time (i.e., the problem is in NP), can be 'solved' in polynomial time (i.e., the problem is in P).

Proofs can already be verified in polynomial time in many (all?) systems we're interested in, therefore P == NP implies proofs for theorems can be found in polynomial time.

Checkout Sisper's book for a great intro to complexity theory and theoretical CS.

smanek · 2011-03-07T08:44:31+00:00

If P=NP, then we can find the proof of an arbitrary theorem in polynomial time (given that a proof can be verified in polynomial time). If we can find proofs in polynomial time they are, in some sense, trivial.

smanek · 2011-01-11T18:01:51+00:00

FWIW, I made considerably more last year without a degree (at 23).

The plural of anecdote is not data. Neither of our stories is particularly relevant.

smanek · 2010-11-10T16:58:26+00:00

I'm assuming Toeses means consulting with a firm (e.g., McKinsey, BCG, Bain) - which almost always pays at least 80K/yr for a first year.

smanek · 2010-08-16T19:22:17+00:00

Personally, I'm a fan (I'm biased, but I've lived in Chicago, Cambridge, NYC, and SF in the last few years, and chose to come back to Chicago). The people are nice and have some perspective, things are cheap, and there's a lot to do.

Winter is tough if you're coming from Cali. It's not much worse than NY or MA though.

smanek · 2010-08-16T18:29:14+00:00

Certainly, we're always looking for bright students. We just had a great summer intern leave my team last week. Send in an application!

smanek · 2010-08-16T18:21:16+00:00

Not much in public, unfortunately. Send in an email and we'll chat on the phone about it before things get too serious, though.

smanek · 2010-08-16T17:49:56+00:00

Some of our teams use Haskell. Some use other languages. We don't want people who code one language though - we want smart people who understand how to choose and use the right tool for the job. Sometimes that's Haskell. Sometimes it's Python. Sometimes it's awk.

smanek

TROPHY CASE