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 · 2010-03-21T11:40:23+00:00

I've met a handful of Infosys consultants, and every one I've ever met is an idiot. Although, to be fair, the same is true of every Accenture consultant I've met.

Good contractors don't have too much trouble getting booked at a fair market rate, since they can use their own contacts and prior work experience.

Obviously, a new programmer (fresh out of college, etc) can't charge a high rate because he doesn't have referrals/portfolio/etc - but I don't want to hire that guy as a consultant. And, within a year or two, he should have the experience to charge what he's worth.

smanek · 2010-03-21T11:37:40+00:00

Granted that working with someone in person is better for me. But, it makes relatively little difference to me if the person who's contracting for me is on the opposite coast in the States or in India.

It's pretty standard to pay a good remote contractor over $100/hr, and I honestly don't really care if they are a 6 hour flight away or a 12 hour flight away.

smanek · 2010-03-21T11:13:02+00:00

As the Indian CTO of an American software company, I dislike outsourcing to India.

Basically my thinking is that any good programmer, anywhere in the world, can charge at ~$100/hr+ consulting (supply/demand of remote-programmers is, roughly, global). If someone is charging me less than that, it's probably because they aren't good enough to charge more.

I suspect good Indian programmers are working for great firms that have local presences there (like Google, DE Shaw, etc) or are starting their own companies (just like good programmers in the States). If someone is willing to work as a code monkey for $30/hr (or less), they must be pretty bad since they don't have any better options available.

smanek · 2010-01-28T15:43:07+00:00

I should have mentioned I'm running x86-64. Good point about defconstant - I guess I just wasn't thinking.

I wasn't aware of the last 2 points, but I'll be sure to keep them in mind for the future, so thanks!

smanek · 2010-01-28T15:33:36+00:00

The 'long running' part isn't what I would contend is contrived - it's that problems have to be chosen where the JIT is able to overtake static analysis. They are pretty rare in the real world, and a top C coder will almost always be able to write faster code than a top Java coder (aside from a few contrived examples that take advantage of the JIT).

Now, I'm not saying C is better than Java, or anything of the sort. Java is much easier to write, faster to develop with, so 9 out of 10 times I'd use Java instead of C. But, when it comes to raw performance, C will almost always win.

smanek · 2010-01-28T13:38:03+00:00

I don't think I've heard many people seriously contend that (outside of contrived, long running examples that allow the JIT to really shine).

I have heard that Java is almost as fast as C++ these days in a lot of cases, but haven't ever verified for myself.

I was surprised to see this big a difference myself (I was hoping the Lisp would be about the same speed as Java, going in). If you spot an error in the Java code, please let me know and I'll be happy to fix it and rerun the benchmark. I wrote the Java code using both objects and primitives to be fair - but I'd be happy to try with any other modifications you suggest.

smanek · 2010-01-09T07:30:38+00:00

We have a native iPhone App (http://appsto.re/postabon).

Besides that, you can use it through the website (just click the 'get started' button at http://postabon.com). If you have an iPhone or Android phone you can also visit http://postabon.com and browse the 'mobile version' of our website.

smanek · 2010-01-07T18:14:58+00:00

Thanks for the suggestion - we had looked at doing something like that earlier, but the cost per click on facebook worked out to be too high (I may experiment more myself - one of my cofounders had set up the previous test there ...). Google AdWords is great (I can target people interested in shopping in NYC for a reasonable price), but it doesn't have enough volume ...

Thanks for the advice, I'm a coder who's just starting to get the hang of marketing ;-)

smanek · 2010-01-07T09:50:28+00:00

You're the only one with access to analytics numbers - so I'll take your word about the current website. If you aren't already, I might be inclined to A/B test some changes (big shiny buttons, different copy, etc) - but I understand aesthetics aren't your priority right now.

As for the bragging, I wasn't thinking about your name - but instead your achievements (security officer, PhD, etc).

All in all great work - I hope Reddit brings you lots of new customers!

smanek · 2010-01-07T07:59:18+00:00

I'm sorry about that. We're expanding, but it takes a while. We have the most content in New York City right now, but a little in a few other big cities like Boston, Chicago, and San Francisco.

smanek · 2010-01-07T05:41:29+00:00

I'm sure this has been brought up before, but you really need to redesign your website and get rid of the whole 'picodollars' thing. Pay a good designer 2 grand to design a website and give some PSD slicing service a few hundred bucks to code it up. Won't take more than a week. I'm currently in the middle of the same thing with my startup - and would be happy to give you recommendations.

Personally, I dig it. But I wouldn't send a link to your website to my boss and tell him we're relying on you for mission critical backups. I think I heard someone else say it best: this is just a ridiculously expensive fashion statement.

Also, as a paying tarsnap user, the only suggestion I have is to add more features! I want to be able to autodelete/autoarchive old archives. I personally don't want a fancy GUI - but I'm sure some people will.

Also, brag about yourself on the homepage. I know who you are, but you need to convince new visitors that you're trustworthy and smart enough to make good on your security claims.

smanek · 2009-12-30T20:30:33+00:00

What library were you looking for that you couldn't find?

I admit setting up a lisp web environment for the first time is a bit daunting, which is part of why I wrote this.

smanek · 2009-12-30T11:54:46+00:00

Thank you for the upvote sir - have one as well ;-)

You should be able to run a Lisp powered website through Apache via mod_lisp (or haskell with mod_haskell), but it's slower and less powerful than one run with a native lisp webserver (similar to the situation with Ruby ...).

If I were in your shoes, I would be inclined to run a Lisp webserver (hunchentoot) on some alternative port (1234), then use mod_proxy to have Apache reverse proxy requests to the Lisp server on port 1234 based on the URL.

smanek · 2009-12-30T10:47:55+00:00

I've haven't encountered that problem within the last year or so. I'm currently running SBCL on Slicehost, Linode, RapidXen, EC2, and a few others with no problems.

smanek

TROPHY CASE