Алгоритмы - это основа компьютерного программирования. Алгоритмы созданы для обработки определенных структур данных с диапазоном допустимых параметров. крайний случай - это проблема или ситуация, которая возникает только при экстремальном (максимальном или минимальном) рабочем параметре. Как программисты, как мы можем предсказать эти случаи, чтобы защитить наше приложение от взлома?
Я продемонстрирую некоторые общие граничные случаи в базовом алгоритме пузырьковой сортировки:
// bubbleSort.jsfunction bubbleSort(array) { var swapped; do { swapped = false; for(var i = 0; i < array.length; i++) { if(array[i] > array[i + 1]) { swap(array, i, i + 1); swapped = true; } } } while(swapped); return array; }function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; }
1. Принятая структура данных
Первый серьезный крайний случай - это непринятая структура данных. Мой алгоритм пузырьковой сортировки работает предсказуемо только для массивов. Javascript не помешает вам вводить в функцию другие структуры данных, такие как обычные объекты. Например, что произойдет, если я введу этот объект:
var obj = {0: 0,
1: 1,
2: 2,
3: 3}
Это приведет к очень странным вещам внутри цикла for, но в конечном итоге наш алгоритм вернет исходный объект.
--> obj
Возможно, это не то, что мы хотим! Если алгоритм будет действительно защищенным от дурака, мы должны проверить, что наша структура данных является массивом, и как-то с этим справиться. Здесь я верну false, чтобы мы могли обрабатывать нежелательные структуры данных как ошибку в нашей программе:
if (!Array.isArray(arr)) {
return false
}
Это также вернет false для ложных значений, таких как null или undefined.
2. Пустота
Пустой массив не нарушит этот конкретный алгоритм сортировки, но пустые значения - это то, на что нужно обратить внимание:
bubbleSort([]) --> []
В контексте многих программ мы хотим обрабатывать пустой массив по-другому, чтобы он не сломал что-то в нашей программе ниже по строке:
if (!arr[0]) {
return false
}
or
if (arr.length === 0) {
return false
}
Для алгоритмов, которые принимают разные структуры и типы данных, мы также должны обращать внимание на пустоту. Вот несколько распространенных:
var str = ''
var obj = {}
var arr = []
var num = 0
Если наш алгоритм проходит через вложенные структуры данных, мы также можем захотеть проверить вложенную пустоту следующим образом:
[[],[],[],[[]],[[[]]]]
3. Допустимые типы
Следующим важным случаем для проверки являются допустимые типы внутри нашего массива. Наш алгоритм пузырьковой сортировки сортирует строки на основе их значений Unicode. Это означает, что заглавные буквы будут стоять перед строчными:
bubbleSort([a,A,b,B]) ---> [A,B,a,b]
Если мы хотим, чтобы алгоритм сортировал строки независимо от заглавных букв, мы можем обработать это:
if (arr[j-1].toLowerCase > arr[j].toLowerCase) {
var temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
Другой случай, который вы можете захотеть обработать, - это строковые числа против обычных числовых значений. Вот один странный пример этого:
2 > '2' ---> false 2 < '2' ---> false 2 === '2' ---> false 2 == '2' ---> true
В случае двух равных чисел, где одно является строкой, единственный оператор, который принимает значение «истина», - это ==. Еще сложнее, если в числовой строке есть буква.
1 > '1a' ---> false 1 < '1a' ---> false 1 === '1a' ---> false 1 == '1a' ---> false 2 > '1a' ---> false 2 < '1a' ---> false
Это может привести к некоторым странным результатам в нашем алгоритме сортировки. Следовательно, мы можем захотеть принимать только числа, а не строки, или обрабатывать разные типы отдельно.
Другой тип, о котором следует помнить, - это логическое значение. true примерно равно 1, а false примерно равно 0.
true == 1 ---> true false == 0 ---> true true > false ---> true true < 2 ---> true true < 'a' ---> false false < 'a' ---> false
Возможно, мы не захотим разрешать логические значения в нашем алгоритме, особенно если мы сортируем массив строк. Сюда входят ложные значения, такие как null, undefined и NaN, которые будут вести себя странно при передаче в оператор сравнения.
Все ложные типы данных действуют по-разному в операторах сравнения:
null < 0.0000000001 ---> true null >= 0 ---> true null > 0 ---> false null == 0 ---> false null === null ---> true null == undefined ---> true undefined < 2 ---> false undefined > 0 ---> false undefined == 1 --> false undefined === undefined ---> true NaN == undefined ---> false NaN === NaN ---> false NaN >= 0 ---> false NaN <= 2 ---> false NaN == null ---> false
Вы можете исключить их из своего алгоритма сортировки. null, пожалуй, самый странный, где он приближается к нулю, но не равен 0 и не больше 0, но == может быть принудительно приведен к значению undefined.
К счастью, в Javascript есть способ принудительно сделать ложные типы данных равными друг другу и ложными. Просто добавьте двойной восклицательный знак к любому из них.
!!null == 0 ---> true !!undefined == 0 ---> true !!NaN == 0 --> true
Это связано с алгоритмами принуждения в Javascript и тем, как различные ложные значения хранятся в памяти. Подробнее об этом здесь: http://www.ecma-international.org/ecma-262/5.1/#sec-11.9.3. и здесь: http://www.ecma-international.org/ecma-262/5.1/#sec-11.8.5
4. Большие ценности
В нашем случае мы должны искать очень большие массивы. Что произойдет, если нашей функции будет передан массив длиной более 1 x 10¹⁰⁰?
Вот здесь-то и пригодится нотация Big O.
Сложность Big O
Сложность Big O - это показатель эффективности алгоритма. Когда мы имеем дело с большими наборами данных, это имеет большое значение. Big O имеет две переменные - время и объем памяти. Память важна, потому что это может нарушить наш алгоритм, если в качестве параметров передаются большие объемы данных. Каждая компьютерная программа хранит данные в стеке и куче. Доступ к стековой памяти осуществляется намного быстрее, но ее меньше. Как это связано с алгоритмами?
Давайте ответим на это двумя версиями пузырьковой сортировки, рекурсивной и итеративной:
// bubbleSort.jsfunction swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; }/// Bubble Sort using for loopsfunction bubbleSort(array) { var swapped; do { swapped = false; for(var i = 0; i < array.length; i++) { if(array[i] > array[i + 1]) { swap(array, i, i + 1); swapped = true; } } } while(swapped); return array; }// Bubble sort using recursion var swapped = true function recursiveSwapping(arr, i = 0) { var len = arr.length; if (i >= len) { return arr } if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); swapped = true } return recursiveSwapping(arr, i + 1) } function recursiveBubbleSort(arr) { if (!swapped) { return arr } swapped = false recursiveSwapping(arr, i = 0) return recursiveBubbleSort(arr) }
В этих двух примерах используется один и тот же точный алгоритм, но память обрабатывается по-разному. Рекурсивная версия алгоритма использует стековую память и, следовательно, будет прервана с ошибкой переполнения стека, если длина массива очень велика. Это связано с тем, что стек отслеживает каждый вызов recursiveSwapping, пока не разрешится исходный вызов. Итеративная версия функции не сталкивается с проблемами переполнения стека.
Теоретически рекурсивная версия также не должна иметь проблем с памятью. Многие языки нижнего уровня допускают так называемую оптимизацию хвостового вызова, которая позволяет писать рекурсивные функции со сложностью памяти 0 (1). До недавнего времени JS не допускал оптимизацию хвостовых вызовов, но в ECMAScript 6 вы можете включить ее в строгом режиме. Просто введите 'use strict’ в верхней части файла, и вы сможете писать рекурсивно, не сталкиваясь с ошибками переполнения стека.
'use strict'
Просто убедитесь, что ваши рекурсивные вызовы функций написаны в последней строке или хвосте вашей функции, как в функции ниже.
function recursiveSwapping(arr, i = 0) {
var len = arr.length;
if (i >= len) {
return arr
}
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
swapped = true
}
// tail call below
return recursiveSwapping(arr, i + 1)
}
5. Некоторые другие крайние случаи, о которых следует помнить.
- Нечетный / четный - числа и длина строки
- Отрицательные числа
- Специальные символы
- Повторяющиеся элементы
- Длина 1
- Длинная строка или большое число
- Нулевые или ложные значения
