The Norvig code is smarter - it always tries to fill the square with the least options. The Whitney code is dumb - it just recursively tries everything that's not blocked by peers in order. Both backtrack on failure.
The codes are equally general - both work off a data driven peer list (peers, p). The K code runs much faster for most boards, but there are boards in which the Norvig heuristic makes a x100 difference.
Personally, I prefer the K version, although I'm aware I am in the minority.
You are probably only in the minority because K, J, APL and what have you look like perl turned up to 11 for those of us who are unfamiliar with the syntax.
Though if you consider that these are all vector programming languages, they are really made for this kind of thing.
Arthur's languages are awesome, no doubt about it. But the fact remains that they are proprietary and prohibitively so. As much as you romanticize k/q, I bet you can't even afford to run it on your home computer, let alone do any real work on it.
K4/Q 32-bit is free for noncommercial use http://kx.com/trialsoftware.php and has been from the day it became generally available. (And before that, k2/k3/ksql were similarly available)
A free / open source K3 interpreter is being developed in https://github.com/kevinlawler/kona , and while incomplete it is already quite capable.
Oh, and Kx are (or at least were) quite reasonable with commercial use licenses for businesses that can't yet afford them.
> Arthur's languages are awesome, no doubt about it.
Last time I asked (3 or 4 years ago), the smallest installation was ~$100k, and it was a multi-core installation.
IIRC in 2006 they mentioned that they were willing to entertain other financing models (such as equity) if it makes sense, although I have no idea how common that was, or if they are still considering it.
Regardless, the claim that "you can't afford to run it on your home computer" is preposterous - k itself is free for noncommercial use, and kona and J are free, both libre and gratis.
Interesting that the clojure stuff is slower than python. From what I gather most clojure stuff never actually gain any of the possible multi-core performance boost that is one of promises of the language.
Not that I don't like clojure, but part of the hype is that it's supposed to do a lot of the scaling inherently just by the design of the language. But in reality it's never that simple. Switching from map to pmap doesn't do much, actually a whole different way of writing the code is necessary. I'd like to see a version of this that tries to maximise multi core performance, and see what a 12-core mac pro can do with the execution times.
It's a simple port that avoids mutation entirely. The fact that it's only slightly slower than the Python version says a lot about Clojure performance.
In anycase, the OP was clear, the goal was to write a comparison of the original design, not to write the fastest Clojure program (and there are many ways to make the Clojure version faster, yet it's not clear to me how to best Norvig's design in pure Python).
> Interesting that the clojure stuff is slower than python. From what I gather most clojure stuff never actually gain any of the possible multi-core performance boost that is one of promises of the language.
Clojure always sad its designed for CONCURENCY and he said that Clojure has great primitives for parallism. Most people just dont know the diffrence.
> Not that I don't like clojure, but part of the hype is that it's supposed to do a lot of the scaling inherently just by the design of the language.
That wasn't a designgoal of clojure to provid parallism just out of box. It maybe is a designgoal now because everybody wants it to be.
> But in reality it's never that simple. Switching from map to pmap doesn't do much, actually a whole different way of writing the code is necessary. I'd like to see a version of this that tries to maximise multi core performance, and see what a 12-core mac pro can do with the execution times.
pmap does work great for some things but just thinking you can throw in some 'p'-s want wrok. Rich or anybody else never claimed that this will be possible he infact always said that it wan't but people in the internet just dont listen that well.
Clojure always said its designed for concurrency and he said that Clojure has great primitives for parallelism. Most people just dont know the difference.
Well, here's the difference (according to Wikipedia):
Parallelism - a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently ("in parallel"). There are several different forms of parallel computing: bit-level, instruction level, data, and task parallelism. Parallelism has been employed for many years, mainly in high-performance computing, but interest in it has grown lately due to the physical constraints preventing frequency scaling.
Concurrency - a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. The computations may be executing on multiple cores in the same chip, preemptively time-shared threads on the same processor, or executed on physically separated processors. A number of mathematical models have been developed for general concurrent computation including Petri nets, process calculi, the Parallel Random Access Machine model and the Actor model.
I would remove the word "simultaneously" from the concurrency definition. Two threads can be executing concurrently on the same processor - strangely, the next sentence seems to acknowledge this. My personal definitions, based on my experience in systems and high performance computing research:
Parallelism: simultaneous calculations executing in the service of a single problem, usually with the goal of improved performance.
Concurrency: executions in the same time granularity, but not necessarily simultaneous. Also not necessarily in the service of the same problem, but some form of synchronization is required.
Having hacked a decent amount of Clojure, I've learned that Clojure can be very fast or very slow depending on which features of the language one chooses to take advantage of. A perusal of the Clojure Google group will illustrate many examples where a few small changes to a program give an order of magnitude performance boost (or penalty for that matter). This makes it somewhat difficult to write performant code in Clojure (for me at least) as a lot of experimentation is required. Additionally, a given program has to run for at least a little while before hotspot JVM optimizations kick in which make a huge difference.
The gulf between hype and reality rarely converges.
One of Clojure's primary goals is to allow sane mutation and out of that falls a facilitation of concurrency and parallelism. However, it does not solve the problem of effectively utilizing multicore processors automatically. How would it ever do that without programmer intervention?
Of course, it is worth keeping in mind that they didn't also go and try to optimize the Python version. So perhaps after doing that Python would win again.
The design of the Clojure code can be clearly seen from the Python code. But I'm not sure if that's idiomatic Clojure. I'd like to see what the Clojure version would look like if a Clojure programmer solved the problem without looking at the Python code first. That would give me more insight into the differences between the languages.
Follow Norvig's lead from Paradigms of Artificial Inteligence - write fast embedded paradigms. So write a performant Constraint Solver DSL couple it with a performant Prolog DSL. Solve all kinds of problems declaratively instead of just Sudoku. I've been working on that https://github.com/swannodette/logos ;)
Yeah, I started a port of this code into Clojure about a year ago with no attempt to keep the design and it diverged a bit. I never finished it though as my plane landed. :)
Hard to argue with. I don't have a Clojure environment running, but I'd like to see a comparison of Norvig's spell-checker, and Rich Hickey's Clojure translation: http://norvig.com/spell-correct.html
There is a port of the spell checker to clojure. What it does is grind the swap file for about two minutes, then abort with an out of memory exception. Sorry, don't have the link handy.
YMMV. I find that stuff I write in Ruby is faster than that I write in clojure. I suppose it depends on the problem space, if your problems are greatly speeded up by mutability and C bindings then clojure is not a perfect fit.
Sure. I'm not saying I'm a good programmer. From the comments here a lot of people seem surprised that any clojure version isn't automatically faster than a python one, just by the intrinsic fastness of clojure. I just don't think clojure is the go-to language for simple raw speed, but apparently I hit a nerve saying it's not super-fast because I'm getting downvoted.
As a clojure novice I would assume that just by using pmap over map, computation would be faster, but it doesn't seem like it, I've experimented a little but never gotten very good at optimizing speed in clojure, here's a little test where I thought I could get at some multi-core goodness by using pmap, but probably the lazy structures are fooling me.
I'm not sure why your comment is being down-voted, but I can say that my question to you definitely was not meant to imply that you might be a bad programmer. My only point is this: as a budding Haskell enthusiast I am constantly shocked by the difference in succinctness between my solutions and those of the experts. However, I would never say that because of my lack of familiarity with Haskell idioms Haskell is a verbose language.
The rote replacement of map with pmap will never work as a general solution because there is overhead involved with using pmap. The impact of the overhead requires thoughtfulness in usage on a case-by-case basis.
I find that a few real-life experiments with clojure has been disturbingly slow, and that it's not trivial to optimize speed with lazy structures and magic background threads. Although some web stuff I've done has been pretty spiffy.
Anecdotally, at what point this is true also seems to depend on the host OS. Windows 7's pmap was beneficial at a lower n than Mac OS X's for a simple O(n) function. I have always wondered why this is.
While sometimes it's great that you have the option to use C bindings in Ruby, my take is that if possible you should write stuff in Ruby when doing Ruby. If that's not the case you are not doing ruby, you are doing C.
I would write clojure and drop back to java for speed. Only in a extrem case I would then use C, but its possible. I haven't done it but read that its not all that bad. (there is a clojure wrapper.
Remember the mantra: servers are cheap, programmers are expensive. If you have a language that's significantly faster to develop with but at a small performance price, i'd still go with it.
If the app becomes a Google-sized success, then I'll worry about performance. Chances are I'll never have to.
You know, part of the reason Google is Google is that they were worried about performance from day 1 - every possible kind of performance.
AltaVista was king at the time. It gave low quality answers, true -- but it was also slow. All the early adopters that I know of that switched to Google were impressed more by its speed than by its quality - if you knew what you were searching for, you DID get high quality content from AltaVista at the time (much like you could with Google even before the recent "farmer" update, despite the complaints from all over). What you couldn't get from AltaVista, no matter how much you tried, was a speedy answer. AltaVista would take 5 seconds; Google would have a response in 0.05 seconds.
Unless your app is defining a new niche, you have to compete with the current players. Facebook needed to compete with MySpace. Google needed to compete with AltaVista.
Google did it by storing an index of the whole internet in Ram. That's performance you worry about from day one, not something you can add in retrospect.
> Google did it by storing an index of the whole internet in Ram. That's performance you worry about from day one, not something you can add in retrospect.
It really depends on implementation. I have changed many applications from RDBMS-based to file-based to memory-based when the need arose. Of course, if you intend speed to be your competitive advantage, then you need to optimize early.
Yes, our current release implements Python 2.5 completely, and our trunk implements 2.7. As for speed, I'll let: http://speed.pypy.org/ speak for itself.
I feel like his reduce-true could be implemented with take-while and reductions, but my Clojure isn't strong enough to produce it. (last (take-while identity (reductions f ns)))) is close, but we need to take one more element than take-while does.
The spikes you are mentioning might be due to the OS lowering your process priority. If you are on a FreeBSD machine, try running rtprio(1) to avoid the OS changing the process priority upon extensive CPU usage.
The spikes are from hard problem instances - he's not running on the same data set each time.
From Norvig's post:
But the main message is that the mean and median stay
about the same even as we sample more, but the maximum
keeps going up--dramatically. The standard deviation
edges up too, but mostly because of the very few very
long times that are way out beyond the 99th percentile.
This is a heavy-tailed distribution, not a normal one.
They are more likely due to properties of the puzzles themselves than operating system behaviour, especially on a modern operating system on a multi-core machine. Plus, in the original Norvig article (http://norvig.com/sudoku.html) he talks about several puzzles which take 10s and 100s of seconds to complete, which is extremely unlikely to be due to scheduler behaviour.
With languages like Python and Clojure several background processes (like GC pauses) could also contribute to some drops in throughput.
Of course, it would be easy to tell these cases apart by counting operations (backtracks, etc) rather than time.
As much as I like lisp the beauty, strength and philosophy of Lisp, it seems like I can't make the switch in my real production project. Why? Because of the readability: (Taken from the article)
So, I see that and I'm like, wtf, where do I start.
let width .. inc apply max of map comp coun, wtf. Let's start from the end.
map all squares with comp count values, take the max of those, increment it, put that in width. ok
then, line join repeat 3 join.. wtf. let's try it from the end;
minus three times the width repeat.. ok, repeat 3width '-', then, join this, repeat it 3 times, then join again with +, and put that in line.
I always struggle like that when reading lisp, people always give example like:
(map square '(1 2 3 4)) where you can read it all in one pass.. but real code is usually more complicated. So, if I had to rewrite that more clearly, I'd probably just separate it in more functions so I don't have to have more than, say 4 nested ().
And, yeah, the problem is not that much the "read from the end", but more about the actual work of each line of lisp being a puzzle to guess where to start reading it. Some are better to read up front, others are better to start from the last. Sometime you skip the first part, and read the last part, then come back at the beginning. That is what trouble me. I want to be able to read code as fast as possible - skim over it while understanding it.
Now, you might argue that you can write nested stuff in every languages. True enough BUT it seems like the philosophy in python is more about making things clearer and using more function if it makes everything simpler/easier to maintain and understand.. while in practically all lisps code I read, it feels like it is a write-only code without thought about you will read it after.
Is it because all the "Here's why lisp is better" are written by new-lisper who are too much excited as they can now use closures and nest everything rather than using simple, yet useful, normal functions?
When I read lisps forum, it's always about how that or that doesn't support tail recursive function or why macro rocks everything, but never talking about readability and good practices about not nesting everything up. Yeah, they say to use real editor, to never look at the (), to align thing smartly.. I don't know for you, but I feel like my brain works in a kind of stack. I can put some stuff in my short memory, but I can't put more than say 5-6 stuff at once. And when I see this:
(let [width (inc (apply max (map (comp count values) squares)))
It just seem too much to read it quickly; I need to stop and think. Yeah, some laugh at me saying "Yeah, you need to think*! You are not used to that! Well, no, when I'm reading a book, I like to think about the concept or the story, not trying to figure out how to read that complicated sentence.
When I read python code, I think about pattern, modularity, what's the goal of the actual file. When I'm reading lisp, I can't go quickly into it because of those 10 levels nested function.
len(values[s]) for s in squares)
(map (comp count values) squares)
How is that better! If you know the standard function this is super easy (in both languages). Note clojure is just one pure function call nothing fancy.
(inc (apply max
1+max
The expressivness is tiny bit better in python because the max function looks at the type of the input. apply is a commen pattern that is easy to anderstand. The python way is a little bit easier to read but the clojure way makes the library simpler.
line = '+'.join(['-'*(width*3)]*3)
line (join \+ (repeat 3 (join (repeat (* 3 width) \-))))
The thing that makes python shorter here is that they alow math on non number. I don't think that a good idea in general but that up to the language designers taste. The diffrence between the code is basiclly that in clojure you have to use repeat two times instead of * and one more join.
So only real diffrences are on the first line clojure uses apply and on the second repeat instead of join.
I think is just a matter of training. Much harder then the language reading is to know what the standard functions really do.
I love Lisps, and I have the same problem. You really have to learn to approach reading code in a different way. Lisp (and Haskell, say) are so information-dense that you just have to look closely at every word to understand what is going on, as opposed to C or Python where you can glance at a "paragraph" of code and get a decent sense of what it is doing , because it is basically executing a set of statements in order. Probably the closest you get to this dense unpacking issue in Python is when reading a gnarly list comprehension.
The upside is that the code actually is smaller, so you have to read less of it. But I agree that it is fatiguing to read dense code that you can't really skim.
The Norvig code is smarter - it always tries to fill the square with the least options. The Whitney code is dumb - it just recursively tries everything that's not blocked by peers in order. Both backtrack on failure.
The codes are equally general - both work off a data driven peer list (peers, p). The K code runs much faster for most boards, but there are boards in which the Norvig heuristic makes a x100 difference.
Personally, I prefer the K version, although I'm aware I am in the minority.