61–70 of 72 posts
Obligatory programming language shootout link: http://benchmarksgame.alioth.debian.org/
The project name changed 6 years ago. "The Virginia Tech shooting in April 2007 once again pushed gun violence into the media headlines. There was no wish to be associated with or to trivialise the slaughter behind the phrase shootout so the project was renamed back on 20th April 2007 - The Computer Language Benchmarks Game." http://benchmarksgame.alioth.debian.org/dont-jump-to-conclus...
A small personal peeve: it doesn't make sense to say that Sudoku is NP-hard, as the linked post does (or NP-complete). First of all, this benchmark (as far as I can tell) uses only traditional 9x9 puzzles, of which there is a finite number. Problems with a finite input space are trivial from the point of view of complexity theory; in order to talk about any kind of completeness or hardness results, you need to genera…
Finding and understanding computational algorithms is part of my daily work. I know what time complexity means. By saying NP-hard, I mean an NxN sudoku cannot be solved in time polynomial to N. Most sophisticated sudoku solving algorithms, including mine, do not assume the grid has a solution or one solution. They test and give all possible solutions. I am really trying to solve an NPC problem. That said, your commen…
About the complexity of Sudoku which is known to have a unique solution: I didn't say there is a polynomial algorithm for it. It's equivalent to the Unambiguous SAT problem, and Valiant and Vazirani proved that it's in some sense almost as hard as the SAT problem itself. You can't call it NP-complete (because that's not known), but if there is a polynomial algorithm for it, then there is a probabilistic polynomial algorithm for every problem in NP; and since you can run a probabilistic algorithm as many times as you want and get independent results, you'd be able to solve every decision problem in NP with immense certainty (although less than 1).
About efficient algorithms for Sudoku, I think that the crux here is average case complexity (defined in some way over the sort of samples you are using). It's not clear to me that average case complexity for Sudoku is high, at least for the kind of puzzles we know how to generate. Certainly solvers based on backtracking seem to handle them very well. It's very hard to prove results about that, though. In any case, if someone has a polynomial time algorithm for Unambiguous SAT, or something equivalent to it, that would pretty amazing (but I doubt it - the average time might be very good, though).
Earlier quoted context omitted.
Finding and understanding computational algorithms is part of my daily work. I know what time complexity means. By saying NP-hard, I mean an NxN sudoku cannot be solved in time polynomial to N. Most sophisticated sudoku solving algorithms, including mine, do not assume the grid has a solution or one solution. They test and give all possible solutions. I am really trying to solve an NPC problem. That said, your commen…
Yeah, I have no problem with that if it's viewed as an NxN problem. I do have a slight tic about this since I've heard "NP-hard" misused so often, including by one guy at a former workplace whose program needed to test all 6 permutations of something-or-other to discover the optimum one, and that was "NP-complete", you see. About the complexity of Sudoku which is known to have a unique solution: I didn't say there is…
Earlier quoted context omitted.
The project name changed 6 years ago. "The Virginia Tech shooting in April 2007 once again pushed gun violence into the media headlines. There was no wish to be associated with or to trivialise the slaughter behind the phrase shootout so the project was renamed back on 20th April 2007 - The Computer Language Benchmarks Game." http://benchmarksgame.alioth.debian.org/dont-jump-to-conclus...
That is ridiculous.
Update the Go example to use 1.1 :D
It's been just 2 days since go1.1beta1 was released, the other language implementations seem more out-of-date than that.
Truthfully though, I didn't notice the others were out of date. I bet OP will update them all :P
Earlier quoted context omitted.
It looks like Go 1.1 might be faster than Java. That might help convince enterprise developers to adopt it.
No way would a microbenchmark ever change any responsible person's mind about tooling. There are a lot of reasons (some of them nearly respectable) to use Java; "it's faster than " isn't one of them.
Earlier quoted context omitted.
That is ridiculous.
What is ridiculous? Understanding what a shootout is? http://en.wikipedia.org/wiki/Shootout
I understand what a shootout is. Do you understand what a programming competition is? I'll give you a clue, it does not involve murder nor does it advocate gun crime. Anyone that can construe a bad message from a programming competition called a 'shootout' is as bad as feminists claiming sciences lack of progress in the field of fluid mechanics is sexism.
This kind of behaviour only encourages the ridiculous "politically correct" world we live in today.
Earlier quoted context omitted.
What is ridiculous? Understanding what a shootout is? http://en.wikipedia.org/wiki/Shootout
Changing the name of a programming competition to not cause some kind of offence is ridiculous in my book. I understand what a shootout is. Do you understand what a programming competition is? I'll give you a clue, it does not involve murder nor does it advocate gun crime. Anyone that can construe a bad message from a programming competition called a 'shootout' is as bad as feminists claiming sciences lack of progres…
Is the benchmarks game listed somewhere as a programming competition?
http://en.wikipedia.org/wiki/Competitive_programming#Notable...
Better stats than time using Linux perf utility. Looks like if you can exclude Java's startup time they are all pretty much very competitive. Clang SVN wins and Go 1.1 native build beats gccgo-4.8. Hmm. * java version "1.7.0_17" - 485,284,671 cycles, 0.133074106 (0.0577s excl. startup) seconds time elapsed, 3.64% of all branches missed * clang svn -O2 - 49,227,286 cycles, 0.029045632 seconds time elapsed, 6.70% of al…