Есть два кода реализующих один и тот же алгоритм: быстрое вычисления последовательности Фибоначчи. Алгоритм в оптимизации не нуждается.
Программы работают примерно одинаково по скорости (до определенных аргументов), но при аргументе в 100 млн. код на Go начинает ощутимо проигрывать Rust'у по памяти: практически в три раза - 150mb vs 50mb. Разумеется, я понимаю, что это говорит о том, что в Rust все очень хорошо с управлением памятью.
Вопрос: можно ли как-то оптимизировать код на Go по памяти или это предел для языка со сборщиком мусора и за автоматическим растовским перемещением значений не угнаться? Вопрос не холиварный, а исключительно практический.
P.S.: Пробовал использовать в Go sync.Pool для big.Int - не помогло. Или не получилось правильно.
// Fast doubling Fibonacci algorithm
package main
import (
"errors"
"flag"
"fmt"
"math/big"
"os"
"strconv"
"time"
)
type Opts struct {
fast, time, otime bool
}
func (opts *Opts) Usage() {
fmt.Printf(
("fib 1.0\n" +
"Author: Garry G.\n\n" +
"Calculating the nth number of the fibonacci sequence\n\n" +
"Usage: %s [OPTIONS] arg arg1 arg2...\n") ,
os.Args[0])
flag.PrintDefaults()
}
func (opts *Opts) Parse() *Opts {
flag.Usage = opts.Usage
flag.BoolVar(&opts.fast, "fast", false, "Use the fast version of the calculation: false")
flag.BoolVar(&opts.time, "time", false, "Output execution time: false")
flag.BoolVar(&opts.otime, "otime", false, "Output only the execution time: false")
flag.Parse()
return opts
}
type BigIntOperators struct{}
func (b BigIntOperators) Mul(x, y *big.Int) *big.Int {
return big.NewInt(0).Mul(x, y)
}
func (b BigIntOperators) Sub(x, y *big.Int) *big.Int {
return big.NewInt(0).Sub(x, y)
}
func (b BigIntOperators) Add(x, y *big.Int) *big.Int {
return big.NewInt(0).Add(x, y)
}
type Fib struct {
BigIntOperators
}
// (Public) Returns F(n).
func (f *Fib) Calc(n uint, fast bool) (*big.Int, error) {
var err error
var fst *big.Int
if n < 0 {
err = errors.New("Negative arguments not implemented")
} else {
switch fast {
case true:
fst, _ = f.fib_fast(n)
default:
fst, _ = f.fib(n)
}
}
return fst, err
}
func (f *Fib) fib(n uint) (*big.Int, *big.Int) {
/* n-е по индексу (от 0) число Фибоначчи
>> fib --fast 10
55
>>fib --otime 10000 100000 1000000
1.0001ms => 10000
70.004ms => 100000
8.2204702s => 1000000
*/
f0 := big.NewInt(0)
f1 := big.NewInt(1)
var i uint
for i = 2; i <= n; i++ {
f0.Add(f0, f1)
f0, f1 = f1, f0
}
return f1,f0
}
// (Private) Returns the tuple (F(n), F(n+1)).
func (f *Fib) fib_fast(n uint) (*big.Int, *big.Int) {
/* n-е по индексу (от 0) число Фибоначчи
>> fib --fast 10
55
>>fib --otime --fast 10000 100000 1000000 10000000 100000000
0s => 10000
2.0001ms => 100000
59.0034ms => 1000000
2.4231386s => 10000000
1m24.9398582s => 100000000
*/
if n == 0 {
return big.NewInt(0), big.NewInt(1)
}
a, b := f.fib_fast(n / 2)
c := f.Mul(a, f.Sub(f.Mul(b, big.NewInt(2)), a))
d := f.Add(f.Mul(a, a), f.Mul(b, b))
if n%2 == 0 {
return c, d
} else {
return d, f.Add(c, d)
}
}
func main() {
opts := &Opts{}
opts.Parse()
fib := &Fib{}
if flag.NArg() == 0 {
flag.Usage()
} else {
// итерируем по позиционным аргументам
for _, s := range flag.Args() {
n, err := strconv.Atoi(s)
if err != nil {
panic(err)
}
start := time.Now()
result, err := fib.Calc(uint(n), opts.fast)
if err != nil {
panic(err)
}
duration := time.Since(start)
if !opts.otime {
fmt.Println(result)
}
if opts.otime || opts.time {
fmt.Printf("%s => %d\n", duration, n)
}
}
}
}
Аналогичный код на Rust:
extern crate num_bigint;
use std::time::{Instant};
use clap::Clap;
use num_traits::{Zero, One};
use num_bigint::BigUint;
use std::mem::replace;
#[derive(Clap, Debug)]
#[clap(name = "fib")]
#[clap(
version = "1.0",
author = "Author: Garry G.",
about="Calculating the nth number of the fibonacci sequence")
]
struct Opts {
#[clap(short, long, about="Use the fast version of the calculation: false")]
fast: bool,
#[clap(short, long, about="Output execution time: false")]
time: bool,
#[clap(short, long, about="Output only the execution time: false")]
otime: bool,
#[clap(required=true, multiple=true, about="Ordinal number of the number")]
input: Vec<usize>,
}
struct Fib;
impl Fib {
/// (Public) Returns F(n).
pub fn calc(n: usize, fast:bool) -> BigUint {
if fast {
Self::fib_fast(n).0
} else {
Self::fib(n).0
}
}
/// Returns the tuple (F(n), F(n+1)).
fn fib(n: usize) -> (BigUint, BigUint) {
/* n-е по индексу (от 0) число Фибоначчи
>> target\release\fib 10
55
>> target\release\fib --otime 10000 100000 1000000
860.139µs => 10000
71.889642ms => 100000
9.80835748s => 1000000
*/
let mut f0: BigUint = Zero::zero();
let mut f1: BigUint = One::one();
for _ in 0..n {
let f2 = f0 + &f1;
// This is a low cost way of swapping f0 with f1 and f1 with f2.
f0 = replace(&mut f1, f2);
}
(f0,f1)
}
/// Returns the tuple (F(n), F(n+1)).
fn fib_fast(n: usize) -> (BigUint, BigUint) {
/* n-е по индексу (от 0) число Фибоначчи
>> target\release\fib --fast 10
55
>> target\release\fib --otime --fast 10000 100000 1000000 10000000 100000000
75.482µs => 10000
2.012551ms => 100000
62.328494ms => 1000000
1.84259102s => 10000000
56.118505675s => 100000000
*/
if n == 0 {
return (0u64.into(), 1u64.into());
}
let (a, b) = Self::fib_fast(n / 2);
let c = &a * (&b * 2u64 - &a);
let d = (&a * &a) + (&b * &b);
if n % 2 == 0 {
(c, d)
} else {
let r = &c + &d;
(d, r)
}
}
}
fn main() {
let opts = Opts::parse();
for n in opts.input {
let start = Instant::now();
let result = Fib::calc(n, opts.fast);
let duration = start.elapsed();
if !opts.otime {
println!("{}", result);
}
if opts.otime || opts.time {
println!("{:?} => {:}", duration, n);
}
}
}