Распространение порядка и алгоритмы сортировки
Она была искусно решена, но я продолжал думать об этом. У меня появилось больше понимания для проявления.
В тот день мой брат показал мне алгоритм сортировки, который он реализовал на ассемблере. Из схемы его объяснения я заметил возможность оптимизации.
Я схватил карандаш и нарисовал квадрат: «Это ваш алгоритм и…», я делю его пополам по диагонали, штрихуя один из получившихся треугольников, «мы можем сделать это так быстро».
Разработка …
В вычислительном отношении мы упорядочиваем список значений, зацикливая и меняя местами элементы, когда условие не выполняется. Мы повторяем это до тех пор, пока перестановка не потребуется.
Чтобы убедиться, что список полностью отсортирован, нам нужно, по крайней мере, повторить цикл по элементам столько раз, сколько у нас есть элементов. Поэтому сначала я нарисовал квадрат.
Для меня грамматика шаблона проектирования сортировки состоит из циклов, условных выражений и операций подкачки. Цикл помогает распространять желаемый порядок и реализовывать его при условном обмене.
В чем тогда была проблема с первым алгоритмом?
Он распространялся только вперед. И много раз.
Список — это одномерный мир, в котором мы можем распространяться в двух противоположных направлениях. Оптимизация, о которой я думал, использует возможность движения назад.
[Код доступен на https://github.com/A-esth/OrderJS]
Путем вложения двух циклов, первый из которых движется вперед, а второй — обратно. Мы можем сортировать весь список за одно продвижение вперед.
Результаты оказались такими, как и предполагалось. Эта оптимизация в два раза быстрее, чем исходная идея. Впрочем, не это меня больше всего интересовало. Это было определенное аналогичное мышление, которое я не мог не развлекать.
Я когда-то писал где-то в своих заметках,
«Информация — это слепок порядка с субстанции».
Сортировка представляется процессом, посредством которого уносится слепок определенного порядка. Несмотря на то, что субстанция виртуальная — цифровой список чисел, она создана по определенному правилу.
В нашем случае порядок, который мы реализовали, довольно прост; возрастающий порядок. Умственное усилие было направлено на оптимизацию. Естественно, информация, написанная в таком списке, не так уж и интересна.
Подумайте о картинках. Разве они не хранятся в виде некоторого массива значений RGB-A?
А теперь представьте, что одинаковые пиксели были разбросаны хаотично. Можем ли мы восстановить исходное изображение?
Выглядит невозможным, верно? Мы можем попытаться изменить порядок, и у нас может получиться совершенно другая картина.
Что, если я скажу вам, что теоретически возможно написать ОГРАНИЧЕНИЕ, распространение которого через эту двумерную виртуальную субстанцию восстанавливало бы изображение, и это независимо от энтропийного повреждения, которое оно получило.
Не знаю насчет осуществимости, но в принципе у нас есть основания думать, что это по крайней мере возможно. Но как?
Изображения представляют собой захваченные цветовые значения сцены. Совокупность физических субстанций, выражающая естественный порядок, поверх которой мы можем наложить слои человеческого порядка.
И да, вы понимаете, самая большая проблема здесь заключается в том, как выразить состав многоуровневого порядка, как правило.
Картина фиксирует следствие такого действующего правила в конкретный момент. Порядок, наложенный на его пиксели, является видимым аспектом порядка, наложенного на основные вещества.
Все это говорит о том, что осмысленный порядок и интересная информация являются побочным продуктом сложных правил.
Необходимость распространять порядок, а не навязывать его мгновенно, отражает тот факт, что информация не может распространяться мгновенно. Также порядок должен начать распространяться откуда-то внутри вещества; источник порядка.
Обычно мы начинаем сортировку с первого элемента списка. Поэтому я спросил себя, а что, если мы хотим начать с середины?
Мне было ясно, что решение этого варианта задачи не может быть быстрее основного случая.
Я разработал алгоритм на бумаге, нарисовав тот же квадрат, и попытался придумать распространение, которое по крайней мере имело бы ту же площадь — время вычисления — что и код прямого-обратного, начиная со среднего элемента.
Решение состоит из внешнего распространения, за которым следует внутреннее распространение. Первый распространяется по мере того, как он передает новую информацию по всему списку, а второй отскакивает от пределов, чтобы сходиться к источнику.
Полученный код является общим ответом на проблему сортировки. Если мы переместим источник в начало, мы вернем прежнее решение, которое является лишь частным случаем.
Теперь, если мы вернемся к этому решению, я хотел бы указать на интересный аспект того, что я закодировал.
Поступательное распространение представляет собой волнообразное движение. Он проникает сквозь вещество до тех пор, пока не встречает сопротивления; последовательность элементов, которая не соответствует требуемому порядку.
Каждый раз, когда требуется обмен, это похоже на сопротивление, которое теряет энергию основной волны и генерирует обратные волны, которые гарантируют передачу информации о произошедшем изменении.
Вопрос, зачем менять местами только соседние элементы? Разве мы не можем придумать идеи, которые использовали бы замену удаленных элементов?
Возможно, вы можете, но я действительно не понимаю, как такое решение может быть универсальным, эффективным и последовательным. Он нарушает непрерывность, обеспечивая мгновенную связь между удаленными частями.
Природа — наше самое большое вдохновение, и мы точно знаем, что все взаимодействия должны происходить локально — за исключением случая квантовой запутанности.
В целом, информация должна следовать связными путями. Вот почему мы используем поля и волны для представления различных физических веществ и их взаимодействий.
И если мы внимательно посмотрим, все, что происходит, является просто побочным продуктом обмена вещами. Динамика и движение объектов в нашей вселенной тоже делается на этой основе. Результатом чего является реальность.
Когда объект перемещается из одного места в другое, он эффективно меняет местами со следующим ближайшим объектом, пока не достигнет места назначения. Он проникает через среду, испуская энергию — останавливает петлю для замены — которая перемещает вещи — обратные волны — по мере прохождения.
Я должен сказать, что степень аналогичного совпадения между шаблоном проектирования алгоритмов сортировки и принципами, лежащими в основе естественных процессов, несколько удивительна.
Что касается списка, с которым мы играли, его динамика не длилась — в зависимости от его размера — более сотен миллисекунд, а иногда и меньше, прежде чем достичь стазиса. Эффективный конец одной возможной мировой истории.
С другой стороны, динамика нашей Вселенной все еще продолжается. До …
