Запълване на наводнение с побитови операции

Имам битова карта, съхранена като (фиксиран) брой цели числа без знак, напр.

1 0 0 1
1 0 1 0
1 1 0 1
0 1 1 0

...се съхранява като целочислен масив [ 9, 10, 13, 6 ] (отгоре надолу, най-значимият бит вляво).

Бих искал да внедря алгоритъм за наводняване. Например, ако m е картата, изобразена по-горе, floodFill(m, 3, 2) трябва да създаде картата:

1 0 0 0
1 0 0 0
1 1 0 0
0 1 1 0

(Тук 3,2 съответства на трети ред (индексиран с 0), втора колона (отдясно). Отговорът ще бъде кодиран като [ 8, 8, 12, 6 ].)

Със сигурност мога да приложа един от стандартните подходи, но се чудя дали мога да се справя по-добре, като използвам трикове за битова манипулация.

Например, ако част от решението се съдържа в карта m0, мисля, че аз m0 | ((m0 >> 1) & m) "увеличавам" запълването на наводнението вдясно.

Това стандартен трик ли е за паралелизиране на запълване на наводнения на битови карти? Може ли някой да измисли пълен алгоритъм? Докажете интересни граници на времето за работа?

Редактиране: някои допълнителни примери:

floodFill ( 0 0 1 1     , 1, 1 ) =  0 0 1 1   
            1 1 1 0                 1 1 1 0
            0 0 1 1                 0 0 1 1
            1 1 0 1                 0 0 0 1

floodFill ( 1 0 0 1     , 1, 2 ) =  0 0 0 0   
            0 1 0 0                 0 1 0 0
            0 1 0 1                 0 1 0 0
            0 0 1 1                 0 0 0 0

c c++ bit-manipulation bitwise-operators
person Philippe    schedule 31.01.2014    source източник
comment
Не съм сигурен, че разбирам примера ви, защото споменавате трети ред, индексиран с 0 (т.е. последният), който е недокоснат?   -  person Joky    schedule 31.01.2014
comment
@Joky Изходът е набор от 1 бита от входа, които са достъпни от позиция 3,2. Последният ред е недокоснат, защото и двата 1 бита са достъпни.   -  person Philippe    schedule 31.01.2014
comment
Добре сега е ясно. Когато видях предложения отговор, не бях единственият, който грешеше :)   -  person Joky    schedule 31.01.2014
comment
не, това не е добър подход, защото при запълване с наводнение трябва да започнете подрекурсия на всяка нова точка. така че това, което ще спечелите от скоростта чрез битова манипулация при запълване на ред, тогава много повече време се губи от неговото разлагане за подрекурсии за запълване на редове   -  person Spektre    schedule 31.01.2014
comment
@Jarod42 прав си, благодаря. Фиксирана.   -  person Philippe    schedule 31.01.2014
comment
@Spektre Не можете напълно да избегнете рекурсията, но надеждата е, че с битови манипулации можете да разгледате всички правилни съседи с една операция и т.н.   -  person Philippe    schedule 31.01.2014
comment
@Philippe Имах предвид, че ако направите това като универсален подход, тогава времето, изразходвано за извличане на информация за това кои точки на рекурсия трябва да бъдат извикани и кои не, обикновено е по-голямо от времето, спестено от подхода на битово изместване на запълването на реда. (Поне това е моят опит), разбира се, ако използвате само няколко случая като само един бит или нито един бит или използвате BYTE и TAB всичките 256 възможности, които биха ускорили нещата. Е, можете да ме докажете, че греша, като използвате класическия бенчмарк и битовия подход. Може да е интересно да сравним скоростите...   -  person Spektre    schedule 01.02.2014

Отговори (1)


arrow_upward
2
arrow_downward

Следват произведения:

std::vector<unsigned> floodFill(const std::vector<unsigned>& map, unsigned int row, unsigned int column)
{
    std::vector<unsigned> res(map.size() + 2); // Add 'border' to avoid special case

    res[1 + row] = (1u << column) & map[row]; // Seed point (column: right to left)

    std::vector<unsigned> last;
    do {
        last = res;

        for (std::size_t i = 0, size = map.size(); i != size; ++i) {
            res[i + 1] |= (res[i] | res[i + 2] | (res[i + 1] << 1u) | (res[i + 1] >> 1u)) & map[i];
        }
    } while (last != res);
    res.pop_back();         // remove extra border.
    res.erase(res.begin()); // remove extra border.
    return res;
}

Тествайте го: (тук използвам C++11)

int main(int argc, char *argv[])
{
    const std::vector<unsigned int> v = {9, 10, 13, 6};
    const std::vector<unsigned int> expected = {8, 8, 12, 6};
    std::vector<unsigned int> res = floodFill(v, 3, 2);

    assert(res == expected);
    assert(floodFill({3, 14, 3, 13}, 1, 1) == std::vector<unsigned int>({3, 14, 3, 1}));
    assert(floodFill({9, 4, 5, 3}, 1, 2) == std::vector<unsigned int>({0, 4, 4, 0}));
    return 0;
}
person Jarod42    schedule 31.01.2014
comment
Това изглежда доста добре! Просто се чудя как можете да използвате res[i] за разлика от last[i], когато изчислявате приноса от предишни редове, тъй като актуализирате същите редове в цикъла. - person Philippe; 31.01.2014
comment
Няма значение, изглежда, тъй като промените така или иначе са монотонни, това не е проблем. Можете дори да запазите итерация тук или там. - person Philippe; 31.01.2014
comment
@Philippe: Вярно е, че разпространявам директно промени от row[i] към row[i + 1] в същия цикъл, но това не е проблем, виждам го като оптимизация. - person Jarod42; 01.02.2014
comment
Между другото, мисля, че кодът може да бъде подобрен (избягвайте да изчислявате непроменени редове във всеки цикъл например, използвайте по-добър метод, за да видите дали има промяна, която векторът сравнява и копира...). - person Jarod42; 01.02.2014
comment
Вероятно, въпреки че в моя конкретен случай на употреба, редовете всъщност са байтове на един 64-битов неподписан. Мога да изчисля всички смени само в 8 инструкции, а сравнението е само една инструкция. - person Philippe; 01.02.2014