I will try the udemy course I took more than half a year ago in Go language.
[Kikagaku style] Algorithm theory learned in Python to improve programming skills (Part 1) https://www.udemy.com/course/algorithm1/
――Do not start writing suddenly, but assemble the process in words. ――At first, assemble in the minimum range. --Write a code that works for the time being. ――Refactor from there to improve the quality. (This time the speed is improved)
--Create a program that displays all the prime numbers up to the received value. ――We expect the following results.
> go build main.go
> ./main
100 <-input
1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 <-output
For the time being, I will try to make it move.
i = number to be judged s = number to divide to determine
I also measured the time taken for processing simply. Completed to get the expected result somehow
func main() {
//1.Receive the number you want to determine the prime number from the input
var n int
fmt.Scan(&n)
//Start measuring time
start := time.Now()
//Output only 1
fmt.Print("1 ")
for i := 2; i <= n; i++ {
//2.Determine if it is a prime number
for s := 2; 0 == 0; s++ {
//3.Output if it is a prime number
if i == s {
fmt.Printf("%d ", i)
break
} else if i % s == 0 {
break
}
}
}
//End of time measurement
end := time.Now()
fmt.Printf("\n%f seconds\n",(end.Sub(start)).Seconds())
}
Output value | Time taken(Seconds) |
---|---|
10 | 0.000154 |
100 | 0.000201 |
1000 | 0.000517 |
10000 | 0.021293 |
100000 | 1.594362 |
1000000 | 130.868357 |
Since it is troublesome to wait for input every time and input a value, it is corrected to pass a value to judge a prime number as an argument. Corrected so that it can be calculated efficiently by extracting the value divided by the prime number that already exists.
Upper limit of the number to be judged as a prime number = n Numbers judged to be prime numbers = i
--Receive n as an argument --Define a slice to store prime numbers. At this time, if the contents of the slice break, add 2 first to judge it as a prime number. --- Store the number of 3> i> n in i. --Initialize falg with true. --Dividing i repeatedly by the contents of the slice --If it is divisible, set flag to false and exit the loop --If not all divisible, add to the prime slice. --Output the contents of the slice
At the first time, the ones that were judged to be prime numbers were output one by one, but a slice was created to store the prime numbers. In addition, it became easier to understand by storing the result of primality test in flag.
func main() {
//Receive as an argument(Outputs prime numbers up to 100 by default)
var n = flag.Int("num", 100, "")
flag.Parse()
//Define a slice to store a prime number. At this time, if the contents of the slice break, add 2 first to judge it as a prime number.
result := []int{2}
//Start measuring time
start := time.Now()
//3 > i >Store the number n in i
for i := 3; i <= *n; i++ {
//Initialize falg with true
flag := true
//Divide i repeatedly by the contents of the slice
for _, v := range result {
//If it is divisible, set flag to false and exit the loop
if i % v == 0 {
flag = false
break
}
}
//If not all divisible, add to the prime slice.
if flag == true {
result = append(result, i)
}
}
//Add 1 first
app := []int{1}
result = append(app, result...)
//Output the contents of the slice
for _, v := range result {
fmt.Printf("%d ", v)
}
//End of time measurement
end := time.Now()
fmt.Printf("\n%f seconds\n",(end.Sub(start)).Seconds())
}
Output value | Time taken(Seconds) |
---|---|
10 | 0.000365 |
100 | 0.000913 |
1000 | 0.004652 |
10000 | 0.016664 |
100000 | 0.369312 |
1000000 | 15.488318 |
The second time, I was able to improve the speed by reducing the number of calculations to calculate the prime number. If you search by How to find a prime number, it says, "You can search from the number less than the square root of the number you want to judge.", So it seems that you can do it faster.
Upper limit of the number to be judged as a prime number = n Numbers judged to be prime numbers = i
--Receive n as an argument --Define a slice to store prime numbers. At this time, if the contents of the slice break, add 2 first to judge it as a prime number. --- Store the number of 3> i> n in i. --Initialize falg with true. --Dividing i repeatedly by the contents of the slice --If it is divisible, set flag to false and exit the loop -** If the number to be divided becomes larger than the square root of the number to be divided, leave the loop as true ** --If not all divisible, add to the prime slice. --Output the contents of the slice
func main() {
//Receive as an argument(Outputs prime numbers up to 100 by default)
var n = flag.Int("num", 100, "")
flag.Parse()
//Define a slice to store a prime number. At this time, if the contents of the slice break, add 2 first to judge it as a prime number.
result := []int{2}
//Start measuring time
start := time.Now()
//3 > i >Store the number n in i.
for i := 3; i <= *n; i++ {
//Initialize falg with true.
flag := true
//Divide i repeatedly by the contents of the slice
for _, v := range result {
//Exit the loop when the square of v exceeds i
if v * v > i { //Add this line
break //Add this line
} //Add this line
//If it is divisible, set flag to false and exit the loop
if i % v == 0 {
flag = false
break
}
}
//If not all divisible, add to the prime slice.
if flag == true {
result = append(result, i)
}
}
//Add 1 first
app := []int{1}
result = append(app, result...)
//Output the contents of the slice
for _, v := range result {
fmt.Printf("%d ", v)
}
//End of time measurement
end := time.Now()
fmt.Printf("\n%f seconds\n",(end.Sub(start)).Seconds())
}
Output value | Time taken(Seconds) |
---|---|
10 | 0.000265 |
100 | 0.000470 |
1000 | 0.002642 |
10000 | 0.006644 |
100000 | 0.053357 |
1000000 | 0.482029 |
Since it is a Go language, I tried to speed up by parallel processing after studying, but it became impossible to divide by the prime numbers I have and it became slower. I divided it into four processes, but it may be faster if I increase the number of processes.
func main() {
//Receive as an argument(Outputs prime numbers up to 100 by default)
var n = flag.Int("num", 100, "")
flag.Parse()
//Distribute the processing time as evenly as possible(However, numbers less than 100 cannot be calculated accurately.)
quarter := *n / 100
minnum1, maxnum1 := 3, quarter*38
minnum2, maxnum2 := quarter*38, quarter*62
minnum3, maxnum3 := quarter*62, quarter*82
minnum4, maxnum4 := quarter*82, *n+1
var result1, result2, result3, result4 []int
ch1, ch2, ch3, ch4 := make(chan bool), make(chan bool), make(chan bool), make(chan bool)
//Start measuring time
start := time.Now()
//Primality test
go func() {
result1 = primeNumber(result1, minnum1, maxnum1)
ch1 <- true
}()
go func() {
result2 = primeNumber(result2, minnum2, maxnum2)
ch2 <- true
}()
go func() {
result3 = primeNumber(result3, minnum3, maxnum3)
ch3 <- true
}()
go func() {
result4 = primeNumber(result4, minnum4, maxnum4)
ch4 <- true
}()
<-ch1
<-ch2
<-ch3
<-ch4
//Add 1 first
app := []int{1, 2}
result1 = append(app, result1...)
//Output the contents of the slice
for _, v := range result1 {
fmt.Printf("%d ", v)
}
for _, v := range result2 {
fmt.Printf("%d ", v)
}
for _, v := range result3 {
fmt.Printf("%d ", v)
}
for _, v := range result4 {
fmt.Printf("%d ", v)
}
//End of time measurement
end := time.Now()
fmt.Printf("\n%f seconds\n", (end.Sub(start)).Seconds())
}
func primeNumber(result []int, minnum int, maxnum int) []int {
//minnum > i >Store the number of maxnum in i.
for i := minnum; i < maxnum; i++ {
//Initialize falg with true.
flag := true
//Divide i repeatedly by the contents of the slice
for v := 2; ; v++ {
//Exit the loop when the square of v exceeds i
if v*v > i { //Add this line
break //Add this line
} //Add this line
//If it is divisible, set flag to false and exit the loop
if i%v == 0 {
flag = false
break
}
}
//If not all divisible, add to the prime slice.
if flag == true {
result = append(result, i)
}
}
return result
}
1st time: Judgment by dividing by all values Second time: Judgment by dividing by the obtained prime number Third time: Judgment by the prime number obtained below the square root 4th time: Primality test for all numbers below the square root in parallel processing
Output value | First time(Seconds) | Second time(Seconds) | Third time(Seconds) | 4th(Seconds) |
---|---|---|---|---|
10 | 0.000154 | 0.000365 | 0.000265 | Undecidable |
10^3 | 0.000517 | 0.004652 | 0.002642 | 0.002725 |
10^4 | 0.021293 | 0.016664 | 0.006644 | 0.007438 |
10^5 | 1.594362 | 0.369312 | 0.053357 | 0.055468 |
10^6 | 130.868357 | 15.488318 | 0.482029 | 0.502561 |
10^7 | Unmeasurable | 785.677291 | 4.943015 | 5.682649 |
10^8 | Unmeasurable | Unmeasurable | 63.365127 | 91.279915 |
This time, in the udemy speed improvement course, there was an explanation up to the second improvement, but when I investigated and improved it myself, it became faster. Since it is a Go language, I tried it with parallel processing, but the result was that the optimum algorithm could not be used, it was slow, and the efficiency was overwhelmingly poor. Also, in the third code, I managed to get closer to O (n).
I myself am a beginner in programming who is studying acclaim, but I thought that it was a perfect introduction to algorithms. Also, the act of verbalization, which is always done in the course, was a good learning for me personally because I felt that I wanted to realize it by programming and it was an important process to connect the programs.
How to calculate the processing time taken by golang? [Go] Basic Grammar ④ (Array / Slice) Parse command line arguments with Go language (golang) flag package Safely combine two slices in Go Go language type conversion int ⇔ float64 # 05 [Go] Basic Grammar ⑦ (Parallel Processing)
Recommended Posts