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
Числа
Строки
Массивы
Объекты
=== vs. ==
Строки
Строки в 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)), то в документе появится: .
Цикл while
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-графикой.
О памяти и указателях
Память
Разберём подробнее особенности работы с указателями на следующем примере (справа зелёным - результат работы скрипта):
Вначале выделяется память для хранения объекта с одним свойством: { 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 означает "нулевой адрес памяти" (это указатель, который никуда не ведет).
null vs. 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++. В большинстве случаев это не критично.