var top = (from w in text.Split(' ')
group w by w into g
orderby g.Count() descending
select g.Key).Take(10); from word in text.Split(' ')
group word by word into g
let count = g.Count()
orderby count descending
select g.Key
Under the covers when it is compiled it's turned into a select. That way it it only does N counts, not potentially N log N (for each comparison in the orderby), where N is the number of items you enumerate (so if you .Take() just 10 it doesn't really matter). (->> (string/split ... #"\s+")
frequencies
(sort-by val)
reverse
(take 10))Much as I love Clojure, it's worth pointing out that Clojure's lazy sequences (include intermediate sequences) get cached, while LINQ evaluates more like Clojure's reducers. (You can even get it to do so in parallel.)
On a side note, I'd like to point out a key difference between this Clojure example and corresponding variants in C#, Python, &c: the Clojure variant has no variables. This isn't just a matter of concision: coming up with descriptive names is hard, and usually means duplicated information, either in the name or the type declaration. Often, those names are re-used over and over again with subtly different meanings, for each stage in a pipeline--forcing the reader to reason carefully about the declaring scope at each use.
Consider, for example:
Swimmer swimmer = new Swimmer("foo");
swimmer.setStyle("butterfly");
swimmer.swim();
return swimmer;
(doto (Swimmer. foo)
(.setStyle "butterfly")
.swim)
Same operation--but with (doto), four uses of a variable and one type declaration have been cleared away. Consider the original post: var words = s.Split(' ');
var wordCounts = words.GroupBy(x => x).Select(x => new { Name = x.Key, Count = x.Count() }).OrderByDescending(x => x.Count);
var countedWords = wordCounts.Select(x => x.Name).Take(10).ToList();
return ExtractTopTen(countedWords);
Six uses of three formal variables, including the bewilderingly confusable countedWords and wordCounts, plus nine uses of the delightfully generic "x". Even in the more compact C# example from this thread, consider: var top = (from w in text.Split(' ')
group w by w into g
orderby g.Count() descending
select g.Key).Take(10);
This variant refers to the temporary variables w (for "words") and g (for "groups"?) six times. Both authors felt the need to reduce the repetition of variables, but the best they could do was to choose single-character names.This is the real power of ->, .., ->>, doto, and friends: eliminating names for things. By thinking about the composition of transformations, instead of the intermediate results, you can make an algorithm easier to understand and change.
I totally agree with you on this.
>Even in the more compact C# example from this thread, consider: var top = (from w in text.Split(' ') group w by w into g orderby g.Count() descending select g.Key).Take(10);
> This variant refers to the temporary variables w (for "words") and g (for "groups"?) six times. Both authors felt the need to reduce the repetition of variables, but the best they could do was to choose single-character names.
> This is the real power of ->, .., ->>, doto, and friends: eliminating names for things. By thinking about the composition of transformations, instead of the intermediate results, you can make an algorithm easier to understand and change.
You lost me somewhere along the way....are you saying the "from w in text"... snippet is bad, and something more along the lines of "This is the real power of ->, .., ->>" is more appropriate?
I ask because that code seems extremely readable to me. Personally, I don't give a shit if it's 30% more verbose or runs 50% slower, for 99% of code (written in the world), optimum performance doesn't matter. Maintainability does matter though. All of this software being written today has to be either maintained by someone, or replaced by something else. And the top ~2% of programmers like you sure as hell aren't going to be taking maintenance jobs any time soon.
I'm curious what the thoughts of a technically smart person such as yourself are on the subject of what companies will be left with 5 to 10 years down the road when consultants have come through and implemented using the currently most optimum platform/language/algorithms?
And I honestly don't mean for this question to be disrespectful. I'm just coming from a situation where I'm a former developer but on a project where I'm not coding, and I ask for features and the developers say they can't do it, or it will be a performance problem. And I know these guys are far more like you than me intelligence/education wise, but the things I ask for I've done tons of times in the past with 10 to 1000 times the data size, without a problem, on far older hardware.
I'm just curious what kind of a support problem you ultra smart people are leaving behind, or if you ever think about the idea that almost no on else is as smart as you?
1. As simple as humanly possible, so that the algorithm is easy to understand and change. Each component is isolated and can be understood and modified in isolation. Boundaries between component and environment are clearly thought-out.
2. As simply expressed as possible: broken up into distinct, well-organized functions, with descriptive, regular names for functions and variables, in context.
3. Well-documented; each function and each namespace come with contextual docs explaining their motivation, arguments, consequences, invariants, etc., with examples.
4. As short as possible, because humans have trouble holding large amounts of context in their head. Minimize the amount of scrolling or jumping between files necessary to understand the algorithm.
5. Well-tested, so that changes can be made freely. The test suite needs to be fast, so one can get feedback within seconds of making a change to the file; ideally a few milliseconds. A balance of typechecking, logical tests with mocks, integration tests, and full stress tests provides a continuum of safety.
I don't see these goals as particularly constrained to any language, but I will say that I feel best able to achieve them in a Lisp. Dunno whether that helps you project your problems at work onto me personally, though. ;-)
return s.Split(' ')
.GroupBy(word => word)
.OrderByDescending(wordGroup => wordGroup.Count())
.Select(wordGroup => wordGroup.Key)
.Take(10).ToList(); return new Swimmer("foo")
{ Style = "butterfly"}
.swim();
It is unidiomatic to have Swimmer.swim return 'this', though. var result = new Swimmer("foo")
{ Style = "butterfly"};
result.swim();
return result;I speak as someone who codes in C# for work and Clojure as a hobby. There's lots of things that just aren't quite possible in C#, and _everything_ is possible in Clojure.
Pointfree is beautiful to read and grok. It's a little trickier to debug, since pretty much every debugger on earth needs points to inspect values.
Edit: Actually, we can also get rid of the 'reverse' by replacing (sort-by val) with (sort-by (comp - val)). Not going to be shorter in terms of character count, though we win on line count.
(->> (string/split s #"\s+")
frequencies
(sort-by val >)
(take 10))
Just mentioning it here because I find it vastly more readable than (comp - val). from collections import Counter
Counter(s1.split(' ')).most_common(10) doStuff = require("doStuff");
var result = doStuff(theString);
isn't JS so efficient?!?Just like math homework back in the day, the teacher didn't do it to check your answer, they did it to check how you arrived at your answer.
I would expect a good candidate to:
1. know that a heap is optimal here (remembering whether Counter uses it is optional)
2. express reluctance to implement it from scratch because surely the stdlib can do it better.
So IMHO using libraries like this ruins the question only in the sense of showing its not a challenge for the candidate. Something so simple should not take a page of code.
Creating a heap is O(n) if I remember correctly, so that may well be the most efficient solution.
Therefore, I am unlikely to take the job.
Just to give another example, our consulting company still gets requests for projects to be deployed against Java 1.4!
d = {}
for word in s1.split(' '):
try:
d[word] += 1
except KeyError:
d[word] = 1
print [(x, d[x]) for x in sorted(d, key=d.get, reverse=True)][:10]d[word] = d.get(word,0) + 1
dictionary.get is quite useful.
Also, I'd consider s.split(None), instead of s.split(' '). It will group whitespace, so that any double space or other whitespace is collapsed into one delimiter.
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. 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).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.
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.
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.
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 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.
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.
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.
d3.entries((s.split(" ").reduce(function(p, v){
v in p ? p[v]++ : p[v] = 1;
return p;}, {})))
.sort(function(a, b){ return a.value > b.value; })
.map(function(d){ return d.key;})
.slice(-10); array_count_values(...)
arsort(...)
array_slice(...)
Thinking.. two of these things belong together, two of these things are kind of the same.. but one of these things is doing his own thing...Seriously built in method naming and argument ordering don't follow any consistent convention in PHP, that's always been the most irksome thing to me...
s1 = 'a a a a a a a a a a a a a a a a A A A A A A A A A A A A A a. a. a. a. a. a. a. a. a.'
those two lines give:
[('a', 16), ('A', 13), ('a.', 9), ('', 1)
(HN might collapse the double space in s1)
Like this here Commonest[StringSplit[string], 10]sorted([(i,sum([i==j for j in s.split()])) for i in list(set(s.split()))],key=lambda x:x[1],reverse=True)[:10]
Uh, no. Your solution just uses a bunch of standard library functions (at least, I hope they're not syntactic forms… and why a function as specific as "frequencies" not in some namespace boggles my mind). I could write that in C with an appropriate standard library.
Ironically, expressing this in something like SQL actually speaks to the expressivity of the language because the solution was produced entirely with syntactic forms.
The fact that such functions are at a Clojure programmer's fingertips is exceptionally important. If you strip out the core functions (and macros) from any lisp or Clojure you are left with almost nothing( see http://stackoverflow.com/questions/3482389/how-many-primitiv...).
Consider that in Clojure, a common act transforming one datastructure into another. Typically only a few kinds: maps, sets, and some kind of sequence.
What is a highly common generic transformation of a sequence to a map? `frequencies`. Particularly since you'd only be doing this with pretty finite sequences, given the finite nature of the built-in maps. Finite here means countable. What generic, domain-independent thing would you be counting? Often, the items themselves.
What? Pure untyped lambda calculus does things "only with syntactic forms". Don't tell me that your solution wouldn't use some basic operators other than rudimentary syntax. Keep in mind that in Lisp-family languages, many things that are a part of syntax in other languages are actually simple functions - arithmetic operations being a case in point - so you really can't avoid using library functions.
I believe that the major point of Clojure etc. is that they provide concise basic operations that you can use everywhere to compose complex operations better than you can do with, say, C#.
Imports System.Linq s.Split(' ').GroupBy(x => x).OrderByDescending(x => x.Count()).Select(x => x.Key).Take(10).ToList();
I'd say 13 characters isn't really a huge differentiator. They're both using exactly the same algorithm, almost exactly the same built-in library functions, and have exactly the same flexibility for programmers to add their own (C# is using extension methods which lets you add methods that look like they belong to the class, but are actually static methods defined elsewhere).There's a lot of benefits to Clojure over C#, but the ability to chain functional list operators really isn't one of them.
tr 'a-z' 'A-Z' | sed 's/[^A-Z][^A-Z]*/\ /g' | grep -v '^$' | sort | uniq -c | sort -nrk1 | head -10
edit: I don't know enough about HN,there should be a newline after the backslash in the sed command.
$ < bible-pg10.txt tr -cs a-zA-Z '\n' | sort | uniq -c | sort -nr | head
62265 the
38915 and
34588 of
13474 to
12846 And
12589 that
12387 in
9762 shall
9668 he
8942 unto
I have a `bins` script that is just `sort | uniq -c | sort -nr`, so that reduces to `tr -cs a-zA-Z '\n' | bins | head`.Unix for Poets, man. It's the shit.
echo $sentence | rs -T | sort | uniq -c | sort -rn|head -10
$ echo Foo foo foo. | rs -T
Foo
foo
foo.
$ echo Foo foo foo. | tr 'a-z' 'A-Z' | sed 's/[^A-Z]/\
/g' | grep -v '^$'
FOO
FOO
FOO
Also the link mentioned using wiki articles for testing, so they would have paragraphs and that's where reshape shines for things like emails, but fails here: $ cat foo
Foo
foo
foo.
$ <foo rs -T
Foo foo foo.
$ <foo tr 'a-z' 'A-Z' | sed 's/[^A-Z]/\
/g' | grep -v '^$'
FOO
FOO
FOO
That that's though makes me think, should I treat contractions special? What about plurals? It's starting to get silly now.What's interesting though is how UNIX shell, being essentially a symbolic FP language, allows one to solve the problem in a clear and concise way. And if one desires, the program can be easily modified to read sentences, say, from network from ssh tunneled via HTTPS. That kind of flexibility can rarely be achieved in languages like C# with tight coupling between the units of abstraction.
In practice, if you use ->> and write neater LINQ, the code is very close. Although LINQ only has group and sum/reduce, no dedicated frequencies function.
In Common Lisp you'd usually supply a TEST keyword parameter (#'STRING= or #'EQUAL in this case). Does Clojure use Java's type system to infer?
(defn frequencies
"Returns a map from distinct items in coll to the number of times
they appear."
{:added "1.2"
:static true}
[coll]
(persistent!
(reduce (fn [counts x]
(assoc! counts x (inc (get counts x 0))))
(transient {}) coll)))def top10(s: String) = s.split(' ').groupBy(identity).mapValues(_.size).toList.sortBy(-_._2).take(10).map(_._1)
def mostCommon(str: String, num: Int) = { str.split(" ").groupBy { s => s} .map { case (k,v) => k -> v.length }.toList .sortBy { _._2 }.reverse.take(num).map { _._1 } }
Edit: remember to sort! (Forgot my coffee this morning...)
Edit again: and aphyr's solution is even more concise and idiomatic, where `s` is the first paragraph of the blog post: