Эффективный способ реализации Towers of Hanoi с шагами, возвращаемыми в виде строки - PullRequest
Новая
       26

Эффективный способ реализации Towers of Hanoi с шагами, возвращаемыми в виде строки

3 голосов
/ 10 апреля 2019

Я сравниваю несколько алгоритмов в JS, Rust и Go. Я реализовал Towers of Hanoi таким образом в Go: 

func Hanoi() (hanoi func(n int, from, via, to string) string) {
    var moves strings.Builder
    var hanoiRe func(n int, from, via, to string)
    hanoiRe = func(n int, from, via, to string) {
        if n > 0 {
            hanoiRe(n-1, from, to, via)
            moves.WriteString(from)
            moves.WriteString("->")
            moves.WriteString(to)
            moves.WriteString("\n")
            hanoiRe(n-1, via, from, to)
        }
    }
    hanoi = func(n int, from, via, to string) string {
        hanoiRe(n, from, via, to)
        return moves.String()
    }
    return
}

Но эта реализация намного медленнее, чем JS или Rust. Поэтому я думаю, что это можно сделать быстрее. Но как?

Я уже пробовал type hanoi struct{moves strings.Builder} с func (h *hanoi) ..., что немного медленнее. Способ использования строки и moves += ... намного медленнее.

EDIT:

Мои сравнения:

JS: 

class HanoiJS {
    constructor() {
        this.moves = "";
    }
    hanoi(n, from, via, to) {
        if (n > 0) {
            this.hanoi(n - 1, from, to, via);
            this.moves += from + "->" + to + "\n";
            this.hanoi(n - 1, via, from, to);
        }
        return this.moves;
    }
}

Ржавчина: 

pub struct Hanoi {
    moves: String
}

impl Hanoi {

    pub fn new() -> Hanoi {
        Hanoi {
            moves: String::new()
        }
    }

    pub fn hanoi(&mut self, n: i32, from: &str, via: &str, to: &str) -> &str {
        if n > 0 {
            self.hanoi(n - 1, from, to, via);
            self.moves.push_str(from);
            self.moves.push_str("->");
            self.moves.push_str(to);
            self.moves.push_str("\n");
            self.hanoi(n - 1, via, from, to);
        }
        return &self.moves;
    }
}

По сравнению с n = 20 и 5 раз: chart

...