Подсчет количества пар соседних чисел в произвольном массиве на haskell

Приятель подкинул задачку: имеется массив 8-битовых чисел произвольной длины, требуется посчитать количество пар чисел в этом массиве, отличающихся на 1 бит. Такие числа я назвал соседними в заголовке статьи. Например, числа 1 (в битовом представлении 01) и 3 (11) - соседние, а числа 1 и 2 (10) - нет.

Ниже привожу решение этой задачи на haskell.

Самое очевидное решение - попарное сравнение чисел - не интересно. Нужно что-то получше, что сузило бы количество сравнений или вообще не требовало бы их. Для этого нужно понять, какими свойствами обладают соседние числа. И с этим как раз все просто. Поскольку соседние числа в битовом представлении отличаются только в одном бите, то, соответственно, число установленных битов для них отличается ровно на единицу. Отсюда у нас появляется простой алгоритм - разбить (partition) весь заданный массив чисел по группам, в которых суммы битов всех элементов будут равны, а затем попарно сравнить все элементы из соседних групп и сложить результаты. В случае массива 8-битовых чисел количество таких групп равно 9 (от 0 до 8 установленных битов), обозначим эти группы g0, g1 .. g8, тогда количество соседних групп равно 8 ((g0, g1), (g1, g2) .. (g7, g8)).

Что ж, задача простая, приступим к ее решению. Я сначала приведу код, который я поместил в файл с названием bits_example.hs, а затем его прокомментирую.

module BitsExample where
import Data.Bits
import Data.List


partitionBySetBits' :: Bits a => Int -> [a] -> [[a]]
partitionBySetBits' (-1) _  = [[]]
partitionBySetBits' n xs    = fst x : partitionBySetBits' (n - 1) (snd x)
    where x = partition (\z -> popCount z == n) xs

partitionBySetBits n = tail . reverse . partitionBySetBits' n

adjacentPairs :: Bits a => ([a], [a]) -> [(a, a)]
adjacentPairs (xs, ys) =
    [(x, y) | x <- xs, y <- ys, (popCount $ x `xor` y) == 1]

nAdjacentNumbers :: (Bits a, Num a) => Int -> [a] -> Int
nAdjacentNumbers n xs =
    let adjacentSets = zip partition $ tail partition
    in foldr (+) 0 (map (length . adjacentPairs) adjacentSets)
    where partition = partitionBySetBits n xs

В программе потребуются модули Data.Bits для манипулирования битовым представлением чисел и Data.List, в котором определена замечательная функция partition. Первая функция partitionBySetBits' полностью оправдывает свое название - она разбивает заданный массив чисел xs на n групп по количеству установленных битов в битовом представлении числа (как видите, я не стал ограничиваться 8-битовыми массивами и данное решение подходит для массивов чисел произвольной битовой базы). Количество установленных битов в числе возвращает функция popCount из модуля Data.Bits, она используется в качестве предиката в функции partition. Функция partition возвращает кортеж, состоящий из пары списков - в первом списке содержатся элементы из исходного списка, которые удовлетворяют условию предиката, во втором - которые не удовлетворяют. Наша функция должна возвращать список списков, поэтому мы помещаем первый список из пары в первый подсписок возвращаемого результата (с помощью функции fst), и далее (с помощью функции snd) последовательно прикрепляем остальные группы путем рекурсивного вызова partitionBySetBits' с уменьшенным значением n для элементов из второго списка пары, возвращенной функцией partition. Когда значение n достигает -1, функция partitionBySetBits' возвращает список, состоящий из пустого списка - это условие прекращения рекурсии. То, что рекурсия не прекращается при достижении n нуля важно - ведь в исходном массиве могут встречаться нули.

Что вернет функция partitionBySetBits'? Очевидно, перевернутый список групп (т.е. g8, g7 .. g0), заканчивающийся ненужным пустым списком. Поэтому ниже определена еще одна функция partitionBySetBits, которая переворачивает список и удаляет ненужный пустой элемент. Запустим ghci и проверим как она работает

$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :l bits_example.hs 
[1 of 1] Compiling BitsExample      ( bits_example.hs, interpreted )
Ok, modules loaded: BitsExample.
*BitsExample> :set +s
*BitsExample> partitionBySetBits 2 [0..3]
[[0],[1,2],[3]]
(0.05 secs, 9664352 bytes)
*BitsExample> partitionBySetBits 4 [0..15]
[[0],[1,2,4,8],[3,5,6,9,10,12],[7,11,13,14],[15]]
(0.01 secs, 2580960 bytes)
*BitsExample> partitionBySetBits 8 [0..255]
[[0],[1,2,4,8,16,32,64,128],[3,5,6,9,10,12,17,18,20,24,33,34,36,40,48,65,66,68,72,80,96,129,130,132,136,144,160,192],[7,11,13,14,19,21,22,25,26,28,35,37,38,41,42,44,49,50,52,56,67,69,70,73,74,76,81,82,84,88,97,98,100,104,112,131,133,134,137,138,140,145,146,148,152,161,162,164,168,176,193,194,196,200,208,224],[15,23,27,29,30,39,43,45,46,51,53,54,57,58,60,71,75,77,78,83,85,86,89,90,92,99,101,102,105,106,108,113,114,116,120,135,139,141,142,147,149,150,153,154,156,163,165,166,169,170,172,177,178,180,184,195,197,198,201,202,204,209,210,212,216,225,226,228,232,240],[31,47,55,59,61,62,79,87,91,93,94,103,107,109,110,115,117,118,121,122,124,143,151,155,157,158,167,171,173,174,179,181,182,185,186,188,199,203,205,206,211,213,214,217,218,220,227,229,230,233,234,236,241,242,244,248],[63,95,111,119,123,125,126,159,175,183,187,189,190,207,215,219,221,222,231,235,237,238,243,245,246,249,250,252],[127,191,223,239,247,251,253,254],[255]]
(0.03 secs, 3654448 bytes)
*BitsExample> 

Работает! Двигаемся дальше. Функция adjacentPairs вспомогательная - она принимает пару списков, соответствующих двум соседним группам и возвращает список пар - все соседние числа, составленные путем попарного комбинирования чисел из этих двух групп. Для определения того, являются ли два числа соседними, используется простой алгоритм: сначала числа складываются с помощью операции исключающего или (xor), а затем к результату применяется функция popCount, если полученное значение равно 1, то эти числа - соседние.

Функция nAdjacentNumbers считает искомое количество пар соседних чисел в произвольном массиве. Для этого исходный массив разбивается на группы с помощью функции partitionBySetBits, а затем, с помощью комбинации функций zip и tail, эти группы преобразуются в список соседних групп типа (g0, g1), (g1, g2) .. (g7, g8), который я назвал adjacentSets (напомню, что выражение zip "abc" $ tail "abc" делает как раз то, что нам нужно: возвращает список ["ab", "bc"]). Далее этот список с помощью map (length . adjacentPairs) преобразуется в список количества пар соседних чисел в соседних группах (здесь используется вспомогательная функция adjacentPairs), элементы которого суммируются в свертке foldr (+) 0.

Вот и все. Важно отметить, что класс этого алгоритма, как и класс примитивного нереализованного нами алгоритма с полным попарным перебором, равен O(n^2), поэтому ожидать чудес от него не стоит, хотя, естественно, nAdjacentNumbers будет выполняться значительно быстрее, чем полный перебор. Квадратичность алгоритма следует из реализации функции adjacentPairs, в которой попарно перебираются элементы соседних групп.

Давайте проверим, как работает наша функция.

*BitsExample> nAdjacentNumbers 0 []
0
(0.00 secs, 2096344 bytes)
*BitsExample> nAdjacentNumbers 1 [0..1]
1
(0.57 secs, 2060080 bytes)
*BitsExample> nAdjacentNumbers 2 [0..3]
4
(0.00 secs, 2573000 bytes)
*BitsExample> nAdjacentNumbers 4 [0..15]
32
(0.00 secs, 2063456 bytes)
*BitsExample> nAdjacentNumbers 8 [0..255]
1024
(0.00 secs, 7082504 bytes)
*BitsExample> nAdjacentNumbers 16 [0..65535]
524288
(1120.68 secs, 285882785392 bytes)
*BitsExample>

Какой интересный результат! Количество пар соседних чисел в массивах, составленных из уникальных чисел, заполняющих в битовом представлении все возможные комбинации, равно числу, являющемуся степенью двойки. Так, для 4-битовых чисел это число равно 2^5, для 8-битовых - 2^10, а для 16-битовых - 2^19. Также отметим, что последнее вычисление выполнялось больше 18 минут, поэтому считать количество пар соседних чисел для полной 32-битовой группы с использованием этого алгоритма нецелесообразно.

А теперь посчитаем количество пар соседних чисел в произвольных 8-битовых массивах. Для этого подключим модуль System.Random и определим функцию randomList

*BitsExample> :m +System.Random
*BitsExample System.Random> let randomList s = randomRs (0,255) (mkStdGen s)
Loading package array-0.4.0.1 ... linking ... done.
Loading package deepseq-1.3.0.1 ... linking ... done.
Loading package old-locale-1.0.0.5 ... linking ... done.
Loading package time-1.4.0.1 ... linking ... done.
Loading package random-1.0.1.1 ... linking ... done.
(0.22 secs, 23528592 bytes)
*BitsExample System.Random> nAdjacentNumbers 8 (take 2000 $ randomList 1 :: [Int])
62330
(1.09 secs, 200541944 bytes)
*BitsExample System.Random> nAdjacentNumbers 8 (take 20000 $ randomList 1 :: [Int])
6249274
(96.87 secs, 18507404864 bytes)
*BitsExample System.Random>

Массив, состоящий из 20000 случайных 8-битовых чисел, рассчитывался полторы минуты. Это очень плохой результат. Нужно улучшать алгоритм. Потенциально, алгоритм расчета может быть улучшен за счет более мелкого разбиения чисел по группам. Давайте подумаем, как это сделать. Допустим мы разобьем битовое представление числа на две равные части - левую и правую (так, для 8-битовых чисел это соответствует разбиению по 4 старшим битам и 4 младшим битам). Какими свойствами будут обладать битовые части для соседних чисел? Количество установленных битов в одной из них (левой или правой) будет совпадать в обоих числах, а в другой - отличаться на единицу. Это свойство мы используем в нашей новой реализации.

Напишем новую функцию разбиения по группам partitionBySetBits2, которая будет разбивать исходный массив чисел по количеству установленных битов в левой и правой части битовых представлений чисел.

partitionBySetBits'' :: (Bits a, Num a) => Int -> Int -> Int -> [a] -> [[a]]
partitionBySetBits'' _ _ (-1) _   = [[]]
partitionBySetBits'' k l n xs     =
    let xs' = partition (\z -> popCount (vpart k l z) == n) xs
    in fst xs' : partitionBySetBits'' k l (n - 1) (snd xs')
    where vpart k l z = z .&. (1 `rotate` l - 1) `shift` k

partitionBySetBits2' :: (Bits a, Num a) => Int -> [a] -> [[[a]]]
partitionBySetBits2' (-1) _  = [[[]]]
partitionBySetBits2' n xs    =
    let xs1 = partitionBySetBits'' 0 n2 n2 xs
    in map (partitionBySetBits'' n2 n2 n2) xs1
    where n2 = n `quot` 2

partitionBySetBits2 n xs =
    map (tail . reverse) (tail $ reverse $ partitionBySetBits2' n xs)

Новая функция partitionBySetBits'' умеет делать разбиение по количеству установленных битов в части битового представления числа. Для этого она принимает два дополнительных параметра: k - порядковый номер начального бита части битового представления и l - длину этой части. Кроме того, по сравнению с partitionBySetBits' мне пришлось добавить ограничение Num a для типовой переменной a - это нужно для функции vpart. Функция vpart переводит битовую часть, определяемую k и l, в число, количество бит в котором определяет предикат для функции partition. В остальном логика partitionBySetBits'' совпадает с логикой partitionBySetBits'. Функция partitionBySetBits'' вызывается дважды (для формирования групп чисел по левой и правой частям битового представления) из вспомогательной функции partitionBySetBits2'. Заметим, что partitionBySetBits2' возвращает список списков списков чисел благодаря новому алгоритму разбиения. Функция partitionBySetBits2 переворачивает все подсписки и удаляет ненужный пустой элемент, являющийся артефактом рекурсии в partitionBySetBits''. Проверим как она работает.

*BitsExample System.Random> partitionBySetBits2 2 [0..3]
[[[0],[2]],[[1],[3]]]
(0.02 secs, 4127056 bytes)
*BitsExample System.Random> partitionBySetBits2 4 [0..15]
[[[0],[4,8],[12]],[[1,2],[5,6,9,10],[13,14]],[[3],[7,11],[15]]]
(0.02 secs, 4157584 bytes)
*BitsExample System.Random> partitionBySetBits2 8 [0..255]
[[[0],[16,32,64,128],[48,80,96,144,160,192],[112,176,208,224],[240]],[[1,2,4,8],[17,18,20,24,33,34,36,40,65,66,68,72,129,130,132,136],[49,50,52,56,81,82,84,88,97,98,100,104,145,146,148,152,161,162,164,168,193,194,196,200],[113,114,116,120,177,178,180,184,209,210,212,216,225,226,228,232],[241,242,244,248]],[[3,5,6,9,10,12],[19,21,22,25,26,28,35,37,38,41,42,44,67,69,70,73,74,76,131,133,134,137,138,140],[51,53,54,57,58,60,83,85,86,89,90,92,99,101,102,105,106,108,147,149,150,153,154,156,163,165,166,169,170,172,195,197,198,201,202,204],[115,117,118,121,122,124,179,181,182,185,186,188,211,213,214,217,218,220,227,229,230,233,234,236],[243,245,246,249,250,252]],[[7,11,13,14],[23,27,29,30,39,43,45,46,71,75,77,78,135,139,141,142],[55,59,61,62,87,91,93,94,103,107,109,110,151,155,157,158,167,171,173,174,199,203,205,206],[119,123,125,126,183,187,189,190,215,219,221,222,231,235,237,238],[247,251,253,254]],[[15],[31,47,79,143],[63,95,111,159,175,207],[127,191,223,239],[255]]]
(0.05 secs, 7290832 bytes)
*BitsExample System.Random>

Переходим к реализации nAdjacentNumbers2. В предыдущем алгоритме мы использовали тот факт, что все соседние числа могут находиться только в соседних группах. Наш новый алгоритм может использовать этот же факт. В самом деле, после фиксации одной из подгрупп, соответствующей количеству битов в левой или правой битовой части числа, в другой подгруппе количество битов для соседних чисел должно отличаться ровно на единицу. Вот и рецепт получения соседних групп. Я не хочу искать аналитическое выражение для поиска соседних подгрупп (мы сделаем это в следующем варианте алгоритма). В случае 8-битовых чисел легко увидеть, что соседние группы соответствуют списку ((0, 0), (0, 1)), ((0, 0), (1, 0)), ((0, 1), (0, 2)), ((0, 1), (1, 1)) .., состоящему из 40 элементов (первый элемент в каждой паре соответствует числу установленных битов в правой части битового представления числа, второй - в левой). Мы просто перечислим все эти элементы в нашей новой функции nAdjacentNumbers2.

nAdjacentNumbers2 :: (Bits a, Num a) => [a] -> Int
nAdjacentNumbers2 xs =
    let adjacentSets = [((0, 0), (0, 1)), ((0, 0), (1, 0)), ((0, 1), (0, 2)),
                        ((0, 1), (1, 1)), ((0, 2), (0, 3)), ((0, 2), (1, 2)),
                        ((0, 3), (0, 4)), ((0, 3), (1, 3)), ((0, 4), (1, 4)),
                        ((1, 0), (1, 1)), ((1, 0), (2, 0)), ((1, 1), (1, 2)),
                        ((1, 1), (2, 1)), ((1, 2), (1, 3)), ((1, 2), (2, 2)),
                        ((1, 3), (1, 4)), ((1, 3), (2, 3)), ((1, 4), (2, 4)),
                        ((2, 0), (2, 1)), ((2, 0), (3, 0)), ((2, 1), (2, 2)),
                        ((2, 1), (3, 1)), ((2, 2), (2, 3)), ((2, 2), (3, 2)),
                        ((2, 3), (2, 4)), ((2, 3), (3, 3)), ((2, 4), (3, 4)),
                        ((3, 0), (3, 1)), ((3, 0), (4, 0)), ((3, 1), (3, 2)),
                        ((3, 1), (4, 1)), ((3, 2), (3, 3)), ((3, 2), (4, 2)),
                        ((3, 3), (3, 4)), ((3, 3), (4, 3)), ((3, 4), (4, 4)),
                        ((4, 0), (4, 1)), ((4, 1), (4, 2)), ((4, 2), (4, 3)),
                        ((4, 3), (4, 4))]
    in foldr (+) 0 (map (xyLength) adjacentSets)
    where partition  = partitionBySetBits2 8 xs
          xyLength z = let x  = fst z
                           y  = snd z
                           x1 = fst x
                           x2 = snd x
                           y1 = fst y
                           y2 = snd y
                       in length $ adjacentPairs (partition!!x1!!x2,
                                                  partition!!y1!!y2)

В функции nAdjacentNumbers2 нет параметра n, так как она может быть использована для поиска числа пар соседних чисел только в 8-битовых массивах, и это отражено внутри ее тела при вызове partitionBySetBits2 8 xs. Строкой выше выполняется основная задача функции: список adjacentSets трансформируется в список количества пар соседних чисел, посчитанных для всех соседних групп с помощью функции xyLength, которая находит соседние группы в списке partition путем непосредственного обращения к его элементам с использованием оператора !!, а затем подсчитывает количество пар соседних чисел в этих подгруппах с помощью нашей старой функции adjacentPairs. Затем все найденные числа складываются с помощью свертки foldr (+) 0. Из-за использования adjacentPairs класс нового алгоритма по-прежнему квадратичный.

Сравним значения, полученные с использованием нового алгоритма с теми, которые мы уже считали.

*BitsExample System.Random> nAdjacentNumbers2 [0..255]
1024
(0.06 secs, 8795888 bytes)
*BitsExample System.Random> nAdjacentNumbers2 (take 2000 $ randomList 1 :: [Int])
62330
(0.74 secs, 140816296 bytes)
*BitsExample System.Random> nAdjacentNumbers2 (take 20000 $ randomList 1 :: [Int])
6249274
(68.79 secs, 12915067416 bytes)
*BitsExample System.Random>

Отлично! Результаты те же, работает чуть быстрее.

А теперь напишем линейный алгоритм. Идея та же, что и в предыдущем, главное отличие - разбивать на подгруппы будем по каждому отдельному биту в битовом представлении. Такие группы примечательны тем, что все элементы в соседних группах являются соседними числами (это очевидно из наших определений соседних групп и соседних чисел), а значит квадратичный алгоритм adjacentPairs больше не нужен - достаточно перемножить длины списков соседних групп. Кроме того, для таких групп достаточно легко вывести выражение для получения полного списка всех соседних групп. Для этого достаточно представить все возможные группы в виде битовых полей. Для 8-битовых чисел длина полного списка таких групп равна 256, что соответствует всем различным вариантам расположения битов в 8-битовом поле. Начиная с группы (0, 0, 0, 0, 0, 0, 0, 0) будем помещать единицу слева направо - это и будут все соседние группы для нулевой группы, затем проделаем то же самое с группой (0, 0, 0, 0, 0, 0, 0, 1) и так далее вплоть до группы (1, 1, 1, 1, 1, 1, 1, 1). Полученные таким образом соседние группы будут соответствовать выражению

[(x, z) | x <- [0..254] :: [Int], y <- [1, 2, 4, 8, 16, 32, 64, 128],
          let z = x .|. y, z /= x]

Его мы и будем использовать для генерации списка соседних групп. Ниже приводится реализация линейного алгоритма подсчета количесива пар соседних чисел в массиве 8-битовых чисел.

partitionBySetBits8' :: (Bits a, Num a) => Int -> [a] -> [[[[[[[[[a]]]]]]]]]
partitionBySetBits8' (-1) _  = [[[[[[[[[]]]]]]]]]
partitionBySetBits8' n xs    =
    let xs1 = partitionBySetBits'' 0 n8 n8 xs
    in let xs2 = map (partitionBySetBits'' n8 n8 n8) xs1
       in let xs3 = map (map (partitionBySetBits'' (n8 * 2) n8 n8)) xs2
          in let xs4 = map (map (map
                                (partitionBySetBits'' (n8 * 3) n8 n8))) xs3
             in let xs5 = map (map (map (map
                                (partitionBySetBits'' (n8 * 4) n8 n8)))) xs4
                in let xs6 = map (map (map (map (map
                                (partitionBySetBits'' (n8 * 5) n8 n8))))) xs5
                   in let xs7 = map (map (map (map (map (map
                                (partitionBySetBits'' (n8 * 6) n8 n8)))))) xs6
             in map (map (map (map (map (map (map
                                (partitionBySetBits'' (n8 * 7) n8 n8))))))) xs7
    where n8 = n `quot` 8

partitionBySetBits8 n xs    =
    let xs1 = partitionBySetBits8' n xs
    in let xs2 = map (tail . reverse) xs1
       in let xs3 = map (map (tail . reverse)) xs2
          in let xs4 = map (map (map (tail . reverse))) xs3
             in let xs5 = map (map (map (map (tail . reverse)))) xs4
                in let xs6 = map (map (map (map (map (tail . reverse))))) xs5
                   in let xs7 = map (map (map (map (map (map
                                                    (tail . reverse)))))) xs6
                      in tail $ reverse $ map (map (map (map (map (map (map
                                                    (tail . reverse))))))) xs7

nAdjacentNumbers8 :: (Bits a, Num a) => [a] -> Int
nAdjacentNumbers8 xs =
    let adjacentSets = [(x, z) | x <- [0..254] :: [Int],
                       y <- [1, 2, 4, 8, 16, 32, 64, 128],
                       let z = x .|. y, z /= x]
    in foldr (+) 0 (map (xyLength) adjacentSets)
    where partition  = partitionBySetBits8 8 xs
          xyLength z = let x              = fst z
                           y              = snd z
                           nonzeroToOne 0 = 0
                           nonzeroToOne _ = 1
                           x1             = nonzeroToOne $ x .&. 1
                           x2             = nonzeroToOne $ x .&. 2
                           x3             = nonzeroToOne $ x .&. 4
                           x4             = nonzeroToOne $ x .&. 8
                           x5             = nonzeroToOne $ x .&. 16
                           x6             = nonzeroToOne $ x .&. 32
                           x7             = nonzeroToOne $ x .&. 64
                           x8             = nonzeroToOne $ x .&. 128
                           y1             = nonzeroToOne $ y .&. 1
                           y2             = nonzeroToOne $ y .&. 2
                           y3             = nonzeroToOne $ y .&. 4
                           y4             = nonzeroToOne $ y .&. 8
                           y5             = nonzeroToOne $ y .&. 16
                           y6             = nonzeroToOne $ y .&. 32
                           y7             = nonzeroToOne $ y .&. 64
                           y8             = nonzeroToOne $ y .&. 128
                       in (length $ partition!!x1!!x2!!x3!!x4!!x5!!x6!!x7!!x8) *
                          (length $ partition!!y1!!y2!!y3!!y4!!y5!!y6!!y7!!y8)

Хоть он выглядит уже не так симпатично, как предыдущие, зато должен работать очень быстро! Проверим.

*BitsExample System.Random> nAdjacentNumbers8 [0..255]
1024
(0.16 secs, 16539728 bytes)
*BitsExample System.Random> nAdjacentNumbers8 (take 2000 $ randomList 1 :: [Int])
62330
(0.20 secs, 31029640 bytes)
*BitsExample System.Random> nAdjacentNumbers8 (take 20000 $ randomList 1 :: [Int])
6249274
(0.91 secs, 209783000 bytes)
*BitsExample System.Random> nAdjacentNumbers8 (take 200000 $ randomList 1 :: [Int])
624987946
(7.82 secs, 1996417336 bytes)
*BitsExample System.Random> nAdjacentNumbers8 (take 2000000 $ randomList 1 :: [Int])
62500089507
(76.73 secs, 19851517872 bytes)
*BitsExample System.Random>

На этот раз действительно быстро. То, что предыдущий алгоритм считал 68 секунд, теперь было посчитано быстрее чем за секунду. Следующий рубеж - массив из 200000 чисел - был посчитан быстрее чем за 8 секунд, а массив из двух миллионов чисел - за 76 секунд, и это хорошо отражает линейность нового алгоритма.

Исходный код примера здесь.

Конфигурация nginx: вложенные if

Как известно, вложенные if в конфигурации nginx запрещены, поскольку это вовсе не языковая конструкция nginx, а обычная директива из модуля rewrite, использование которой в ее же собственном контексте if не предусмотрено - так уж она сделана. Использование списка условий, разделенных логическими операторами и и или тоже не предусмотрено. Обычно для эмуляции вложенных условий с использованием директивы if предлагают использовать регулярные выражения. Например if в

        location /test_if.html {
            set $cond $host::$arg_a;
            if ($cond ~* '^localhost::.+') {
                echo "Matched: host = '$host', a = '$arg_a'";
                break;
            }
            echo "Not matched: host = '$host', a = '$arg_a'";
        }

проверяет, что имя, указанное в HTTP хедере Host, соответствует значению localhost и в URI присутствует аргумент a (в этом случае переменная $arg_a будет не пустой).

К сожалению, условие в директиве if имеет ограничения. По крайней мере, это не выражение, и, как я уже сказал, оно не может быть составлено в виде цепочки выражений, разделенных логическими операторами. Кроме того, в случае сравнения чего-то с регулярным выражением, это что-то может быть только именем переменной, именно поэтому нам пришлось ввести новую переменную $cond, а не записать это просто как

            if ($host::$arg_a ~* '^localhost::.+') {

В данном случае nginx просто не запустится, заявив unknown "host::$arg_a" variable. Выражение для регулярного выражения в условии if также имеет ограничение: в нем нельзя использовать переменные - они просто не будут расширяться. Но что тогда делать, если мы хотим сравнить $host на соответствие не константному выражению localhost, а значению, определенному в какой-нибудь переменной, например $goodhost? Ответ - использовать другую переменную $cond и другое регулярное выражение.

        location /test_if.html {
            set $goodhost 'localhost';
            set $cond $host::$goodhost::$arg_a;
            if ($cond ~* '^(.*)::\1::.+') {
                echo "Matched: host = '$host', a = '$arg_a'";
                break;
            }
            echo "Not matched: host = '$host', a = '$arg_a'";
        }

В данном примере мы соединили через произвольно выбранный нами разделитель :: три переменных $host, $goodhost и $arg_a и присвоили это значение переменной $cond. А регулярное выражение, с которым мы сопоставляем это значение, проверяет, что его первая часть (до разделителя ::) и вторая часть (до второго разделителя ::) равны, а последняя часть (после второго разделителя) не пуста.

Идея понятна, последний пример - трансляция псевдокода

            if ($host == $goodhost && not_empty($arg_a)) {
                if ($arg_a == 'ok') {
                    echo "Matched: host = '$host', a is Ok";
                } else {
                    echo "Matched: host = '$host', a is '$arg_a'";
                }
            } else {
                echo "Not matched: host = '$host', a = '$arg_a'";
            }

Результат трансляции:

        location /test_if.html {
            set $goodhost 'localhost';
            set $cond $host::$goodhost::$arg_a;
            if ($cond ~* '^(.*)::\1::ok$') {
                echo "Matched: host = '$host', a is Ok";
                break;
            }
            if ($cond ~* '^(.*)::\1::.+$') {
                echo "Matched: host = '$host', a = '$arg_a'";
                break;
            }
            echo "Not matched: host = '$host', a = '$arg_a'";
        }

vim: редактирование файлов от имени суперпользователя, добавление новых сегментов Powerline

Настроить редактирование системных файлов от имени суперпользователя на домашнем компьютере несложно. Заводим файл в директории /etc/sudoers.d/ с произвольным именем, например users. Помещаем в него строки

Host_Alias    LOCAL = desktop
Cmnd_Alias    VIM = /usr/bin/vim, /usr/bin/vimdiff
Defaults!VIM  env_keep += "HOME"
username      LOCAL = NOPASSWD: VIM

Здесь имя desktop соответствует имени локального хоста. Если вы специально не изменяли это имя в вашей системе, то вместо desktop напишите localhost. Алиас хоста LOCAL используется в последней строке и разрешает редактирование файлов от имени суперпользователя только с локального компьютера. Имя username соответствует имени учетной записи пользователя, которому будет позволено редактировать файлы с помощью sudo. В данном примере мы разрешили пользователю username запускать программы vim и vimdiff от имени суперпользователя без ввода пароля. Кроме того, в третьей строке мы попросили sudo использовать оригинальное значение переменной окружения $HOME: это нужно для того, чтобы vim загружал скрипт .vimrc и все дополнительные плагины из домашней директории пользователя username, а не из директории суперпользователя.

Что здесь нехорошо? Собственно то, что мы дали пользователю username возможность выполнить любую системную команду с привилегией суперпользователя! Не забываем, что из vim можно выполнить системную команду с помощью :!. Именно поэтому в первом предложении я написал на домашнем компьютере: не стоит давать такие привилегии обычному пользователю username на промышленном сервере.

Последнее украшательство - добавление алиасов в файл .bashrc:

alias svim='sudo vim'
alias svimdiff='sudo vimdiff'

Теперь vim с правам суперпользователя можно вызывать как svim, а vimdiff - как svimdiff.

Всё это прекрасно, но хотелось бы, чтобы vim каким-нибудь образом отмечал то, что мы редактируем файл от имени суперпользователя. Что ж, это достаточно легко сдедать с помощью плагина Powerline. Лично я по-прежнему использую старую версию плагина, которую можно загрузить отсюда, поэтому следующий рецепт относится именно к ней.

Итак, наша задача - добавить новый сегмент, на котором, в случае, если пользователь редактирует файл от имени суперпользователя, во всех режимах vim будет красоваться жирная, хорошо заметная надпись SUDO на красном фоне. Поскольку это сообщение достаточно важное, пусть оно будет находиться в начале статусной строки. Для этого в файле .vim/autoload/Powerline/Segments.vim перед строкой

    \ Pl#Segment#Create('paste_indicator' , '%{&paste ? "PASTE" : ""}', Pl#Segment#Modes('!N')),

добавим похожую строку

    \ Pl#Segment#Create('sudo_indicator'  , '%{empty($SUDO_USER) ? "" : "SUDO"}', Pl#Segment#Modes('!N')),

Это и есть новый сегмент, который мы назвали sudo_indicator (первый аргумент функции Pl#Segment#Create()). Второй аргумент Pl#Segment#Create() соответствует коду, который будет выполнен для определения текста сегмента. В нашем случае мы опираемся на тот простой факт, что команда sudo определяет переменную окружения $SUDO_USER, в которой записано имя пользователя, получившего привилегии суперпользователя, соответственно, если эта переменная определена (то есть vim был запущен из sudo), то второй аргумент будет равен SUDO, иначе - пустой строке. Третий параметр: Pl#Segment#Modes('!N') - говорит о том, что если текущее окно не в фокусе, то данный сегмент не будет отображаться - это нам вполне подходит.

Далее помещаем новый сегмент на первую позицию списка всех сегментов. Для этого в файле .vim/autoload/Powerline/Themes/default.vim добавляем строку

        \ , 'sudo_indicator'

перед строкой

        \ , 'paste_indicator'

а в файле .vim/autoload/Powerline/Colorschemes/default.vim описываем цветовые характеристики сегмента:

    \
    \ Pl#Hi#Segments(['sudo_indicator'], {
        \ 'n': ['brightgreen', 'brightestred', ['bold']],
        \ }),

(это можно поместить, например, за определением

    \ Pl#Hi#Segments(['SPLIT'], {
        \ 'n': ['white', 'gray2'],
        \ 'N': ['white', 'gray0'],
        \ 'i': ['white', 'darkestblue'],
        \ }),

). Если вы используете другую тему или цветовую схему Powerline (то есть не default), то данные определения нужно поместить в соответствующие файлы. Итак, почти все готово, обновляем кэш Powerline:

:PowerlineClearCache

и открываем какой-нибудь файл с помощью svim. Вот какую статусную строку я увидел после этих изменений:

Хорошо, но не очень. Видите темно-красные артефакты вокруг стрелки с SUDO? Исследование показало, что они связаны с сегментом paste_indicator, когда его текст соответствует пустой строке. Вы можете убедиться в этом выполнив

:set paste

и

:set nopaste

несколько раз. К сожалению, как я понял, данная версия Powerline не способна удовлетворительно решить проблему с сегментом, который может содержать пустое значение. Если такой сегмент находится не в самом начале списка сегментов, то мы будем время от времени получать подобные стрелочные артефакты. В нашем случае возможны четыре решения данной проблемы:

1. удалить сегмент paste_indicator (плохо);
2. сделать так, чтобы надпись в paste_indicator присутствовала всегда (т.е. PASTE или NOPASTE - тоже не очень хорошо - зачем нам избыточная информация);
3. перенести индикатор SUDO в комбинированный сегмент fileinfo (см. .vim/autoload/Powerline/Segments.vim), тоже не очень хорошо - придется использовать серый фон;
4. сделать так, чтобы фон индикатора paste_indicator всегда соответствовал фону следующего постоянного сегмента mode_indicator. В этом случае цвет стрелочных артефактов будет совпадать с цветом фона следующего сегмента и, соответственно, они должны бесследно исчезнуть;

Лично я воспользовался последним вариантом и переопределил paste_indicator в .vim/autoload/Powerline/Colorschemes/default.vim как

    \
    \ Pl#Hi#Segments(['paste_indicator'], {
        \ 'n': ['brightestred', 'brightgreen', ['bold']],
        \ 'i': ['brightestred', 'white', ['bold']],
        \ 'v': ['brightestred', 'brightorange', ['bold']],
        \ 'r': ['brightgreen', 'brightred', ['bold']],
        \ 's': ['brightestred', 'gray5', ['bold']],
        \ }),

После перзагрузки кэша Powerline и запуска svim я получил следующие картинки: 

В нормальном режиме при установленном paste это выглядит так:

 

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

Из тех, с которыми мне доводилось работать самому. Вообще-то лучший визуальный анализ - это просмотр исходного кода. Однако, он дает только качественное представление об исследуемых параметрах программы, да и не изобрели еще автоматического транслятора человеческих мыслей в персистентные формы. Итак, рассмотрим два, на мой взгляд, потрясающих инструмента для тестирования работы программ и визуализации результатов тестирования. Это gprof2dot и massif-visualizer. По правде говоря, обе программы - всего лишь оболочки над, соответственно, еще более потрясающим инструментом valgrind. Все что они делают - это читают результаты прогона тестируемой программы из-под valgrind и генерируют отчеты в визуально привлекательной форме, то есть в виде изображений.

Итак, напишем простейшую программу, которую мы будем тестировать, и поместим ее в файл test.cc.

class  A
{
    public:
        A() : a_( 0 ) { a(); }

        ~A() { delete a_; }

        void a( void ) { a_ = new int( 0 ); }

        void  realloc( void ) { delete a_; a_ = new int( 0 ); }

    private:
        int *  a_;
};

int  main( void )
{
    A  a[ 10 ];

    for ( int  i( 0 ); i < 10; ++i )
    {
        a[ i ].realloc();
    }
}

В функции main() создаем массив a из десяти объектов типа A. В конструкторе класса A с помощью функции-члена a() выделяется динамическая память под объект типа int, а в деструкторе она освобождается. Кроме того, в классе A имеется функция-член realloc(), которая освобождает выделенную память и снова выделяет ее. Функция realloc() вызывается для всех элементов массива a внутри функции main(). Две функции внутри класса A нам будут нужны для демонстрации работы gprof2dot, а манипуляции с динамической памятью - для massif-visualizer.

Откомпилируем нашу программу

g++ -g -o test test.cc

и приступим к разбору утилит.

gprof2dot. Эта утилита позволяет выводить красивые диаграммы вызова функций на основании результатов профилирования тестируемой программы. Самый стандартный профилировщик для gcc - это gprof, отсюда и название gprof2dot. Однако мы не будем использовать gprof, так как для его поддержки пришлось бы компилировать программу со специальными флагами. Вместо этого будем использовать инструмент callgrind, входящий в состав valgrind, а gprof2dot сообщим, что мы использовали callgrind с помощью опции --format=callgrind. Кроме того, для получения результирующего изображения нам понадобится пакет graphviz, который предоставляет утилиту dot (вторая часть в названии gprof2dot), которая, в свою очередь, умеет генерировать из промежуточного dot-файла изображение заданного формата.

Запускаем тестируемую программу из-под valgrind

valgrind --tool=callgrind --callgrind-out-file=callgrind.out ./test

и строим изображение

gprof2dot --format=callgrind --output=out.dot -s callgrind.out
dot -Tpng out.dot -o out.png

Опция -s команды gprof2dot позволяет записывать имена функций более компактно: это весьма полезно, когда полученное изображение оказывается очень большим (а это всегда так).

Вот так выглядит полученная картинка out.png (кликните по изображению для его увеличения):

Изображение состоит из набора элементов двух типов: прямоугольников - функций и стрелок - вызовов функций. Каждый элемент сопровождается профильной информацией. Для функций - это библиотека или исполняемая программа, которой принадлежит функция, имя функции, время ее выполнения в процентах от общего времени исполнения программы и количество ее вызовов. Стрелки сопровождаются информацией о времени выполнения всей иерархии функций, вызовы которых они порождают и количестве вызовов дочерней функции из родительской, соединенных этой стрелкой. Качественная информация о времени выполнения отдельных функций передается цветом прямоугольника: чем теплее цвет - тем больше времени заняло выполнение данной функции. Так, корневая функция, вместо имени которой указан адрес (верхний прямоугольник), окрашена красным цветом и время ее выполнения соответствует 100%, так как вызовы всех остальных функций были порождены ею, значение в скобках - 0.00% - это время выполнения ее тела. Функции, которые выполнялись за меньшее время окрашены в оранжевый, желтый и зеленый цвета, самые быстрые - в синий.

Соответственно, на нашем изображениии видно, что львиную долю времени заняли вызовы системных функций линковщика, в частности _dl_relocate_object() была вызвана 7 раз и заняла 88.92% всего времени. Наша главная функция main() потратила всего лишь 2.19% от общего времени. И это не удивительно в случае такой простой программы, как наша. Конструктор A::A() вызывался 10 раз из функции main() и потратил 0.95% общего времени, функция-член A::realloc() вызывалась тоже 10 раз и потратила 1.04% общего времени. Все время обоих функций было затрачено на вызов оператора new() и, затем, функции malloc().

Что если нас не интересуют системные вызовы? Утилита gprof2dot позволяет строить вызовы функций из определенного корня с помощью опции -z. Например, чтобы построить вызовы всех фунций, начиная с нашей функции main(), нужно выполнить

gprof2dot --format=callgrind --output=out_main.dot -s -z main callgrind.out
dot -Tpng out_main.dot -o out_main.png

Полученное изображение out_main.png представляет собой небольшой участок общей картинки:

Есть еще одна полезная опция -l - это когда нужно изобразить все, что вызывает указанную функцию.

massif-visualizer. Эта утилита полезна, когда нужно визуализировать выделение и освобождение динамической памяти в процессе прогона тестируемой программы. Она тоже является простой оболочкой над инструментом massif из состава valgrind. При сборке программы вручную важно учесть, что она зависит от библиотек разработки KDE.

Запустим программу test под massif

valgrind --tool=massif --massif-out-file=massif.out --time-unit=B --detailed-freq=1 ./test

и откроем сгенерированный файл massif.out с помощью massif-visualizer

massif-visualizer massif.out

Откроется вот такое окно:

В центральной области расположен график, изображающий этапы выделения и освобождения динамической памяти. Горизонтальная ось графика - время работы программы, выраженное в байтах, это соответствует опции massif --time-unit=B. Время, выраженное в байтах, лучше всего подходит для небольших тестовых программ, каковой и является наша программа test. Другие возможные единицы измерения времени в massif - количество инструкций (по умолчанию) и миллисекунды. Опция --detailed-freq=1 в нашем случае также имеет важное значение: она задает самое детализированное накопление снапшотов, то есть столбцов графика и элементов из списка справа от него. В случае продолжительно работающих программ ее значение по умолчанию 10 является более предпочтительным, чем 1.

По вертикальной оси отложено количество выделенной динамической памяти. Очевидно, пиковое значение 40 байт соответствует десятикратному значению размера типа int (4 байта * 10 элементов массива a). Память, выделенная функцией A::a(), обозначена желтым цветом. Она постепенно снижалась за счет вызова функции A::realloc() в цикле for внутри main(). Вызовам A::realloc() соответствуют синие столбцы на графике. В итоге, в конце программы вся память была освобождена, поскольку на правом крае графика столбцы отсутствуют.

Список снапшотов справа от графика также позволяет судить о динамике использования памяти. Самый верхний элемент списка имеет белый окрас, что соответствует нулевой выделенной памяти, затем цвет постепенно теплеет до красного: память выделяется, в конце списка окрас элементов начинает белеть: память освобождается. Кроме цветовой информации в списке снапшотов присутствуют ссылки на строки в исходном коде, в которых происходят изменения, связанные с выделением или освобождением динамической памяти.

C++: члены класса в тени формальных параметров конструктора

Возьмем простую программу

class  A
{
    public:
        explicit A( int  a ) : a( a )
        {}

    private:
        int  a;
};

int  main( void )
{
    A  a( 0 );

    return 0;
}

Что здесь плохо? Видите ли вы потенциальную опасность? Попробуем скомпилировать с включенными предупреждениями:

g++ -Wall -o test test.cc

Всё хорошо. Запуск программы на выполнение также не приводит к каким-либо проблемам (и это неудивительно). А теперь попробуем так:

g++ -Wall -Wshadow -o test test.cc
test.cc: In constructor «A::A(int)»:
test.cc:23:30: предупреждение: декларация «a» перекрывает элемент класса, на который указывает 'this' [-Wshadow]
         explicit A( int  a ) : a( a )
                              ^

Итак, с помощью опции компилятора -Wshadow нам удалось получить интересное предупреждение, которое намекает на то, что если мы будем использовать имя a внутри тела конструктора, то это никоим образом не будет член класса A, но одноименный формальный параметр, переданный в конструктор. Вот так то! Всё бы ничего, мы ведь сами не дураки и знаем, что если нам понадобится член класса, то мы сможем обратиться к нему через указатель this.

Казалось бы, в чем проблема, просто не использовать -Wshadow и дело с концом. А теперь представьте, что ваш код, написанный в таком стиле, когда имя формального параметра совпадает с именем члена класса, инициализируемого этим параметром, является частью большого проекта, при сборке которого было решено добавить -Wshadow, и вы не можете убрать эту опцию при сборке вашей части (такое вполне возможно, если система построения проекта хорошо автоматизирована и вы можете изменять на своей стороне лишь часть деклараций)! Компиляция вашего участка превратится в настоящий кошмар с выводом на экран огромного количества предупреждений, подобных приведенному выше (особенно если вы предпочитаете помещать реализации конструкторов внутри заголовочных файлов).

Как же с этим бороться? Самый очевидный способ - рефакторинг. Имена формальных параметров конструкторов и членов класса должны отличаться. Например, именем формального параметра в приведенном примере остается a, а имя члена класса переименовываем в a_. Лично мне такой стиль совершенно не импонирует. В самом деле, инициализацию членов класса через формальные параметры конструктора хотелось бы рассматривать как чисто языковой элемент, не вдаваясь в подробности реализации, такие как копирование одного объекта в другой. Иначе страдает абстракция и такой, казалось бы, простой шаблон, как инициализация членов класса формальными параметрами конструктора, начинает обрастать ненужными деталями.

Второй способ - обрамление объявлений конструкторов прагмами компилятора, отключающими диагностические сообщения. Например, в случае gcc конструктор A из приведенного выше примера может быть записан так:

#pragma GCC diagnostic ignored "-Wshadow"
        explicit A( int  a ) : a( a )
        {}
#pragma GCC diagnostic pop

Минусы здесь очевидны. Во-первых, мы так и не добились желаемого уровня абстракции шаблона инициализации членов класса, засорив его еще менее понятными объявлениями. Во-вторых, прагмы, как известно, не переносимы, и для разных компиляторов они будут отличаться. В-третьих, если проект достаточно большой, то вставка большого количества прагм замусорит код.

В общем, как правильно решить такую проблему мне пока не ясно. Очень хочется сохранить простой шаблон инициализации членов класса формальными параметрами конструктора, в котором оба языковых элемента (то есть члены класса и формальные параметры конструктора) рассматриваются абстрактно и имеют одно имя. Однако C++, к сожалению, не является настолько выразительным, чтобы это можно было сделать безопасно, и включение опции -Wshadow напоминает нам об этом. Увы, по всей видимости, использование разных имен для членов класса и формальных параметров конструктора - это единственный полностью безопасный подход.