02.11.2009

Результаты домашки №1

Ну что же, давайте подведем итоги первой домашки :)

Задача 1

Эта задача вызвала некоторые затруднения почти у всех принявших участие. Я заметил несколько типичных проблем:

1. Велосипедизм. Как верно заметил nop, задача сводится к классической задаче поиска подстроки в строке. Многие это почувствовали, однако поленились погуглить и решили изобрести свой велосипед. Существует огромное количество алгоритмов поиска подстроки, самый простейший (brute force algorithm) можно закодить так:

var subArrayIndex = function(haystack, needle) {
   var i, j;
   var m = haystack.length;
   var n = needle.length;

   for (i = 0; i <= m - n; i += 1) {
      for (j = 0; j < n && needle[j] === haystack[i + j]; j += 1);
      if (j >= n) {
          return i;
      }
   }

   return -1;
};

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

3. Сравнение с приведением типов. Практически все для сравнения элементов массивов использовали == и !=. Ребята, если вы еще не знаете, знайте: в яваскрипте == и != делает приведение типов. Это означает, например, что 1 == '1' выдаст true. Для сравнения без приведения типов используйте === и !==.

Задача 2

Вторая задача была на замыкание и проблем не вызвала. Просто приведу свое решение:

var toArrayOfFunctions = function(array) {
    var makeFunction = function(item) {
        return function() {
            return item;
        };
    };
    var i;
    var len = array.length;
    var functions = [];
    for (i = 0; i < len; i += 1) {
        functions[i] = makeFunction(array[i]);
    }
    return functions;
};

UPD: В одном из решений второй задачи заметил еще проблему, которую назовем «порча входных данных». Нужно помнить, что объекты (массивы в том числе) передаются по ссылке, а не по значению. Если в функции вы делаете какие-то хирургические операции с принятым в аргументах объектом, то вы меняете непосредственно переданный объект.

Пример:

var add1 = function(array) {
    for (var i = 0; i < array.length; i += 1) {
        // Трах-бабах-хуяк - портим переданный массив
        array[i] = array[i] + 1;
    }
    return array;
};

var a = [1, 2, 3];
var b = add1(a); // a и b теперь один и тот же массив [2, 3, 4]

4 комментария:

ikokostya комментирует...

Степан, а как вам решение 2 задачи от Aishek с new Function('return ' + array[currentIndex] + ';'); ?

Aishek комментирует...

Раньше меня такой метод для задачи 2 предложил nop.

А по первой задаче надо было написать конечный автомат.

Степан Резников комментирует...

Использовать new Function() плохо по тем же причинам, что и eval().

Главная беда - очень медленно. Я проверил оба решения на массиве с 1000 элементами. Метод использующий замыкания отработал за 3ms, метод использующий new Function() - за 115ms. (Замерял в FF3.)

Eval is evil :)

ikokostya комментирует...
Этот комментарий был удален автором.