Как создать универсальную функцию хода с нуля

В этой статье будет рассмотрен процесс создания универсальной функции хода с нуля. Но сначала нам нужно уточнить, что это такое.

Что такое функция перемещения?

Вот одно из самых простых объяснений, которые я смог найти;

Структура данных содержит элементы, содержащие данные. Обход структуры данных означает: «посещение» или «прикосновение» к элементам структуры и выполнение каких-либо действий с данными.

Ключевые слова в этом определении: посещение элементов и структуры данных.

Во-первых, нет "посещения", если нечего посещать (элементы).< /p>

Во-вторых, «структура данных» — очень широкое понятие. В самых общих чертах структура данных – это набор данных, каким-то образом связанных друг с другом, упорядоченных в некотором логическом порядке, где одна точка данных связана с другой и т. д.

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

Структуры данных имеют почти геометрическую природу. Если бы вы рисовали изображения на доске, они выглядели бы как полосы, квадраты, треугольники, круги и деревья.

Чем проще фигура, тем проще по ней перемещаться, и многие языки программирования имеют для этого встроенные функции.

Самая простая форма — это «полоски», как массивы. Эти простые структуры данных тривиальны для прохождения, и вместо них обычно используется термин **итерация**, который отмечает своего рода различие в простоте.

Обход, который мы хотим обсудить в этой статье, менее тривиален; тот, который использовался для посещения узлов сложной структуры данных.

Итерация

Теперь, когда мы знаем, что означает обход, мы можем приступить к наброску того, как будет выглядеть функция.

const traverse = (target: unknown): void => {
  /** Do something here **/
}

traverse({ ... })

Нет смысла в обходе, если мы не хотим что-то делать. То, что мы хотим сделать с каждой точкой данных, не важно, важно только то, что мы можем это сделать.

Тогда нам нужна функция обратного вызова, которой мы можем делегировать любую задачу, которую хотим выполнить. каждую точку данных.

const traverse = (target: unknown, callback: Function): void => {
  /** 
   * Do something here, eventually invoke callback().
   **/
}

const callback = (data: unknown): void => {
  /** Do something here with data point **/
}

traverse({ ... }, callback)

Мы будем повторять операцию для каждой точки данных, которую мы называем итерацией.

Поддержка любой структуры данных

Первая проблема при создании универсальной функции перемещения заключается в том, что ей нужно знать, как перейти к каждой точке данных в структуре данных.

Мы используем TypeScript для примеров кода. Таким образом, в JavaScript очевидным местом для начала является возможность перехода к каждому элементу или паре ключ-значение в массиве или объекте.

Но не упускаем ли мы другие структуры данных?

Как насчет поддержки Map, WeakMap и Set? Мы можем добавить код для итерации и для них.

За исключением того, что функция traverse также может работать с экземплярами классов, созданными кем угодно. Иногда точки данных не обязательно сопоставляются со всеми свойствами экземпляра класса. Но мы не знаем того, чего не знаем.

Чтобы преодолеть эту проблему, нам нужно «информировать» функцию перемещения о других структурах данных и дать ей набор инструкций для каждой точки данных.

const registeredIterableClasses: IterableClassEntry[] = []

const registerIterableClass = (entry: IterableClassEntry): void => {
  registeredIterableClasses.push(entry)
}

const traverse = (target: unknown, callback: Function): void => {
  /**
   * 1. If target is a non-iterable type, exit early.
   * 2. If the target is iterable, access registeredIterableClasses
   *    and find the correct strategy to read the iterable's references.
   * 3. Invoke callback() on each data point traversed.
   **/
}

const callback = (data: unknown): void => {
  /** Do something here with data point **/
}

traverse({ ... }, callback)

Для начала нужно знать, как получить доступ к ссылкам на структуру данных. Помните, мы хотим сделать функцию traverse() максимально универсальной. Возможно, обратный вызов должен иметь возможность изменять значения или удалять значения. Что, если мы хотим клонировать данные?

Теперь мы понимаем, что для того, чтобы дать traverse() необходимые инструкции для работы со структурой данных, нам нужно дать ей больше.

interface IterableClassEntry {
  classRef: any // Reference to class itself as id
  instantiate: Function // use to create a new instance of the class
  getKeys: Function // use to get a list of references to each data point
  read: Function // use to read a value
  write: Function // used to update a value
  remove: Function // used to remove a reference to a value
}

Поддержка вложения

n

Теперь мы рассмотрели, как перемещаться по структурам данных.

Следующая проблема, которую необходимо решить, заключается в том, что структуры данных могут содержать другие структуры данных.

Для этого мы можем использовать рекурсию. Мы вызываем одну и ту же функцию обхода для каждой пройденной точки данных, чтобы она, в свою очередь, делала то же самое для любых точек данных в них. И так далее, пока не перестанут встречаться итерируемые структуры данных.

const registeredIterableClasses: IterableClassEntry[] = []

const registerIterableClass = (entry: IterableClassEntry): void => {
  registeredIterableClasses.push(entry)
}

const traverse = (target: unknown, callback: Function): void => {
  /**


1. Immediately invoke callback(target).
2. If the target is iterable, access registeredIterableClasses
   and find the correct strategy to read the iterable's references.
3. Invoke traverse() on each data point traversed.
**/
}


const callback = (data: unknown): void => {
  /** Do something here with data point **/
}

traverse({ ... }, callback)

Работа с циклическими ссылками

И последнее, но не менее важное: существуют структуры данных, которые в какой-то момент ссылаются сами на себя. Это правдоподобный сценарий, вы можете найти его в «круговой» структуре типа, похожей на график.

Если вы столкнетесь с этим, а алгоритм не знает, как это обнаружить, это, скорее всего, вызовет бесконечный цикл или динамическую блокировку, а также приведет к тому, что ваша программа исчерпает память и зависнет или завершится.

Этой теме можно было бы посвятить отдельную статью. Я напишу об этом позже.

Оптимизация

Функция обхода может быть довольно дорогой. Иногда вам может потребоваться выполнить это только для среза или «диапазона глубины» и/или иметь стратегию раннего выхода, чтобы избежать ненужных итераций с другими точками данных, как только вы получите нужный результат от обратного вызова.

Окончательный результат

Я надеюсь, что это краткое руководство помогло вам понять ключевые детали реализации собственной функции хода.

Если вы не можете утруждаться созданием своего собственного, вам повезло. Я уже создал этот готовый к работе traverse() функция, которую может использовать каждый.

Также опубликовано здесь

Главное изображение