Резюме
- Дочерние объекты, которые одновременно являются изменяемыми и совместно используемыми, могут сделать недействительными любые или все их родительские объекты.
- В общей изменяемости произвольной формы мы не можем кэшировать какие-либо вычисления, зависящие от общей изменяемой сущности.
- Если мы ограничим область совместного использования кодом, который, как мы надеемся, не сделает наш кеш недействительным, то мы можем кэшировать результаты столько, сколько захотим.
- Ограничение объема совместного использования подразумевает, что у нас есть некий контейнерный объект: Арена.
Интерфейсы, инкапсуляция и ссылки.
Прежде всего оговорка. Я буду использовать такие термины, как «интерфейс» и «инкапсуляция», и буду определять их немного иначе, чем обычно. Это может быть немного странно, но, надеюсь, это будет иметь смысл.
Вместо того, чтобы писать код и пытаться его исправить, давайте сначала попробуем создать хороший код. Я не гарантирую, что он эффективен, но соглашусь на (в основном) правильность. Для этого нам нужно как-то доказать, что наш код работает. Вообще говоря, логический вывод мы начинаем с некоторых определений.
Мы представляем сущность A, которая является частью вашей программы. A содержит некоторые данные, которые могут быть в допустимом или недействительном состоянии. Если A когда-нибудь удастся перейти в недопустимое состояние и остаться в нем, то мы говорим, что наша программа не работает. Иногда нам нужно временно прервать A, когда мы переходим из двух допустимых состояний. Чтобы гарантировать, что A не останется сломанным, мы обводим его рамкой. Код внутри коробки может сломать A, а код вне коробки — нет. A всегда допустим вне коробки. Барьер между двумя областями мы назовем интерфейсом. Чтобы упростить понимание, я буду называть область внутри коробки опасной зоной, а код вне коробки — безопасной зоной.
Сейчас я не буду обсуждать, как построить интерфейс или как он должен выглядеть. Для каждого языка он будет разным. Можно с уверенностью сказать, что мы можем запускать любой код в безопасной зоне, и он не нарушит A, потому что именно так мы определили интерфейс.
Код из безопасной зоны может вызывать код из опасной зоны, но он должен проходить через интерфейс. Когда код из опасной зоны вернется, A должен быть действительным. Он должен быть действительным, потому что именно так мы определили наш интерфейс. Между тем A можно временно сделать недействительным, если, когда мы вернемся в безопасную зону, у нас будет действительный A.
Функцию, которую мы можем вызвать из интерфейса безопасной зоны, но которая существует внутри опасной зоны, мы будем вызывать общедоступная функция. Общедоступной функции разрешено предполагать, что объект действителен при запуске, и она несет ответственность за обеспечение того, что объект действителен при выходе.
Итак, теперь у нас есть некоторое представление о том, что такое интерфейс. Давайте поговорим об инкапсуляции. Допустим, мы хотим сделать опасную зону как можно меньше, чтобы свести к минимуму количество кода, который может сломать A. Я определяю инкапсуляцию как попытку сделать опасную зону как можно меньше.
Если опасная зона простирается навсегда и охватывает всю нашу программу, то нам всегда нужно беспокоиться о том, что мы можем случайно сломать A при написании кода. Мы не хотим беспокоиться о том, чтобы сломать любую другую часть нашей программы, когда мы модифицируем любую другую часть. Это слишком много размышлений. Если мы сделаем опасную зону небольшой, то нам придется беспокоиться о том, чтобы сломать A, только когда мы внутри нее.
Введем еще одно определение. Определение ссылки. Допустим, у нас есть две сущности, родительская и дочерняя. Если вы можете сломать родителя, изменив дочерний элемент или сделав его недействительным, мы говорим, что родитель содержит ссылку на дочерний элемент. Мы определим ссылку таким образом, независимо от того, содержит ли объект физический указатель на другой объект. Я мог бы расслабиться и сказать, что сущность «знает» о другой.
В этой статье мы будем иметь дело только со случаем, когда нет циклических ссылок.
Общая изменчивость
Учтите, что у нас есть две сущности в нашей программе A и B. A знает о B, но B не знает о A. Мы нарисуем это так:
B не знает о A, поэтому интерфейс для B может быть примерно B. Обратное неверно. Aзнает о B, и его можно было бы сделать недействительным, если бы B были недействительны. Чтобы инкапсулировать A, мы должны окружить опасную зону и для B.
Теперь мы можем определить правильный размер интерфейса для любой сущности, используя следующие правила.
- Опасная зона для
Aсодержит самA. - Если объект
Aзнает о другом объектеB, то опасная зона дляAвключает в себя опасную зону дляB. - Если объект
Aне знает о другом объектеB, тоBнаходится за пределами опасной зоны дляA, потому чтоBне может сделатьAнедействительным по нашему определению ссылки.
У нас проблема с общей изменчивостью. Рассмотрим два объекта A и B, которые не знают друг о друге, но имеют общий дочерний объект с именем C, о котором они оба знают. Опасная зона для Aохватывает A и C, а опасная зона для B включает B и C. Поскольку A и B не знают друг о друге, они не принадлежат друг другу в опасные зоны. Если бы было возможно, что Bможет вызвать поломку A, то это означало бы, что A знает о B: противоречие.
Теперь мы видим эту проблему. Интерфейсы A и B пересекаются. Чтобы изменить C, мы должны сначала войти в обе опасные зоны для A и B. Потенциально у нас есть ситуация, когда A может изменить C и сделать B недействительным, или наоборот. Эта проблема только усугубится, если у нас будет больше родителей. Мы обсудим два способа решения этой проблемы.
Пример проблемы.
Для целей этой статьи мы рассмотрим ряд объектов, называемых задачами. Каждая задача имеет длительность (в днях) и имя. Задание может быть выполнено только после завершения всех его зависимостей. Задача без зависимостей запускается сразу. В этой статье мы будем использовать следующий пример:
Решение 1. Свободная общая изменчивость.
В безопасной ржавчине мы можем разделить владение, используя Rc. Это означает, что нам не нужно беспокоиться о том, как долго что-то будет жить; он будет автоматически удален, когда на него больше ничего не ссылается. Чтобы иметь общую изменчивость в однопоточном контексте, мы можем использовать RefCell. Если мы объединим их, мы можем создать произвольные графоподобные структуры, которые имеют общую изменчивость. Я упомянул эту реализацию для полноты картины и почти наверняка RefCell внутри Rc является антишаблоном.
Начнем с определения нашего типа данных. У него есть имя, продолжительность и список зависимостей. Заворачиваем все это в наш сэндвич Rc, RefCell:
use std::cell::RefCell; use std::rc::Rc;#[derive(Clone, Eq, PartialEq, Debug, PartialOrd, Ord)] pub struct InnerTask { name: &'static str, duration: u32, dependencies: Vec<Task>, } #[derive(Clone, Eq, PartialEq, Debug, PartialOrd, Ord)] struct Task(Rc<RefCell<InnerTask>>);
Мы видели из предыдущей части, что мы не можем одновременно иметь общую изменчивость и эту идею внутренней непротиворечивости. Это означает, что мы вынуждены вычислять на лету любой результат, который зависит от детей. Мы решаем проблему опасной зоны, утверждая, что родителю не разрешено заботиться о значении дочернего элемента, а только то, что он имеет значение. Это важно, если мы хотим использовать реализацию на основе RefCell:
impl Task {
fn new (name: &'static str, duration: u32, dependencies: Vec<Task>) -> Self {
Task(Rc::new(RefCell::new(InnerTask {
name: name,
duration: duration,
dependencies: dependencies,
})))
}
fn set_duration (&self, duration: u32) {
self.0.borrow_mut().duration = duration;
}
fn start_time (&self) -> u32 {
(&self.0.borrow().dependencies)
.into_iter()
.map(|dependency| dependency.end_time())
.max()
.unwrap_or(0)
}
fn end_time(&self) -> u32 {
self.start_time() + self.0.borrow().duration
}
}Время начала Task является максимальным временем окончания всех его дочерних элементов. Время окончания — это просто время начала плюс продолжительность задачи.
Как видите, start_time обращается к каждой зависимости по очереди, чтобы получить результат. В нашем небольшом примере это будет тривиально, но в более сложных графах мы могли бы выполнять экспоненциально растущее количество вызовов. Нам не разрешено кэшировать результаты, потому что какая-то другая часть нашей программы может изменить одну из других задач и сделать недействительным время начала и окончания.
Это простая реализация. Я не предоставляю никаких методов для изменения зависимостей; с RefCellвнутри Rc мы должны быть осторожны при создании циклических ссылок. Мы ограничиваемся только созданием Task с использованием старых Task.
fn main () { let lay_foundation = Task::new("Lay Foundation", 10, vec![]); let build_walls = Task::new("Build Walls", 5, vec![lay_foundation.clone()]); let build_roof = Task::new("Build Roof", 11, vec![build_walls.clone()]); let paint_walls = Task::new("Paint Walls", 2, vec![build_walls.clone()]); let furnish_house = Task::new("Furnish House", 3, vec![build_roof.clone(), paint_walls.clone()]);println!("Days require to finish house: {}", furnish_house.end_time()); }
Это работает, но я не рекомендую. Программист должен гарантировать, что мы никогда не кэшируем результаты любых наших вычислений, как бы заманчиво это ни было. Кроме того, это асимптотически медленно. Время начала и окончания для lay_foundation необходимо вычислять несколько раз. В более сложных примерах, возможно, придется вычислять экспоненциальное число раз.
Решение 2: Арена.
В предыдущем примере есть общая изменчивость, но нет внутренней согласованности. Однако, если мы ограничим распространение изменяемых ссылок объектами, которым мы доверяем, чтобы не нарушить нашу структуру, мы можем кэшировать результаты столько, сколько захотим. Все сами узлы должны быть доверенными, поскольку они могут иметь ссылку на любой другой узел, и мы можем давать изменяемые ссылки только на доверенные объекты.
Чтобы создать место, где только доверенные лица могут изменять наши узлы, мы должны создать интерфейс. Внутри интерфейса у нас есть доверенный код, а снаружи у нас есть все остальное. Мы называем сущность, которая содержит интерфейс, P.
Мы не позволяем P передавать изменяемые ссылки на отдельные узлы в безопасную зону, потому что за пределами P нельзя доверять, чтобы не нарушить нашу структуру согласно нашему определению P. Поэтому P должен иметь эксклюзивный доступ на запись ко всем отдельным узлам. Учитывая, что P — это объект с интерфейсом, который имеет эксклюзивный доступ на запись к своим отдельным узлам, мы можем сказать, что P — это арена.
Вы могли заметить, что я не говорю, что P объект. P может быть чем угодно. Это могут быть struct и enum, комбинация объектов или любая другая сущность, которую можно определить. Я только заявляю, что чем бы ни было P, у него есть два свойства: всему коду внутри P доверяют, чтобы не сломать его, и он имеет эксклюзивный изменяемый доступ ко всем своим узлам.
Как и в предыдущей статье, чтобы решить нашу проблему общей изменяемости, мы избавляемся от общей части и говорим, что весь изменяемый доступ осуществляется через общедоступные функции для P.
Обратите внимание, что для кэширования результатов вычислений мы должны иметь интерфейс и связанный с ним объект P, и мы знаем, что P должен иметь монопольный доступ на запись к своим членам. Арена — это не «лучший» способ решения проблемы изменчивости с внутренней согласованностью, это единственный способ. Эйнштейн говорил, что нужно делать вещи «как можно проще, но не проще». Хотя арена может быть не простой, это самый простой способ написать наш код, оставаясь при этом правильным.
Чтобы реализовать это, мы можем создать структуру данных Graph, которая представляет собой просто набор узлов с уникальными идентификаторами. GraphNode содержит некоторые данные и набор входящих и исходящих ребер.
use std::collections::{HashMap, HashSet}; use std::hash::Hash;use uuid::Uuid;#[derive(Debug, Clone, Eq, PartialEq)] struct GraphNode<T> { data: T, incoming: HashSet<Uuid>, outgoing: HashSet<Uuid>, } impl<T> GraphNode<T> { fn new (data: T) -> Self { GraphNode { data: data, incoming: HashSet::new(), outgoing: HashSet::new(), } } }#[derive(Debug, Clone)] pub struct Graph<T: Eq + Hash> ( HashMap<Uuid, GraphNode<T>> );
Это очень простая реализация графа. У нас есть некоторые базовые функции, которые я буду описывать по большей части, связанные с добавлением, удалением и запросом узлов. Есть более эффективные реализации, но они не относятся к данной статье:
impl<T: Eq + Hash> Graph<T> {
pub fn new() -> Self {
Graph(HashMap::new())
}
pub fn add_edge(&mut self, start: &Uuid, end: &Uuid) {
self.0.get_mut(start).map(|node| {
node.outgoing.insert(*end);
});
self.0.get_mut(end).map(|node| {
node.incoming.insert(*start);
});
}
pub fn remove_edge(&mut self, start: &Uuid, end: &Uuid) {
self.0.get_mut(start).map(|node| {
node.outgoing.remove(end);
});
self.0.get_mut(end).map(|node| {
node.incoming.remove(start);
});
}
pub fn remove_node(&mut self, node_id: &Uuid) -> T {
let node = self.0.remove(node_id).expect("remove_node: invalid key");
for start in node.incoming.iter() {
self.0.get_mut(start).map(|start_node| {
start_node.outgoing.remove(node_id);
});
}
for end in node.outgoing.iter() {
self.0.get_mut(end).map(|end_node| {
end_node.incoming.remove(node_id);
});
}
node.data
}
pub fn add_node(&mut self, node: T) -> Uuid {
let key = Uuid::new_v4();
self.0.insert(key, GraphNode::new(node));
key
}
pub fn get(&self, key: &Uuid) -> &T {
&self.0.get(key).expect("get: invalid key.").data
}
pub fn get_outgoing(&self, key: &Uuid) -> &HashSet<Uuid> {
&self.0.get(key).expect("get_outgoing: invalid key.").outgoing
}
pub fn get_incoming(&self, key: &Uuid) -> &HashSet<Uuid> {
&self.0.get(key).expect("get_incoming: invalid key.").incoming
}
}Мы реализуем нашу фактическую структуру Task, которая содержит поля name и duration и больше ничего. Одним из преимуществ использования арены является то, что мы можем отделить данные, представляющие отношения между узлами, от самих узлов. Это означает, что узел может поддерживать свои собственные инварианты, которые не зависят от того, является ли он частью более крупной структуры:
#[derive(Clone, Eq, PartialEq, Hash, Debug, PartialOrd, Ord)]
pub struct Task {
name: &'static str,
duration: u32,
}
impl Task {
fn new (name: &'static str, duration: u32) -> Self {
Task {
name: name,
duration: duration,
}
}
}Как и в предыдущей статье, мы создаем «представление» графика, которое временно его замораживает. Это позволяет нам кэшировать результаты вычислений сколько угодно. Когда мы изменяем любой из узлов или структуру графа, нам приходится отбрасывать кеш, потому что он больше недействителен. Структура представления содержит кеш времени начала и времени окончания:
struct GraphView<'a> {
graph: &'a Graph<Task>,
start_times: HashMap<Uuid, u32>,
end_times: HashMap<Uuid, u32>,
}Если мы хотим кэшировать результаты, мы можем использовать немного шаблонного кода и написать что-то вроде следующего:
impl<'a> GraphView<'a> { fn new (graph: &'a Graph<Task>) -> Self { GraphView { graph: graph, start_times: HashMap::new(), end_times: HashMap::new(), } } fn end_time(&mut self, key: &Uuid) -> u32 { // Boilerplate if let Some(result) = self.end_times.get(key) { return result.clone(); } // Actual query let result = self.graph.get(key).duration + self.start_time(key);// Boilerplate self.end_times.insert(key.clone(), result); result } fn start_time(&mut self, key: &Uuid) -> u32 { // Boilerplate if let Some(result) = self.start_times.get(key) { return result.clone(); }// Actual query. let result = self.graph.get_incoming(key) .into_iter() .map(|key_out| self.end_time(key_out)) .max() .unwrap_or(0);// Boilerplate self.start_times.insert(key.clone(), result); result } }
Шаблон просто проверяет, вычислили ли мы уже значение. Если у нас есть, мы просто возвращаем значение, в противном случае мы вычисляем значение и вставляем результат в HashMap. На самом деле это просто замаскированный поиск в глубину.
Это позволяет нам писать любой запрос обхода графа в декларативной манере. Мы можем написать, что мы хотим, чтобы результат основывался на других узлах графа, и нам не нужно беспокоиться о фактическом выполнении запроса.
Имейте в виду, что эта реализация асимптотически эффективна как для тяжелых случаев чтения, так и для тяжелых случаев записи. В реализациях с тяжелым чтением мы кэшируем результаты промежуточных вычислений и лениво выполняем минимальное количество шагов, необходимых для получения результата. При больших нагрузках записи мы полностью отказываемся от кеша и должны обновлять только важные данные в самих отдельных узлах, и ничего больше.
Мы можем использовать график следующим образом:
fn main() { let mut graph = Graph::new();let lay_foundation = graph.add_node(Task::new("Lay foundation", 1)); let build_walls = graph.add_node(Task::new("Build walls", 2)); graph.add_edge(&lay_foundation, &build_walls);let build_roof = graph.add_node(Task::new("Build roof", 4)); graph.add_edge(&build_walls, &build_roof);let paint_walls = graph.add_node(Task::new("Paint walls", 8)); graph.add_edge(&build_walls, &paint_walls);let furnish_house = graph.add_node(Task::new("Furnish house", 16)); graph.add_edge(&paint_walls, &furnish_house);let mut view = GraphView::new(&graph); println!("Days require to finish house: {:?}", view.end_time(&furnish_house)); }
Это решение многословно, но имеет надежные гарантии. Мы можем расширить эту структуру несколькими способами. Если нам нужны узлы разных типов, мы можем иметь одну коллекцию узлов для каждого типа внутри нашей структуры Graph. Если нам нужны различные типы соединений между узлами, мы можем изменить нашу структуру GraphNode, чтобы иметь больше полей, чем просто incoming и outgoing. Мы даже можем обнаружить циклы, если немного изменим код представления:
struct GraphView2<'a> { graph: &'a Graph<Task>, // Store an Option rather than the value itself. // None means a circular reference start_times: HashMap<Uuid, Option<u32>>, end_times: HashMap<Uuid, Option<u32>>, } impl<'a> GraphView2<'a> { fn new (graph: &'a Graph<Task>) -> Self { GraphView2 { graph: graph, start_times: HashMap::new(), end_times: HashMap::new(), } } fn end_time(&mut self, key: &Uuid) -> Option<u32> { if let Some(result) = self.end_times.get(key) { return result.clone(); } // We assume that a node is part of a circular reference // until proved otherwise. self.end_times.insert(key.clone(), None); let result = self.start_time(key) .map(|time| time + self.graph.get(key).duration);self.end_times.insert(key.clone(), result); result } fn start_time(&mut self, key: &Uuid) -> Option<u32> { if let Some(result) = self.start_times.get(key) { return result.clone(); } self.start_times.insert(key.clone(), None);let result = self.graph.get_incoming(key) .into_iter() .map(|key_out| self.end_time(key_out)) .fold(Some(0), |max_time, end_time| Some(max_time?.max(end_time?)));self.start_times.insert(key.clone(), result); result } }
В этом примере start_time и end_time возвращают None, если узлы являются частью циклической ссылки, поэтому мы можем обнаружить их и соответствующим образом обработать.
Вывод
Я представляю два способа создания кода, который имеет общую изменчивость в некоторой произвольной структуре ациклического графа в Rust. С одной стороны, у нас есть структура произвольной формы, включающая Rc и RefCell. Недостатком такой структуры является то, что мы не можем кэшировать результаты, зависящие от других сущностей. Кроме того, мы должны быть осторожны, чтобы не ввести ссылочные циклы. Это кажется простым, но имеет некоторые сложные оговорки.
С другой стороны, мы можем создать какую-то арену. Я привожу пример реализации: график. Я могу отделить данные, представляющие отношения между узлами, от данных самих узлов. Граф можно временно заморозить для изменения, чтобы мы могли выполнять запросы. Он не использует RefCell, поэтому имеет более сильные статические гарантии в отношении заимствования. Он асимптотически эффективен для различных вариантов использования. Мы можем писать декларативные запросы и эффективно их выполнять. Он также может быть расширен различными способами. На мой взгляд, это самая простая «правильная» реализация.
В следующей статье я расскажу о структурах, содержащих ссылочные циклы.
Этот пост изначально был размещен в Блокноте Эндрю
