Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
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)
 }





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

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

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