4 ms·

I'm a newbie, but the question seemed approachable so I went for it. This is what I came up with. (Python, btw.) def top_ten(s): words = s.split(' ')

by spenuke 13y ago

I'm a newbie, but the question seemed approachable so I went for it. This is what I came up with. (Python, btw.) def top_ten(s): words = s.split(' ') word_list = set(words) return sorted(word_list, key=lambda x: words.count(x))[:10] The question didn't ask for word counts, so I didn't see the need for a dictionary. I'd appreciate any advice on my solution. I'd be thrilled if I'm not too far off from being capable of starting to apply for jobs.

jessedhillon 13y ago
This is a great approach. Even better because you carefully examined the requirements and found an interpretation which allowed you to make an optimization (words only, not counts, therefore sets are useful)
- jules 13y ago
  This isn't an optimization. He turned a O(n) algorithm into a O(n^2) one.
matchu 13y ago
The need for the dictionary shows up when your text gets significantly large. Each call to `words.count` is going to re-examine each word of the text to count 'em up, so, if n is the number of words in the text, and m is the number of distinct words in the text, then this solution is at least O(mn + nlog(n)) whereas the dictionary-based solution is O(nlog(n)). That is, we're re-reading the word list over and over, whereas the dict-based solution only reads it once. It's therefore more likely to be more efficient. But I like the readability of this solution and there's a strong argument to be made for it on that basis, especially if the string is short. If this were a job interview, this would be a totally acceptable solution, though it'd be important to be able to discuss why other solutions might be faster and why you prefer this one anyway.
- spenuke 13y ago
  Hey, thanks much! I'm going to have to spend some time with these logarithmic evaluations to really get what you're saying, but I dig the basic concept. Very helpful.
- kyllo 13y ago
  Isn't the difference between O(mn + nlog(n)) vs O(nlog(n)) running time going to get less significant as the value of n gets larger? I thought the whole point of Big O / asymptotic analysis is that you can ignore lower-order terms and constant factors because they are insignificant for any appreciably large input size. And also because the lower order terms and constant factors vary too much depending on the programming language, the compiler or VM, the hardware, etc.
  - spenuke 13y ago
    I'd never heard of Big O until this thread, but from what I can tell it'll only be when a solution is in the O(logn) that "running time will get less significant as n gets larger". This is simply the way you describe logarithmic growth, so maybe that's where you got confused. Also, wouldn't it be fair to say that a logarithm (nlogn) is a lower order term than mn? In which case your definition stands. At any rate, I wanted to test this out, so I made a naive benchmark for running these functions. The dict solution was ten times faster (0.0011s vs 0.015s) than the list version with ~1350 words. The dict solution ran in 0.13s at ~162,000 words, while I waited a couple minutes before killing the list version on that input.
    - kyllo 13y ago
      Oh, you're right, m is not a constant but also varies somewhat independently of n, so you can't exclude it from the big O notation. And whether mn or nlogn is the lower order of the two terms depends highly on the value of m, which is the number of unique words in the text. A really long text that's just the same word over and over will have a big n but a small m.
      - matchu 13y ago
        Worst-case big-O runtime is therefore O(n^2), and best case is O(n log(n)) :)
abecedarius 13y ago
Nice. Just a little fixing and polishing: def top_ten(s): words = s.split() return sorted(set(words), key=words.count, reverse=True)[:10] (to get the most common words instead of the least).
shill 13y ago
> I'd appreciate any advice on my solution. You should always compare your results to what is expected. For a problem like this, use a small set of test data that can easily be counted and sorted in your head or on paper. You forgot reverse=True and your results show the 10 least common words. ;) This kind of error happens to all of us. That's why we have unit tests and QA teams. If you made this mistake during an interview I wouldn't give it much importance and we would have a good laugh about it.
- spenuke 13y ago
  Ha, nice! Funny you should mention that. I did exactly that when tooling around in the repl and forgot the reverse kw, saw something fishy, and fixed it. Promptly forgot it again when I typed it in this comment. :)
kyllo 13y ago
Ooh, this is fun! In Ruby, without imports/requires: def toptenwords(str) words = str.split words.sort_by{|word| words.count(word)}.uniq.reverse.take(10) end or as a one-liner, without any variable declarations in the function scope: def toptenwords(str) str.split.sort_by{|word| str.split.count(word)}.uniq.reverse.take(10) end
- kragen 13y ago
  I think this version and spenuke's version are impractically slow, but yours is actually O(N²). If you give it an 824 000 word input, it will do 0.6 quadrillion word comparisons, which you will probably not be willing to wait for. A more practical solution: counts = Hash.new { 0 } IO.read('bible-pg10.txt').split.each { |w| counts[w] += 1; } counts.keys.sort_by { |w| -counts[w] }.take 10 This is still O(N lg N) instead of O(N lg 10) like the Python version, but it's good enough this time; it still gave me ["the", "and", "of", "to", "And", "that", "in", "shall", "he", "unto"] reasonably quickly. I'd be interested to see if there's a way to do this in a single expression in Ruby.
  - kyllo 13y ago
    I actually was working on a hash-based solution first, using group_by, but I switched to using just array after seeing the Python version. I didn't really think about the time complexity of the count operation inside the sort_by operation, thanks for pointing that out. You definitely can do a hash-based solution in a single expression in Ruby. Here's a very ugly and kludgy example that you could probably improve on if you wanted to. I don't think it's n^2 because the group_by just counts the occurrences of each word and returns a hash where the count is the key: str.split.group_by{|w| str.split.count(w)}.sort_by{|k,v| k}.reverse.flatten.uniq.keep_if{|w| w.is_a?(String)}.take(10) I'm also trying to work out a better way to do this using "chunk" because although hashes are fast to access, they are not fundamentally sortable, and sort_by returns a 2d array just like chunk does anyway.

by spenuke 13y ago

jessedhillon 13y ago

This is a great approach. Even better because you carefully examined the requirements and found an interpretation which allowed you to make an optimization (words only, not counts, therefore sets are useful)

jules 13y ago
This isn't an optimization. He turned a O(n) algorithm into a O(n^2) one.

matchu 13y ago

The need for the dictionary shows up when your text gets significantly large. Each call to `words.count` is going to re-examine each word of the text to count 'em up, so, if n is the number of words in the text, and m is the number of distinct words in the text, then this solution is at least O(mn + nlog(n)) whereas the dictionary-based solution is O(nlog(n)). That is, we're re-reading the word list over and over, whereas the dict-based solution only reads it once. It's therefore more likely to be more efficient. But I like the readability of this solution and there's a strong argument to be made for it on that basis, especially if the string is short. If this were a job interview, this would be a totally acceptable solution, though it'd be important to be able to discuss why other solutions might be faster and why you prefer this one anyway.

spenuke 13y ago
Hey, thanks much! I'm going to have to spend some time with these logarithmic evaluations to really get what you're saying, but I dig the basic concept. Very helpful.
kyllo 13y ago
Isn't the difference between O(mn + nlog(n)) vs O(nlog(n)) running time going to get less significant as the value of n gets larger? I thought the whole point of Big O / asymptotic analysis is that you can ignore lower-order terms and constant factors because they are insignificant for any appreciably large input size. And also because the lower order terms and constant factors vary too much depending on the programming language, the compiler or VM, the hardware, etc.
- spenuke 13y ago
  I'd never heard of Big O until this thread, but from what I can tell it'll only be when a solution is in the O(logn) that "running time will get less significant as n gets larger". This is simply the way you describe logarithmic growth, so maybe that's where you got confused. Also, wouldn't it be fair to say that a logarithm (nlogn) is a lower order term than mn? In which case your definition stands. At any rate, I wanted to test this out, so I made a naive benchmark for running these functions. The dict solution was ten times faster (0.0011s vs 0.015s) than the list version with ~1350 words. The dict solution ran in 0.13s at ~162,000 words, while I waited a couple minutes before killing the list version on that input.
  - kyllo 13y ago
    Oh, you're right, m is not a constant but also varies somewhat independently of n, so you can't exclude it from the big O notation. And whether mn or nlogn is the lower order of the two terms depends highly on the value of m, which is the number of unique words in the text. A really long text that's just the same word over and over will have a big n but a small m.
    - matchu 13y ago
      Worst-case big-O runtime is therefore O(n^2), and best case is O(n log(n)) :)

abecedarius 13y ago

Nice. Just a little fixing and polishing: def top_ten(s): words = s.split() return sorted(set(words), key=words.count, reverse=True)[:10] (to get the most common words instead of the least).

shill 13y ago

> I'd appreciate any advice on my solution. You should always compare your results to what is expected. For a problem like this, use a small set of test data that can easily be counted and sorted in your head or on paper. You forgot reverse=True and your results show the 10 least common words. ;) This kind of error happens to all of us. That's why we have unit tests and QA teams. If you made this mistake during an interview I wouldn't give it much importance and we would have a good laugh about it.

spenuke 13y ago
Ha, nice! Funny you should mention that. I did exactly that when tooling around in the repl and forgot the reverse kw, saw something fishy, and fixed it. Promptly forgot it again when I typed it in this comment. :)

kyllo 13y ago

Ooh, this is fun! In Ruby, without imports/requires: def toptenwords(str) words = str.split words.sort_by{|word| words.count(word)}.uniq.reverse.take(10) end or as a one-liner, without any variable declarations in the function scope: def toptenwords(str) str.split.sort_by{|word| str.split.count(word)}.uniq.reverse.take(10) end

kragen 13y ago
I think this version and spenuke's version are impractically slow, but yours is actually O(N²). If you give it an 824 000 word input, it will do 0.6 quadrillion word comparisons, which you will probably not be willing to wait for. A more practical solution: counts = Hash.new { 0 } IO.read('bible-pg10.txt').split.each { |w| counts[w] += 1; } counts.keys.sort_by { |w| -counts[w] }.take 10 This is still O(N lg N) instead of O(N lg 10) like the Python version, but it's good enough this time; it still gave me ["the", "and", "of", "to", "And", "that", "in", "shall", "he", "unto"] reasonably quickly. I'd be interested to see if there's a way to do this in a single expression in Ruby.
- kyllo 13y ago
  I actually was working on a hash-based solution first, using group_by, but I switched to using just array after seeing the Python version. I didn't really think about the time complexity of the count operation inside the sort_by operation, thanks for pointing that out. You definitely can do a hash-based solution in a single expression in Ruby. Here's a very ugly and kludgy example that you could probably improve on if you wanted to. I don't think it's n^2 because the group_by just counts the occurrences of each word and returns a hash where the count is the key: str.split.group_by{|w| str.split.count(w)}.sort_by{|k,v| k}.reverse.flatten.uniq.keep_if{|w| w.is_a?(String)}.take(10) I'm also trying to work out a better way to do this using "chunk" because although hashes are fast to access, they are not fundamentally sortable, and sort_by returns a 2d array just like chunk does anyway.