Блог

Я работаю с big.Int s и мне нужно протестировать 0. Прямо сейчас я использую zero = big.NewInt(0) и Cmp(zero)==0 который работает нормально, но мне было интересно, есть ли более быстрый способ специально для 0 (мне нужно, чтобы эта программа была очень быстрой)?

big.Int предоставляет Int.Bits() доступ к необработанным байтам представления, которое представляет собой фрагмент, и оно использует тот же базовый массив: возвращенный фрагмент не копируется. Так что это быстро. Он подвергается «поддержке реализации отсутствующей низкоуровневой функциональности Int».

Идеально, именно то, что мы хотим.

0. Тестирование на 0

В документации big.Int также указано, что «нулевое значение для Int представляет значение 0». Таким образом, в нулевом значении (которое представляет 0 ) срез будет пустым (нулевое значение для срезов равно nil , а длина nil среза равна 0 ). Мы можем просто проверить это:

 if len(i1.Bits()) == 0 {
}
  

Также обратите внимание, что существует Int.BitLen() функция, возвращающая this , в которой также указано, что «длина бита 0 равна 0». Поэтому мы также можем использовать это:

 if i1.BitLen() == 0 {
}
  

Давайте сравним эти решения:

 func BenchmarkCompare(b *testing.B) {
    zero := big.NewInt(0)
    i1 := big.NewInt(1)
    i2 := big.NewInt(0)
    for i := 0; i < b.N; i   {
        if i1.Cmp(zero) == 0 {
        }
        if i2.Cmp(zero) == 0 {
        }
    }
}

func BenchmarkBits(b *testing.B) {
    i1 := big.NewInt(1)
    i2 := big.NewInt(0)
    for i := 0; i < b.N; i   {
        if len(i1.Bits()) == 0 {
        }
        if len(i2.Bits()) == 0 {
        }
    }
}

func BenchmarkBitLen(b *testing.B) {
    i1 := big.NewInt(1)
    i2 := big.NewInt(0)
    for i := 0; i < b.N; i   {
        if i1.BitLen() == 0 {
        }
        if i2.BitLen() == 0 {
        }
    }
}
  

Результаты тестов:

 BenchmarkCompare-8      76975251            13.3 ns/op
BenchmarkBits-8         1000000000           0.656 ns/op
BenchmarkBitLen-8       1000000000           1.11 ns/op
  

Получение битов и сравнение длины фрагмента в 0 20 раз быстрее, чем сравнение его с другим big.Int представлением 0 , использование Int.BitLen() также в 10 раз быстрее.

1. Тестирование на 1

Что-то подобное можно было бы сделать, чтобы проверить big.Int , равно ли значение 1 , но, вероятно, не так быстро, как тестирование на ноль: 0 это самое особое значение. Его внутреннее представление представляет собой nil срез, для любого другого значения требуется не nil срез. Также: 0 имеет еще одно особое свойство: его абсолютное значение — само по себе.

Это свойство абсолютного значения важно, поскольку Int.Bits() возвращает абсолютное значение. Таким образом, в случае ненулевого значения проверка только фрагмента битов недостаточна, поскольку она не содержит знаковой информации.

Таким образом, тестирование 1 может быть реализовано путем проверки, представляет ли содержимое bits 1 , и знак положительный:

 func isOne(i *big.Int) bool {
    bits := i.Bits()
    return len(bits) == 1 amp;amp; bits[0] == 1 amp;amp; i.Sign() > 0
}
  

Давайте сравним это вместе со сравнением числа с one := big.NewInt(1) :

 func BenchmarkCompareOne(b *testing.B) {
    one := big.NewInt(1)
    i1 := big.NewInt(0)
    i2 := big.NewInt(1)
    i3 := big.NewInt(2)
    for i := 0; i < b.N; i   {
        if i1.Cmp(one) == 0 {
        }
        if i2.Cmp(one) == 0 {
        }
        if i3.Cmp(one) == 0 {
        }
    }
}

func BenchmarkBitsOne(b *testing.B) {
    i1 := big.NewInt(0)
    i2 := big.NewInt(1)
    i3 := big.NewInt(2)
    for i := 0; i < b.N; i   {
        if isOne(i1) {
        }
        if isOne(i2) {
        }
        if isOne(i3) {
        }
    }
}
  

И результаты теста:

 BenchmarkCompareOne-8       58631458            18.9 ns/op
BenchmarkBitsOne-8          715606629            1.76 ns/op
  

Неплохо! Наш способ тестирования для 1 снова в 10 раз быстрее.