Index-based programming или зачем нам все эти if, switch, тернарный оператор?

    Недавно читал топип о красоте кода. В комментариях, набрала популярность тема переноса скобочек при записи условного оператора. В одном из вариантов пример из статьи выглядел так:
    if (typeof a ! == "undefined"
    && typeof b ! == "undefined"
    && typeof c === "string")
    { 
        call_function(a, b, c);
        // ...
    }
    
    Задумался над самими условиями: они немного странные, хотя и часто встречаются. Внутри «call_function» будет проверяться тип «a» и тип «b», но не тип «с». С другой стороны, количество поддерживаемых сочетаний типов «a» и «b», поддерживаемых функцией конечно, и, скорее всего, фиксировано, а, значит, было бы полезно эти сочетания увидеть. А этот пост натолкнул на мысль, что можно вообще обойтись без условных операторов. Так и зародилась идея отказаться от условных операторов в пользу индексов. Несмотря на то, подход рассматривается в рамках Javascript, он с успехом может быть применен во многих других языках после учета их синтаксических особенностей.

    Не надейтесь увидеть тут картины Рембранта мира программирования. Код в статье — произведение Дали. Впрочем, как и сама статья.

    Итак, вот как может выглядеть развернутое условие (напишу в своем стиле и сразу в Совершенной дизъюнктивной нормальной форме(СДНФ)):
    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]
    
    Знак "+" конвертирует переменную 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]
    
    Также как для тернарного оператора первым(нулевым) идет случай для false, для switch-а первым идет случай default, что в общем-то удобно, поскольку он один, его наличие обязательно — это некий аналог нуля.

    Второй принцип индекс-ориентированного программирования: наличие особого нулевого варианта.

    Однако, идея индекс-ориентированного программирования несколько шире, чем замена условных операторов. Еще пара примеров.

    Генерации перестановок из индекса:

    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]
    
    Немного пояснений: "~~(x)" — короткая запись "Math.floor(x)", о которой узнал из видео с livecoding. При использовании короткой записи следует соблюдать ограничение: 0<=x<=2147483647.9999998(подобрано экспериментально). Для сравнения ограничение для "Math.floor": -9007199254740992<=x<9007199254740993. Обращение массива нужно, чтобы получить перестановки в лексикографическом порядке. По индексу получаем(i_to_insert_order) одну из возможных последовательностей вставки элементов. В принципе, ее достаточно, чтобы получить перестановку реальных элементов:
    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']
    
    Но, чтобы увидеть явную перестановку, мы эту вставку эмулируем. Для этого и нужна функция correct. Возможно, это не очень удачный пример, поскольку в нем размывается основная суть.

    Третий принцип индекс-ориентированного программирования: нумерация вариантов.

    Генерация числа Фибоначчи по номеру:

    Воспользуемся сокращенной формулой Бине. Затем, сравним результат с табличным.
      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

      0
      На мой взгляд, переусложнено, но это может быть из-за ограничений языка. Я недостаточно знаю 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)

      Вкратце, делаем ассоциативный массив [множество типов аргументов] -> лямбда
      Плюсы — мало букв. Минусы — кол-во элементов в мапе растет весьма быстро.
        0
        тут была одна особенность, если аргумент не определен, то это вызывает синтаксическую ошибку при попытке передать его в функцию, но typeof определяет его тип:
        //x не существует
        test_func(x) //ReferenceError: x is not defined
        typeof x //'undefined'
        
          0
          не синтаксическую, описался
      • НЛО прилетело и опубликовало эту надпись здесь
          0
          Про память — сейчас добавлю.
          Взятие по индексу — точно быстрее, чем последовательный перебор 'else if'-ами. Cомнение вызывает indexOf, но можно обойтись без него и, он как минимум пропорционален числу условий, а может и быстрее. Поиск в хеш-мапе приблизительно O(1), за исключением коллизий, — тут зависит от реализации. Хотя, была ситуация: поиск по длинным строкам в качестве ключа жутко тормозил, пришлось сначала искать по числовому хешу от строки(вычисление которого, впрочем, также вписывается в этот подход). Что касается вычислений, то возведение в целую степень также может быть линейным, но такие алгоритмы врядли еще где остались. Однако, завершения вычисления 50-го число фибоначчи рекурсивным алгоритмом не дождался(отчасти поэтому не включил код в статью), а для индексного результат был без задержки. По-хорошему, конечно, надо бы сделать замеры скорости, но для простых формул — это не актуально. Итого, ответ — возможно, но только для неоптимизированных вариантов: как вы правильно заметили, расходуется дополнительная память, — мы преобразуем временную сложность в пространственную.
          • НЛО прилетело и опубликовало эту надпись здесь
          0
          Время от времени применяю на практике уже лет 25 (правда, не знал как это называется), но обычно только в случаях хорошо ложащихся на классические массивы, когда разворачивание в условные операторы реально является тупой копипастой, когда условия N-го уровня повторяются каждом N-1 уровне, да ещё являются четко дискретными.
            +3
            Называется это «табличный метод». Code Complete, второе издание, 18 глава.
              0
              спасибо, добавлю упоминание в конец статьи
            +2
            var 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);
            
              +1
              var 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);
              
                +2
                var 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);
                
                  +2
                  Решил сравнить скорости: jsperf.com/ibp-array-vs-object-index, результат не показателен.
                  Ваш вариант, мне нравится даже больше :)
                0
                Обычно составные ключи разделяю подчеркиванием:
                var type = typeof a + '_' + typeof b + '_' + typeof c,
                    callback = {
                       "object_object_string": process,
                       "object_object_undefined": process,
                       ...
                

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое