JavaScript для ИИ


Введение

Этим документом начинается серия материалов, посвящённых искусственному интеллекту и компьютерным наукам. Начнём мы с рассмотрения основных технологий программирования и структур данных, а затем перейдём к задачам, которые, обычно, принято относить к "интеллектуальным".

В качестве рабочего инструмента программирования выбран язык JavaScript. Для его использования необходим лишь текстовый редактор (например Notepad++) и браузер (предпочтительно Google Chrome, который имеет неплохие средства отладки). В интернете есть множество материалов, посвящённых JavaScript, из которых стоит отметить w3schools.com, developer.mozilla.org и javascript.ru. Конспективно JavaScript рассмотрен и в шпаргалке на этом сайте. Мы не будем детально описывать язык, делая лишь иногда небольшие отступления о его характерных особенностях. В этом документе представлен экспресс-обзор возможностей JavaScript.


Hello world

Создадим программу (скрипт) на JavaScript. Для этого откроем любой текстовый редактор и наберём:

<script>
   var st = "Hello world";                        // <- текстовая строка (а это комментарий)
   document.write("Приветствие "+st);             // выводим текст в html-документ
</script>
Файл сохраним с расширением html (например hello.html) и затем откроем в браузере. Там появится строка:
   Приветствие Hello world.

Глобальный (видимый отовсюду) объект document является текущим html-документом, а его метод (функция) write выводит строку в том месте документа, где её вызвали. При этом write может содержать произвольное число аргументов (через запятую), которые выводятся последовательно. Например, можно было написать: document.write("Приветствие ", st).

JavaScript имеет C-подобный синтаксис. Например, операторы управления логикой программы (алгоритма) имеют следующий вид:

if(a==1) res=1; else res=2;                       // условный переход

switch (a) {                                      // оператор ветвления
  case 1:  res=1;  break;                         // если a==1, то res=1
  case 2:  res=2;  break;                         // если a==2, то res=2
  default: res=0;  break;                         // в любом другом случае res=0
}

for (i = 0; i < 100; i++) a[i]=i;                 // цикл for перебирает числа от 0 дл 99

i=0;
while (i < 10) {                                  // цикл while перебирает числа от 0 до 9
   i++;
}

do {                                              // цикл do-while (условие проверяется в конце)
   i++;
} while (i < 10)
Каждая команда JavaScript оканчивается точкой с запятой (её можно не ставить, если команд в строке больше нет). В фигурные скобки окружают блоки из нескольких команд (выше, например, цикл while). Код скрипта находится между парой тегов <script> ... </script>. Их в документе может быть любое количество и они, обычно, чередуются с обычным текстом и тегами html-разметки. Далее в примерах тег script будет опускаться.


html - файл

В общем случае, html-файл, в котором бракзер исполняет код JavaScript, состоит из двух разделов: заголовка (head) и тела документа (body):

<html>                                         

   <head>                                      
      <title>Example Hello</title>             
      <script src="hello.js"></script>         
   </head>

   <body>                                      
      <h1>Заголовок в начале страницы</h1>
      <h2>Название подраздела</h2>
      <p>Абзац, начинающийся с новой строчки. Жирный текст</p>
   </body>
</html>
Скрипт можно также загрузить из внешнего файла, как это сделано выше для файла hello.js (таких подключений "внешних модулей" может быть любое количество).

Непосредственный вывод текста при помощи функции document.write(...) стоит использовать для простых случаев. В реальных проектах принято разделять визуальную составляющую информации (где, что должно находиться на странице), её внешний вид (он задается стилями) и динамическое поведение (собственно скрипт). JavaScript может обратиться к любому элементу страницы и поменять его. Соответствующий пример мы рассмотрим в конце этого документа.


Типы данных

Базовыми типами в JavaScript являются: числа (Number), строки (String), массивы (Array) и объекты (Object). JavaScript - это полиморфный язык, т.е. тип переменной может меняться и зависит от контекста её использования. Для объявления переменной служит директива var:

var size    = 5;                                  // это число  Number
var ok      = true;                               // это логическая переменная
var name    = "Tom";                              // это строка String
var friends = [ "Jerry", "Merry", 137 ];          // это массив Array
var house   = { addr:"City",  rooms:5 };          // это объект Object

JavaScript
Числа
Числа в JavaScript вещественные, но с ними можно делать и целочисленные операции (например, логический сдвиг на 8 бинарных разрядов 1 << 8 равен 2 в степени 8 или ). Существует объект Math, который предоставляет различные методы работы с числами. Например, Math.sqrt(2) - квадратный корень, Math.sin(Math.PI) - синус и число пи, Math.random() - псевдослучайное число от 0 до 1, а Math.floor(x) - целая часть вещественного числа x. Полный список всех функций можно найти, например, здесь.

JavaScript
Строки
Строки могут быть в двойных ("строка") или одинарных ('строка') кавычках. Их можно чередовать, например "это 'строка' в строке". Знак плюс для строк означает их соединение, причём "строка"+5 равно "", а "строка"+(5+7) - равно "" (сначала складываются числа, результат переводится в строку и присоединяется к строке). Каждая строка имеет свойство length, хранящее её длину ("123abc".length равно 6). Строки можно сравнивать. Если s1="abc", а s2="acb", то s1 < s2 будет истиной (true), а s1 == s2 - ложью (false).

JavaScript
Массивы
Массив можно объявить пустым: friends = [] или инициализировать значениями. В примере выше, массив friends содержит три элемента и его длина (свойство friends.length) равна . Можно также задать размер массива, но не определять его элементы: friends = new Array(3). Доступ к элементам массива получается при помощи квадратных скобок, с нумерацией, ведущейся от нуля: frends[0] - это "Jerry", а frends[2] - 137 (элементы массива могут иметь различный тип).

JavaScript
Объекты
Объекты похожи на массивы, но доступ к хранимым в них данным происходит не по номеру, а по имени (которое называется свойством). На имя ссылаются, как и в массивах, при помощи квадратных скобок: house["rooms"] или через точку: house.rooms (без кавычек). В обоих случаях получится . Новые разновидности данных (свойства) в объект можно добавлять и после его объявления. Например, в дальнейшем, написав house.open = true;, мы добавим в объект house третье свойство "open" со значением true.

JavaScript
=== vs. ==
Полиморфность языка приводит к некоторым особенностям сравнения величин. В JavaScript существует два вида равенства: двойное == и тройное ===. Операция с двумя равенствами (==) делает сначала преобразование типов, а лишь затем величины сравнивает между собой. Так, "1"==1 равно (истина), а "1"===1 равно (ложь, так как величины имеют различный тип: строка и число). К чему будут преобразованы типы зависит от контекста. Например, при сравнении строки и числа, число преобразуется к строке, как и при "складывании" строк ("строка"+5 это "строка5"). Если тип величин известен, лучше использовать более быстрое тройное равенство (нет приведения типов).


Строки

Строки в JavaScript менять нельзя. Как только строка создана – она такая навсегда. Любые операции с ними приводят к созданию новых строк. Об этом стоит помнить при анализе производительности кода. Чтобы изменить некоторые символы в строке, можно превратить её в массив или воспользоваться регулярными выражениями.

Приведём примеры работы со строками (нумерация символов строк, как и в массивах, начинается с нуля):

var s = "box";                                    // ссылка на эту строку
var txt = "string \
in next line";                                    // строка на нескольких линиях

s.length                                          // число символов в строке
s.charAt(5)                                       // символ на 5-той позиции; тоже что s[5]
s.charCodeAt(5)                                   // код unicode символа на 5-той позиции

var arr = "a,b,c".split(',')                      // => массив ["a", "b", "c"] (строку на подстроки)
s = s.substr(1, 2)                                // подстрока c 1-го символа длиной 2
if( s.includes('ox') ){...}                       // есть ли подстрока
'абв'.repeat(2);                                  // повторяем строку 2 раза: 'абвабв'

Существуют функции, понимающие регулярные выражения . Например, заменить в строке все (параметр g) слова "тяжело" на слово "легко", без учёта высоты букв (параметр i), можно следующим образом:

s = 'Тяжело учиться, ох как тяжело.';
s = s.replace(/тяжело/gi, 'легко');               // => легко учиться, ох как легко.
Выражение в косых чертах (слешах) называется шаблоном поиска. Он может содержать различные специальные символы:
^ - начало строки, [xy] - один из символов ([abcd] - то же, что [a-d]), . - любой символ, + - повторение предыдущего символа 1 или более раз, {n,m} повторение в интервале [n...m] раз, \s - пробел, табуляция или перевод каретки, \d - цифра [0-9] и т.д. Приведём примеры шаблонов (опуская слеши):
^[0-9]+                                           // строка, начинающейся с цифры
(\d{1,2}\/\d{1,2}\/\d{4})                         // дата: 18/1/2017


Функции

Ключевое слово function объявляет функцию. Например, факториал числа (n!=n·(n-1)·...·1 и 0!=1!=1) даёт следующая функция:

function fac(n)
{
   if( n < 2 ) return 1;                          // защита от отрицательных чисел

   var res = n;                                   // возвращаемое значение
   while( --n )                                   // пока (n = n-1) > 0
      res *= n;                                   // перемножаем числа: res=res*n
   return res;                                    // возвращаем результат
}
Если написать: document.write("5!=", fac(5)), то в документе появится: .

JavaScript
Цикл while
Первая строка с условием if - "защита" от отрицательных чисел, а ключевое слово return возвращает значение функции. Далее начинает работать цикл while, который "крутится" до тех пор, пока выражение в круглых скобках истинно. В этих скобках происходит уменьшение числа n на 1. Возможны два способа уменьшения: n-- и --n (оба эквивалентны n = n-1). Однако, в первом случае сначала проводится проверка условия, а затем уменьшение, а во втором (-- впереди) - сначала число уменьшается, а только затем участвует в проверке. В JavaScript, как и в C/C++, число "считается истинным", если оно отлично от нуля и ложным при нулевом значении. Поэтому while крутится до тех пор, пока n больше единицы. При n=1 получаем цепочку:
while(--1)while( 0 )while(false) ⇒ цикл не выполняем.


Объекты и классы

В JavaScript функция одновременно является именем класса (потенциального множества однотипных объектов). Следующий код декларирует существование класса House, который хранит в себе 3 свойства (addr, rooms, open), а также может выполнять определенные действия (имеет методы):

function House(addr, rooms)                       // задаём три свойства
{
   this.addr  = addr;                             // адрес дома
   this.rooms = rooms;                            // число комнат
   this.open  = false;                            // по умолчанию закрыт
}

House.prototype.toString = function ()            // выдать объект как строку
{
     return "Дом в "+this.addr + ", "+this.rooms+" комнат, сейчас "+(this.open?"открыт":"закрыт");
}

House.prototype.unlock = function ()              // открыть дом
{
   this.open  = true;                             // изменяем значение свойства
}

House.square = function (r)                       // статическая функция (площадь окружности)
{
   return Math.PI * r * r;
}
Описав класс, можно создать произвольное число объектов - экземпляров этого класса. Для этого служит оператор new:
var house = new House("City", 5);                 // создаём объект, как экземпляр класса House
var villa = new House("Country", 10);             // создаём другой объект

villa.unlock();                                   // вызываем метод класса

document.write(house, ' (', house.open, ')
'); // выводим объекты как строки document.write(villa, ' (', villa.open, ')
'); // и получаем значение их свойств через точку document.write(House.square(1)); // вызываем статическую функцию
В результате работы этого скрипта получится:

Обратим внимание, что когда мы описываем класс как абстрактную сущность, доступ к свойствам осуществляется при помощи указателя this. А для экземпляра класса доступ к свойствам делается как и для любого объекта (выше так выведены значения свойства house.open и villa.open двух различных объектов).

Все методы которые доступны объектам (экземплярам класса) должны объявляться при помощи свойства prototype. Если его нет, то метод является статическим. Он не доступен экземплярам, но может быть вызван самим классом (выше - функция вычисления площади окружности). Подобным статическим образом организованы константы (свойства) и методы встроенного в JavaScript объекта Math (выше - число PI).


Канвас

JavaScript позволяет рисовать на html-странице. Для этого служит тег canvas, в котором задаётся ширина (width) и высота (height) области рисования. Ниже приведен простой пример html-документа:

<html>

   <head>
      <style>
         canvas.dashed {background-color: #fff; border: 1px dashed black; }
      </style>
   </head>

   <body>
      <canvas id="canID" class="dashed" width="600" height="40"></canvas>
      <script> .... </script>
   </body>
</html>
В его заголовке объявляется класс стиля с именем dashed. Если канвас (описанный в теле документа) содержит свойство class="dashed", то область рисования окажется обведенной пунктирной рамкой. Тег канвас, по-мимо указания размеров и класса стиля содержит идентификатор id = "canID". По этому идентификатору к канвасу можно "достучаться" из JavaScript:
plot();                                          // запускаем функцию рисования

function plot()
{
   var canvas = document.getElementById('canID');// получаем объект канваса
   var ctx = canvas.getContext('2d');            // у него есть свойство - контекст рисования
   ctx.fillRect(canvas.width/2-50, canvas.height/2-10, 100, 20);
}
В этом примере сначала получается объект html-страницы canvas при помощи функции getElementById. Этот объект имеет функцию getContext которая возвращает контекст рисования. Это тоже объект, со множеством функций рисования графических примитивов и работы с растровой графикой. В частности, в последней строке функции выводится залитый прямоугольник размерами 100 x 20 в центре канваса (объект canvas знает свои размеры). Вот к чему это приводит:

По-мимо вывода графики, канвас может взаимодействовать с мышкой. Ниже приведена ханойская головоломка, которая будет подробно рассмотрена в дальнейшем. В ней есть стержня и дисков (числа можно менять). Эти диски необходимо по одному переложить с первого стержня на второй. Можно использовать все стержни, но диски большего диаметра должны всегда находиться ниже дисков меньшего диаметра (кликните мышкой по картинке).

Кроме канваса, выводить графику можно при помощи векторных картинок в svg-формате или средствами WebGL, позволяющего работать с 3D-графикой.


О памяти и указателях

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

Разберём подробнее особенности работы с указателями на следующем примере (справа зелёным - результат работы скрипта):

function prn(x,y){ document.write("x.v=",x.v,", y.v=",y.v,'
'); } var x = { v:1 }; // выделяется память под объект, на неё ссылается x var y = x; prn(x,y); // y ссылается на эту же память x.v = 2; prn(x,y); // данные в памяти может поменять, как x y.v = 3; prn(x,y); // так и y x = { v:4 }; prn(x,y); // x теперь ссылается на другую память y = x; prn(x,y); // исходная память "потеряна"

Вначале выделяется память для хранения объекта с одним свойством: { v:1 }. На эту память ссылаются 2 переменные x и y. Поэтому изменение свойства v в одной (любой) переменной, "почувствует" и другая. Затем, в присвоении x = { v:4 }, выделяется память на хранение ещё одного объекта. Переменная "x" ссылается на него, а "y" ссылается на старый объект. Теперь изменения свойства v этих переменных происходят независимо (каждое в своей памяти). Наконец, при присвоении y=x, переменная "y" начинает ссылаться (как и "x") на новый объект. На старый объект уже ни кто не ссылается и сборщик мусора браузера эту память освободит. Ситуация со строками аналогична, и переменная объявленная как x="строка", является указателем на память, где строка хранится.

Сборщик мусора, освобождающий неиспользуемую память, в современных браузерах достаточно эффективен. Однако, ему стоит помогать, указывая когда память становится не нужной. Например, пусть для вычислений был выделен очень большой массив var ar = new Array(1000000). После его использования стоит написать ar = null, что приведёт к освобождению памяти. Ключевое слово null означает "нулевой адрес памяти" (это указатель, который никуда не ведет).

JavaScript
null vs. undefined
Переменные могут быть также неопределёнными (вообще ни куда не ссылаться). Между неопределённым свойством undefined и нулевым свойством null есть заметная разница. Пусть obj = { x:null }. Тогда свойство obj.y является undefined (его там нет), а свойство obj.x в объекте есть (и под его указатель выделена память), но оно (свойство) ссылается на "нулевой" адрес памяти. При сравнении без приведения типов null === undefined получится (это различные сущности), a null == undefined - это .

В низкоуровневых языках, таких как C/С++ или Assembler, программист должен заботиться, как о выделении памяти, так и о её освобождении. JavaScript в этом отношении существенно более дружественный язык. Например, если при обращении к элементу массива мы выходим за границы массива (свойство length), ни чего "плохого" не происходит и размер массива автоматически увеличивается. Впрочем, за всё необходимо платить. И в данном случае - чуть более низким (хотя и не существенно) быстродействием по сравнению с низкоуровневыми языками.


Быстродействие

Раз зашла речь о быстродействии, проведём несколько тестов. Так как они занимают время, будем запускать их по нажатию кнопки run. Для этого добавим в html-файл следующий код:

<input type="button" value="run" onclick="speed()">  время = <b id="timeID"></b> ms.

<script>
var totTime = 0, totRuns = 0;                     // общее время и число запусков функции

function speed()
{
   var time = window.performance.now();           // начальное время
   Fib(35);                                       // некоторые вычисления
   time = window.performance.now() - time;        // время, затраченное на вычисления

   totTime += time;                               // суммарное время
   totRuns++;                                     // число запусков

   document.getElementById("timeID").innerHTML = time.toFixed(0) + ", aver = "
                                               + (totTime/totRuns).toFixed(0) + "("+totRuns+")";
}
</script>

В результате появится кнопка (type="button") с надпиью "run" (value="run"), при нажатии на которую запустится функция speed (onclick="speed()"). Последняя строка функции поменяет текст в теге <b>: время = ms (нажмите на кнопку несколько раз).

Функция getElementById объекта document находит на html-странице тег со свойством id="timeID" и возвращает его как объект (аналогично канвасу). У него есть свойство innerHTML - текст внутри тега: <b id="timeID">...</b>. В этом месте и выводится время вычислений в миллисекундах (ms) и среднее значение по totRuns запускам. Для этого, перед началом вычислений в переменной time запоминается время, а после вычислений оно вычитается из времени на тот момент. Текущее время возвращает окно браузера - объект window.

Ниже в таблице приведено время в миллисекундах работы рекурсивной функции Fib1(n) (см. следующий документ) в JavaScript и С++ (gcc 64bit). Кроме этого, дано время суммирования в цикле по i c 10000000 итерациями некоторых величин:

Fib(35) Fib(40)   i      i*i  sqrt(i*0.1) sin(i*0.1)
JavaScript 100 1100 140 140 130 330
C++ 60 700 25 30 315 600

Как видно, быстродействие скриптового языка JavaScript вполне сравнимо с быстродействием C++. Заметим, что синус от "целочисленных" аргументов (например, sin(i*1)) почти в 5 раз медленнее, чем от "вещественных" (например, sin(i*0.1)). Небольшого ускорения можно добиться также, положив var sin = Math.sin; и затем писать не Math.sin(...), а sin(...) и т.д.

Google Chrome часто повторяемые участки JavaScript кода компилирует в ассемблер. Поэтому, вычисления с "дорогими" вещественными функциями, подобными exp или sin будут работать со сравнимой скоростью. В целочисленных вычислениях C++, конечно, быстрее, т.к. не производит ненужных преобразований типов переменных.

На комплексных тестах JavaScript, уступает С++, впрочем, не значительно. Например, задача коммивояжёра, решаемая методом ветвей и границ на JavaScript требует примерно на 25% больше времени, чем тот же алгоритм, реализованный на C++. В большинстве случаев это не критично.