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 > |
Приветствие 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) |
html - файл
В общем случае, html-файл, в котором бракзер исполняет код JavaScript, состоит из двух разделов: заголовка (head) и тела документа (body):
< html > <!-- html-комментарий --> < head > <!-- в заголовке можно подключить внешние файлы --> < title >Example Hello</ title > <!-- название этого документа --> < script src = "hello.js" ></ script > <!-- текст скрипта содержится в hello.js --> </ head > < body > <!-- собственно тело html-документа --> < h1 >Заголовок в начале страницы</ h1 > < h2 >Название подраздела</ h2 > < p >Абзац, начинающийся с новой строчки. < b >Жирный текст</ b ></ p > </ body > </ html > |
Непосредственный вывод текста при помощи функции 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; // возвращаем результат } |
Цикл 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; } |
var house = new House( "City" , 5); // создаём объект, как экземпляр класса House var villa = new House( "Country" , 10); // создаём другой объект villa.unlock(); // вызываем метод класса document.write(house, ' (' , house.open, ')<br>' ); // выводим объекты как строки document.write(villa, ' (' , villa.open, ')<br>' ); // и получаем значение их свойств через точку document.write(House.square(1)); // вызываем статическую функцию |
Дом в City, 5 комнат, сейчас закрыт (false)
Дом в Country, 10 комнат, сейчас открыт (true)
3.141592653589793
Обратим внимание, что когда мы описываем класс как абстрактную сущность, доступ к свойствам осуществляется при помощи указателя 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 > |
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); } |
По-мимо вывода графики, канвас может взаимодействовать с мышкой. Ниже приведена ханойская головоломка, которая будет подробно рассмотрена в дальнейшем. В ней есть стержня и дисков (числа можно менять). Эти диски необходимо по одному переложить с первого стержня на второй. Можно использовать все стержни, но диски большего диаметра должны всегда находиться ниже дисков меньшего диаметра (кликните мышкой по картинке).
Кроме канваса, выводить графику можно при помощи векторных картинок в 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++. В большинстве случаев это не критично.