Re: email stop words
On 3/20/2013 10:41 PM, markspace wrote:
On 3/20/2013 4:40 PM, markspace wrote:
When indexing text files, there's a concept known as "stop words", which
are basically really common words that you don't normally want to index.
I just got done with a preliminary part of a project, where I indexed my
gmail inbox by parsing out all the white-space separated words from all
of my emails. For what it's worth, here's the 19 most common words in
my inbox, out of over 600 million characters, nearly 4 million words,
and probably almost 400,000 email messages.
OK, weird. I removed the auto-boxing from the HashMap I was using, and
it got MUCH slower. I'd estimate 30x slower, although I didn't let the
biggest test run to completion.
Any ideas?
Mine run to: I ended up making a lot more objects to avoid the immutable
Integer, and ended up using so much memory the garbage collector started
trashing.
You didn't say exactly what your code was like, but I imagine
you were using a HashMap<Word,Integer> and processing each Word
with something along the lines of
Integer count = map.get(word);
map.put(word, count == null ? 1 : count + 1);
.... and that you switched to something more like
Integer count = map.get(word);
map.put(word, new Integer(count == null
? 1 : count.intValue() + 1);
If so, the slowdown is probably due to increased memory pressure
and garbage collection: `new' actually creates a new object every
time, while auto-boxing uses (the equivalent of) Integer.valueOf().
The latter maintains a pool of a couple hundred small-valued Integers
and doles them out whenever needed, using `new' only for un-pooled
values.
(It's probably not the frequent words that kill you, since
their counts will grow too large to be satisfied from the pool.
But the "long tail" may be murder: Using `new' you'll have many
millions of Integer objects representing small numbers, whereas
by using auto-boxing every "five" would be the same object.)
My suggestion would be to implement a Counter class that
wraps a mutable integer value. Then you'd use
HashMap<Word,Counter> map = ...;
Counter count = map.get(word);
if (count == null)
map.put(word, new Counter());
count.increment();
This way you'd create just one Counter per unique Word, instead
of one Integer for every occurrence of every word. To deal with
the long tail, make Counter extend Number and use
HashMap<Word,Number> map = ...;
Number count = map.get(word);
if (count == null) {
map.put(word, 1);
} else if (count < THRESHOLD) {
map.put(word, count + 1);
} else {
if (count == THRESHOLD) {
count = new Counter(THRESHOLD);
map.put(word, count);
}
count.increment();
}
This uses the pooled Integers as long as they last (they're created
anyhow, so they take no additional space), and then one Counter
object for each Word that appears more than THRESHOLD times.
Or, you could just go back to auto-boxing.
--
Eric Sosman
esosman@comcast-dot-net.invalid