Программирование на TypeScript/JavaScript
Написание интерактивных ресурсоемких программ для веб-браузеров
Делаем однопоточные программы на TypeScript/JavaScript адаптивными
Недавно я переписал несколько демонстрационных программ алгоритмов десятилетней давности с Java Web Applets на JavaScript. Для молодежи в аудитории, еще на заре Всемирной паутины, веб-скрипты означали написание Java, а не JavaScript. Проблемы с безопасностью и производительностью привели к тому, что Java устарела как язык сценариев веб-страниц.
Я никогда не программировал на JavaScript, но подумал, насколько это сложно? Все интерпретируемые языки в значительной степени представляют собой LISP с другим синтаксисом, и я отточил свои навыки программирования на LISP!
Первое, что я узнал, это то, что большая часть JavaScript странная, запутанная и плохая, но почти все плохие части скрыты, а TypeScript добавляет много нового. Microsoft Visual Studio Code упрощает программирование на TypeScript, компиляцию в JavaScript, а затем отладку кода, выполняемого в Chrome. Очень здорово!
Второе, что я узнал, это то, что веб-браузеры запускают JavaScript как один поток. Настольный интерпретатор JavaScript, Node.js, поддерживает «рабочие» потоки, но многопоточность не поддерживается Chrome. Это означало, что я не мог использовать подход, использовавшийся в исходных версиях программ на Java, где один поток выполнял алгоритм для демонстрации, а другой поток обрабатывал взаимодействие с пользователем. Все должно было обрабатываться одним потоком.
Это создало проблему: алгоритмы, которые должны были быть продемонстрированы, были требовательны к вычислительным ресурсам и требовали многоминутной работы. Если бы код просто запускал исходный алгоритм при нажатии кнопки запуска, окно браузера зависало бы до завершения алгоритма. Демонстрацию можно было просмотреть, но с ней нельзя было каким-либо образом взаимодействовать — даже для нажатия кнопки «Остановить». Это было бы противоположностью отзывчивой интерактивной программе!
Многопоточность упрощает написание интерактивных программ, но не является абсолютно необходимой. На самом деле, в исходной операционной системе Apple Macintosh не было ни многопроцессорности, ни многопоточности! Существует два основных подхода к написанию интерактивных программ в однопоточной среде. Во-первых, основная программа часто выполняет системный вызов, обрабатывающий такие события, как щелчки мышью и клавиатурой. Во-вторых, основная программа должна быть написана таким образом, чтобы она работала всего несколько миллисекунд, прежде чем вернуть управление операционной системе вместе с запросом, который операционная система снова выполнит в ближайшем будущем. Второй подход мы проиллюстрируем демонстрационной программой для поиска с возвратом и локального поиска с использованием задачи N-Queens.
Загрузите мой код с GitLab, чтобы продолжить: https://gitlab.com/HenryKautz/n-queens.
Вы можете запустить демоверсии с сайта моего университета: https://www.cs.rochester.edu/u/kautz/tsQueens/tsQueens.html.
Задача состоит в том, чтобы расставить N ферзей на шахматной доске NxN так, чтобы никакие два ферзя не атаковали друг друга или определили, что это невозможно. Чтобы усложнить задачу, можно при желании предварительно разместить некоторые из ферзей на фиксированных позициях на доске. Эта вторая версия, называемая N-Queens Completion, может быть показана как NP-сложная, что означает, что, скорее всего, не существует алгоритма для задачи, который масштабируется неэкспоненциально с N. Таким образом, N-Queens является хорошей областью для демонстрационного эвристического поиска. алгоритмы. После необязательного изменения размера доски и исправления некоторых ферзей пользователь может выбрать алгоритм поиска с возвратом или алгоритм локального поиска.
Алгоритм локального поиска легко настроить так, чтобы он реагировал на взаимодействие. Алгоритм высокого уровня состоит в том, чтобы поместить ферзя в каждом ряду в случайном месте, а затем, пока есть атакующие ферзи, попытаться переместить ферзя, чтобы уменьшить количество атак.
Мы можем превратить это в однопоточный интерактивный алгоритм, заменив цикл while обработчиком событий. Вот ключевые части кода, где «. . ». указывает места, где код был опущен для ясности. Когда пользователь нажимает кнопку с надписью «Локальный поиск», ее обработчик
function localSearchButtonHandler() {
nqueens.StartLocalSearchSolver();
}
вызывает метод класса nQueen
StartLocalSearchSolver() {
. . .
this.RandomlyPlaceQueens();
this.step = 0;
HaltFlag = false;
Schedule(LocalSearchSolverStepper);
. . .
}
который планирует первую итерацию поиска. Расписание — это просто служебная функция, которая использует window.setTimeout для установки своего аргумента для запуска через некоторое количество миллисекунд в будущем. Значение задержки контролируется другими обработчиками кнопок.
function Schedule(fn) {
. . .
window.setTimeout(fn, delay);
}
Когда LocalSearchSolverStepper запускается, он просто вызывает метод nQueens, который выполняет одну итерацию локального поиска. Это необходимо, потому что setTimeout требует, чтобы его первый аргумент был функцией, а не методом.
function LocalSearchSolverStepper() {
nqueens.LocalSearchSolver();
}
Теперь обратимся к методу nQueens, выполняющему работу по локальному поиску. Сначала он проверяет, не превысило ли число шагов заданное отсечение, и если это так, уведомляет пользователя о том, что поиск не удался, и возвращает результат. В противном случае создается список строк, содержащих атакующих ферзей. Если их нет, он уведомляет пользователя об успешном поиске и возвращается. Если ни одно из условий не выполняется, он перемещает одну из ферзей.
LocalSearchSolver() {
if (this.step > this.cutoff) {
// Failed to find solution before reaching cutoff
TellUser('Local search failed after ' + this.step +
' flips.');
return;
}
// Set R to a list of rows containing attacking queens
. . .
if (R.length == 0) {
TellUser('Local search succeeded using ' + this.step +
' flips.')
return;
}
// Randomly pick a row containing an attacking queen and
// move the queen to a best possible column
. . .
// Get ready for next step
if (HaltFlag) {
TellUser('Local search solver halted at step ' +
this.step + '.');
return;
}
Schedule(LocalSearchSolverStepper);
}
Мы видели HaltFlag в StartLocalSearchSolver, где он был инициализирован значением false. Обработчик кнопки с надписью «Остановить» устанавливает для нее значение true, если пользователь нажимает на нее. Если в этот момент кода HaltFlag был изменен на true, пользователь уведомляется о том, что поиск был остановлен, и метод возвращается. Если HaltFlag остается ложным, вызывается Schedule, чтобы запланировать следующую итерацию поиска.
Этот общий шаблон можно использовать для любого алгоритма, который естественным образом принимает форму одного длительного цикла. Вы можете предпочесть стилистические вариации шаблона, например, перенести тест для HaltFlag в Schedule. Ключевые элементы:
- Функция выполняет одну итерацию основного цикла
- Использование window.SetTimeout для планирования или изменения расписания выполнения этой функции
- Глобальная переменная, которую можно использовать для остановки алгоритма до его завершения.
Что, если алгоритм не принимает форму одного цикла? Например, предположим, что это рекурсивный алгоритм. Нужно ли нам вручную переписывать его, чтобы заменить рекурсию итерацией? Счастливый ответ заключается в том, что мы не делаем. Мы можем использовать концепцию под названием «генератор», чтобы заставить любой алгоритм работать короткими импульсами. Генератор — это объект особого типа, основная функция которого дает не один результат, а серию результатов с течением времени. Генератор инициализируется путем вызова точно так же, как вызов функции или метода. Однако вместо возврата значения он выдает значение. Оператор yield приостанавливает, а не завершает работу генератора после сохранения его внутреннего состояния. Затем метод генератора next возобновляет выполнение до тех пор, пока снова не встретится yield. Программисты, знакомые с концепцией итератора в JavaScript, поймут, что генераторы — это способ написания итераторов без необходимости явного сохранения состояния объекта между итераторами. Генераторы также можно рассматривать как своего рода продолжение для читателей, знакомых с этой концепцией.
Генераторы имеют одну дополнительную функцию, которая является особенностью их реализации TypeScript: их также можно вызывать и возвращать значения, как и обычные функции! Мы будем использовать эту двойную природу генераторов в нашем коде.
Давайте рассмотрим, что происходит, когда пользователь нажимает кнопку «Поиск с возвратом». Следующий бит кода
function backtrackingButtonHandler() {
nqueens.StartBacktrackingSolver();
}
вызывает метод StartBacktrackingSolver в nQueens.
StartBacktrackingSolver() {
HaltFlag = false;
DoneFlag = false;
. . .
this.step = 0;
. . .
BacktrackGenerator = this.BacktrackSolver(0);
Schedule(BacktrackingSolverStepper);
. . .
}
На этот раз мы используем два глобальных флага: HaltFlag, чтобы указать, что поиск завершился каким-либо образом (успех, неудача, превышение лимита поиска с возвратом или нажатие пользователем кнопки «Остановить»), и DoneFlag, чтобы указать, что поиск закончился в успех. Метод генератора BacktrackSolver инициализируется и сохраняется в глобальной переменной BacktrackGenerator. Затем, как и в алгоритме локального поиска, планируется запустить «шаговую» функцию. Пошаговая функция немного сложнее, чем функция локального поиска, потому что мы решили возложить на нее ответственность за определение того, следует ли перепланировать себя для продолжения поиска.
function BacktrackingSolverStepper() {
BacktrackGenerator.next();
if (HaltFlag) {
if (!DoneFlag) {
TellUser('Backtracking search halted after ' +
nqueens.step + ' backtracks.')
}
}
else {
Schedule(BacktrackingSolverStepper);
}
}
Теперь перейдем к собственно алгоритму поиска. Символ * перед именем метода сообщает компилятору TypeScript, что мы определяем генератор. Входным параметром является номер ряда (начиная с 0), в котором должны быть размещены ферзи. Метод возвращает true, если удается разместить ферзей в этом и во всех последующих рядах таким образом, чтобы не было атак. Метод возвращает значение true, если он готов приостановить выполнение, чтобы разрешить обработку системных событий. Важное различие между return и yield заключается в том, что return завершает возможное рекурсивное выполнение генератора, а yield просто приостанавливает работу генератора. Метод возвращает false, если не удается завершить размещение ферзей или достигнуто ограничение на количество выполняемых шагов поиска.
* BacktrackSolver(rowToPlace: number) {
let status: boolean;
if (rowToPlace >= this.Dim) {
HaltFlag = true;
DoneFlag = true;
return true;
}
. . .
yield true;
// Try each column in this row, return true if any succeed
for (let col = 0; col < this.Dim; col++) {
if ( // A queen can be placed in this column
// without attacks
. . . ) {
// Put a queen in this column of rowToPlace
. . .
// Recursively fill out the rest of the board
status = yield* this.BacktrackSolver(rowToPlace +
1);
if (status) {
return true;
}
// That didn’t work, so remove the queen from col
. . .
this.step += 1;
if (this.step >= this.cutoff) {
DoneFlag = false;
HaltFlag = true;
return false;
}
}
}
// All columns failed so return
if (rowToPlace == 0) {
HaltFlag = true;
DoneFlag = true;
TellUser('Backtracking proves no solution exists.');
}
return false;
}
Первое, что делает генератор, это проверяет, решил ли он головоломку. Если rowToPlace не меньше N, то все строки должны быть успешно заполнены. И DoneFlag, и HaltFlag установлены в true, и генератор возвращает true.
Затем генератор выдает true. Это приостанавливает его выполнение и делает его готовым к продолжению, когда вызывается BacktrackGenerator.next().
Затем генератор пробует каждый столбец rowToPlace, чтобы увидеть, может ли он поместить туда неатакующего ферзя. Если это так, он ставит ферзя, а затем рекурсивно вызывает себя. Вызов выполняется с использованием yield *, что означает, что возможность yield делегирована рекурсивному вызову BacktrackSolver. Таким образом, оператор yield true в рекурсивном вызове сохранит состояние всего стека рекурсивных вызовов перед тем, как приостановить себя, и при вызове BacktrackGenerator.next() выполнение продолжится с этого самого внутреннего вызова BacktrackSolver.
Если этот рекурсивный вызов возвращает истину, то проблема решена и алгоритм немедленно возвращает истину. Обратите внимание, что этот истинный статус будет передаваться через все рекурсивные вызовы BacktrackSolver до тех пор, пока не будет достигнут BacktrackSolver(0). Если рекурсивный вызов возвращает false, то ферзь удаляется, а счетчик this.steps увеличивается; если this.steps достигает максимального предела, установленного пользователем, генератор устанавливает HaltFlag в true, а DoneFlag в false и возвращает false. Если предел не достигнут, алгоритм пытается поместить ферзя в другой столбец. Если ни один из столбцов для RowToPlace не выполнен успешно, алгоритм возвращает false. Перед возвратом он проверяет, выполняется ли вызов верхнего уровня BacktrackSolver(0); если это так, то должно быть так, что проблема ферзей не имеет решения, поэтому печатается сообщение об этом.
Как и в случае с алгоритмом локального поиска, существуют и другие способы организации кода рекурсивной функции, требующей больших вычислительных ресурсов, чтобы сделать ее отзывчивой. Ключевые идеи:
- Функция превращается в генератор. Генератор может быть вызван как собственно генератор или как обычная функция или метод.
- Один или несколько операторов yield должны быть вставлены везде, где код хочет, чтобы его можно было приостановить.
- Рекурсивные вызовы самого себя выполняются с помощью команд yield *. Это использует природу генератора генератора.
- Возможные рекурсивные вызовы функции завершаются с помощью return, а не с помощью yield. Это использует функциональную природу генератора.
- Объект генератора хранится в глобальной переменной, а его метод next() вызывается функцией, выполнение которой запланировано с помощью window.setTimeout.
- Глобальная переменная может использоваться для предотвращения повторного планирования (вызова функции) следующего метода генератора.
Вот скриншот программы nQueens в процессе работы:
Если вы нашли этот пост полезным или у вас есть лучший или более чистый способ добиться тех же эффектов, оставьте комментарий!
