Peter Norvig's Sudoku solver: Clojure & Python side by side
jkkramer.wordpress.com
jkkramer.wordpress.com
p,:3/:_(p:9\:!81)%3
s:{*(,x)(,/{@[x;y;:;]'&21=x[&|/p[;y]=p]?!10}')/&~x}
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.
Though if you consider that these are all vector programming languages, they are really made for this kind of thing.
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.
That is the only true thing you wrote.
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.
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.
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).
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.
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.
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.
but part of the hype
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?
Initially Python was faster, however after some discussion and some performance optimisations Erlang got faster: http://erlang.org/pipermail/erlang-questions/2011-March/0571...
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.
Not true according to these microbenchmarks and certainly not in my own experience.
I find that stuff I write in Ruby is
faster than that I write in clojure.
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.
https://github.com/sunkencity/Adaptor-Reductor/blob/master/s...
Sure. I'm not saying I'm a good programmer.
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.
A beautiful deck, may I add!
1. I guess you compair small programms and clojure suffers from the JVM startup slowness not because of the clojure implementation.
2. You can use java objects, collection or arrays from clojure its just not often used.
3. Clojure has very good Java bindings and I think the C bindings arn't that bad. (there is a wrapper ofer the normal java stuff)
I guess ruby only performs better for scripting.
http://shootout.alioth.debian.org/u32/benchmark.php?test=all...
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.
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.
I am amazed that Python ran anywhere close to Closure in terms of speed, let alone faster!
Don't want to start a religious war,
but to me the Python code just looks more
clean.
I do agree that the python code looks a little cleaner but both look fine.
Edit: did the down-voters ever cared to read the code or even write a Python module in C?
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.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.
(let [width (inc (apply max (map (comp count values) squares)))
line (join \+ (repeat 3 (join (repeat (* 3 width) \-))))]
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)))
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.
/end of rant.
len(values[s]) for s in squares)
(map (comp count values) squares)
(inc (apply max
1+max
line = '+'.join(['-'*(width*3)]*3)
line (join \+ (repeat 3 (join (repeat (* 3 width) \-))))
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.
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.
(inc (->> squares (map (comp count values))
(reduce max)))
Deleted comment
Update: Ah, it looks like you can get literal asterisks if you use your whitespace carefully:
* asterisk * another one emphasis