Ar manote, kad šios dvi kilpos sąlygų tikrinimo parinktys yra lygiavertės našumu?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Viskas prasidėjo nuo „smegenų apšilimo“; turėjau pateikti pavyzdį, kaip optimaliai ieškoti didžiausio lyginio skaičiaus sveikųjų skaičių [-x....x] masyve. Man buvo įdomu, kiek geresnis našumas būtų, jei naudočiau loginį dauginimą iš 1, kad išsiaiškinčiau, ar skaičius yra lyginis, ar ne.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Mano programavimo patirtis Go nėra labai didelė, šiek tiek daugiau nei pusantrų metų, naudojau, nors ir dažnai, bet grynai utilitariniais tikslais (na, gal išskyrus vieną projektą, susijusį su didelės apkrovos http paslauga), todėl pradėjo nuo to. Atidarykite „GoLand“ ir parašykite paprastą testą
package main
import (
"fmt"
"log"
"math"
"math/rand"
"time"
)
const size = 100000000 //math.MaxInt32*2
type Result struct {
Name string
Duration time.Duration
Value int32
}
func main() {
log.Println("initial array capacity: " + fmt.Sprint(size))
var maxValue int32
// Будем варьировать диапазон чисел от минимального
// до максимального. Чем меньше диапазон, тем больше
// процессорного времени будет уходить на операцию
// сравнения текущего числа, с ранее найденным и наоборот
for maxValue = 128; maxValue < math.MaxInt32/2+1; maxValue = maxValue * 2 {
test(maxValue)
}
}
func test(maxValue int32) {
log.Println("max threshold: " + fmt.Sprint(maxValue))
arr := make([]int32, size)
for i := range arr {
arr[i] = rand.Int31n(maxValue)
// в тестовых данных нам нужны и отрицательные числа
sign := rand.Intn(2)
if sign == 1 {
arr[i] = -arr[i]
}
}
// запускаем тест "деление с остатком"
result := maxEvenDividing("maxEvenDividing", arr)
log.Printf(result.Name+"t result: "+fmt.Sprint(result.Value)+"ttduration %s", result.Duration)
// запускаем тест "конъюнкции"
result = maxEvenConjunction("maxEvenConjunction", arr)
log.Printf(result.Name+"t result: "+fmt.Sprint(result.Value)+"ttduration %s", result.Duration)
}
func maxEvenDividing(name string, arr []int32) Result {
start := time.Now()
var current int32 = math.MinInt32
for _, value := range arr {
if value > current && value%2 == 0 {
current = value
}
}
duration := time.Since(start)
result := Result{name, duration, current}
return result
}
func maxEvenConjunction(name string, arr []int32) Result {
start := time.Now()
var current int32 = math.MinInt32
for _, value := range arr {
if value > current && value&1 == 0 {
current = value
}
}
duration := time.Since(start)
result := Result{name, duration, current}
return result
}
Gauname rezultatą, kuris parodo, kad kuo aukštesnė riba, tuo dažniau atsiranda našumo svyravimai.
Palyginkitemax threshold: 128
maxEvenDividing result: 126 duration 116.0067ms
maxEvenConjunction result: 126 duration 116.0066ms
max threshold: 16384
maxEvenDividing result: 16382 duration 115.0066ms
maxEvenConjunction result: 16382 duration 111.0064ms
......
max threshold: 8388608
maxEvenDividing result: 8388606 duration 109.0063ms
maxEvenConjunction result: 8388606 duration 109.0062ms
max threshold: 16777216
maxEvenDividing result: 16777214 duration 108.0062ms
maxEvenConjunction result: 16777214 duration 109.0062ms
max threshold: 33554432
maxEvenDividing result: 33554430 duration 114.0066ms
maxEvenConjunction result: 33554430 duration 110.0063ms
max threshold: 67108864
maxEvenDividing result: 67108860 duration 111.0064ms
maxEvenConjunction result: 67108860 duration 109.0062ms
max threshold: 134217728
maxEvenDividing result: 134217726 duration 108.0062ms
maxEvenConjunction result: 134217726 duration 109.0063ms
max threshold: 268435456
maxEvenDividing result: 268435446 duration 111.0063ms
maxEvenConjunction result: 268435446 duration 110.0063ms
Akivaizdu, kad šiuo atveju skirtingiems slenksčiams turime skirtingus bandymų duomenų rinkinius, procesoriaus apkrova (mano i5-2540M nešiojamame kompiuteryje) svyruoja apie 20...30%, atmintis, kurią užima programa, paleista iš GoLand, yra vidutiniškai apie 813 MB - tai taip pat turi įtakos rezultato patikimumui, turite išsaugoti bandomuosius atvejus diske ir atlikti visus kiekvienos slenksčio testus atskirai vienas nuo kito.
O dabar galvodamas, kaip visa tai įgyvendinti su minimaliomis sąnaudomis, automatiškai pakoreguoju būklės patikrą
if value > current && value&1 == 0 {
current = value
}
apie
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Dar kartą atlieku testus... ir nieko nebesuprantu :)
Laikas, praleistas vykdymui, pradeda skirtis nebe procentais/procento dalimis, o 10...15%.Greitai pridedu dar 2 testus:
func maxEvenDividing2(name string, arr []int32) Result {
start := time.Now()
var current int32 = math.MinInt32
for _, value := range arr {
if value <= current {
continue
}
if value%2 == 0 {
current = value
}
}
duration := time.Since(start)
result := Result{name, duration, current}
return result
}
func maxEvenConjunction2(name string, arr []int32) Result {
start := time.Now()
var current int32 = math.MinInt32
for _, value := range arr {
if value <= current {
continue
}
if value&1 == 0 {
current = value
}
}
duration := time.Since(start)
result := Result{name, duration, current}
return result
}
Paleidžiu ir gaunu šią nuotrauką:pradinė masyvo talpa: 100000000
didžiausia riba: 128
maxEvenDividing rezultatas: 126 trukmė 116.0066ms
maxEvenDividing2 rezultatas: 126 trukmė 79.0045 ms
maxEvenConjunction rezultatas: 126 trukmė 114.0065ms
maxEvenConjunction2 rezultatas: 126 trukmė 83.0048ms
didžiausia riba: 256
maxEvenDividing rezultatas: 254 trukmė 111.0063ms
maxEvenDividing2 rezultatas: 254 trukmė 77.0044 ms
maxEvenConjunction rezultatas: 254 trukmė 110.0063ms
maxEvenConjunction2 rezultatas: 254 trukmė 80.0046ms
didžiausia riba: 512
maxEvenDividing rezultatas: 510 trukmė 114.0066ms
maxEvenDividing2 rezultatas: 510 trukmė 80.0045 ms
maxEvenConjunction rezultatas: 510 trukmė 110.0063ms
maxEvenConjunction2 rezultatas: 510 trukmė 80.0046ms
didžiausia riba: 1024
maxEvenDividing rezultatas: 1022 trukmė 109.0063ms
maxEvenDividing2 rezultatas: 1022 trukmė 77.0044 ms
maxEvenConjunction rezultatas: 1022 trukmė 111.0063ms
maxEvenConjunction2 rezultatas: 1022 trukmė 81.0047ms
didžiausia riba: 2048
maxEvenDividing rezultatas: 2046 trukmė 114.0065ms
maxEvenDividing2 rezultatas: 2046 trukmė 79.0045 ms
maxEvenConjunction rezultatas: 2046 trukmė 113.0065ms
maxEvenConjunction2 rezultatas: 2046 trukmė 81.0046ms
didžiausia riba: 4096
maxEvenDividing rezultatas: 4094 trukmė 114.0065ms
maxEvenDividing2 rezultatas: 4094 trukmė 80.0046 ms
maxEvenConjunction rezultatas: 4094 trukmė 111.0063ms
maxEvenConjunction2 rezultatas: 4094 trukmė 78.0045ms
didžiausia riba: 8192
maxEvenDividing rezultatas: 8190 trukmė 107.0062ms
maxEvenDividing2 rezultatas: 8190 trukmė 77.0044 ms
maxEvenConjunction rezultatas: 8190 trukmė 111.0063ms
maxEvenConjunction2 rezultatas: 8190 trukmė 77.0044ms
didžiausia riba: 16384
maxEvenDividing rezultatas: 16382 trukmė 109.0063ms
maxEvenDividing2 rezultatas: 16382 trukmė 77.0044 ms
maxEvenConjunction rezultatas: 16382 trukmė 108.0062ms
maxEvenConjunction2 rezultatas: 16382 trukmė 77.0044ms
didžiausia riba: 32768
maxEvenDividing rezultatas: 32766 trukmė 112.0064ms
maxEvenDividing2 rezultatas: 32766 trukmė 77.0044 ms
maxEvenConjunction rezultatas: 32766 trukmė 109.0062ms
maxEvenConjunction2 rezultatas: 32766 trukmė 78.0045ms
didžiausia riba: 65536
maxEvenDividing rezultatas: 65534 trukmė 109.0062ms
maxEvenDividing2 rezultatas: 65534 trukmė 75.0043 ms
maxEvenConjunction rezultatas: 65534 trukmė 109.0063ms
maxEvenConjunction2 rezultatas: 65534 trukmė 79.0045ms
didžiausia riba: 131072
maxEvenDividing rezultatas: 131070 trukmė 108.0061ms
maxEvenDividing2 rezultatas: 131070 trukmė 76.0044 ms
maxEvenConjunction rezultatas: 131070 trukmė 110.0063ms
maxEvenConjunction2 rezultatas: 131070 trukmė 80.0046ms
didžiausia riba: 262144
maxEvenDividing rezultatas: 262142 trukmė 110.0063ms
maxEvenDividing2 rezultatas: 262142 trukmė 76.0044 ms
maxEvenConjunction rezultatas: 262142 trukmė 107.0061ms
maxEvenConjunction2 rezultatas: 262142 trukmė 78.0044ms
didžiausia riba: 524288
maxEvenDividing rezultatas: 524286 trukmė 109.0062ms
maxEvenDividing2 rezultatas: 524286 trukmė 78.0045 ms
maxEvenConjunction rezultatas: 524286 trukmė 109.0062ms
maxEvenConjunction2 rezultatas: 524286 trukmė 80.0046ms
didžiausia riba: 1048576
maxEvenDividing rezultatas: 1048574 trukmė 109.0063ms
maxEvenDividing2 rezultatas: 1048574 trukmė 80.0045 ms
maxEvenConjunction rezultatas: 1048574 trukmė 114.0066ms
maxEvenConjunction2 rezultatas: 1048574 trukmė 78.0044ms
didžiausia riba: 2097152
maxEvenDividing rezultatas: 2097150 trukmė 111.0064ms
maxEvenDividing2 rezultatas: 2097150 trukmė 79.0045 ms
maxEvenConjunction rezultatas: 2097150 trukmė 112.0064ms
maxEvenConjunction2 rezultatas: 2097150 trukmė 77.0044ms
didžiausia riba: 4194304
maxEvenDividing rezultatas: 4194302 trukmė 111.0063ms
maxEvenDividing2 rezultatas: 4194302 trukmė 78.0045 ms
maxEvenConjunction rezultatas: 4194302 trukmė 111.0063ms
maxEvenConjunction2 rezultatas: 4194302 trukmė 77.0044ms
didžiausia riba: 8388608
maxEvenDividing rezultatas: 8388606 trukmė 109.0062ms
maxEvenDividing2 rezultatas: 8388606 trukmė 78.0045 ms
maxEvenConjunction rezultatas: 8388606 trukmė 114.0065ms
maxEvenConjunction2 rezultatas: 8388606 trukmė 78.0045ms
didžiausia riba: 16777216
maxEvenDividing rezultatas: 16777214 trukmė 109.0062ms
maxEvenDividing2 rezultatas: 16777214 trukmė 77.0044 ms
maxEvenConjunction rezultatas: 16777214 trukmė 109.0063ms
maxEvenConjunction2 rezultatas: 16777214 trukmė 77.0044ms
didžiausia riba: 33554432
maxEvenDividing rezultatas: 33554430 trukmė 113.0065ms
maxEvenDividing2 rezultatas: 33554430 trukmė 78.0045 ms
maxEvenConjunction rezultatas: 33554430 trukmė 110.0063ms
maxEvenConjunction2 rezultatas: 33554430 trukmė 80.0045ms
didžiausia riba: 67108864
maxEvenDividing rezultatas: 67108860 trukmė 112.0064ms
maxEvenDividing2 rezultatas: 67108860 trukmė 77.0044 ms
maxEvenConjunction rezultatas: 67108860 trukmė 112.0064ms
maxEvenConjunction2 rezultatas: 67108860 trukmė 80.0046ms
didžiausia riba: 134217728
maxEvenDividing rezultatas: 134217726 trukmė 109.0063ms
maxEvenDividing2 rezultatas: 134217726 trukmė 78.0044 ms
maxEvenConjunction rezultatas: 134217726 trukmė 114.0065ms
maxEvenConjunction2 rezultatas: 134217726 trukmė 81.0047ms
didžiausia riba: 268435456
maxEvenDividing rezultatas: 268435446 trukmė 111.0064ms
maxEvenDividing2 rezultatas: 268435446 trukmė 79.0045 ms
maxEvenConjunction rezultatas: 268435446 trukmė 114.0065ms
maxEvenConjunction2 rezultatas: 268435446 trukmė 79.0045ms
didžiausia riba: 536870912
maxEvenDividing rezultatas: 536870910 trukmė 107.0062ms
maxEvenDividing2 rezultatas: 536870910 trukmė 76.0043 ms
maxEvenConjunction rezultatas: 536870910 trukmė 109.0062ms
maxEvenConjunction2 rezultatas: 536870910 trukmė 80.0046ms
Neradau aiškaus paaiškinimo, kodėl „Go“ kompiliatorius neoptimizuoja kodo ir visada tikrina antrąją sąlygą, net jei pirmoji klaidinga. O gal mano akys tiesiog neryškios ir nematau jokios akivaizdžios klaidos? O gal reikia pateikti specialias instrukcijas kompiliatoriui? Būčiau dėkingas už protingus komentarus.
PS: Taip, savo malonumui panašius testus atlikau Java 5 ir Java 7/8 – viskas aišku, vykdymo laikas toks pat.
Šaltinis: www.habr.com