Сиздин оюңузча, циклдин ичиндеги шарттарды сыноонун бул эки варианты аткаруу жагынан эквиваленттүүбү?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Мунун баары “мээни жылытуудан” башталды; мен бүтүн сандардын [-x....x] массивиндеги эң чоң жуп санды оптималдуу издөөгө мисал келтиришим керек болчу. Сандын жуп же жуп экенин аныктоо үчүн логикалык көбөйтүүнү 1ге колдонсом, аткаруу канчалык жакшы болорун ойлоп жаттым.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Go программасында менин программалоо тажрыйбам анчалык деле кенен эмес, бир жарым жылдан ашык убакыттан кийин, мен аны көп учурда колдондум, бирок утилитарлык максаттар үчүн (жакшы, балким, жогорку жүктөмдүү http кызматына байланыштуу бир долбоорду кошпогондо), ошондуктан мен аны менен башталды. GoLand ачыңыз жана жөнөкөй тест жазыңыз
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
}
Биз босого канчалык жогору болсо, өндүрүмдүүлүктүн термелүүсү ошончолук көп пайда болоорун көрсөткөн натыйжаны алабыз.
салыштырууmax 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
Бул учурда, ар кандай босоголор үчүн бизде тесттик маалыматтардын ар кандай топтому бар экендиги түшүнүктүү, процессордун жүктөмү (менин i5-2540M ноутбукумда) 20..30% тегерегинде өзгөрөт, GoLand'тен иштеген тиркеме ээлеген эс тутуму орточо. болжол менен 813МБ - бул жыйынтыктын ишенимдүүлүгүнө да таасирин тийгизет, сиз дискте тест учурларын сактап, ар бир босого үчүн бардык тесттерди бири-биринен обочолонтуп жүргүзүү керек.
Эми мунун баарын минималдуу чыгымдар менен кантип ишке ашырууну ойлонуп, мен автоматтык түрдө абалды текшерүүнү оңдойм
if value > current && value&1 == 0 {
current = value
}
боюнча
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Мен тесттерди кайра иштетем... жана мен эч нерсени түшүнбөйм :)
Аткаруу үчүн сарпталган убакыт мындан ары пайыздар/пайыздын бөлчөктөрү менен эмес, 10..15% менен айырмалана баштайт. Мен дагы 2 тестти тез эле кошом:
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
}
Мен аны иштетип, бул сүрөттү алам:баштапкы массивдин кубаттуулугу: 100000000
максималдуу босого: 128
maxEvenDividing натыйжасы: 126 узактыгы 116.0066ms
maxEvenDividing2 натыйжасы: 126 узактыгы 79.0045ms
maxEvenConjunction натыйжасы: 126 узактыгы 114.0065ms
maxEvenConjunction2 натыйжасы: 126 узактыгы 83.0048ms
максималдуу босого: 256
maxEvenDividing натыйжасы: 254 узактыгы 111.0063ms
maxEvenDividing2 натыйжасы: 254 узактыгы 77.0044ms
maxEvenConjunction натыйжасы: 254 узактыгы 110.0063ms
maxEvenConjunction2 натыйжасы: 254 узактыгы 80.0046ms
максималдуу босого: 512
maxEvenDividing натыйжасы: 510 узактыгы 114.0066ms
maxEvenDividing2 натыйжасы: 510 узактыгы 80.0045ms
maxEvenConjunction натыйжасы: 510 узактыгы 110.0063ms
maxEvenConjunction2 натыйжасы: 510 узактыгы 80.0046ms
максималдуу босого: 1024
maxEvenDividing натыйжасы: 1022 узактыгы 109.0063ms
maxEvenDividing2 натыйжасы: 1022 узактыгы 77.0044ms
maxEvenConjunction натыйжасы: 1022 узактыгы 111.0063ms
maxEvenConjunction2 натыйжасы: 1022 узактыгы 81.0047ms
максималдуу босого: 2048
maxEvenDividing натыйжасы: 2046 узактыгы 114.0065ms
maxEvenDividing2 натыйжасы: 2046 узактыгы 79.0045ms
maxEvenConjunction натыйжасы: 2046 узактыгы 113.0065ms
maxEvenConjunction2 натыйжасы: 2046 узактыгы 81.0046ms
максималдуу босого: 4096
maxEvenDividing натыйжасы: 4094 узактыгы 114.0065ms
maxEvenDividing2 натыйжасы: 4094 узактыгы 80.0046ms
maxEvenConjunction натыйжасы: 4094 узактыгы 111.0063ms
maxEvenConjunction2 натыйжасы: 4094 узактыгы 78.0045ms
максималдуу босого: 8192
maxEvenDividing натыйжасы: 8190 узактыгы 107.0062ms
maxEvenDividing2 натыйжасы: 8190 узактыгы 77.0044ms
maxEvenConjunction натыйжасы: 8190 узактыгы 111.0063ms
maxEvenConjunction2 натыйжасы: 8190 узактыгы 77.0044ms
максималдуу босого: 16384
maxEvenDividing натыйжасы: 16382 узактыгы 109.0063ms
maxEvenDividing2 натыйжасы: 16382 узактыгы 77.0044ms
maxEvenConjunction натыйжасы: 16382 узактыгы 108.0062ms
maxEvenConjunction2 натыйжасы: 16382 узактыгы 77.0044ms
максималдуу босого: 32768
maxEvenDividing натыйжасы: 32766 узактыгы 112.0064ms
maxEvenDividing2 натыйжасы: 32766 узактыгы 77.0044ms
maxEvenConjunction натыйжасы: 32766 узактыгы 109.0062ms
maxEvenConjunction2 натыйжасы: 32766 узактыгы 78.0045ms
максималдуу босого: 65536
maxEvenDividing натыйжасы: 65534 узактыгы 109.0062ms
maxEvenDividing2 натыйжасы: 65534 узактыгы 75.0043ms
maxEvenConjunction натыйжасы: 65534 узактыгы 109.0063ms
maxEvenConjunction2 натыйжасы: 65534 узактыгы 79.0045ms
максималдуу босого: 131072
maxEvenDividing натыйжасы: 131070 узактыгы 108.0061ms
maxEvenDividing2 натыйжасы: 131070 узактыгы 76.0044ms
maxEvenConjunction натыйжасы: 131070 узактыгы 110.0063ms
maxEvenConjunction2 натыйжасы: 131070 узактыгы 80.0046ms
максималдуу босого: 262144
maxEvenDividing натыйжасы: 262142 узактыгы 110.0063ms
maxEvenDividing2 натыйжасы: 262142 узактыгы 76.0044ms
maxEvenConjunction натыйжасы: 262142 узактыгы 107.0061ms
maxEvenConjunction2 натыйжасы: 262142 узактыгы 78.0044ms
максималдуу босого: 524288
maxEvenDividing натыйжасы: 524286 узактыгы 109.0062ms
maxEvenDividing2 натыйжасы: 524286 узактыгы 78.0045ms
maxEvenConjunction натыйжасы: 524286 узактыгы 109.0062ms
maxEvenConjunction2 натыйжасы: 524286 узактыгы 80.0046ms
максималдуу босого: 1048576
maxEvenDividing натыйжасы: 1048574 узактыгы 109.0063ms
maxEvenDividing2 натыйжасы: 1048574 узактыгы 80.0045ms
maxEvenConjunction натыйжасы: 1048574 узактыгы 114.0066ms
maxEvenConjunction2 натыйжасы: 1048574 узактыгы 78.0044ms
максималдуу босого: 2097152
maxEvenDividing натыйжасы: 2097150 узактыгы 111.0064ms
maxEvenDividing2 натыйжасы: 2097150 узактыгы 79.0045ms
maxEvenConjunction натыйжасы: 2097150 узактыгы 112.0064ms
maxEvenConjunction2 натыйжасы: 2097150 узактыгы 77.0044ms
максималдуу босого: 4194304
maxEvenDividing натыйжасы: 4194302 узактыгы 111.0063ms
maxEvenDividing2 натыйжасы: 4194302 узактыгы 78.0045ms
maxEvenConjunction натыйжасы: 4194302 узактыгы 111.0063ms
maxEvenConjunction2 натыйжасы: 4194302 узактыгы 77.0044ms
максималдуу босого: 8388608
maxEvenDividing натыйжасы: 8388606 узактыгы 109.0062ms
maxEvenDividing2 натыйжасы: 8388606 узактыгы 78.0045ms
maxEvenConjunction натыйжасы: 8388606 узактыгы 114.0065ms
maxEvenConjunction2 натыйжасы: 8388606 узактыгы 78.0045ms
максималдуу босого: 16777216
maxEvenDividing натыйжасы: 16777214 узактыгы 109.0062ms
maxEvenDividing2 натыйжасы: 16777214 узактыгы 77.0044ms
maxEvenConjunction натыйжасы: 16777214 узактыгы 109.0063ms
maxEvenConjunction2 натыйжасы: 16777214 узактыгы 77.0044ms
максималдуу босого: 33554432
maxEvenDividing натыйжасы: 33554430 узактыгы 113.0065ms
maxEvenDividing2 натыйжасы: 33554430 узактыгы 78.0045ms
maxEvenConjunction натыйжасы: 33554430 узактыгы 110.0063ms
maxEvenConjunction2 натыйжасы: 33554430 узактыгы 80.0045ms
максималдуу босого: 67108864
maxEvenDividing натыйжасы: 67108860 узактыгы 112.0064ms
maxEvenDividing2 натыйжасы: 67108860 узактыгы 77.0044ms
maxEvenConjunction натыйжасы: 67108860 узактыгы 112.0064ms
maxEvenConjunction2 натыйжасы: 67108860 узактыгы 80.0046ms
максималдуу босого: 134217728
maxEvenDividing натыйжасы: 134217726 узактыгы 109.0063ms
maxEvenDividing2 натыйжасы: 134217726 узактыгы 78.0044ms
maxEvenConjunction натыйжасы: 134217726 узактыгы 114.0065ms
maxEvenConjunction2 натыйжасы: 134217726 узактыгы 81.0047ms
максималдуу босого: 268435456
maxEvenDividing натыйжасы: 268435446 узактыгы 111.0064ms
maxEvenDividing2 натыйжасы: 268435446 узактыгы 79.0045ms
maxEvenConjunction натыйжасы: 268435446 узактыгы 114.0065ms
maxEvenConjunction2 натыйжасы: 268435446 узактыгы 79.0045ms
максималдуу босого: 536870912
maxEvenDividing натыйжасы: 536870910 узактыгы 107.0062ms
maxEvenDividing2 натыйжасы: 536870910 узактыгы 76.0043ms
maxEvenConjunction натыйжасы: 536870910 узактыгы 109.0062ms
maxEvenConjunction2 натыйжасы: 536870910 узактыгы 80.0046ms
Мен эмне үчүн Go компилятору кодду оптималдаштырбай турганын жана биринчиси жалган болсо дагы, ар дайым экинчи шартты текшерип жатканын так түшүндүрмө таба алган жокмун. Же, балким, менин көзүм бүдөмүк болуп, мен эч кандай ачык катаны көрбөй жатамбы? Же компиляторго атайын көрсөтмөлөрдү беришиңиз керекпи? Мен акылга сыярлык комментарийлер үчүн кубанычтамын.
PS: Ооба, жөн гана көңүл ачуу үчүн, мен Java 5 жана Java 7/8 боюнча окшош тесттерди өткөрдүм - баары түшүнүктүү, аткаруу убактысы бирдей.
Source: www.habr.com