-1
$\begingroup$

Find the 10 top most occurring strings in a huge array of Strings.

Since the array is huge, it is not possible to load it in memory completely. My idea is to parse the arrays one by one and put the strings in a hash table with string as key and occurrence count as value. But this would take too much memory.

Is there any other optimized solution? Given that we only care about top 10 keys.

$\endgroup$
  • 2
    $\begingroup$ Your question is poorly written. The title is a very clear question by itself. But the text of the question has no (single) string, but many arrays of objects (whatever that may be: symbols, symbol strings, ...?). There seem to be an undecipherable confusion between the statement of the otiginal problem and your attempt at a specific solution which may or may not be workable. Asking questions properly is the first step towards answering them, either by people who help you, or by yourself. I also assume you meant to say: "... hash table with objects as keys and occurrence counts as values ...". $\endgroup$ – babou May 30 '15 at 10:11
  • $\begingroup$ this question looks related, or even a possible duplicate. $\endgroup$ – Ran G. May 30 '15 at 18:33
1
$\begingroup$

One optimized way is a streaming algorithm given by Charikar, Chen and Farach-Colton, known as CountSketch. See

It takes logarithmic space (in the size of your input), and gives an approximation for the $k$ most-frequent elements in that input. $k$ is an input parameter, that also affects the memory in use.

There are also extensions for sliding windows algorithms, and to other ways of measuring which element is considered "frequent".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.