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. Конкатенация массивов
Конкатенация в питоне делается элементарно - здесь массивы можно просто складывать:
В растовской версии для массива используется стандартный макрос vec!.
В функции concatenate_array конкатенация массивов делается в 3 приема:
на первом шаге создается новый массив, имеющий размерность первого под-массива,
на втором шаге в новый массив копируется содержимое первого под-массива,
на третьем шаге к новому массиву добаляется второй под-массив:
В питоне строки - 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:
Дано число, представленное в виде строки.
Сделать инкремент числа.
Вариант на питоне:
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("."));
}
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)
В питоне для любого класса определен специальный метод __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
Имеется текстовой файл, В каждой строке записано одно слово.
Вывести из файла в алфавитном порядке только те слова, которые являются 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)
}