воскресенье, 19 июня 2011 г.

Чтение чужого кода - весьма полезное занятие, можно узнать много интересного, хотя все конечно зависит от того, кем этот код написан. В этом плане, код создателя Clojure - Ричарда Хикки, просто эльдорадо какое-то :)
Вот один интересный прием использованный в Clojure - допустим у нас есть объект - массив фиксированной длины содержащий до 32-х элементов. Массив заполнен не полностью, некоторые элементы равны null, некоторые содержат полезные данные. Доступ к элементам осуществляется обычным образом, по индексу.
Ход мыслей обычного программиста - массив небольшой, поэтому можно просто создавать его полностью, часть элементов массива будут раны null, часть заняты полезными данными, код будет проще и будет быстрее работать, так как не нужно вычислять индекс элемента в массиве. Однако Ричард Хикки решил иначе, дело в том, что этот массив - часть персистентной структуры данных, поэтому создавать массив полностью накладно, так как такие массивы будут создаваться очень часто в процессе, называемом path copying. 
Вот как это сделано в clojure - объект содержит массив и маску (32 бита). Массив содержит только полезные данные, то есть, если в массиве 4 элемента, и 28 null-ов, то будет создан массив из 4-х элементов. Маска служит индексом, если i-й элемент массива равен null, то i-й бит маски будет сброшен, а в противном случае - установлен.
Самое интересное в этом - поиск элемента в массиве по индексу. Допусти мы хотим получить значение i-го элемента массива. Для этого, нам нужно выполнить сравнение:
int bit = 1 << i; 
if (mask & bit == 0) return null;
в противном случае, элемент не равен null и нам нужно найти его смещение в массиве. Допустим, array - наш массив, он имеет размер - от 0 до  32х. Для получения индекса i-го элемента в массиве, мы должны выполнить следующие операции:
int index = numberOfSetBits(mask & (bit - 1));
return array[index]; 
где numberOfSetBits - функция, возвращающая количество не нулевых битов числа. Это вычисляется за несколько тактов процессора :)
Представим, что у нас есть массив из 4-х элементов. Допустим, 0-й, 3-й, 6-й и 7-й элементы не равны null. В этом случае, маска будет выглядеть так - 11001001. Младший бит соответствует первому элементу массива, а старший - последнему. Теперь, вычислим индекс последнего элемента массива - i = 7, bit = 1 << 7 = 10000000. Поскольку bit - степень двойки, то bit - 1 будет равно 1111111. Если мы побитово сравним это значение с маской, то мы получим все те же биты, что и в маске, кроме старшего - 11001001 & 1111111 = 1001001. Теперь, если мы посчитаем биты в этом числе, то получим число не null элементов индекс которых меньше нашего i, а именно 3. Именно это число и будет индексом в нашем массиве, не включающем null значения.
Все эти битовые операции выполняются за считанные такты процессора и код в целом работает быстрее. Вообще, мне очень нравятся такие не очевидные решения :)

Комментариев нет: