[PYTHON] I implemented N-Queen in various languages and measured the speed
What is N Queen?
[Wikipedia](http://en.wikipedia.org/wiki/%E3%82%A8%E3%82%A4%E3%83%88%E3%83%BB%E3%82%AF%E3%82 From% A4% E3% 83% BC% E3% 83% B3)
--Place N queens on the chess board --At this time, do not place any piece in a position where it can be taken by another piece. --Check how many combinations like the above are
Measured language and environment
- C++
- g++ 4.9.2
- clang++ 3.6.0
- Java
- openjdk 1.8.0_45
- Scala
- Scala 2.11.6
- Ruby
- ruby 2.1.2p95
- jruby 1.5.6
- Python
- Python 2.7.9
- Python 3.4.3
- Jython 2.5.3
- PyPy 2.5.0 with GCC 4.9.2
- Go
- go version 1.3.3
Measurement method
--The execution time was measured 10 times, and the average of the maximum and minimum values removed was used as the measurement result.
Supplement
--C ++ measured both with and without the optimization option (-O2) --scala, jruby, go are measured even when compiled and executed --The code used is here
result
The order is from the top to the shortest calculation time
- N=8
| language | Execution time[sec] |
|---|---|
| g++(optimized) | 0.004061574 |
| clang++(optimized) | 0.004093134 |
| Go(build) | 0.005815614 |
| g++ | 0.012018177 |
| clang++ | 0.012222187 |
| Python2 | 0.040775757 |
| Python3 | 0.051630976 |
| Ruby | 0.056118734 |
| Java | 0.078041175 |
| PyPy | 0.11399388 |
| Go(run) | 0.134464302 |
| Scala(compiled) | 0.282327195 |
| JRuby(compiled) | 0.504547193 |
| JRuby | 0.532120016 |
| Scala | 0.999965983 |
| Jython | 1.589687792 |
- N=10
| language | Execution time[sec] |
|---|---|
| clang++(optimized) | 0.056653161 |
| g++(optimized) | 0.058508989 |
| Go(build) | 0.088222303 |
| Java | 0.112575218 |
| PyPy | 0.155844031 |
| Go(run) | 0.216286206 |
| g++ | 0.238363557 |
| clang++ | 0.24784999 |
| Scala(compiled) | 0.37189259 |
| Ruby | 0.73327008 |
| Python2 | 0.772239671 |
| Scala | 0.89499009 |
| Python3 | 0.904239401 |
| JRuby(compiled) | 1.196120654 |
| JRuby | 1.211435426 |
| Jython | 2.741914947 |
- N=12
| language | Execution time[sec] |
|---|---|
| Java | 0.703052139 |
| Scala(compiled) | 1.410754272 |
| clang++(optimized) | 1.534444107 |
| g++(optimized) | 1.618736218 |
| Scala | 1.858531651 |
| PyPy | 2.310975255 |
| Go(build) | 2.535418489 |
| Go(run) | 2.653822287 |
| g++ | 7.054370503 |
| clang++ | 7.600850881 |
| JRuby | 16.90064013 |
| JRuby(compiled) | 16.99699324 |
| Ruby | 23.417935 |
| Jython | 24.83727352 |
| Python2 | 25.03811865 |
| Python3 | 28.62561042 |
- N=14
Calculating
Summary
--I thought C ++ was the fastest regardless of the value of N, but the result was unexpected. ―― Java rank goes up as N gets bigger ――PyPy is doing his best (small average feeling)
Recommended Posts