Haskell at Eaton

antilamer — 15.12.2009 Предположительно таков.

Задача: задан битовый массив из N бит, где N кратно 8. Надо построить способ итерации по позициям единичных бит в этом массиве.

Исходная идея подсмотрена на stackoverflow (правда, похоже, что автор ее не имел в виду): собрать итератор по единичным битам битового массива как конкатенацию итераторов по битам его байтов.
Таких итераторов, "составных блоков" итератора по всему массиву, существует всего 256 разных штук, по числу различных байтов.
Например, для байта 74 (01001010) такой итератор возвращает 1, затем 4, затем 6.
Эти маленькие итераторы можно посчитать на этапе создания программы, а не на этапе выполнения, и как бы "закэшировать", тем самым избежав оверхеда от наивного цикла типа for(int j=7; j>=0; --j) if(data[i]&(1<<j)) {...}.

Уточняю:
- Будем представлять итераторы в шарповской модели "T GetCurrent(), boolean MoveNext". MoveNext() продвигается к следующему элементу, GetCurrent() возвращает элемент под итератором.
- Для каждого из 256 байтов запомним позиции единиц в них. Например, для 74 это 1, 4 и 6. Итератор по битам некоторого фиксированного байта - это линейный конечный автомат, цепочка. Его состояние - это "j", индекс в этот маленький массив позиций единичек.
- Соберем из этих байтовых автоматиков автомат для всего массива, следующего вида:

int i=0; // номер текущего байта
int j=0; // номер текущего единичного бита, 1-based.

bool advance() {
    switch(data[i]) {
        ...case B: [продвинуть j согласно автомату для B, т.е. j++, 
                    либо продвинуть i если автомат закончился]...
    }
}

Теперь сплющим этот автомат до одного автомата с состоянием (i,j) и минимизируем его, получив автомат с состоянием вида "одно целое число".

Например, если бы байты у нас состояли из всего двух битов, то было бы что-то такое:

Псевдокод до минимизации:

int i, j;
int cur;
bool advance() {
    while(true) switch(j,data[i]) {
    case 0,00: if(i==n) return false; i++; j=0; continue;
    case 0,01: j=2; cur=i+1; return true;
    case 0,10: j=1; cur=i+0; return true;
    case 0,11: j=1; cur=i+0; return true;
    case 1,00: // невозможно
    case 1,01: // невозможно
    case 1,10: if(i==n) return false; i++; j=0; continue;
    case 1,11: j=2; cur=i+1; return true;
    case 2,00: // невозможно
    case 2,01: if(i==n) return false; i++; j=0; continue;
    case 2,10: // невозможно
    case 2,11: if(i==n) return false; i++; j=0; continue;
    }
}

После минимизации:

int[] zs={4,0,1,2};
int i=0, s=zs[data[0]];
int cur;
bool advance() {
    while(true) switch(s) {
    case 0: s=4; cur=i+1; return true;
    case 1: s=4; cur=i; return true;
    case 2: s=3; cur=i; return true;
    case 3: s=4; cur=i+1; return true;
    case 4: if(i==n) return false; s=zs[data[i++]];
    }
}

Если заранее известно, что битсет разреженный и что меняться не будет, то "case 4" можно соптимизировать, построив сначала векторными командами индекс позиций-следующих-ненулевых-байтов.

Интересно бы это попробовать сделать для нормальных (8-битовых) байтов (у автомата будет где-то тысяча состояний) и сравнить перформанс со стандартнобиблиотечным при различных коэффициентах заполненности массива.

PS Это не имеет никакого отношения к моей работе, просто решил поразвлечься задачкой :) Чего и вам желаю.

Оставить комментарий

Популярные посты:

• Ранее
• Архив