Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
 iakovlev.org 
 Languages
 С
 GNU С Library 
 Qt 
 STL 
 Threads 
 C++ 
 Samples 
 stanford.edu 
 ANSI C
 Libs
 LD
 Socket
 Pusher
 Pipes
 Encryption
 Plugin
 Inter-Process
 Errors
 Deep C Secrets
 C + UNIX
 Linked Lists / Trees
 Asm
 Perl
 Python
 Shell
 Erlang
 Go
 Rust
 Алгоритмы
NEWS
Последние статьи :
  Тренажёр 16.01   
  Эльбрус 05.12   
  Алгоритмы 12.04   
  Rust 07.11   
  Go 25.12   
  EXT4 10.11   
  FS benchmark 15.09   
  Сетунь 23.07   
  Trees 25.06   
  Apache 03.02   
 
TOP 20
 MINIX...3057 
 Solaris...2933 
 LD...2906 
 Linux Kernel 2.6...2486 
 William Gropp...2182 
 Rodriguez 6...2016 
 C++ Templates 3...1946 
 Trees...1938 
 Kamran Husain...1866 
 Secure Programming for Li...1792 
 Максвелл 5...1711 
 DevFS...1695 
 Part 3...1684 
 Stein-MacEachern-> Час...1632 
 Go Web ...1627 
 Ethreal 4...1619 
 Стивенс 9...1607 
 Arrays...1607 
 Максвелл 1...1593 
 FAQ...1539 
 
  01.01.2024 : 3621733 посещений 

iakovlev.org

Rosetta code

Rosetta code - это веб-сайт в стиле вики, где приведены различные алгоритмы и их реализация на множестве языков программирования. На данный момент на розетте опубликовано 800 задач, представлено 600 (!) языков программирования,
В этом документе будут представлены реализации алгоритмов, представленных в Category Simple.
Исходники к данной статье можно взять тут

В этой статье описана реализация алгоритмов на двух языках - на расте и питоне. Сравнение дает возможность понять разницу между двумя подходами в реализации различных алгоритмов, между системным и высокоуровневым языком.

 1. Конкатенация массивов
 2. Копирование строки
 3. Создание файла
 4. Переменная среды
 5. Факториал
 6. Файловый ввод-вывод
 7. Рекурсия
 8. Максимальный элемент в массиве
 9. Инкремент
 10. Null object
 11. Чтение файла
 12. Сравнение строк
 13. Cклеивание строк
 14. Форматирование строк
 15. Поиск подстроки в строке
 16. Системное время
 17. String tokenization
 18. Создание словаря(ассоциативного массива)
 19. Итерация словаря
 20. Создание дву-мерного массива
 21. Создание словаря из 2 массивов
 22. Сортировка словаря по ключу
 23. Одно-связный список 
 24. Двойной связный список
 25. Ordered words
 26. Поиск строки в массиве строк
 27. Бинарный поиск в числовом массиве
 
 




1. Конкатенация массивов

Конкатенация в питоне делается элементарно - здесь массивы можно просто складывать:

 arr1 = [1, 2, 3]
 arr2 = [4, 5, 6]
 arr3 = arr1 + arr2
В растовской версии для массива используется стандартный макрос vec!. В функции concatenate_array конкатенация массивов делается в 3 приема: на первом шаге создается новый массив, имеющий размерность первого под-массива, на втором шаге в новый массив копируется содержимое первого под-массива, на третьем шаге к новому массиву добаляется второй под-массив:

 fn main() {
     let a_vec: Vec = vec![1, 2, 3, 4, 5];
     let b_vec: Vec = vec![6; 5];
 
     let c_vec = concatenate_arrays::(a_vec.as_slice(), b_vec.as_slice());
 
     println!("{:?} ~ {:?} => {:?}", a_vec, b_vec, c_vec);
 }
 
 fn concatenate_arrays(x: &[T], y: &[T]) -> Vec {
     let mut concat: Vec = vec![x[0].clone(); x.len()];
 
     concat.clone_from_slice(x);
     concat.extend_from_slice(y);
 
     concat
 }



2. Копирование строки

В питоне строки - immutable тип. В расте есть два типа строк - String и &str. &str - immutable строка фиксированного размера. String - динамическая изменяемая строка.

Код на питоне - что бы мы не делали со строкой, при любой попытке изменения строки создается ее копия:
 a='123'
 b=a # создаем ссылку на ту же строку               
 print a==b, a is b # True True
 b='456' # создаем новую строку
 print a==b, a is b # False False
 
 import copy
 c='123'
 d=copy.deepcopy(c) # создаем ссылку на ту же строку
 print c==d, c is d # True True
 d='456' # создаем новую строку
 print c==d, c is d # False False
Код на расте:

 fn main() {
   
     let s1 = "A String";
 
     // Create an additional reference to "A String".
     let s2: &str = s1;
 
     // Create a copy of "A String"
     let s3: String = s1.to_string();
 
     println!("s1 = {}, s2 = {}, s3 = {}", s1, s2, s3);
 
     let s1 = "A String";
     let mut s2 = s1;
     s2 = "Another String";
     println!("s1 = {}, s2 = {}", s1, s2);
     
 }



3. Создание файла

Задача: создать файл output.txt и каталог docx. Сделать это дважды: сначала в текущем каталоге, потом в корневом.

Код на питоне:
 import os
 def create(directory):
     with open(os.path.join(directory, "output.txt"), "w"):
         pass
     os.mkdir(os.path.join(directory, "docs"))
  
 create(".") # current directory
 create("/") # root directory
Код на расте:

 use std::fs::{self, File};
 use std::io::Write;
 
 fn main() {
 
     let mut new_file = File::create("./output.txt").unwrap();
     match new_file.write_all(b"Nothing here...") {
         Ok(()) => (),
         Err(e) => println!("Failed to write to file: {}", e),
     }
 
     let result = fs::create_dir("./docs");
     if result.is_err() {
         println!("Failed to create a directory: {}", result.err().unwrap());
     }
     
     let mut new_file = File::create("/output.txt").unwrap();
     let result = fs::create_dir("/docs");
 }



4. Переменная среды

Вывести переменную среды на питоне:
 import os
 print os.environ['HOME']
Вывести переменную среды на расте:

 use std::env;
 
 fn main() {
     let variables = ["PATH", "HOME", "USER"];
 
     for variable in &variables {
         match env::var(variable) {
             Ok(value) => println!("{}={}", variable, value),
             Err(e) => println!("Could not read {}: {}.", variable, e),
         }
     }
 }



5. Факториал

Вычислить факториал двумя способами - с помощью итерации и с помощью рекурсии. Варианты на питоне:
 def factorial_iter(n):
     result = 1
     for i in range(1, n+1):
         result *= i
     return result
 
 def factorial(n):
     z=1
     if n>1:
         z=n*factorial(n-1)
     return z
Варианты на расте:

 fn factorial_recursive(n: usize) -> usize {
     match n {
         0 => 1,
         _ => n * factorial_recursive(n - 1),
     }
 }
 
 fn factorial_iterative(n: usize) -> usize {
     (1..n + 1).fold(1, |p, t| p * t)
 }
 
 
 fn main() {
     let fs = vec![("Recursive", factorial_recursive as fn(usize) -> usize),
                   ("Iterative", factorial_iterative as fn(usize) -> usize)];
     for (name, f) in fs {
         println!("---------\n{}", name);
         for i in 1..10 {
             println!("{}", f(i))
         }
     }
 }



6. Файловый ввод-вывод

Прочитать содержимое исходного файла в переменную и сохранить эту переменную в результирующий файл. Вариант на питоне:
 with open('input.txt') as infile:
     with open('output.txt', 'w') as outfile:
         for line in infile:
             outfile.write(line)
Вариант на расте:

 use std::fs::File;
 use std::io::{Read, Write};
 
 fn main() {
     let mut file = File::open("./input.txt").unwrap();
     let mut data = Vec::new();
     file.read_to_end(&mut data).unwrap();
     let mut file = File::create("./output.txt").unwrap();
     file.write_all(&data).unwrap();
 }



7. Рекурсия

Найти ограничение рекурсии. У меня на 16-й убунте питон показал 1000:
 def recurse(counter):
   print(counter)
   counter += 1
   recurse(counter)
   
 import sys
 print(sys.getrecursionlimit())
 #recurse(0)  
Раст показывает 47500:

 fn recursion(n: i32) {
     println!("deep: {}", n);
     recursion(n + 1);
 }
 
 fn main() {
     recursion(0);
 }



8. Максимальный элемент в массиве

В питоне есть функция, вычисляющая максимум:
 max(values)
Аналогичная функция есть и в расте:

 fn main() {
     let nums = [1,2,39,34,20];
     println!("{:?}", nums.iter().max());
     println!("{}", nums.iter().max().unwrap());
 }



9. Инкремент

Дано число, представленное в виде строки. Сделать инкремент числа. Вариант на питоне:
 next = str(int('123') + 1)
 
Вариант на расте:

 fn next_string(input: &str) -> String {
     (input.parse::<i64>().unwrap() + 1).to_string()
 }
  
 fn main() {
     let s = "-1";
     let s2 = next_string(s);
     println!("{:?}", s2);
 }



10. Null object

Проверка обьекта на null. Питон:
 x = None
 if x is None:
   print "x is None"
 else:
   print "x is not None"
Раст:

 fn check_number(num: &Option<u8>) {
     if num.is_none() {
         println!("Number is: None");
     } else {
         println!("Number is: {}", num.unwrap());
     }
 }
 
 fn main() {
     let mut possible_number: Option<u8> = None;
     check_number(&possible_number);
 
     possible_number = Some(31);
     check_number(&possible_number);
 }



11. Чтение файла

Построчное чтение файла. Питон:
 with open("foobar.txt") as f:
     for line in f:
         process(line)
Раст:

 use std::fs::File;
 use std::io::{BufReader, BufRead};
 use std::env::args;
 use std::borrow::ToOwned;
 
 fn main() {
     let filename = {
         if let Some(o_s) = args().nth(1) {
             o_s.to_owned()
         } else {
             panic!("You must enter a filename to read line by line")
         }
     };
 
     let file = File::open(filename).unwrap();
     let reader = BufReader::new(file);
 
     for line in reader.lines() {
         // Handle any errors that may arise
         match line {
             Ok(ln) => print!("{}", ln),
             Err(error) => print!("{}", error),
         }
     }
     println!("");
 }



12. Сравнение строк

Питон:
 def compare(a, b):
     print("\n%r is of type %r and %r is of type %r"
           % (a, type(a), b, type(b)))
     if a <  b:      print('%r is strictly less than  %r' % (a, b))
     if a <= b:      print('%r is less than or equal to %r' % (a, b))
     if a >  b:      print('%r is strictly greater than  %r' % (a, b))
     if a >= b:      print('%r is greater than or equal to %r' % (a, b))
     if a == b:      print('%r is equal to %r' % (a, b))
     if a != b:      print('%r is not equal to %r' % (a, b))
     if a is b:      print('%r has object identity with %r' % (a, b))
     if a is not b:  print('%r has negated object identity with %r' % (a, b))
  
 compare('YUP', 'YUP')
 compare('BALL', 'BELL')
 compare('24', '123')
Раст:

 // For case-insensitive compare only.
 use std::ascii::AsciiExt;
 
 fn main() {
     // only same types can be compared
     // String and String or &str and &str
     // exception: strict equality and inequality also work on &str and String
     let a: &str = "abc";
     let b: String = "Bac".to_owned();
 
     // Strings are coerced to &str when borrowed and needed
     if a == b {
         println!("The strings are equal")
     }
     if a != b {
         println!("The strings are not equal")
     }
     if a > &b {
         println!("The first string is lexically after the second")
     }
     if a < &b {
         println!("The first string is lexically before the second")
     }
     if a >= &b {
         println!("The first string is not lexically before the second")
     }
     if a <= &b {
         println!("The first string is not lexically after the second")
     }
 
     // case-insensitives:
     // everything else, create owned Strings, then compare as above
     let a2 = a.to_ascii_uppercase();
     let b2 = b.to_ascii_uppercase();
 
     // equality
     // this avoids new allocations
     if a.eq_ignore_ascii_case(&b) {
         println!("Both strings are equal when ignoring case")
     }
 
   if a2 == b2 {
         println!("The strings are equal")
     }
     if a2 != b2 {
         println!("The strings are not equal")
     }
     if a2 > b2 {
         println!("The first string is lexically after the second")
     }
     if a2 < b2 {
         println!("The first string is lexically before the second")
     }
     if a2 >= b2 {
         println!("The first string is not lexically before the second")
     }
     if a2 <= b2 {
         println!("The first string is not lexically after the second")
     }
 }



13. Cклеивание строк

Питон:
 s1 = "hello"
 print s1 + " world"
Раст:

 fn add_world(mut x: String) -> String {
     // world is a &'a[u8]
     let world = " world";
     x.push_str(world);
     x
 }
 
 fn main() {
     // The call to_string() turns a &[u8] into a Vec<u8>.
     // This is done because Vecs are growable but slices aren't.
     let hello = "hello".to_string();
     let hello_world = add_world(hello);
     println!("{}", hello_world);
 }



14. Форматирование строк

Питон:
 str = 'Mary had a %s lamb.' % 'little'
Раст

 fn main() {
     println!("Mary had a {} lamb", "little");
     // You can specify order
     println!("{1} had a {0} lamb", "little", "Mary");
     // Or named arguments if you prefer
     println!("{name} had a {adj} lamb", adj="little", name="Mary");
 }



15. Поиск подстроки в строке

Даны 2 строки. Определить, начинается ли первая строка со второй строки, входит ли вообще вторая строка в первую строку, заканчивается ли первая строка второй строкой. Питон:
 "abcd".startswith("ab") #returns True
 "abcd".endswith("zn") #returns False
 "bb" in "abab" #returns False
 "ab" in "abab" #returns True
 loc = "abab".find("bb") #returns -1
 loc = "abab".find("ab") #returns 0
 loc = "abab".find("ab",loc+1) #returns 2
Раст:

 fn match_string(container: &str, target: &str) -> (bool, bool, bool) {
     let starts = container.starts_with(target);
     let ends = container.ends_with(target);
     let contains = starts || ends || container.contains(target);
 
     (starts, contains, ends)
 }
 
 fn print_info(container: &str, target: &str) {
     println!(r#"Matching "{}" in the string "{}""#, target, container);
     let (starts, contains, ends) = match_string(container, target);
 
     if starts {
         println!(r#""{}" starts with "{}""#, container, target);
     }
     if contains {
         println!(r#""{}" contains "{}""#, container, target);
     }
     if ends {
         println!(r#""{}" ends with "{}""#, container, target);
     }
 }
 
 fn main() {
     print_info("abcd", "ab");
     print_info("abcd", "bc");
     print_info("abcd", "cd");
 }



16. Системное время

Вывести системное время. Питон:
 import time
 print time.ctime()
Раст:

 extern crate time;
 use time::{at, get_time, strftime};
 
 fn main() {
     // Prints the current time as a timespec containing the seconds
     // and nanoseconds since 1970-01-01T00:00:00Z.
     let time_ts = get_time();
     println!("seconds: {} nanoseconds: {}", time_ts.sec, time_ts.nsec);
 
     // Convert the timespec to a broken-down time value Tm
     // Could also use "let time_tm = now();" to get directly
     let time_tm = at(time_ts);
 
     // Display time formatted according to the asctime format in ISO
     // C, in the local timezone, eg "Wed Oct 29 22:26:17 2014"
     println!("ctime: {}", time_tm.ctime());
 
     // Display time formatted according to RFC 822,
     // eg "Wed, 29 Oct 2014 22:26:17"
     println!("rfc822: {}", time_tm.rfc822());
 
     // Display time formatted according to RFC 3339/ISO8601
     // eg "2014-10-29T22:26:17+07:00"
     println!("rfc3339: {}", time_tm.rfc3339());
 
     // Display time in a custom format (eg "22:26:17") using strftime
     println!("Custom: {}", strftime("%H:%M:%S", &time_tm).unwrap());
 }



17. String tokenization

Строка состоит из слов, разделенных запятыми. Заменить запятые на точки. Питон:
 text = "Hello,How,Are,You,Today"
 tokens = text.split(',')
 print ('.'.join(tokens))
Раст:

 fn main() {
     let s = "Hello,How,Are,You,Today";
     let tokens: Vec<&str> = s.split(",").collect();
     println!("{}", tokens.join("."));
 }



18. Создание словаря(ассоциативного массива)

Питон:
 hash = dict(red="FF0000", green="00FF00", blue="0000FF")
 hash = { 'key1':1, 'key2':2, }
В расте есть стандартный словарь - HashMap. В качестве ключа в примере выступает строка, значения - кортеж:

 se std::collections::HashMap;
 
 fn main() {
     let mut olympic_medals = HashMap::new();
     olympic_medals.insert("United States", (1072, 859, 749));
     olympic_medals.insert("Soviet Union", (473, 376, 355));
     olympic_medals.insert("Great Britain", (246, 276, 284));
     olympic_medals.insert("Germany", (252, 260, 270));
     println!("{:?}", olympic_medals);
 }



19. Итерация словаря

Питон:
 for key, value in myDict.items():
     print ("key = %s, value = %s" % (key, value))
Раст:

 use std::collections::HashMap;
 
 fn main() {
     // Note that `HashMap` does not preserve order. If this is important,
     // `std::collections::BTreeMap` is what you want.
     let mut olympic_medals = HashMap::new();
     olympic_medals.insert("United States", (1072, 859, 749));
     olympic_medals.insert("Soviet Union", (473, 376, 355));
     olympic_medals.insert("Great Britain", (246, 276, 284));
     olympic_medals.insert("Germany", (252, 260, 270));
     for (country, medals) in olympic_medals {
         println!("{} has had {} gold medals, {} silver medals, and {} bronze medals",
                  country,
                  medals.0,
                  medals.1,
                  medals.2);
     }
 }



20. Создание дву-мерного массива

Сначала мы набираем в консоли 2 числа. Питон:
 width = int(raw_input("Width of myarray: "))
 height = int(raw_input("Height of Array: "))
 myarray = [[0] * width for i in xrange(height)]
 myarray[0][0] = 3.5
 print myarray[0][0]
Раст:

 use std::env;
 fn main() {
     let mut args = env::args().skip(1).flat_map(|num| num.parse());
     let rows = args.next().expect("Expected number of rows as first argument");
     let cols = args.next().expect("Expected number of columns as second argument");
  
     assert!(rows != 0 && cols != 0);
  
     // Creates a vector of vectors with all elements initialized to 0.
     let mut v = init_vec(rows, || init_vec(cols, || 0));
     v[0][0] = 1;
     println!("{}", v[0][0]);
  
  
 }
  
 // Returns a dynamically-allocated array of size `n`, 
 // initialized with the values computed by `f`
  
 fn init_vec(n: usize, f: F) -> Vec
     where F: Fn() -> T
 {
     let mut vec = Vec::with_capacity(n);
     for _ in 0..n {
         vec.push(f());
     }
     vec
 }



21. Создание словаря из 2 массивов

Питон:
 keys = ['a', 'b', 'c']
 values = [1, 2, 3]
 hash = {key: value for key, value in zip(keys, values)}
Раст:

 use std::collections::HashMap;
  
 fn main() {
     let keys = ["a", "b", "c"];
     let values = [1, 2, 3];
  
     let hash = keys.iter().zip(values.iter()).collect::<HashMap<_, _>>();
     println!("{:?}", hash);
 }



22. Сортировка словаря по ключу

Питон:
 people = [('joe', 120), ('foo', 31), ('bar', 51)]
 sorted(people)
Раст:

 pub struct Element {
     name: String,
     value: String,
 }
 
 impl Element {
     fn new(name: &str, value: &str) -> Element {
         Element {
             name: name.to_string(),
             value: value.to_string(),
         }
     }
 }
 
 pub fn sort_by_name(elements: &mut Vec<Element>) {
     elements.sort_by(|a, b| a.name.cmp(&b.name));
 }
 
 fn main() {
     let mut values = vec![
         Element::new("Iron", "Fe"),
         Element::new("Cobalt", "Co"),
         Element::new("Nickel", "Ni"),
         Element::new("Copper", "Cu"),
         Element::new("Zinc", "Zn"),
     ];
     sort_by_name(&mut values);
     println!("{:?}", values);
 }



23. Одно-связный список (итерация)

В питоне для любого класса определен специальный метод __iter__, который можно использовать для итерации. Мы создаем упрощенный класс, конструктор которого одновременно будет выполнять роль ноды, в которой будет храниться текущее значение и указатель на следующую ноду. (Данный пример практически бесполезен, он просто демонстрирует простоту питоновской реализации, и по хорошему, нужно создавать отдельный класс для ноды, а в классе самого списка добавить указатели )
 class LinkedList(object):
   def __init__(self, value, next):
     self.value = value;
     self.next = next
   def __iter__(self):
     node = self
     while node != None:
       yield node.value
       node = node.next;
  
 lst = LinkedList("big",  next=
   LinkedList(value="fjords",next=
     LinkedList(value="vex",   next=
       LinkedList(value="quick", next=
         LinkedList(value="waltz", next=
           LinkedList(value="nymph", next=None))))));
  
 for value in lst:
   print value,;
 print
 
Раст:

 type Link<T> = Option<Box<Node<T>>>;
 
 pub struct List<T> {
     head: Link<T>,
 }
 
 struct Node<T> {
     elem: T,
     next: Link<T>,
 }
 
 impl<T> List<T> {
     pub fn new() -> Self {
         List { head: None }
     }
 
     pub fn push(&mut self, elem: T) {
         let new_node = Box::new(Node {
             elem: elem,
             next: self.head.take(),
         });
         self.head = Some(new_node);
     }
 }
 
 /// Iteration by value (simply empties the list as the caller now owns all values)
 pub struct IntoIter<T>(List<T>);
 
 impl<T> Iterator for IntoIter<T> {
     type Item = T;
     fn next(&mut self) -> Option<Self::Item> {
         self.0.head.take().map(|node| {
             let node = *node;
             self.0.head = node.next;
             node.elem
         })
     }
 }
 
 /// Iteration by immutable reference
 pub struct Iter<'a, T: 'a> {
     next: Option<&'a Node<T>>,
 }
 
 impl<'a, T> Iterator for Iter<'a, T> {
     type Item = &'a T;
     fn next(&mut self) -> Option<Self::Item> {
         self.next.take().map(|node| {
             self.next = node.next.as_ref().map(|node| &**node);
             &node.elem
         })
     }
 }
 
 // Iteration by mutable reference
 pub struct IterMut<'a, T: 'a> {
     next: Option<&'a mut Node<T>>,
 }
 
 impl<'a, T> Iterator for IterMut<'a, T> {
     type Item = &'a mut T;
     fn next(&mut self) -> Option<Self::Item> {
         self.next.take().map(|node| {
             self.next = node.next.as_mut().map(|node| &mut **node);
             &mut node.elem
         })
     }
 }
 
 /// Methods implemented for List<T>
 impl<T> List<T> {
     pub fn iter(&self) -> Iter<T> {
         Iter { next: self.head.as_ref().map(|node| &**node) }
     }
 
     pub fn iter_mut(&mut self) -> IterMut<T> {
         IterMut { next: self.head.as_mut().map(|node| &mut **node) }
     }
 }
     
 impl<T> IntoIterator for List<T> {
     type Item = T;
     type IntoIter = IntoIter<T>;
 
     fn into_iter(self) -> Self::IntoIter {
         IntoIter(self)
     }
 }
 
 fn main() {
     let mut list = List::new();
     list.push(1);
     list.push(2);
     list.push(3);
 
     for item in list.iter() {
         println!("{}", item);
     }
 }



24. Двойной связный список

В данной версии имеется возможность для добавления ноды и итерации. Питон:
 class List:
     def __init__(self, data, next=None, prev=None):
         self.data = data
         self.next = next
         self.prev = prev
  
     def append(self, data):
         if self.next == None:
             self.next = List(data, None, self)
             return self.next
         else:
             return self.next.append(data)
  
 # Build the list
 tail = head = List(10)
 for i in [ 20, 30, 40 ]:
     tail = tail.append(i)
  
 # Traverse forwards
 node = head
 while node != None:
     print(node.data)
     node = node.next
  
 # Traverse Backwards
 node = tail
 while node != None:
     print(node.data)
     node = node.prev
Раст:

 se std::mem;
 use std::ptr;
 
 pub struct LinkedList<T> {
     length: usize,
     list_head: Link<T>,
     list_tail: Rawlink<Node<T>>,
 }
 
 type Link = Option<Box<Node<T>>>;
 
 struct Rawlink<T> {
     p: *mut T,
 }
 
 struct Node<T> {
     next: Link<T>,
     prev: Rawlink<Node<T>>,
     value: T,
 }
 
 impl<T> Node<T> {
     fn new(v: T) -> Node<T> {
         Node {
             value: v,
             next: None,
             prev: Rawlink::none(),
         }
     }
 }
 
 mpl<T> Rawlink<T> {
     fn none() -> Self {
         Rawlink { p: ptr::null_mut() }
     }
 
     fn some(n: &mut T) -> Rawlink<T> {
         Rawlink { p: n }
     }
 }
 
 impl<'a, T> From<&'a mut Link<T>> for Rawlink<Node<T>> {
     fn from(node: &'a mut Link<T>) -> Self {
         match node.as_mut() {
             None => Rawlink::none(),
             Some(ptr) => Rawlink::some(ptr),
         }
     }
 }
 
 fn link_no_prev<T>(mut next: Box<Node<T>>) -> Link<T> {
     next.prev = Rawlink::none();
     Some(next)
 }
 
 impl<T> LinkedList<T> {
     pub fn new() -> LinkedList<T> {
         LinkedList {
             length: 0,
             list_head: None,
             list_tail: Rawlink { p: ptr::null_mut() },
         }
     }
 
     #[inline]
     fn push_front_node(&mut self, mut new_head: Box<Node<T>>) {
         match self.list_head {
             None => {
                 self.list_head = link_no_prev(new_head);
                 self.list_tail = Rawlink::from(&mut self.list_head);
             }
             Some(ref mut head) => {
                 new_head.prev = Rawlink::none();
                 head.prev = Rawlink::some(&mut *new_head);
                 mem::swap(head, &mut new_head);
                 head.next = Some(new_head);
             }
         }
         self.length += 1;
     }
     pub fn push_front(&mut self, elt: T) {
         self.push_front_node(Box::new(Node::new(elt)));
     }
 }
 
 fn main() {
     use std::collections;
     let mut list1 = collections::LinkedList::new();
     list1.push_front(8);
 
     let mut list2 = LinkedList::new();
     list2.push_front(8);
 }



25. Ordered words

Имеется текстовой файл, В каждой строке записано одно слово. Вывести из файла в алфавитном порядке только те слова, которые являются ordered words, например: abbey. Питон:
 from itertools import groupby
 o = (w for w in map(str.strip, open("unixdict.txt")) if sorted(w)==list(w))
 print list(next(groupby(sorted(o, key=len, reverse=True), key=len))[1])
Раст:

 use std::fs::File;
 use std::io::{BufReader, BufRead};
 
 fn is_ordered(s: &str) -> bool {
     let mut prev = '\x00';
     for c in s.chars() {
         if c < prev {
             return false;
         }
         prev = c;
     }
 
     true
 }
 
 fn find_longest_ordered_words(dict: Vec<String>) -> Vec<String> {
     let mut result = Vec::new();
     let mut longest_length = 0;
 
     for s in dict.into_iter() {
         if is_ordered(&s) {
             let n = s.len();
             if n > longest_length {
                 longest_length = n;
                 result.truncate(0);
             }
             if n == longest_length {
                 result.push(s.to_owned());
             }
         }
     }
 
     result
 }
 
 fn main() {
     let lines = BufReader::new(File::open("unixdict.txt").unwrap())
         .lines()
         .map(|l| l.unwrap())
         .collect();
 
     let longest_ordered = find_longest_ordered_words(lines);
 
     for s in &longest_ordered {
         println!("{}", s.to_string());
     }
 }



26. Поиск строки в массиве строк

Питон:
 haystack=["Zig","Zag","Wally","Ronald","Bush","Krusty","Charlie","Bush","Bozo"]
  
 for needle in ("Washington","Bush"):
   try:
     print haystack.index(needle), needle
   except ValueError, value_error:
     print needle,"is not in haystack"
Раст:

 fn main() {
     let haystack = vec!["Zig", "Zag", "Wally", "Ronald", "Bush", "Krusty", "Charlie", "Bush",
                         "Boz", "Zag"];
 
     println!("First occurence of 'Bush' at {:?}",
              haystack.iter().position(|s| *s == "Bush"));
     println!("Last occurence of 'Bush' at {:?}",
              haystack.iter().rposition(|s| *s == "Bush"));
     println!("First occurence of 'Rob' at {:?}",
              haystack.iter().position(|s| *s == "Rob"));
 }



27. Бинарный поиск в числовом массиве

Реализовать итерационный и рекурсивный варианты. Питон:
 def binary_search_iter(l, value):
     low = 0
     high = len(l)-1
     while low <= high: 
         mid = (low+high)//2
         if l[mid] > value: high = mid-1
         elif l[mid] < value: low = mid+1
         else: return mid
     return -1
 
 def binary_search_recursion(l, value, low = 0, high = -1):
     if not l: return -1
     if(high == -1): high = len(l)-1
     if low >= high:
         if l[low] == value: return low
         else: return -1
     mid = (low+high)//2
     if l[mid] > value: return binary_search(l, value, low, mid-1)
     elif l[mid] < value: return binary_search(l, value, mid+1, high)
     else: return mid
Раст:

 fn main() {
     println!("{:?}", binary_search(&[1, 2, 3, 4, 5, 6], 6));
     println!("{:?}", binary_search_rec(&[1, 2, 3, 4, 5, 6], 6));
 }
 
 /// iterative version
 fn binary_search<T: Ord>(haystack: &[T], needle: T) -> Option<usize> {
     let mut low = 0;
     let mut high = haystack.len() - 1;
 
     if high == 0 {
         return None;
     }
 
     while low <= high {
         // avoid overflow
         let mid = (low + high) >> 1;
 
         if haystack[mid] > needle {
             high = mid - 1
         } else if haystack[mid] < needle {
             low = mid + 1
         } else {
             return Some(mid);
         }
     }
     None
 }
 
 /// recursive version
 fn binary_search_rec<T: Ord>(haystack: &[T], needle: T) -> Option<usize> {
     fn recurse<T: Ord>(low: usize, high: usize, haystack: &[T], needle: T) -> Option<usize> {
         match (low + high) / 2 {
             _ if high < low => None,
             mid if haystack[mid] > needle => recurse(low, mid - 1, haystack, needle),
             mid if haystack[mid] < needle => recurse(mid + 1, high, haystack, needle),
             mid => Some(mid),
         }
     }
     recurse::<T>(0, haystack.len() - 1, haystack, needle)
 }





Оставьте свой комментарий !

Ваше имя:
Комментарий:
Оба поля являются обязательными

 Автор  Комментарий к данной статье