Та гогцоо доторх нөхцөлийг шалгах эдгээр хоёр сонголт нь гүйцэтгэлийн хувьд тэнцүү гэж бодож байна уу?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Энэ бүхэн "тархи халаах"-аас эхэлсэн бөгөөд би бүхэл тоонуудын массив дахь хамгийн том тэгш тоог олох оновчтой хайлтын жишээг өгөх ёстой байсан. Хэрэв би тоо тэгш эсэхийг логикоор 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-аас ажиллаж байгаа програмын эзэлдэг санах ой дунджаар байна. ойролцоогоор 813MB - энэ нь үр дүнгийн найдвартай байдалд нөлөөлдөг тул та тестийн тохиолдлуудыг дискэн дээр хадгалж, босго тус бүрийн бүх тестийг бие биенээсээ тусгаарлах хэрэгтэй.
Одоо энэ бүгдийг хамгийн бага зардлаар хэрхэн хэрэгжүүлэх талаар бодож, би нөхцөл байдлын шалгалтыг автоматаар засч залруулж байна
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 хөрвүүлэгч яагаад кодыг оновчтой болгохгүй, эхнийх нь худал байсан ч хоёр дахь нөхцөлийг үргэлж шалгадаг талаар би тодорхой тайлбар олж чадаагүй. Эсвэл миний нүд бүрэлзэж, ямар ч тодорхой алдаа олж харахгүй байна уу? Эсвэл хөрвүүлэгчид тусгай заавар өгөх шаардлагатай юу? Ухаантай сэтгэгдлүүд байвал би баяртай байх болно.
Жич: Тийм ээ, зүгээр л хөгжилтэй байхын тулд би Java 5 болон Java 7/8 дээр ижил төстэй туршилтуудыг явуулсан - бүх зүйл тодорхой, гүйцэтгэлийн хугацаа ижил байна.
Эх сурвалж: www.habr.com