Sizningcha, pastadir ichidagi shartlarni sinovdan o'tkazishning ushbu ikkita varianti ishlash jihatidan tengmi?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Hammasi “miyaning isishi” bilan boshlandi; men [-x....x] butun sonlar massividagi eng katta juft sonni optimal qidirishga misol keltirishim kerak edi. Agar raqamning juft yoki yo‘qligini aniqlash uchun mantiqiy 1 ga ko‘paytirishdan foydalansam, unumdorlik qanchalik yaxshi bo‘lardi, deb o‘ylardim.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Go'dagi dasturlash tajribam unchalik katta emas, bir yarim yildan ko'proq vaqt davomida men uni tez-tez ishlatgan bo'lsam ham, faqat utilitar maqsadlarda foydalanardim (ehtimol, yuqori yuklangan http xizmati bilan bog'liq bitta loyihadan tashqari), shuning uchun men u bilan boshlandi. GoLand-ni oching va oddiy test yozing
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
}
Biz natijaga erishamiz, bu chegara qanchalik baland bo'lsa, unumdorlikdagi o'zgarishlar shunchalik tez-tez paydo bo'ladi.
Solishtiringmax 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
Bu holda, turli chegaralar uchun bizda test ma'lumotlarining turli to'plamlari borligi aniq, protsessor yuki (mening i5-2540M noutbukimda) 20..30% atrofida o'zgarib turadi, GoLand-dan ishlaydigan dastur tomonidan egallangan xotira o'rtacha. taxminan 813 MB - bu natijaning ishonchliligiga ham ta'sir qiladi, siz test holatlarini diskda saqlashingiz va har bir chegara uchun barcha testlarni bir-biridan ajratilgan holda bajarishingiz kerak.
Va endi, bularning barchasini minimal xarajatlar bilan qanday amalga oshirish haqida o'ylab, men avtomatik ravishda holatni tekshirishni tuzataman
if value > current && value&1 == 0 {
current = value
}
haqida
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Men yana testlarni o'tkazaman ... va men hech narsani tushunishni to'xtataman :)
Amalga oshirish uchun sarflangan vaqt endi foizlar/foiz kasrlari bilan emas, balki 10..15% ga farq qila boshlaydi. Men tezda yana 2 ta testni qo'shaman:
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
}
Men uni ishga tushiraman va bu rasmni olaman:boshlang'ich massiv sig'imi: 100000000
maksimal chegara: 128
maxEvenDividing natijasi: 126 davomiyligi 116.0066 ms
maxEvenDividing2 natijasi: 126 davomiyligi 79.0045 ms
maxEvenConjunction natijasi: 126 davomiyligi 114.0065 ms
maxEvenConjunction2 natijasi: 126 davomiyligi 83.0048 ms
maksimal chegara: 256
maxEvenDividing natijasi: 254 davomiyligi 111.0063 ms
maxEvenDividing2 natijasi: 254 davomiyligi 77.0044 ms
maxEvenConjunction natijasi: 254 davomiyligi 110.0063 ms
maxEvenConjunction2 natijasi: 254 davomiyligi 80.0046 ms
maksimal chegara: 512
maxEvenDividing natijasi: 510 davomiyligi 114.0066 ms
maxEvenDividing2 natijasi: 510 davomiyligi 80.0045 ms
maxEvenConjunction natijasi: 510 davomiyligi 110.0063 ms
maxEvenConjunction2 natijasi: 510 davomiyligi 80.0046 ms
maksimal chegara: 1024
maxEvenDividing natijasi: 1022 davomiyligi 109.0063 ms
maxEvenDividing2 natijasi: 1022 davomiyligi 77.0044 ms
maxEvenConjunction natijasi: 1022 davomiyligi 111.0063 ms
maxEvenConjunction2 natijasi: 1022 davomiyligi 81.0047 ms
maksimal chegara: 2048
maxEvenDividing natijasi: 2046 davomiyligi 114.0065 ms
maxEvenDividing2 natijasi: 2046 davomiyligi 79.0045 ms
maxEvenConjunction natijasi: 2046 davomiyligi 113.0065 ms
maxEvenConjunction2 natijasi: 2046 davomiyligi 81.0046 ms
maksimal chegara: 4096
maxEvenDividing natijasi: 4094 davomiyligi 114.0065 ms
maxEvenDividing2 natijasi: 4094 davomiyligi 80.0046 ms
maxEvenConjunction natijasi: 4094 davomiyligi 111.0063 ms
maxEvenConjunction2 natijasi: 4094 davomiyligi 78.0045 ms
maksimal chegara: 8192
maxEvenDividing natijasi: 8190 davomiyligi 107.0062 ms
maxEvenDividing2 natijasi: 8190 davomiyligi 77.0044 ms
maxEvenConjunction natijasi: 8190 davomiyligi 111.0063 ms
maxEvenConjunction2 natijasi: 8190 davomiyligi 77.0044 ms
maksimal chegara: 16384
maxEvenDividing natijasi: 16382 davomiyligi 109.0063 ms
maxEvenDividing2 natijasi: 16382 davomiyligi 77.0044 ms
maxEvenConjunction natijasi: 16382 davomiyligi 108.0062 ms
maxEvenConjunction2 natijasi: 16382 davomiyligi 77.0044 ms
maksimal chegara: 32768
maxEvenDividing natijasi: 32766 davomiyligi 112.0064 ms
maxEvenDividing2 natijasi: 32766 davomiyligi 77.0044 ms
maxEvenConjunction natijasi: 32766 davomiyligi 109.0062 ms
maxEvenConjunction2 natijasi: 32766 davomiyligi 78.0045 ms
maksimal chegara: 65536
maxEvenDividing natijasi: 65534 davomiyligi 109.0062 ms
maxEvenDividing2 natijasi: 65534 davomiyligi 75.0043 ms
maxEvenConjunction natijasi: 65534 davomiyligi 109.0063 ms
maxEvenConjunction2 natijasi: 65534 davomiyligi 79.0045 ms
maksimal chegara: 131072
maxEvenDividing natijasi: 131070 davomiyligi 108.0061 ms
maxEvenDividing2 natijasi: 131070 davomiyligi 76.0044 ms
maxEvenConjunction natijasi: 131070 davomiyligi 110.0063 ms
maxEvenConjunction2 natijasi: 131070 davomiyligi 80.0046 ms
maksimal chegara: 262144
maxEvenDividing natijasi: 262142 davomiyligi 110.0063 ms
maxEvenDividing2 natijasi: 262142 davomiyligi 76.0044 ms
maxEvenConjunction natijasi: 262142 davomiyligi 107.0061 ms
maxEvenConjunction2 natijasi: 262142 davomiyligi 78.0044 ms
maksimal chegara: 524288
maxEvenDividing natijasi: 524286 davomiyligi 109.0062 ms
maxEvenDividing2 natijasi: 524286 davomiyligi 78.0045 ms
maxEvenConjunction natijasi: 524286 davomiyligi 109.0062 ms
maxEvenConjunction2 natijasi: 524286 davomiyligi 80.0046 ms
maksimal chegara: 1048576
maxEvenDividing natijasi: 1048574 davomiyligi 109.0063 ms
maxEvenDividing2 natijasi: 1048574 davomiyligi 80.0045 ms
maxEvenConjunction natijasi: 1048574 davomiyligi 114.0066 ms
maxEvenConjunction2 natijasi: 1048574 davomiyligi 78.0044 ms
maksimal chegara: 2097152
maxEvenDividing natijasi: 2097150 davomiyligi 111.0064 ms
maxEvenDividing2 natijasi: 2097150 davomiyligi 79.0045 ms
maxEvenConjunction natijasi: 2097150 davomiyligi 112.0064 ms
maxEvenConjunction2 natijasi: 2097150 davomiyligi 77.0044 ms
maksimal chegara: 4194304
maxEvenDividing natijasi: 4194302 davomiyligi 111.0063 ms
maxEvenDividing2 natijasi: 4194302 davomiyligi 78.0045 ms
maxEvenConjunction natijasi: 4194302 davomiyligi 111.0063 ms
maxEvenConjunction2 natijasi: 4194302 davomiyligi 77.0044 ms
maksimal chegara: 8388608
maxEvenDividing natijasi: 8388606 davomiyligi 109.0062 ms
maxEvenDividing2 natijasi: 8388606 davomiyligi 78.0045 ms
maxEvenConjunction natijasi: 8388606 davomiyligi 114.0065 ms
maxEvenConjunction2 natijasi: 8388606 davomiyligi 78.0045 ms
maksimal chegara: 16777216
maxEvenDividing natijasi: 16777214 davomiyligi 109.0062 ms
maxEvenDividing2 natijasi: 16777214 davomiyligi 77.0044 ms
maxEvenConjunction natijasi: 16777214 davomiyligi 109.0063 ms
maxEvenConjunction2 natijasi: 16777214 davomiyligi 77.0044 ms
maksimal chegara: 33554432
maxEvenDividing natijasi: 33554430 davomiyligi 113.0065 ms
maxEvenDividing2 natijasi: 33554430 davomiyligi 78.0045 ms
maxEvenConjunction natijasi: 33554430 davomiyligi 110.0063 ms
maxEvenConjunction2 natijasi: 33554430 davomiyligi 80.0045 ms
maksimal chegara: 67108864
maxEvenDividing natijasi: 67108860 davomiyligi 112.0064 ms
maxEvenDividing2 natijasi: 67108860 davomiyligi 77.0044 ms
maxEvenConjunction natijasi: 67108860 davomiyligi 112.0064 ms
maxEvenConjunction2 natijasi: 67108860 davomiyligi 80.0046 ms
maksimal chegara: 134217728
maxEvenDividing natijasi: 134217726 davomiyligi 109.0063 ms
maxEvenDividing2 natijasi: 134217726 davomiyligi 78.0044 ms
maxEvenConjunction natijasi: 134217726 davomiyligi 114.0065 ms
maxEvenConjunction2 natijasi: 134217726 davomiyligi 81.0047 ms
maksimal chegara: 268435456
maxEvenDividing natijasi: 268435446 davomiyligi 111.0064 ms
maxEvenDividing2 natijasi: 268435446 davomiyligi 79.0045 ms
maxEvenConjunction natijasi: 268435446 davomiyligi 114.0065 ms
maxEvenConjunction2 natijasi: 268435446 davomiyligi 79.0045 ms
maksimal chegara: 536870912
maxEvenDividing natijasi: 536870910 davomiyligi 107.0062 ms
maxEvenDividing2 natijasi: 536870910 davomiyligi 76.0043 ms
maxEvenConjunction natijasi: 536870910 davomiyligi 109.0062 ms
maxEvenConjunction2 natijasi: 536870910 davomiyligi 80.0046 ms
Nima uchun Go kompilyatori kodni optimallashtirmasligi va birinchisi noto'g'ri bo'lsa ham, har doim ikkinchi shartni tekshirib ko'rishi haqida aniq tushuntirish topa olmadim. Yoki mening ko'zlarim xiralashgan va men hech qanday aniq xatoni ko'rmayapmanmi? Yoki kompilyatorga maxsus ko'rsatmalar berishingiz kerakmi? Mantiqiy mulohazalar uchun xursand bo'lardim.
PS: Ha, shunchaki o'yin-kulgi uchun men Java 5 va Java 7/8 da shunga o'xshash testlarni o'tkazdim - hamma narsa aniq, bajarilish vaqti bir xil.
Manba: www.habr.com