Palacinka sort Swift vs Rust

  • Začetnik teme Začetnik teme bmaxa
  • Datum pokretanja Datum pokretanja
bmaxa

bmaxa

Legenda
Poruka
70.808
Elem ovo je krajnje neefikasan sort, ali interesantno malo za OO/genericko programiranje kao primer.
Elem evo dve verzije u Swiftu (OO i kombinacija sa Generickim) i u Rustu (samo Genericki)
Swift OOP:
Swift: 
import Foundation
@main
struct MainStruct{
  static func main(){
    let domain = Pancake()
    var search = Search()
    print(domain.makeTestState())
    search.verbose = false
    let s = domain.makeTestState()
    search.id(domain,s)
  }
}

protocol State{
  func copyState()->State
}

protocol Move{
}

protocol Domain {
  func makeTestState()->State
  func heuristic(_:State)->Int
  func bf(_:State)->Int
  func getMove(_:Int)->Move
  func makeMove(_:State,_:Move)
  func unmakeMove(_:State,_:Move)
}

struct Search{
  var solution: [State] = []
  var threshold: Int = 0
  var verbose: Bool = false
  mutating func df(_ domain:Domain,_ state:State,_ depth:Int)->Bool{
    if depth == 0 { print("Treshold ", threshold) }
    if domain.heuristic(state) == 0 {
      solution[depth] = state.copyState()
      return true
    }
    if depth == threshold { return false }
    if verbose {
      let string = ""
      print(string.padding(toLength: depth*4, withPad: " ", startingAt: 0),state)
    }
    var i = 0
    while i<domain.bf(state) {
      let move = domain.getMove(i)
      domain.makeMove(state,move)
      if df(domain,state,depth+1) {
        domain.unmakeMove(state,move)
        solution[depth] = state.copyState()
        return true
      }
      domain.unmakeMove(state,move)
      i += 1
    }
    return false
  }
  mutating func id(_ domain:Domain,_ start:State){
    threshold = 0
    while(true) {
      solution = Array(repeating:PancakeState(),count:threshold+1)
      if df(domain,start,0) { break }
      threshold += 1
    }
    for i in solution {
      print(i)
    }
  }
}
struct PancakeMove: Move{
  init(_ i_:Int) { i = i_ }
  var i: Int
}

class PancakeState: State,CustomStringConvertible {
  init(){}
  init(_ i:PancakeState) {
    state = i.state
  }
  init(_ a:[Int]){
    state = a
  }
  var description:String {
    var rc = ""
    rc += "["
    var first = true
    for i in state {
      if !first {
        rc += " "
      }
      rc += String(i)
      first = false
    }
    rc += "]"
    return rc
  }
  func copyState()->State {
    return PancakeState(self)
  }
  var state:[Int] = []
}
class Pancake: Domain {
  func makeTestState()->State {
    PancakeState([0,5,4,7,2,6,1,3])
  }
  func heuristic(_ s:State)->Int {
    let ps = s as! PancakeState
    var res = 0
    for i in 1...ps.state.count-1 {
      if abs(ps.state[i]-ps.state[i-1])>1 { res += 1}
    }
    if ps.state[0] != 0 { res += 1 }
    return res
  }
  func bf(_ s:State)->Int {
    let ps = s as! PancakeState
    return ps.state.count - 1
  }
  func getMove(_ i:Int)->Move {
    PancakeMove(i+2)
  }
  func makeMove(_ s:State,_ m:Move) {
    let ps = s as! PancakeState
    let pm = m as! PancakeMove
    ps.state[0...pm.i-1].reverse()
  }
  func unmakeMove(_ s:State,_ m:Move){
    makeMove(s,m)
  }
}

i genericka Swift:
Swift: 
import Foundation
@main
struct MainStruct{
  static func main(){
    let domain = Pancake()
    var search = Search<Pancake>()
    print(domain.makeTestState())
    search.verbose = false
    let s = domain.makeTestState()
    search.id(domain,s)
  }
}

protocol State{
  init()
  func copyState()->State
}

protocol Domain {
  associatedtype State
  associatedtype Move
  func makeTestState()->State
  func heuristic(_:State)->Int
  func bf(_:State)->Int
  func getMove(_:Int)->Move
  func makeMove(_:State,_:Move)
  func unmakeMove(_:State,_:Move)
}

struct Search<D:Domain> where D.State:State {
  var solution: [State] = []
  var threshold: Int = 0
  var verbose: Bool = false
  mutating func df(_ domain:D,_ state:D.State,_ depth:Int)->Bool{
    if depth == 0 { print("Treshold ", threshold) }
    if domain.heuristic(state) == 0 {
      solution[depth] = state.copyState()
      return true
    }
    if depth == threshold { return false }
    if verbose {
      let string = ""
      print(string.padding(toLength: depth*4, withPad: " ", startingAt: 0),state)
    }
    var i = 0
    while i<domain.bf(state) {
      let move = domain.getMove(i)
      domain.makeMove(state,move)
      if df(domain,state,depth+1) {
        domain.unmakeMove(state,move)
        solution[depth] = state.copyState()
        return true
      }
      domain.unmakeMove(state,move)
      i += 1
    }
    return false
  }
  mutating func id(_ domain:D,_ start:D.State){
    threshold = 0
    while(true) {
      solution = Array(repeating:D.State(),count:threshold+1)
      if df(domain,start,0) { break }
      threshold += 1
    }
    for i in solution {
      print(i)
    }
  }
}

class PancakeState: State,CustomStringConvertible {
  required init(){}
  init(_ i:PancakeState) {
    state = i.state
  }
  init(_ a:[Int]){
    state = a
  }
  typealias R = PancakeState
  var description:String {
    var rc = ""
    rc += "["
    var first = true
    for i in state {
      if !first {
        rc += " "
      }
      rc += String(i)
      first = false
    }
    rc += "]"
    return rc
  }
  func copyState()->State {
    return PancakeState(self)
  }
  var state:[Int] = []
}
class Pancake: Domain {
  typealias State = PancakeState
  typealias Move = Int
  func makeTestState()->State {
    PancakeState([0,5,4,7,2,6,1,3])
  }
  func heuristic(_ s:State)->Int {
    let ps = s
    var res = 0
    for i in 1...ps.state.count-1 {
      if abs(ps.state[i]-ps.state[i-1])>1 { res += 1}
    }
    if ps.state[0] != 0 { res += 1 }
    return res
  }
  func bf(_ s:State)->Int {
    let ps = s
    return ps.state.count - 1
  }
  func getMove(_ i:Int)->Int {
    return i+2
  }
  func makeMove(_ s:State,_ m:Int) {
    let ps = s
    let pm = m
    ps.state[0...pm-1].reverse()
  }
  func unmakeMove(_ s:State,_ m:Move){
    makeMove(s,m)
  }
}

Potom Rust:
Kod: 
#![allow(non_snake_case)]
fn main() {
    let mut domain = Pancake;
    let mut search = Search::<Pancake>::new();
    println!("{:?}",Pancake::makeTestState());
   
    search.verbose = false;
   
    let mut s = Pancake::makeTestState();
   
    search.id(&mut domain,&mut s);
}

struct Search<T:Domain> where T::S:std::fmt::Debug+State{
    solution :Vec<T::S>,
    threshold: i32,
    verbose: bool
}

impl<T> Search<T> where T::S:std::fmt::Debug+State,T:Domain{
    fn new()->Search<T> {
        Search{solution:Vec::new(),threshold:0,verbose:false}
    }
    fn df(&mut self,domain:&mut T,state:&mut T::S,depth: i32)->bool {
        if depth == 0 { println!("Threshold {}",self.threshold); }
        if T::heuristic(state) == 0 {
            self.solution[depth as usize] = state.clone();
            return true;
        }
        if depth == self.threshold {
            return false;
        }
        if self.verbose { println!("{}{:?}"," ".repeat(depth as usize * 4),state); }
        let mut i = 0;
        while i < T::bf(state) {
            let mov = T::getMove(i);
            T::makeMove(state,&mov);
            if self.df(domain,state,depth+1) {
                T::unmakeMove(state,&mov);
                self.solution[depth as usize] = state.clone();
                return true;
            }
            T::unmakeMove(state,&mov);
            i+=1;
        }
        false
    }
    fn id(&mut self,domain:&mut T,start:&mut T::S) {
        self.threshold = 0;
        loop {
            self.solution.resize(self.threshold as usize + 1,State::new());
            if self.df(domain,start,0) { break; }
            self.threshold+=1;
        }
        for i in self.solution.iter() {
            println!("{:?}",i);
        }
    }
}

#[derive(Clone,Debug)]
struct PancakeState {
    state: Vec<i32>
}

impl State for PancakeState {
    fn new()->Self {
        PancakeState{state:Vec::new()}
    }
}

impl PancakeState {
    fn new()->PancakeState {
        PancakeState{state:vec![0, 5, 4, 7, 2, 6, 1, 3]}
    }
}

struct Pancake;

trait State:Clone+std::fmt::Debug{
    fn new()->Self;
}

trait Domain {
    type S;
    type M;
    fn makeTestState()->Self::S;
    fn heuristic(s:&Self::S)->i32;
    fn bf(s:&Self::S)->i32;
    fn getMove(i:i32)->Self::M;
    fn makeMove(s:&mut Self::S,m:&Self::M);
    fn unmakeMove(s:&mut Self::S,m:&Self::M);
}

impl Domain for Pancake {
    type S = PancakeState;
    type M = i32;
    fn makeTestState()->Self::S {
        PancakeState::new()
    }
    fn heuristic(s:&Self::S)->i32 {
        let mut res=0;
        let mut i = 1;
        while i<s.state.len() {
            if (s.state[i]-s.state[i-1]).abs() > 1 {
                res+=1;
            }
            i+=1;
        }
       
        if s.state[0] != 0 {
            res+=1;
        }
        res
    }
    fn bf(s:&Self::S)->i32 {
        (s.state.len()-1) as i32
    }
    fn getMove(i:i32)->i32 {
        i+2
    }
    fn makeMove(s:&mut Self::S,m:&i32) {
        s.state[0..*m as usize].reverse();
    }
    fn unmakeMove(s:&mut Self::S,m:&i32) {
        Self::makeMove(s,m);
    }
}

I sad poredjenje brzina:
Kod: 
bmaxa@Branimirs-Air pancake % swiftc -O pancake.swift -o pancakeswift -parse-as-library
bmaxa@Branimirs-Air pancake % time ./pancakeswift
[0 5 4 7 2 6 1 3]
Treshold  0
Treshold  1
Treshold  2
Treshold  3
Treshold  4
Treshold  5
Treshold  6
Treshold  7
Treshold  8
Treshold  9
[0 5 4 7 2 6 1 3]
[5 0 4 7 2 6 1 3]
[2 7 4 0 5 6 1 3]
[1 6 5 0 4 7 2 3]
[7 4 0 5 6 1 2 3]
[3 2 1 6 5 0 4 7]
[0 5 6 1 2 3 4 7]
[6 5 0 1 2 3 4 7]
[4 3 2 1 0 5 6 7]
[0 1 2 3 4 5 6 7]
./pancakeswift  6.50s user 0.03s system 99% cpu 6.528 total
bmaxa@Branimirs-Air pancake % swiftc -O pancake1.swift -o pancake1swift -parse-as-library
bmaxa@Branimirs-Air pancake % time ./pancake1swift
[0 5 4 7 2 6 1 3]
Treshold  0
Treshold  1
Treshold  2
Treshold  3
Treshold  4
Treshold  5
Treshold  6
Treshold  7
Treshold  8
Treshold  9
[0 5 4 7 2 6 1 3]
[5 0 4 7 2 6 1 3]
[2 7 4 0 5 6 1 3]
[1 6 5 0 4 7 2 3]
[7 4 0 5 6 1 2 3]
[3 2 1 6 5 0 4 7]
[0 5 6 1 2 3 4 7]
[6 5 0 1 2 3 4 7]
[4 3 2 1 0 5 6 7]
[0 1 2 3 4 5 6 7]
./pancake1swift  4.31s user 0.02s system 99% cpu 4.339 total
Dakle genericka je 33% brza
Sad da vidimo Rust:
Kod: 
bmaxa@Branimirs-Air pancake % rustc -O pancake.rs -o pancakers
bmaxa@Branimirs-Air pancake % time ./pancakers
PancakeState { state: [0, 5, 4, 7, 2, 6, 1, 3] }
Threshold 0
Threshold 1
Threshold 2
Threshold 3
Threshold 4
Threshold 5
Threshold 6
Threshold 7
Threshold 8
Threshold 9
PancakeState { state: [0, 5, 4, 7, 2, 6, 1, 3] }
PancakeState { state: [5, 0, 4, 7, 2, 6, 1, 3] }
PancakeState { state: [2, 7, 4, 0, 5, 6, 1, 3] }
PancakeState { state: [1, 6, 5, 0, 4, 7, 2, 3] }
PancakeState { state: [7, 4, 0, 5, 6, 1, 2, 3] }
PancakeState { state: [3, 2, 1, 6, 5, 0, 4, 7] }
PancakeState { state: [0, 5, 6, 1, 2, 3, 4, 7] }
PancakeState { state: [6, 5, 0, 1, 2, 3, 4, 7] }
PancakeState { state: [4, 3, 2, 1, 0, 5, 6, 7] }
PancakeState { state: [0, 1, 2, 3, 4, 5, 6, 7] }
./pancakers  0.18s user 0.00s system 98% cpu 0.184 total

Dakle Rust je bas brzi. Mada mi se Swift vise svidja :P
 
Poslednja izmena:
Heh, iz nekog razloga su struct brzi od class i to duplo u Swift, ili je mozda pozivao virtuelno ko zna
ili konvertovao ili nesto slicno, evo je verzija sa struct:
Swift: 
import Foundation
@main
struct MainStruct{
  static func main(){
    let domain = Pancake()
    var search = Search<Pancake>()
    print(domain.makeTestState())
    search.verbose = false
    var s = domain.makeTestState()
    search.id(domain,&s)
  }
}

protocol State{
  init()
  func copyState()->State
}

protocol Domain {
  associatedtype State
  associatedtype Move
  func makeTestState()->State
  func heuristic(_:State)->Int
  func bf(_:State)->Int
  func getMove(_:Int)->Move
  func makeMove(_:inout State,_:Move)
  func unmakeMove(_:inout State,_:Move)
}

struct Search<D:Domain> where D.State:State {
  var solution: [State] = []
  var threshold: Int = 0
  var verbose: Bool = false
  mutating func df(_ domain:D,_ state:inout D.State,_ depth:Int)->Bool{
    if depth == 0 { print("Treshold ", threshold) }
    if domain.heuristic(state) == 0 {
      solution[depth] = state.copyState()
      return true
    }
    if depth == threshold { return false }
    if verbose {
      let string = ""
      print(string.padding(toLength: depth*4, withPad: " ", startingAt: 0),state)
    }
    var i = 0
    while i<domain.bf(state) {
      let move = domain.getMove(i)
      domain.makeMove(&state,move)
      if df(domain,&state,depth+1) {
        domain.unmakeMove(&state,move)
        solution[depth] = state.copyState()
        return true
      }
      domain.unmakeMove(&state,move)
      i += 1
    }
    return false
  }
  mutating func id(_ domain:D,_ start:inout D.State){
    threshold = 0
    while(true) {
      solution = Array(repeating:D.State(),count:threshold+1)
      if df(domain,&start,0) { break }
      threshold += 1
    }
    for i in solution {
      print(i)
    }
  }
}

struct PancakeState: State,CustomStringConvertible {
  init(){}
  init(_ i:PancakeState) {
    state = i.state
  }
  init(_ a:[Int]){
    state = a
  }
  var description:String {
    var rc = ""
    rc += "["
    var first = true
    for i in state {
      if !first {
        rc += " "
      }
      rc += String(i)
      first = false
    }
    rc += "]"
    return rc
  }
  func copyState()->State {
    return PancakeState(self)
  }
  var state:[Int] = []
}
struct Pancake: Domain {
  typealias State = PancakeState
  typealias Move = Int
  func makeTestState()->State {
    PancakeState([0,5,4,7,2,6,1,3])
  }
  func heuristic(_ s:State)->Int {
    let ps = s
    var res = 0
    for i in 1...ps.state.count-1 {
      if abs(ps.state[i]-ps.state[i-1])>1 { res += 1}
    }
    if ps.state[0] != 0 { res += 1 }
    return res
  }
  func bf(_ s:State)->Int {
    let ps = s
    return ps.state.count - 1
  }
  func getMove(_ i:Int)->Int {
    return i+2
  }
  func makeMove(_ s:inout State,_ m:Int) {
    s.state[0...m-1].reverse()
  }
  func unmakeMove(_ s:inout State,_ m:Move){
    makeMove(&s,m)
  }
}

Dakle, duplo brze:
Kod: 
bmaxa@Branimirs-Air pancake % swiftc -O pancake2.swift -o pancake2swift -parse-as-library
bmaxa@Branimirs-Air pancake % time ./pancake2swift
[0 5 4 7 2 6 1 3]
Treshold  0
Treshold  1
Treshold  2
Treshold  3
Treshold  4
Treshold  5
Treshold  6
Treshold  7
Treshold  8
Treshold  9
[0 5 4 7 2 6 1 3]
[5 0 4 7 2 6 1 3]
[2 7 4 0 5 6 1 3]
[1 6 5 0 4 7 2 3]
[7 4 0 5 6 1 2 3]
[3 2 1 6 5 0 4 7]
[0 5 6 1 2 3 4 7]
[6 5 0 1 2 3 4 7]
[4 3 2 1 0 5 6 7]
[0 1 2 3 4 5 6 7]
./pancake2swift  2.48s user 0.03s system 99% cpu 2.522 total
 
Prijavite se ili registrujte da biste poslali poruku.

Slične teme

Т
  • Anketa Anketa
Chrome vs Firefox vs Opera
2
Odgovora
31
Pregleda
701
acabg
acabg
Belgradeboy
Mobilni telefon vs lap top/kompjuter
Odgovora
17
Pregleda
437
Belgradeboy
Belgradeboy
Umri_muski
VSim card
Odgovora
1
Pregleda
214
Umri_muski
Umri_muski

Back
Top