jules

123 ms·

961.
by jules 11y ago
That's basically what this is, except you do it for the query rather than for the index, and you build the structure more intelligently than just inserting all possible insertions/deletions/substitutions. If you wanted to mak
962.
by jules 11y ago
Yes, the O(length of string) is per step in the automaton. Sorry if that was unclear, it was not my intention to mislead. Note however that that is for the naive version. The only point of the naive version is as a pedagogical stepping ston
963.
Levenshtein automata can be simple and fast(julesjacobs.github.io)
63 points by jules 11y ago|22 comments
964.
by jules 11y ago
Americans read and write dates in middle endian. Germans and Dutch only read numbers with decade flip, they are written as usual. Furthermore with "two and forty" there can be no confusion since it's not "two and four&
965.
by jules 11y ago
It will take exactly as long as it takes for lab grown meat to become viable. When that happens it becomes very easy for the general population to view eating meat from animals as evil.
966.
by jules 11y ago
Now you're talking about the cost of constructing the DFA, not searching the index with the resulting DFA. The cost of construcing the DFA is irrelevant, and even then you can construct the DFA in O(n) with my method for fixed max ed
967.
by jules 11y ago
> You can argue about the lengths of these strings and the simplicity of your step function all day long, at the end of the day it's still θ(n²) and no better than the simple dynamic programming approach. It's not O(n^2), but I
968.
by jules 11y ago
That's a nice soundbite but it's not correct. The worst case performance with the DFA is linear, the same as them.
969.
by jules 11y ago
I replied to this in the other thread to avoid splitting the conversation in two.
970.
by jules 11y ago
In practice with Lucene, len(string) and len(query) are like 10. So it's totally irrelevant. Furthermore computing the step is extremely fast: you're just doing a handful of min()'s. Even a single cache miss is going to compl
971.
by jules 11y ago
Computing the step() is extremely fast. And if that's not fast enough then do the DFA construction as I described. The approach is different, yes, but that's the point.
972.
by jules 11y ago
This is not correct. The end result of the step() based automaton is the same: it prunes exactly the same search paths as any Levenshtein automaton would. And the part where I described how to build the DFA gives you exactly a Levenshtein a
973.
by jules 11y ago
I'm not a 100x programmer, I just did a couple of things that drastically reduced the time: 1. I didn't follow that paper. Even trying to understand that paper would have taken way more time, so after 5 minutes of trying to unders
974.
by jules 11y ago
It was for the general case. The reason that I was able to do this is because I was less persistent than them. I tried to understand the paper but after 5 minutes I realized that even understanding the paper was going to take WAY more time
975.
by jules 11y ago
He is doing both Google and people who were rejected by Google a favor by pointing out that Google's interviews are not indicative of real world performance. He might have hurt his own chances a bit in the process, but overall this wil
976.
by jules 11y ago
Of course multiplying two numbers is easy: primary school children learn how to do it. Doing it in your head under pressure in an interview is entirely different.
977.
by jules 11y ago
The difficulty of Levenshtein automata is highly overstated. When I read that Lucene blog post I wrote an implementation in an hour, and prior to reading that post I hadn't even heard of Levenshtein automata.
978.
by jules 11y ago
On the contrary, that they are willing to admit this fact indicates that they know what they are doing.
979.
by jules 11y ago
A natural distribution in this case is the exponential distribution. In the first minute 80% gets thrown out. In the second minute 80% of the remainder gets thrown out, etc.
980.
by jules 11y ago
Who were the true winners of the industrial revolution? The employees making the machines? Nah. The true winners here will be the ones that always have been and always will be the winners.
981.
by jules 11y ago
There is a crucial difference between the lottery and startup investments. Presumably the latter have positive expected payout, whereas the lottery has negative expected payout. If the $5 makes zero difference to your life then the expected
982.
by jules 11y ago
The subsets you partition in are necessarily non-measurable sets. That makes them very strange. Any reasonble set that you can come up with is measurable. Even the set of points with rational coordinates is measurable. Of course you cannot
983.
by jules 11y ago
The real question here is what you bring to the table in an early stage startup. You can put yourself around the type of people you need to meet, but at the end of the day they are not going to be your co-founder unless you bring something
984.
by jules 11y ago
It gets very weird. Some models say that going outside of the observable bubble is the same as passing the event horizon of a black hole. When you are in a spaceship and you pass the event horizon of a black hole, nothing happens to you yet
985.
by jules 11y ago
It's not entirely clear what happens when a spaceship goes outside our observable bubble due to issues with conservation of information (similar to how it's not entirely clear what happens when you drop a spaceship in a black hole
986.
by jules 11y ago
Note that the multiverse that this article is talking about is very different than the many worlds multiverse. The many worlds multiverse is just that the whole universe is in a quantum state. The multiverse that this article is talking abo
987.
by jules 11y ago
> there is a lot of literature about how much sodium is too much Is there? I remember reading an article a while back saying that all those claims turned out to be based on a handful of flawed studies, and that for healthy people there i
988.
by jules 11y ago
You're right, I can't come up with a single meal that is as nutritious and balanced as one serving of Soylent. The thing is that unlike with Soylent you're not eating the exact same meal every time. If there's one thing
989.
by jules 11y ago
It depends on the type of noodles. Some types you can just soak, and then you throw them into the wok to heat them (because eating cold noodles isn't very nice). Some of them you have to soak with boiling or at least hot water to make
990.
by jules 11y ago
All 3 together? Not that much. At least one of those 3? 99% of the time.

More ›