Re: Algorithm on search
On May 6, 2:15 pm, p...@informatimago.com (Pascal J. Bourguignon)
wrote:
Vincent SHAO <vincent.shao.b...@gmail.com> writes:
Search engine have to record all of the query string. Now i
have a search engine log which contains 10 milllion query
strings, but almost of them are repeated, not more than 3
million of them are non-repeated. My task is to pick the
top 10 most popular query string, memory < 1G, the length of
the query string is no more than 255.
The faster, the better. the principal solutions, algorithm
and data structure.
Sounds like homework... Is it homework?
It sounds like a problem that really could come up
professionally (which doesn't mean it isn't homework---a well
conceived course will use realistic examples).
In real "search engine" queries, it's not strings, but _sets_ of
keywords that are searched, so already your data structures will be
suboptimal... That is, unless it's homework.
What about SQL or LDAP? The problem is that he probably should
consider requests that different only in white space to be the
same; for that matter (considering SQL), something like "SELECT
* FROM table1 WHERE a > 5 AND b < 10" is the same as "select *
from table1 where b < 10 and a > 5". He probably needs to
normalize the input somewhat, but how far depends on the project
requirements.
Anyway, the obvious solution is to use an std::map< Query, long >
for starters, then copy the tabluation into a vector (of
Map::value_type) and sort that on the criteria he's interested
in. If that's not fast enough, replace std::map with a not
yet standard hash_map, and only if that's not fast enough, to
start worrying about other solutions.
In anycase, have a look athttp://en.wikipedia.org/wiki/Bloom_filter
That saves space, not time, and probably isn't appropriate for
such a small table. (Space savings become time savings when the
result in less disk accesses. In his case, however, the
complete table will almost certainly fit into real memory.)
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34