Недавно читал топип о красоте кода. В комментариях, набрала популярность тема переноса скобочек при записи условного оператора. В одном из вариантов пример из статьи выглядел так:
Не надейтесь увидеть тут картины Рембранта мира программирования. Код в статье — произведение Дали. Впрочем, как и сама статья.
Итак, вот как может выглядеть развернутое условие (напишу в своем стиле и сразу в Совершенной дизъюнктивной нормальной форме(СДНФ)):
Получилось как-то длинно. Видим, что тут больше подходит совершенная конъюнктивная нормальная форма(СКНФ):
Пусть «а» может иметь типы 'undefined', 'object', 'boolean', 'number', 'string', 'function', но нам важно поведение только при 'object', 'string', 'number', поведение при других типах аналогично поведению при 'undefined'.
Пусть для «b» все будет аналогично.
Тип «с» — учитываем только 'string' и 'undefined'.
Итого, количество вариантов = 4*4*2, каждый из которых соответствует одной элементарной конъюнкции в СДНФ, но теперь мы можем их различать и менять поведение для каждого конкретного случая.
Итак, первый принцип индекс-ориентированного программирования: охват всех вариантов.
Естественно условия могут быть любыми. Зачем ограничиваться одним условным оператором, когда есть другие ему подобные.
Второй принцип индекс-ориентированного программирования: наличие особого нулевого варианта.
Однако, идея индекс-ориентированного программирования несколько шире, чем замена условных операторов. Еще пара примеров.
Третий принцип индекс-ориентированного программирования: нумерация вариантов.
И, наконец, четвертый принцип индекс-ориентированного программирования: алгоритмы сложности О(1).
Преимущества:
объект Number
перестановка
числа Фибоначчи
вычислительная сложность
Steve McConnell. Code Complete, Second Edition. Глава 18: Табличные методы
if (typeof a ! == "undefined"
&& typeof b ! == "undefined"
&& typeof c === "string")
{
call_function(a, b, c);
// ...
}
Не надейтесь увидеть тут картины Рембранта мира программирования. Код в статье — произведение Дали. Впрочем, как и сама статья.
Итак, вот как может выглядеть развернутое условие (напишу в своем стиле и сразу в Совершенной дизъюнктивной нормальной форме(СДНФ)):
if(false
||(true
&&typeof a === "string"
&&typeof b === "string"
&&typeof с === "string"
)||(true
&&typeof a === "object"
&&typeof b === "string"
&&typeof с === "string"
)||(true
&&typeof a === "number"
&&typeof b === "string"
&&typeof с === "string"
)||(true
&&typeof a === "string"
&&typeof b === "object"
&&typeof с === "string"
)||(true
&&typeof a === "object"
&&typeof b === "object"
&&typeof с === "string"
)||(true
&&typeof a === "number"
&&typeof b === "object"
&&typeof с === "string"
)||(true
&&typeof a === "string"
&&typeof b === "number"
&&typeof с === "string"
)||(true
&&typeof a === "object"
&&typeof b === "number"
&&typeof с === "string"
)||(true
&&typeof a === "number"
&&typeof b === "number"
&&typeof с === "string"
)
){
call_function(a, b, c);
// ...
}
Получилось как-то длинно. Видим, что тут больше подходит совершенная конъюнктивная нормальная форма(СКНФ):
if(true
&&(false
||typeof a === "string"
||typeof a === "number"
||typeof a === "object"
)&&(false
||typeof b === "string"
||typeof b === "number"
||typeof b === "object"
)&&(false
||typeof c === "string"
)
){
call_function(a, b, c);
// ...
}
Пусть «а» может иметь типы 'undefined', 'object', 'boolean', 'number', 'string', 'function', но нам важно поведение только при 'object', 'string', 'number', поведение при других типах аналогично поведению при 'undefined'.
Пусть для «b» все будет аналогично.
Тип «с» — учитываем только 'string' и 'undefined'.
Итого, количество вариантов = 4*4*2, каждый из которых соответствует одной элементарной конъюнкции в СДНФ, но теперь мы можем их различать и менять поведение для каждого конкретного случая.
Аналог условного оператора:
//тут у нас есть переменные "a", "b", "c"
//нужно выполнить определенные действия
//в зависимости от их типов
var a_type_index = {'undefined':0, 'object':1, 'boolean':0, 'number':2, 'string':3, 'function':0}[typeof a]
var b_type_index = {'undefined':0, 'object':1, 'boolean':0, 'number':2, 'string':3, 'function':0}[typeof b]
var c_type_index = {'undefined':0, 'object':0, 'boolean':0, 'number':0, 'string':1, 'function':0}[typeof c]
var index = a_type_index + b_type_index*4 + c_type_index*4*4
В демонстрационных целях, решил не усложнять код...
Все, что теперь осталось — выбрать по индексу, что делать:но потом передумал и решил, что универсальное решение — более красивое. Думаю, многим удобно думать в числах:
//тут у нас есть переменные "a", "b", "c"
//нужно выполнить определенные действия
//в зависимости от их типов
var types = ['undefined', 'object', 'boolean', 'number', 'string', 'function']
var a_type_index = types.indexOf(typeof a)
//уменьшаем количество различаемых типов
a_type_index = +'010230'[a_type_index]
var b_type_index = types.indexOf(typeof b)
b_type_index = +'010230'[b_type_index]
var c_type_index = types.indexOf(typeof c)
c_type_index = +'000010'[c_type_index]
var index = a_type_index + b_type_index*4 + c_type_index*4*4
;[
//c has incorrect type
//b has incorrect type
//types a: incorrect, object, number, string
show_err_all, show_err_bc, show_err_bc, show_err_bc,
//b has object type
//types a: incorrect, object, number, string
show_err_ac, show_err_c, show_err_c, show_err_c,
//b has number type
//types a: incorrect, object, number, string
show_err_ac, show_err_c, show_err_c, show_err_c,
//b has string type
//types a: incorrect, object, number, string
show_err_ac, show_err_c, show_err_c, show_err_c,
//c has string type
//b has incorrect type
//types a: incorrect, object, number, string
show_err_ab, show_err_b, show_err_b, show_err_b,
//b has object type
//types a: incorrect, object, number, string
show_err_a, process, process, process, process,
//b has number type
//types a: incorrect, object, number, string
show_err_a, process, process, process, process,
//b has string type
//types a: incorrect, object, number, string
show_err_a, process, process, process, process
][index](a, b, c)
Итак, первый принцип индекс-ориентированного программирования: охват всех вариантов.
Естественно условия могут быть любыми. Зачем ограничиваться одним условным оператором, когда есть другие ему подобные.
Аналог тернарного оператора:
var b_status = false
//с использованием тернарного оператора
var str_status = b_status? 'ok': 'this is false'
//с использованием индексов
var str_status = ['this is false','ok'][+b_status]
Аналог оператора множественного выбора:
var i_state = 1
//с использованием switch
switch (i_state) {
case 1:
console.log('you select 1')
break
case 2:
console.log('you select 2')
break
default:
console.log('you select another')
}
//с использованием индексов
i_state = 0|[0,1,2][i_state]
//если нужно получить числовой индекс по строке
//i_state = 0|{'one':1, 'two':2}[str_state]
//i_state = ['one', 'two'].indexOf(str_state)+1
[
function(){
//default
console.log('you select another')
},function(){
//i_state == 1
console.log('you select 1')
},function(){
//i_state == 2
console.log('you select 2')
}
][i_state]
Второй принцип индекс-ориентированного программирования: наличие особого нулевого варианта.
Однако, идея индекс-ориентированного программирования несколько шире, чем замена условных операторов. Еще пара примеров.
Генерации перестановок из индекса:
function factorial(n){
if(n<=1) return 1;
var ret = 1;
for(var i=2; i<=n; i++) ret *= i;
return ret;
}
function i_to_insert_order(n, i){
var arr = []
var i_tmp = i
for(var j=0; j<n; j++){
var a = i_tmp%(j+1)
arr[j] = a
i_tmp = ~~(i_tmp/(j+1))
}
return arr
}
function correct(arr){
var n = arr.length;
for(var i=1; i<n; i++){
// for(var j=0; j<i; j++){
for(var j=i-1; j>=0; j--){
//if(arr[j]>=arr[i]) arr[j]++
arr[j] += arr[j]>=arr[i]
}
}
}
//correct([0,0,0,0,0]) == [4,3,2,1,0]
var n = 5
var arr_perm = []
for(var i=0; i<factorial(n); i++){
var arr = i_to_insert_order(n, i)
//arr = 0, 0..1, 0..2, 0..3, 0..4
correct(arr)
arr_perm.push(arr)
}
arr_perm.reverse()
//arr_perm.length == factorial(n)
//arr_perm[0] == [0,1,2,3,4]
//arr_perm[-1] == [4,3,2,1,0]
function insert(arr, i, elem){arr.splice(i, 0, elem)}
//исходное множество
var elements = ['word', 'symbol', 'face', 'colors', 'song']
//получаем 35-ю последовательность вставки
var order = i_to_insert_order(5, 35)
var arr = []
for(var i=0; i<order.length; i++) insert(arr, order[i], elements[i])
//arr == ['word', 'song', 'colors', 'symbol', 'face']
Третий принцип индекс-ориентированного программирования: нумерация вариантов.
Генерация числа Фибоначчи по номеру:
Воспользуемся сокращенной формулой Бине. Затем, сравним результат с табличным. const ? = (1+Math.sqrt(5))/2
function fib_by_index(i){
return Math.round(Math.pow(?, i)/Math.pow(5,0.5))
}
fib_by_index(6) == 8
fib_by_index(50) == 12586269025
И, наконец, четвертый принцип индекс-ориентированного программирования: алгоритмы сложности О(1).
Преимущества:
- быстродействие(при большом числе условий)
- устойчивость к атакам по времени
- повышенный расход памяти
- нужно вычислять все условия для индекса
объект Number
перестановка
числа Фибоначчи
вычислительная сложность
Steve McConnell. Code Complete, Second Edition. Глава 18: Табличные методы
Комментарии (14)
stychos
07.11.2015 03:19Очень понравился пример со switch.
Также к плюсам данного подхода можно отнести большую скорость при большом числе условий.
А не может ли оказаться, что взятие элемента массива по индексу и предшествующая арифметика (для больших условий) не выигрывают по скорости? Ну и для массива решений нужна дополнительная память.
dtestyk
07.11.2015 07:46Про память — сейчас добавлю.
Взятие по индексу — точно быстрее, чем последовательный перебор 'else if'-ами. Cомнение вызывает indexOf, но можно обойтись без него и, он как минимум пропорционален числу условий, а может и быстрее. Поиск в хеш-мапе приблизительно O(1), за исключением коллизий, — тут зависит от реализации. Хотя, была ситуация: поиск по длинным строкам в качестве ключа жутко тормозил, пришлось сначала искать по числовому хешу от строки(вычисление которого, впрочем, также вписывается в этот подход). Что касается вычислений, то возведение в целую степень также может быть линейным, но такие алгоритмы врядли еще где остались. Однако, завершения вычисления 50-го число фибоначчи рекурсивным алгоритмом не дождался(отчасти поэтому не включил код в статью), а для индексного результат был без задержки. По-хорошему, конечно, надо бы сделать замеры скорости, но для простых формул — это не актуально. Итого, ответ — возможно, но только для неоптимизированных вариантов: как вы правильно заметили, расходуется дополнительная память, — мы преобразуем временную сложность в пространственную.stychos
07.11.2015 07:48Спасибо за науку! (задавая вопрос, как раз про indexOf и думал — но я не представляю, как он реализован)
VolCh
08.11.2015 22:14Время от времени применяю на практике уже лет 25 (правда, не знал как это называется), но обычно только в случаях хорошо ложащихся на классические массивы, когда разворачивание в условные операторы реально является тупой копипастой, когда условия N-го уровня повторяются каждом N-1 уровне, да ещё являются четко дискретными.
bakhirev
09.11.2015 01:04+2var type = typeof a + typeof b + typeof c, callback = { "objectobjectstring": process, "objectobjectundefined": process, "objectstringstring": process, "objectstringundefined": process, "objectnumberstring": process, "objectnumberundefined": process, "stringobjectstring": process, "stringobjectundefined": process, "stringstringstring": process, "stringstringundefined": process, "stringnumberstring": process, "stringnumberundefined": process, "numberobjectstring": process, "numberobjectundefined": process, "numberstringstring": process, "numberstringundefined": process, "numbernumberstring": process, "numbernumberundefined": process }[type] || process; callback && callback(a, b, c);bakhirev
09.11.2015 01:20+1var type = typeof a + typeof b + typeof c; ({ "objectobjectstring": process, "objectobjectundefined": process, "objectstringstring": process, "objectstringundefined": process, "objectnumberstring": process, "objectnumberundefined": process, "stringobjectstring": process, "stringobjectundefined": process, "stringstringstring": process, "stringstringundefined": process, "stringnumberstring": process, "stringnumberundefined": process, "numberobjectstring": process, "numberobjectundefined": process, "numberstringstring": process, "numberstringundefined": process, "numbernumberstring": process, "numbernumberundefined": process }[type] || process)(a, b, c);bakhirev
09.11.2015 01:53+2var type = (typeof a)[0] + (typeof b)[0] + (typeof c)[0]; ({ "oos": process, "oou": process, "oss": process, "osu": process, "ons": process, "onu": process, "sos": process, "sou": process, "sss": process, "ssu": process, "sns": process, "snu": process, "nos": process, "nou": process, "nss": process, "nsu": process, "nns": process, "nnu": process }[type] || process)(a, b, c);dtestyk
09.11.2015 02:18+2Решил сравнить скорости: jsperf.com/ibp-array-vs-object-index, результат не показателен.
Ваш вариант, мне нравится даже больше :)
dtestyk
09.11.2015 02:13Обычно составные ключи разделяю подчеркиванием:
var type = typeof a + '_' + typeof b + '_' + typeof c, callback = { "object_object_string": process, "object_object_undefined": process, ...
Scf
На мой взгляд, переусложнено, но это может быть из-за ограничений языка. Я недостаточно знаю JS, так что напишу свой вариант на псевдокоде:
val valid_a = ['object', 'string', 'number']
val valid_b = valid_a
val valid_c = ['string', 'undefined']
//список всех возможных валидных троек для параметров
val tuples = decartMultiplication(valid_a, valid_b, valid_c, (a, b, c) -> Tuple3(a, b, c))
val dispatchMap = Map<Tuple3, Closure>
tuples.forEach(tuple -> dispatchMap.put(tuple, (a, b, c) -> call_function(a, b, c))
//usage
val dispatcher = dispatchMap.get(Tuple3(a.type, b.type, c.type))
if (dispatcher != null) dispatcher(a, b, c) else call_badargs(a, b, c)
Вкратце, делаем ассоциативный массив [множество типов аргументов] -> лямбда
Плюсы — мало букв. Минусы — кол-во элементов в мапе растет весьма быстро.
dtestyk
тут была одна особенность, если аргумент не определен, то это вызывает синтаксическую ошибку при попытке передать его в функцию, но typeof определяет его тип:
dtestyk
не синтаксическую, описался