Earlier quoted context omitted.
Where did you get your list from, and can you share it?
For research purposes.
For science.
SeenBefore: A search engine for what you have seen before
71–80 of 97 posts
Re: SeenBefore: A search engine for what you have seen before
#72Earlier quoted context omitted.
Storing a list of 1.7 million strings for us takes 70mb stored in memory. Testing for membership is an O(1) op. Very happy with it. We use mongo as a dumb data store as well as a bunch of other infrastructure tools, like http://circleci.com we could have only dreamt of years ago.
> Testing for membership is an O(1) op Curious how. O(1) an array index lookup, not a string lookup, I thought.
Re: SeenBefore: A search engine for what you have seen before
#73Earlier quoted context omitted.
Storing a list of 1.7 million strings for us takes 70mb stored in memory. Testing for membership is an O(1) op. Very happy with it. We use mongo as a dumb data store as well as a bunch of other infrastructure tools, like http://circleci.com we could have only dreamt of years ago.
> Testing for membership is an O(1) op Curious how. O(1) an array index lookup, not a string lookup, I thought.
[deleted]
Re: SeenBefore: A search engine for what you have seen before
#74Earlier quoted context omitted.
> Testing for membership is an O(1) op Curious how. O(1) an array index lookup, not a string lookup, I thought.
http://redis.io/commands/sismember
Again just curious, but I'd still like to know how. Someone there asks the mod how it could be O(1), the mod replies it's a "hash table lookup". But Wikipedia at http://en.wikipedia.org/wiki/Big_O_notation suggests that such lookup is no faster than O(log log n). I think the redis info is incorrect.
O(1) implies that the location of the member in the list is already known, with no search required. I don't see how that could be the case when it's a key lookup. The key could be anywhere in the list, even if the list is sorted. They key would have to be searched for, it seems.
Re: SeenBefore: A search engine for what you have seen before
#75Earlier quoted context omitted.
Storing a list of 1.7 million strings for us takes 70mb stored in memory. Testing for membership is an O(1) op. Very happy with it. We use mongo as a dumb data store as well as a bunch of other infrastructure tools, like http://circleci.com we could have only dreamt of years ago.
Why not use a bloom filter?
Maybe because of this fact (according to Wikipedia)?: "The more elements that are added to the set, the larger the probability of false positives."
Re: SeenBefore: A search engine for what you have seen before
#76Earlier quoted context omitted.
http://redis.io/commands/sismember
Again just curious, but I'd still like to know how. Someone there asks the mod how it could be O(1), the mod replies it's a "hash table lookup". But Wikipedia at http://en.wikipedia.org/wiki/Big_O_notation suggests that such lookup is no faster than O(log log n). I think the redis info is incorrect. O(1) implies that the location of the member in the list is already known, with no search required. I don't see how tha…
O(1) means constant time.
Redis sets are interesting, because there are a few possible implementations under the hood, but the typical case winds up implementing it as a hash table. Hash tables have constant time lookup.
Think of it this way (this isn't literally what happens, but it's close).
1) Take the url you're looking for. Run it through a hash function. This takes an (amortized) constant amount of time.
2) Now you have an index to check. (the return value from the hash function). So index into your actual table, and check to see what's stored there. If there's a value stored there, then the url is a member of the set. This also takes a constant amount of time.
Does this help?
Re: SeenBefore: A search engine for what you have seen before
#77Earlier quoted context omitted.
Again just curious, but I'd still like to know how. Someone there asks the mod how it could be O(1), the mod replies it's a "hash table lookup". But Wikipedia at http://en.wikipedia.org/wiki/Big_O_notation suggests that such lookup is no faster than O(log log n). I think the redis info is incorrect. O(1) implies that the location of the member in the list is already known, with no search required. I don't see how tha…
O(1) means constant time. Redis sets are interesting, because there are a few possible implementations under the hood, but the typical case winds up implementing it as a hash table. Hash tables have constant time lookup. Think of it this way (this isn't literally what happens, but it's close). 1) Take the url you're looking for. Run it through a hash function. This takes an (amortized) constant amount of time. 2) Now…
> So index into your actual table, and check to see what's stored there
But that check isn't a constant time lookup. The lookup time can vary. (Analogously, a lookup in a phone book can vary in time; we can't necessarily go to the exact spot the first time.) So the total time for both steps must vary as well. I think.
Re: SeenBefore: A search engine for what you have seen before
#78Earlier quoted context omitted.
O(1) means constant time. Redis sets are interesting, because there are a few possible implementations under the hood, but the typical case winds up implementing it as a hash table. Hash tables have constant time lookup. Think of it this way (this isn't literally what happens, but it's close). 1) Take the url you're looking for. Run it through a hash function. This takes an (amortized) constant amount of time. 2) Now…
> So index into your actual table, and check to see what's stored there But that check isn't a constant time lookup. The lookup time can vary. (Analogously, a lookup in a phone book can vary in time; we can't necessarily go to the exact spot the first time.) So the total time for both steps must vary as well. I think.
I think where you're getting confused is that you're conceptualizing this like a search problem, where you compare values and inspect each member to see if it matches the target.
That's not what's going on here. Instead, you use the value as in input into a function that tells you where to look for it, then you look, to see if it's there.
If it's not there, it won't be anywhere else, so you don't have to keep looking. Things get interesting with collisions but that's a subject for another time.
Re: SeenBefore: A search engine for what you have seen before
#79Earlier quoted context omitted.
> So index into your actual table, and check to see what's stored there But that check isn't a constant time lookup. The lookup time can vary. (Analogously, a lookup in a phone book can vary in time; we can't necessarily go to the exact spot the first time.) So the total time for both steps must vary as well. I think.
I think where you're getting confused is that you're conceptualizing this like a search problem, where you compare values and inspect each member to see if it matches the target. That's not what's going on here. Instead, you use the value as in input into a function that tells you where to look for it, then you look, to see if it's there. If it's not there, it won't be anywhere else, so you don't have to keep looking…
OK, thanks, I'm starting to understand. Good explanation. I quit being lazy and searched around too, to see that it's possible.
Re: SeenBefore: A search engine for what you have seen before
#80For those using Firefox, there is a similar add-on called RecallMonkey.
https://addons.mozilla.org/en-us/firefox/addon/prospector-re...