Ĉu vi pensas, ke ĉi tiuj du ebloj por provi kondiĉojn ene de buklo estas ekvivalentaj en rendimento?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Ĉio komenciĝis per "cerba varmigo"; mi devis doni ekzemplon de optimuma serĉo por la plej granda para nombro en tabelo de entjeroj [-x....x]. Mi scivolis kiom pli bona rendimento estus se mi uzus logikan multiplikon per 1 por eltrovi ĉu nombro estas para aŭ ne.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Mia sperto pri programado en Go ne estas tre vasta, iom pli ol unu jaro kaj duono, mi uzis ĝin, kvankam ofte, sed pure por utilismaj celoj (nu, eble krom unu projekto rilata al altŝarĝa http-servo), do mi komencis per ĝi. Malfermu GoLand kaj skribu simplan teston
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
}
Ni ricevas rezulton, kiu montras, ke ju pli alta estas la sojlo, des pli ofte aperas fluktuoj en rendimento.
Komparumax 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
Estas klare, ke en ĉi tiu kazo, por malsamaj sojloj ni havas malsamajn arojn da testaj datumoj, la procesoro-ŝarĝo (sur mia tekkomputilo i5-2540M) varias ĉirkaŭ 20..30%, la memoro okupata de la aplikaĵo kuranta de GoLand estas averaĝe. ĉirkaŭ 813MB - ĉi tio ankaŭ influas la fidindecon de la rezulto, vi devas konservi testajn kazojn sur disko kaj ruli ĉiujn provojn por ĉiu sojlo izole unu de la alia.
Kaj nun, pensante pri kiel efektivigi ĉion ĉi per minimumaj kostoj, mi aŭtomate korektas la kondiĉan kontrolon
if value > current && value&1 == 0 {
current = value
}
sur
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Mi denove faras la testojn... kaj mi ĉesas kompreni ion ajn :)
La tempo pasigita por ekzekuto komencas diferenci ne plu je procentoj/frakcioj de procento, sed je 10..15%.Mi rapide aldonas 2 pliajn provojn:
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
}
Mi kuras ĝin kaj ricevas ĉi tiun bildon:komenca tabelkapacito: 100000000
Maksimuma sojlo: 128
maxEvenDividing rezulto: 126 daŭro 116.0066ms
maxEvenDividing2 rezulto: 126 daŭro 79.0045ms
maxEvenConjunction rezulto: 126 daŭro 114.0065ms
maxEvenConjunction2 rezulto: 126 daŭro 83.0048ms
Maksimuma sojlo: 256
maxEvenDividing rezulto: 254 daŭro 111.0063ms
maxEvenDividing2 rezulto: 254 daŭro 77.0044ms
maxEvenConjunction rezulto: 254 daŭro 110.0063ms
maxEvenConjunction2 rezulto: 254 daŭro 80.0046ms
Maksimuma sojlo: 512
maxEvenDividing rezulto: 510 daŭro 114.0066ms
maxEvenDividing2 rezulto: 510 daŭro 80.0045ms
maxEvenConjunction rezulto: 510 daŭro 110.0063ms
maxEvenConjunction2 rezulto: 510 daŭro 80.0046ms
Maksimuma sojlo: 1024
maxEvenDividing rezulto: 1022 daŭro 109.0063ms
maxEvenDividing2 rezulto: 1022 daŭro 77.0044ms
maxEvenConjunction rezulto: 1022 daŭro 111.0063ms
maxEvenConjunction2 rezulto: 1022 daŭro 81.0047ms
Maksimuma sojlo: 2048
maxEvenDividing rezulto: 2046 daŭro 114.0065ms
maxEvenDividing2 rezulto: 2046 daŭro 79.0045ms
maxEvenConjunction rezulto: 2046 daŭro 113.0065ms
maxEvenConjunction2 rezulto: 2046 daŭro 81.0046ms
Maksimuma sojlo: 4096
maxEvenDividing rezulto: 4094 daŭro 114.0065ms
maxEvenDividing2 rezulto: 4094 daŭro 80.0046ms
maxEvenConjunction rezulto: 4094 daŭro 111.0063ms
maxEvenConjunction2 rezulto: 4094 daŭro 78.0045ms
Maksimuma sojlo: 8192
maxEvenDividing rezulto: 8190 daŭro 107.0062ms
maxEvenDividing2 rezulto: 8190 daŭro 77.0044ms
maxEvenConjunction rezulto: 8190 daŭro 111.0063ms
maxEvenConjunction2 rezulto: 8190 daŭro 77.0044ms
Maksimuma sojlo: 16384
maxEvenDividing rezulto: 16382 daŭro 109.0063ms
maxEvenDividing2 rezulto: 16382 daŭro 77.0044ms
maxEvenConjunction rezulto: 16382 daŭro 108.0062ms
maxEvenConjunction2 rezulto: 16382 daŭro 77.0044ms
Maksimuma sojlo: 32768
maxEvenDividing rezulto: 32766 daŭro 112.0064ms
maxEvenDividing2 rezulto: 32766 daŭro 77.0044ms
maxEvenConjunction rezulto: 32766 daŭro 109.0062ms
maxEvenConjunction2 rezulto: 32766 daŭro 78.0045ms
Maksimuma sojlo: 65536
maxEvenDividing rezulto: 65534 daŭro 109.0062ms
maxEvenDividing2 rezulto: 65534 daŭro 75.0043ms
maxEvenConjunction rezulto: 65534 daŭro 109.0063ms
maxEvenConjunction2 rezulto: 65534 daŭro 79.0045ms
Maksimuma sojlo: 131072
maxEvenDividing rezulto: 131070 daŭro 108.0061ms
maxEvenDividing2 rezulto: 131070 daŭro 76.0044ms
maxEvenConjunction rezulto: 131070 daŭro 110.0063ms
maxEvenConjunction2 rezulto: 131070 daŭro 80.0046ms
Maksimuma sojlo: 262144
maxEvenDividing rezulto: 262142 daŭro 110.0063ms
maxEvenDividing2 rezulto: 262142 daŭro 76.0044ms
maxEvenConjunction rezulto: 262142 daŭro 107.0061ms
maxEvenConjunction2 rezulto: 262142 daŭro 78.0044ms
Maksimuma sojlo: 524288
maxEvenDividing rezulto: 524286 daŭro 109.0062ms
maxEvenDividing2 rezulto: 524286 daŭro 78.0045ms
maxEvenConjunction rezulto: 524286 daŭro 109.0062ms
maxEvenConjunction2 rezulto: 524286 daŭro 80.0046ms
Maksimuma sojlo: 1048576
maxEvenDividing rezulto: 1048574 daŭro 109.0063ms
maxEvenDividing2 rezulto: 1048574 daŭro 80.0045ms
maxEvenConjunction rezulto: 1048574 daŭro 114.0066ms
maxEvenConjunction2 rezulto: 1048574 daŭro 78.0044ms
Maksimuma sojlo: 2097152
maxEvenDividing rezulto: 2097150 daŭro 111.0064ms
maxEvenDividing2 rezulto: 2097150 daŭro 79.0045ms
maxEvenConjunction rezulto: 2097150 daŭro 112.0064ms
maxEvenConjunction2 rezulto: 2097150 daŭro 77.0044ms
Maksimuma sojlo: 4194304
maxEvenDividing rezulto: 4194302 daŭro 111.0063ms
maxEvenDividing2 rezulto: 4194302 daŭro 78.0045ms
maxEvenConjunction rezulto: 4194302 daŭro 111.0063ms
maxEvenConjunction2 rezulto: 4194302 daŭro 77.0044ms
Maksimuma sojlo: 8388608
maxEvenDividing rezulto: 8388606 daŭro 109.0062ms
maxEvenDividing2 rezulto: 8388606 daŭro 78.0045ms
maxEvenConjunction rezulto: 8388606 daŭro 114.0065ms
maxEvenConjunction2 rezulto: 8388606 daŭro 78.0045ms
Maksimuma sojlo: 16777216
maxEvenDividing rezulto: 16777214 daŭro 109.0062ms
maxEvenDividing2 rezulto: 16777214 daŭro 77.0044ms
maxEvenConjunction rezulto: 16777214 daŭro 109.0063ms
maxEvenConjunction2 rezulto: 16777214 daŭro 77.0044ms
Maksimuma sojlo: 33554432
maxEvenDividing rezulto: 33554430 daŭro 113.0065ms
maxEvenDividing2 rezulto: 33554430 daŭro 78.0045ms
maxEvenConjunction rezulto: 33554430 daŭro 110.0063ms
maxEvenConjunction2 rezulto: 33554430 daŭro 80.0045ms
Maksimuma sojlo: 67108864
maxEvenDividing rezulto: 67108860 daŭro 112.0064ms
maxEvenDividing2 rezulto: 67108860 daŭro 77.0044ms
maxEvenConjunction rezulto: 67108860 daŭro 112.0064ms
maxEvenConjunction2 rezulto: 67108860 daŭro 80.0046ms
Maksimuma sojlo: 134217728
maxEvenDividing rezulto: 134217726 daŭro 109.0063ms
maxEvenDividing2 rezulto: 134217726 daŭro 78.0044ms
maxEvenConjunction rezulto: 134217726 daŭro 114.0065ms
maxEvenConjunction2 rezulto: 134217726 daŭro 81.0047ms
Maksimuma sojlo: 268435456
maxEvenDividing rezulto: 268435446 daŭro 111.0064ms
maxEvenDividing2 rezulto: 268435446 daŭro 79.0045ms
maxEvenConjunction rezulto: 268435446 daŭro 114.0065ms
maxEvenConjunction2 rezulto: 268435446 daŭro 79.0045ms
Maksimuma sojlo: 536870912
maxEvenDividing rezulto: 536870910 daŭro 107.0062ms
maxEvenDividing2 rezulto: 536870910 daŭro 76.0043ms
maxEvenConjunction rezulto: 536870910 daŭro 109.0062ms
maxEvenConjunction2 rezulto: 536870910 daŭro 80.0046ms
Mi ne povis trovi klaran klarigon, kial la Go-kompililo ne optimumigas la kodon kaj ĉiam kontrolas la duan kondiĉon, eĉ se la unua estas falsa. Aŭ eble miaj okuloj estas nur malklaraj kaj mi ne vidas evidentan eraron? Aŭ ĉu vi bezonas doni iujn specialajn instrukciojn al la kompililo? Mi ĝojus pro prudentaj komentoj.
PS: Jes, nur por amuzo, mi faris similajn provojn sur Java 5 kaj Java 7/8 - ĉio estas klara, la ekzekuttempo estas la sama.
fonto: www.habr.com