Алгоритм быстрого подсчета заданных символов в строке.

[mishapk]

Подскажите Алгоритм быстрого подсчета заданных символов в строке.
Последовательно это понятно, разделить строку на несколько частей и сканировать параллельно тоже понятно.
Но может есть какой то еще более лучший способ - классический алгоритм?

[sourceman]

Боуер-Мур
http://algolist.manual.ru/search/esearch/bm.php

Быстрый поиск
http://algolist.manual.ru/search/esearch/qsearch.php

Сообщение отредактировано: sourceman - 21.09.10, 16:48

[shm]

Цитата mishapk @ 21.09.10, 14:02

Цитата mishapk @ 21.09.10, 14:02

быстрого подсчета заданных символов в строке.

Именно подсчета символов в строке, а не поиск подстроки.

1. Заводишь массив из 256 элементов (в общем виде, для конкретной задачи как правило меньше)
2. Всем клементам массива присваиваешь нули.
4. В цикле пробегаешься по всей строки для каждого найденого символа увеличивашь на 1 соответствующий элемент в массиве просчета. Т.е mas[str[i]]++;, где mas массив, str - строка, i - номер символа в строке
5. Выводишь значения счетчика из массива для нужных символов

Добавлено 21.09.10, 18:41

Цитата mishapk @ 21.09.10, 14:02

разделить строку на несколько частей и сканировать параллельно тоже понятно.

Так и разделить. Допустим надо обработать массив из 1000 элементов. В одном потоке обрабатываешь от 0 до 500, в другом от 500 до 1000, результаты суммируешь. Также см. распараллеливание вычислений (а это уже намного сложней).

[Pavia]

mishapk
Можно и быстрее но это уже зависит от архитектуры. Или если у нас есть частная задача.

[leo]

Цитата shm @ 21.09.10, 18:37

Допустим надо обработать массив из 1000 элементов

Маловато будет, т.к. пока будет создан второй поток, первый успеет по несколько раз пройтись по этим 1000 символам

Добавлено 22.09.10, 06:52
PS: Если бы речь шла о поиске одного конкретного символа, то можно было бы юзать обработку по 4 или 8 байт одновременно, как это делается в продвинутых реализациях StrLen

[shm]

Цитата leo @ 22.09.10, 06:48

Маловато будет, т.к. пока будет создан второй поток, первый успеет по несколько раз пройтись по этим 1000 символам

Ну этож понятно, я это чтобы пример проще получился

[mishapk]

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

Сообщение отредактировано: mishapk - 22.09.10, 12:20

[MIF]

ДЕлаешь как предложил shm, а потом полученные значения умножаешь на количество нулевых бит в букве и суммируешь.

[mishapk]

Я правильно понял?
символ 'a'-имеет код 97 = 1100001b то есть результат для данного символа равен 4.

[sourceman]

shm

Цитата

Именно подсчета символов в строке, а не поиск подстроки.

Это понятно, я предложил с учетом переделать

Сообщение отредактировано: sourceman - 22.09.10, 12:59

[Romtek]

Генри С. Уоррен, мл.: Алгоритмические трюки для программистов Смотри главу 5. Подсчет битов.