さび対 アルゴリズムの問​​題に関する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% .