[JAVA] 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

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

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

8_Queen.png

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

10_Queen.png

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

12_Queen.png

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

I implemented N-Queen in various languages and measured the speed
I measured the speed of list comprehension, for and while with python2.7.
I implemented the VGG16 model in Keras and tried to identify CIFAR10
I implemented the inverse gamma function in python
I read and implemented the Variants of UKR
I implemented Human In The Loop ― Part ① Dashboard ―
HMAC in various languages
Numerical representation of days of the week in various languages
Receive the form in Python and do various things
I checked the reference speed when using python list, dictionary, and set type in.
I compared the speed of the reference of the python in list and the reference of the dictionary comprehension made from the in list.
I measured various methods of interprocess communication in multiprocessing of python3
I tried to illustrate the time and time in C language
I tried programming the chi-square test in Python and Java.
Compete for file IO in various languages and compare speeds
I compared the speed of Hash with Topaz, Ruby and Python
What automation should I do in RPA, VBA, and programming languages?
[AOJ] Descending sort in various languages
I got lost in the maze
I participated in the ISUCON10 qualifying!
I wrote the queue in Python
I wrote the stack in Python
I implemented the K-means method (clustering method)
I replaced the numerical calculation of Python with Rust and compared the speed
Implemented in python after understanding the phenomenon that various probability distributions occur
The file name was bad in Python and I was addicted to import
I connected the thermo sensor to the Raspberry Pi and measured the temperature (Python)
What are the "pipeline" and "{...}" in the Jenkins Pipeline pipeline {...} (for Groovy beginners, for experienced languages)
I saved the scraped data in CSV!
I implemented Cousera's logistic regression in Python
I wrote the selection sort in C
I wrote unit tests for various languages
I can't get the element in Selenium!
Various comments to write in the program
Find it in the procession and edit it
I wrote the sliding wing in creation.
Implemented DQN in TensorFlow (I wanted to ...)
I want to visualize where and how many people are in the factory
I got the date from the pub rice in Kagawa and drew a graph
I can't use the "next_results" parameter in the Twitter API Search API! ?? Causes and remedies
I compared the speed of go language web framework echo and python web framework flask
Talking about the features that pandas and I were in charge of in the project
Note that I understand the least squares algorithm. And I wrote it in Python.
Try to display the Fibonacci sequence in various languages in the name of algorithm practice
I want to get the file name, line number, and function name in Python 3.4