06. Массивы

Контрольные задания

  1. Испытательный стенд Написать функцию forEach, которая принимает в качестве первого аргумента массив и применяет к каждому его элементу функцию, заданную вторым аргументом. Если функция не задана, массив не меняется. 

    
var a = [0,1,2,3,4,5];               
forEach(a); // Масcив a не изменился

var a = [0,1,2,3,4,5];               
// Возвести все элементы массива в квадрат
forEach(a,function(x){return x*x;}); // Массив a: [0,1,4,9,16,25]
    Решение
    
function forEach(a,f)
{
  if (f) for(var i=0; i<a.length; i++) a[i]=f(a[i]);
}

    Комментарий

    Локальной переменной a присваивается ссылка на массив, который располагается где-то в памяти (вне функции). Поэтому a[i] — это формула доступа к i-ому элементу массива внутри функции. Можно читать элементы, а можно их менять при помощи инструкции a[i]=f(a[i]).

    Тестирование

    Как это проверить на испытательном стенде. Выносим в испытательный стенд такой код: 

    
function forEach(a,f)
{
  if (f) for(var i=0; i<a.length; i++) a[i]=f(a[i]);
}
var a = [0,1,2,3,4,5];               
forEach(a); // Масcив a не изменился
alert(a);   // 0,1,2,3,4,5
// Возвести все элементы массива в квадрат
forEach(a, function (x) {return x*x;} ); 
alert(a);   // 0,1,4,9,16,25

  2. Испытательный стенд Написать функцию filter, которая принимает в качестве первого аргумента массив и возвращает массив из элементов, для которых функция, заданная вторым аргументом, возвращает значение true. 

    
var a = [0,-1,2,-3,45,-6];               
// Создать массив из положительных элементов 
// исходного массива
var b = filter(a, function (x) 
  { return x>0;}); // [2,45]

var a = [1,,,2,,3,undefined,4]               
// Создать массив из элементов исходного массива,  
// имеющих определённые значения. 
var b = filter(a, function (x) 
  { return x != undefined;}); // [1,2,3,4]

var a = [1,{x:1},"кот",[1,2],function(x){return x*x},true]               
// Создать массив из элементов исходного массива, имеющих  
// значения элементарного типа
var b = filter(a, function (x) 
  { 
    return typeof(x) == "number" ||
           typeof(x) == "string" ||
           typeof(x) == "boolean";                       
  }); // [1,"кот",true]
    Решение
    
function filter(a,f)
{
  var result = [];
  for(var i=0; i<a.length; i++) if (f(a[i])) result.push(a[i]);
  return result;
}

    Комментарий

    Функция создает пустой массив и добавляет в него методом push те элементы исходного массива, которые проходят проверку.

    Тестирование

    Как это проверить на испытательном стенде. Выносим в испытательный стенд такой код: 

    
function filter(a,f)
{
  var result = [];
  for(var i=0; i<a.length; i++) if (f(a[i])) result.push(a[i]);
  return result;
}
var a = [0,-1,2,-3,45,-6];               
// Создать массив из положительных элементов исходного массива
var b = filter(a, function (x) { return x>0;}); // [2,45]
alert(b); // 2,45
a = [1,,,2,,3,undefined,4]               
// Создать массив из элементов исходного массива, имеющих 
// определённые значения. 
b = filter(a, function (x) { return x != undefined;}); // [1,2,3,4]
alert(b); // 1,2,3,4
a = [1,{x:1}, "кот", [1,2], function (x) {return x*x}, true]               
// Создать массив из элементов исходного массива, имеющих значения 
// элементарного типа
b = filter(a, function (x) 
 { 
   return typeof(x) == "number" ||
          typeof(x) == "string" ||
          typeof(x) == "boolean";                       
  }); // [1,"кот",true]
alert(b); // 1,кот,true

  3. Испытательный стенд Написать функцию toOne, которая принимает в качестве аргумента массив, каждый элемент которого содержит, либо значение элементарного типа, либо массив, подобный исходному. Функция должна возвращать массив, содержащий значения элементарного типа в том порядке, в котором они следуют в исходном массиве без учета вложенности. 

    
var a = [0,1,[2,3],4,5,6];               
toOne(a);  // Возвращает [0,1,2,3,4,5,6]

var a = [0,[1,[2]],3,[4,[[5,6]]]];               
toOne(a);  // Возвращает [0,1,2,3,4,5,6]
    Решение
    
function toOne(a)
{
  var result = [];
  for(var i=0; i<a.length; i++) 
    if (typeof a[i] == "object") result = result.concat(toOne(a[i]));
    else                         result.push(a[i]);
  return result;
}

    Комментарий

    Работает эта рекурсивная функция так.

    1. Создаётся пустой массив result.
    2. Затем просматриваются все элементы массива-аргумента.
      • Если очередной элемент имеет элементарный тип, он добавляется к result методом push.
      • Если элемент является массивом на него воздействует функция toOne, которая преобразует его к массиву из значений элементарного типа. Этот массив при помощи метода concat добавляется к result. Так как метод result.concat возвращает результат, не меняя исходный массив result, результат присваивается result.
    3. Когда цикл завершается, возвращается массив result.

    Пояснение

    Инструкция: 

    
var result = [];

    работает так. Где-то в памяти создается массив (пустой) и ссылка на него записывается в локальную переменную result.

    Слова «когда цикл завершается, возвращается массив result» означает следующее. Возвращается ссылка на массив, после чего локальная переменная result уничтожается. Заметьте, уничтожается не массив (который где-то в памяти, отдельно от функции), а локальная ссылка на него. Но если мы записываем x = toOne(a), то ссылка на созданный массив записывается в переменную x. Если мы вызываем toOne(a) без присваивания, ссылка пропадает. JavaScript обнаруживает, что на созданный массив нет ни одной ссылки, и запускает сборщик мусора.

    Можно записать функцию, использую только метод push: 

    
function toOne(a)
{
  var result = [];
  for(var i=0; i<a.length; i++) 
    if (typeof a[i] == "object") 
    {
      var t = toOne(a[i]);
      for(var j=0; j<t.length; j++) result.push(t[i]);
    }
    else result.push(a[i]);
  return result;
}

    Этот вариант менее красив. Что касается его эффективности, то вопрос открыт: требуются тестовые испытания с замером времени исполнения и анализом затрат памяти. Все зависит от эффективности реализаций методов concat и push, про которые мы ничего не знаем.

  4. Испытательный стенд Написать функцию-конструктор Matrix(n,M) для работы с квадратными матрицами размерностью nxn.

    Аргументы конструктора:
    n Количество строк (и столбцов) матрицы
    M Матрица, необязательный параметр, если отсутствует, создается матрица, заполненная нулями.
    Конструктор должен поддерживать три метода:
    sum Сумма матриц
    mul Произведение матриц
    toString Переопределить метод toString так, чтобы результирующая строка содержала элементы матрицы по строкам, и каждая строка завершалась бы символом "\n" — переводом строки.

    Определения

    Матрица размерностью mxn — это таблица, в которой m строк и n столбцов. В квадратной матрице m равно n, то есть число строк равно числу столбов.

    Пусть даны две квадратные матрицы A и B: 

    
    a11 a12 ... a1n 
A = ...
    an1 an2 ... ann

    b11 b12 ... b1n 
B = ...                                              
    bn1 bn2 ... bnn

    Матрица C 

    
    c11 c12 ... c1n    
C = ...                                                 
    cn1 cn2 ... cnn

    является суммой матриц A и B (C=A+B), если: cij = aij + bij для всех i и j от 1 до n.

    То есть каждый элемент суммы равен сумме аналогичных элементов.

    Пример
    
      11 12 13 
A   = 21 22 23
      31 32 33

      1100 1200 1300 
B   = 2100 2200 2300
      3100 3200 3300

      1111 1212 1313 
A+B = 2121 2222 2323
      3131 3232 3333

    Матрица С является произведением матриц A и B (C=A*B), если: 

    
        n
cij = сумма(aik*bkj) для всех i и j от 1 до n.
       k=1

    То есть каждый элемент cij равен сумме произведений элементов из i-ой строки матрицы A и j-го столбца матрицы B. Говорят, cij равно произведению i-ой строки матрицы A на j-ый столбец матрицы B.

    Пример
    
    11 12 13 
A = 21 22 23
    31 32 33

    1100 1200 1300 
B = 2100 2200 2300
    3100 3200 3300

Первая строка матрицы-произведения: 
c11 = 11*1100 + 12*2100 + 13*3100 = 77600 
c12 = 11*1200 + 12*2200 + 13*3200 = 81200
c12 = 11*1300 + 12*2300 + 13*3300 = 84800

Вторая строка матрицы-произведения: 
c21 = 21*1100 + 22*2100 + 23*3100 = 140600
c22 = 21*1200 + 22*2200 + 23*3200 = 147200
c23 = 21*1300 + 22*2300 + 23*3300 = 153800

Третья строка матрицы-произведения: 
c31 = 31*1100 + 32*2100 + 33*3100 = 203600
c32 = 31*1200 + 32*2200 + 33*3200 = 213200
c33 = 31*1300 + 32*2300 + 33*3300 = 222800


          77600  81200  84800 
С = A*B = 140600 147200 153800
          203600 213200 222800

    Пример использования конструктора

    
var m1 = new Matrix(3);
var m2 = new Matrix(3,
        [ 
          [11,12,13],
          [21,22,23],
          [31,32,33]
        ]
      );  
m1 = m1.sum(m2);
var m2 = new Matrix(3,
        [ 
          [1100,1200,1300],
          [2100,2200,2300],
          [3100,3200,3300]
        ]
      );  
var m4 = m1.sum(m2); 
alert(m4);  // Получили:
            //   1111, 1212, 1313 
            //   2121, 2222, 2323
            //   3131, 3232, 3333
            // (alert использует метод toString автоматически)
   
var m5 = m1.mul(m2); 
alert(m5);  // Получили:
            //   77600, 81200, 84800 
            //   140600, 147200, 153800
            //   203600, 213200, 222800
            // (alert использует метод toString автоматически)
    Решение
    
function Matrix(n,M)
{
  this.n = n;
  // Создаём матрицу
  this.M = new Array(n);
  // Инициализируем матрицу
  for (var i=0; i<n; i++)
  {
    this.M[i] = new Array(n);
    for (var j=0; j<n; j++) this.M[i][j] = M ? M[i][j] : 0;
  }
  // Сложение текущей матрицы с матрицей matr
  this.sum = function (matr)
  {
    var a = new Matrix(this.n);
    for (var i=0; i<this.n; i++)
      for (var j=0; j<this.n; j++) 
        a.M[i][j] = this.M[i][j] + matr.M[i][j];
    return a;    
  }
  // Умножение текущей матрицы на матрицу matr
  this.mul = function (matr)
  {
    var a = new Matrix(this.n);
    for (var i=0; i<this.n; i++)
      for (var j=0; j<this.n; j++)
      {
        var s = 0;
        for (var k=0; k<this.n; k++)
            s += this.M[i][k]*matr.M[k][j];
        a.M[i][j] = s;
      }
    return a;    
  }
  // Преобразование матрицы в строку
  this.toString = function ()
  {
    var str = "";
    for (var i=0; i<this.n; i++) str += this.M[i].join(", ") + "\n";
    return str;
  }
}

    Комментарий

    Создание и инициализация матрицы: 

    
01  // Создаём матрицу
02  this.M = new Array(n);
03  // Инициализируем матрицу
04  for (var i=0; i<n; i++)
05  {
06    this.M[i] = new Array(n);
07    for (var j=0; j<n; j++) this.M[i][j] = M ? M[i][j] : 0;
08  }

    В строке 02 в объекте (на который ссылается ключевое слово this) будет создано свойство М в виде массива из n элементов (строки будущей матрицы).

    В строке 06 каждому элементу с номером i созданного массива присваивается массив из n элементов.

    В строке 07 каждый элемент созданного массива инициализируется соответствующим элементом второго аргумента, а если его нет — нулем.

    Сложение текущей матрицы с матрицей matr: 

    
01  this.sum = function (matr)
02  {
03    var a = new Matrix(this.n);
04    for (var i=0; i<this.n; i++)
05      for (var j=0; j<this.n; j++) 
06        a.M[i][j] = this.M[i][j] + matr.M[i][j];
07    return a;    
08  }

    В строке 03 создаётся объект Matrix — нулевая квадратная матрица c размером, равным размеру текущей матрицы. Для построения этого объекта применяется создаваемый конструктор, но никакой рекурсии не возникает. Смотрите комментарии к решению задания 5 из 4 заметки (про комплексные числа). (Суть: методы будут вызываться уже после того, как будет создан экземпляр объекта.)

    Теперь остается только заполнить построенную нулевую матрицу элементами, каждый из которых равен соответствующей сумме элементов (текущей матрицы и матрицы, выступающей в качестве аргумента метода).

    В строке 07 ссылка на построенную матрицу (равная сумме матриц) возвращается в качестве результата выполнения метода.

    Можно было, конечно, этот метод записать и по-другому: 

    
01  this.sum = function (matr)
02  {
03    var a = new Matrix(this.n, this.M);
04    for (var i=0; i<this.n; i++)
05      for (var j=0; j<this.n; j++) 
06        a.M[i][j] += matr.M[i][j];
07    return a;    
08  }

    Умножение текущей матрицы на матрицу matr выполняется аналогично сложению (не считая более сложной математики).

    Преобразование матрицы в строку — прозрачно. Символ "\n" задает переход на новую строку при выводе на экран.

  5. Испытательный стенд Написать функцию-конструктор и создать с ее помощью объект Plusik, который реализует Роботландского исполнителя Плюсик.

    Плюсик — это модель стекового калькулятора. Стек служит для хранения чисел. Числа помещаются в стек по одному, подобно тому, как кольца детской пирамидки нанизываются на стержень. За один раз взять из стека можно только одно число с вершины числовой пирамиды. Копия числа в стеке не сохраняется, зато становится доступным следующее число, расположенное «ниже» взятого.

    Cистема команд Плюсика:
    команда сокращенная форма описание
    запомни число з число Число, записанное в команде отправляется на хранение в стек.
    очисть о Из стека удаляются все элементы.
    сложи
    вычти
    умножь
    дели    		 с
    в
    у
    д    		 Все эти команды работают одинаково: из стека извлекаются два числа и над ними выполняется операция. Результат помещается в стек. Второе число, извлеченное из стека, вычислитель считает первым операндом операции.

    Ситуация отказа возникает когда:

    • в стеке меньше двух чисел;
    • выполняется деление на ноль.

    Класс Plusik должен иметь следующий интерфейс:

    • метод make, который получает в качестве аргумента команду Плюсика (в виде строки), выполняет ее и возвращает код ошибки:
      • 0 — ошибок нет
      • 1 — ошибка в записи команды («не понял»)
      • 2 — ошибка при выполнении команды («не могу»)
    • метод get, который возвращает число с верхушки стека

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

    Пользователь может вводить команды в любом регистре с любым числом пробелов перед командой, после нее и перед числом в команде запомни.

    Примеры работы с Плюсиком

    1) Вычислить: 12*5 

    
var p = new Plusik(); // Создали Плюсика
p.make("Запомни 12"); // Записали в стек 12, вернули 0 
p.make("Запомни 5");  // Записали в стек 5, вернули 0 
p.make("у");          // Выполнили умножение, вернули 0 
p.get();              // Вернули 60

    2) Вычислить: 100-(20+10) 

    
var p = new Plusik();     // Создали Плюсика
p.make("  З    100    "); // Записали в стек 100, вернули 0 
p.make(" з   20");        // Записали в стек 20, вернули 0 
p.make("з 10");           // Записали в стек 10, вернули 0 
p.make("Сложи");          // Сложили 20 и 10, вернули 0 
p.make("Вычти");          // Выполнили вычитание, вернули 0 
p.get();                  // Вернули 70

    3) Аварийные сообщения 

    
var p = new Plusik();   // Создали Плюсика
p.make("Сохрани 100");  // Вернули 1 ("не понял")
p.make("запомни");      // Вернули 2 ("не могу")
p.make("запомни 1");    // Записали в стек 1, вернули 0 
p.make("сложи");        // Вернули 2 ("не могу") 
p.make("запомни 0");    // Записали в стек 0, вернули 0 
p.make("дели");         // Вернули 2 ("не могу")
    Решение
    
function Plusik()
{
  this.stack = []; // Стек Плюсика

  // Вернуть число с верхушки стека
  this.get = function () 
    {
      return this.stack.length ? this.stack[this.stack.length-1] : "";
    };

  // СКИ Плюсика: команды и функции, которые выполняют эти команды  
  // this.op[i][0] -- i-ая команда Плюсика в виде строки
  // this.op[i][1] -- функция, выполняющая i-ую команду Плюсика 
  this.op = [
              [
                "запомни", 
                function (stack, x) 
                {
                  if (isNaN(-x)) return 1; // x -- не число
                  stack.push(x); 
                  return 0;
                }
              ], 
              [
                "сложи",   
                function (stack) 
                {
                  if (stack.length < 2)  return 2; // "не могу"
                  var op2 = stack.pop();
                  stack.push((stack.pop()-0)+(op2-0));
                  return 0;
                }
              ],
              [
                "вычти",  
                function (stack) 
                {
                  if (stack.length < 2)  return 2; // "не могу"
                  var op2 = stack.pop();
                  stack.push(stack.pop()-op2);
                  return 0;
                }
              ],
              [
                "умножь",  
                function (stack) 
                {
                  if (stack.length < 2)  return 2; // "не могу"
                  var op2 = stack.pop();
                  stack.push(stack.pop()*op2);
                  return 0;
                }
              ], 
              [
                "дели",
                function (stack) 
                {
                  if (stack.length < 2)  return 2; // "не могу"
                  var op2 = stack.pop();
                  if (!(-op2)) return 2; // "не могу"
                  stack.push(stack.pop()/op2);
                  return 0;
                }
              ], 
              [
                "очисти",
                function (stack) 
                {
                  stack.length = 0;
                  return 0;
                }
              ]
            ];

  // Выполнение команды, заданной строкой str 
  this.make = function (str)
    {
       // Удалим незначащие пробелы (в начале и конце строки)
       str = str.replace(/(^\s*)|(\s*$)/g,""); 
       // Выделим лексемы (их может быть две или одна)
       var lex = str.split(/\s+/); 
       // Переведем команду (это первая лексема) в нижний регистр 
       lex[0] = lex[0].toLowerCase();
       // Определим команду 
       for(var i=0; i<this.op.length; i++)
         if (this.op[i][0] == lex[0] ||
             this.op[i][0].charAt(0) == lex[0]) break;
       // Если команда не найдена, возвращаем 1 ("не понял")
       if (i>=this.op.length) return 1;
       // Выполним команду
       return this.op[i][1](this.stack,lex[1]);
     }   
}
var p = new Plusik();
p.make("Запомни 10");
p.make("Запомни 20");
p.make("сложи");
alert(p.get());  // 30
...

    Комментарий

    Построенное выше решение нельзя назвать коротким, но оно предельно простое в силу своей структурности:

    1. Заводим стек для Плюсика: 
      
this.stack = []; // Стек Плюсика
    2. Определяем СКИ Плюсика, то есть задаем команды и функции, которые эти команды выполняют 
      
this.op = [ ... ];
    3. Записываем метод 
      
this.make = function (str) {...};
      который принимает строку с командой Плюсика и передает ее на выполнение нужной функции из СКИ.

    Обратите внимание, в каждой функции, выполняющей команду из СКИ Плюсика, первым аргументом записан параметр stack. Например, так выглядит функция выполняющая команду запомни x: 

    
function (stack, x) 
{
  if (isNaN(-x)) return 1; // x -- не число
  stack.push(x); 
  return 0;
}

    Зачем этот аргумент? Ведь стек Плюсика доступен, как this.stack, и проще было бы записать функцию без первого аргумента: 

    
function (x) 
{
  if (isNaN(-x)) return 1; // x -- не число
  this.stack.push(x); 
  return 0;
}

    Увы, это работать не будет. Ибо ключевое слово this относится к объекту, в контексте которого будет работать функция. И этим объектом будет не объект Plusik, а массив this.op (массив тоже объект). Мы будем вызывать функцию как this.op[i][1](...), то есть контекстом ее выполнения будет массив this.op. Вот почему стек Плюсика явно передается в функцию в качестве первого аргумента: this.op[i][1](this.stack,lex[1])

    Вспомним определение из заметки 4:

    Объект, посредством которого вызывается метод, становится значением ключевого слова this.

    И вот еще один уместный по данному поводу фрагмент из заметки 4.

    Пусть задано следующее определение функции: 

    
function sq() {return this.x*this.y;}

    и два объекта: 

    
var rect = { x:10, y:20, square:sq };
var cube = { x:2, y:3, z:16, square:sq };

    Тогда: 

    
rect.square()  // Равно 200
               // Вызывается функция sq(), в ней this ссылается 
               // на объект rect  

cube.square()  // Равно 6
               // Вызывается функция sq(), в ней this ссылается 
               // на объект cube

    Ничего не изменится, если функцию sq() задать в виде литерала внутри первого объекта. При вызове в контексте второго объекта this внутри этой функции будет ссылаться не на первый, а на второй объект, в контексте которого выполняется вызов: 

    
var rect = { x:10, y:20, square:function () {return this.x*this.y;} };
var cube = { x:2, y:3, z:16, square:rect.square };
   
rect.square()  // Равно 200
               // Здесь this относится к rect
cube.square()  // Равно 6
               // Здесь this относится к cube, хотя функция 
               // определена в rect

    Видим, насколько JavaScript является контекстно-зависимым языком. В других объектно-ориентированных языках методы жёстко привязаны к объектам, внутри которых они заданы, и не могут работать с другими объектами.

    На самом деле, можно было поступить по-другому. Можно было обойтись без передачи аргумента stack: 

    
this.op = [
            [
              "запомни", 
              function (x) 
              {
                if (isNaN(-x)) return 1; // x -- не число
                this.stack.push(x); 
                return 0;
              }
            ], 
...

    если при вызове методов явно указывать объект вызова: 

    
return this.op[i][1].call(this, lex[1]);

    О методе call читайте в заметке 7.

    Формат обращения к методу call:

    функция.call(объект, список_фактических_аргументов);

    Метод call позволяет выполнить функцию в контексте какого либо объекта, и тогда ключевое слово this внутри функции будет относиться к этому объекту.

    Пример
    
var ob1 = {x:1,y:2};
var ob2 = {x:10,y:20};
function f(t) {return t*(this.x+this.y);}
sum.call(ob1,2); // Равно 6
sum.call(ob2,2); // Равно 60