さび対 アルゴリズムの問​​題に関するC ++

Rust. Rustbook, , , -.

Rust , , vis-à-vis C/C++. Rust, (, , RAII .) «» C . C++.

Rust C++, , .

: , , Rust. , Rust C++, . Rust C++.

. , , , . , , , . github. . .

Rust

+ Rust « » : , ( , ), gdb. Rust , .

+ , : , , , . , () ( STL C++).

+ ( std::move, ). ( &, C++).

+ — UTF-8. , (N) , .

+ ( ). , (, Python).

+- Rust , . Rust , . , .

- , ( borrow checker) , ( ). , , borrow checker'.

- Rust , , . C++ Rust .

- Rust . , StackOverflow. . , GUI, wxWidgets, Qt.

Rust

B A. n , n — - B ( A ). .

// return position of the element if found
fn binary_search(vec: &[u32], value: u32) -> Option<usize> {
    let mut l: i32 = 0;
    let mut r: i32 = vec.len() as i32 - 1;
    while  l <= r {
        let i = ((l + r) / 2) as usize;
        if vec[i] == value {
          return Some(i);
        } else if vec[i] > value {
          r = i as i32 - 1;
        } else if vec[i] < value {
          l = i as i32 + 1;
        } 
    }
    None
}

Rust, :

2. , mut
3. Rust , . l = i as i32 + 1

: - , . , .

stdin

fn read_line() -> String {
    let mut line = String::new();
    io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn main() {
    // 1. Read the array
    let n: usize = read_line().parse().unwrap();
    let mut a_vec: Vec<u32> = vec![0; n as usize];
    for (i, token) in read_line().split_whitespace().enumerate() {
        a_vec[i] = token.parse().unwrap();    
    }

...

1. , -, , String::new() .
2. , , Option, None . unwrap panic!, None.
3. String::parse , .. .
4. Rust ( Python). split_whitespace().enumerate() , .

_merge, in place .

fn _merge(left_slice: &mut [u32], right_slice: &mut [u32]) -> u64

Rust unsafe , .. , . Rust ( , , — ). :

fn _merge(vec: &mut [u32], left: usize, mid: usize, right: usize) -> u64

. . , , Rust — , .., , mut , . unsafe . , , .

Node:

// Type of the reference to the node
type Link = Option<Box<Node>>;

// Huffman tree node struct
#[derive(Debug,Eq)]
struct Node {
    freq: u32,
    letter: char,
    left: Link,
    right: Link,
}

impl Ord for Node {
    // reverse order to make Min-Heap
    fn cmp(&self, b: &Self) -> Ordering {
        b.freq.cmp(&self.freq)
    }
}

1. .
2. #[derive(Debug,Eq)]. Debug — -. Eq — .
3. Node / Ord. . , Node Min-.

.

impl Node {
...
    // traverse tree building letter->code `map`
    fn build_map(&self, map: &mut HashMap<char, String>, prefix: String) {
        match self.right {
            Some(ref leaf) => leaf.build_map(map, prefix.clone() + "1"),
            _ => { },
        }
        match self.left {
            Some(ref leaf) => { leaf.build_map(map, prefix + "0"); },
            _ => { map.insert(self.letter, prefix); },
        }
    }
}

1. , &Some(ref leaf).
2. match switch C. match , _ => { }.
3. -? prefix.clone(), .

: . , . : (0 — , 1 — ), , . Rust , , , , . :

fn add_letter(root: &mut Link, letter: char, code: &str) {
    let mut p: &mut Node = root.as_mut().unwrap();
    for c in code.chars() {
        p = match {p} {
            &mut Node {left: Some(ref mut node), ..} if c == '0' => {
                node
            },
            &mut Node {left: ref mut opt @ None, ..} if c == '0' => {
                *opt = Node::root();
                opt.as_mut().unwrap()
            },
            &mut Node {right: Some(ref mut node), ..} if c == '1' => {
                node
            },
            &mut Node {right: ref mut opt @ None, ..} if c == '1' => {
                *opt = Node::root();
                opt.as_mut().unwrap()
            },
            _ => { panic!("error"); }
        }
    }
    p.letter = letter;
}

1. match p. &mut Node {left: Some(ref mut node), ..} if c == '0' « p Node , left node c '0'».
2. Rust , panic!("...") ( ).

— - , . :

fn get_levenshtein_distance(str1: &str, str2: &str) -> u32 {
    let n = str1.len() + 1;
    let m = str2.len() + 1;
    // compute 2D indexes into flat 1D index
    let ind = |i, j| i * m + j;
    let mut vec_d: Vec<u32> = vec![0; n * m];
    for i in 0..n {
        vec_d[ind(i, 0)] = i as u32;
    }
    for j in 0..m {
        vec_d[ind(0, j)] = j as u32;
    }

    for (i, c1) in str1.chars().enumerate() {
        for (j, c2) in str2.chars().enumerate() {
            let c =  if c1 == c2 {0} else {1};
            vec_d[ind(i + 1, j + 1)] = min( min( vec_d[ind(i, j + 1)] + 1
                                               , vec_d[ind(i + 1, j)] + 1
                                               )
                                          , vec_d[ind(i, j)] + c
                                          );
        }
    }
  return vec_d[ind(n - 1, m - 1)];
}

1. str1: &str — . , , std::string_view C++17.
2. let ind = |i, j| i * m + j; — .

Rust vs C++

, , , . Intel Core i7-4770, 16GB DDR3, SSD, Linux Mint 18.1 64-bit. :

[>] rustc --version
rustc 1.22.1 (* 2017-11-22)
[>] g++ -v
...
gcc version 7.2.0

:

1. , , /dev/null
2. * (core) ( /)
3. 10 ,
4. , , , . .
5. , C++ - / iostream. . , std::sync_with_stdio(false)
6. , Rust Huffman encoding HashMap
7. Rust , C++. , .
8. , Rust 10%, , , .

, , , Rust C++. , , , .

, github: https://github.com/dmitryikh/rust-vs-cpp-bench.

, !

11.12.2017

!
:

1. binary_search. Option
2. Binary_search A, A
3. -DNDEBUG C++. ..
4. Huffman_decoding, - C++ . .
5. , - .

. , ±10% .