powered by simpleCommunicator - 2.0.58     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / самый эффективный способ посчитать позиции в битмапе?
25 сообщений из 85, страница 1 из 4
самый эффективный способ посчитать позиции в битмапе?
    #39852135
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
какой самый эффективный способ в таком битмапе: 101011101000110
определить, что 1 находится на позициях: 1,3,5,6,7,9,13,14
?
итерацией там аж 2 for + 1 if получается
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852140
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852142
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Замени один for на таблицу масок. Никак ты не получишь N результатов быстрее чем за O(N).
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852168
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
забыл упомянуть, что 64 битами тут не ограничивается
строка может иметь более миллиона 0/1
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852177
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ИМХО быстрее всего таблицу использовать из 256 элементов, где каждый элемент это вектор с индексами.
Индекс Значение0102130 14250 2......255 0 1 2 3 4 5 6 7
Дальше побайтно прогонять через таблицу.

Можно по два байта за раз, тогда таблица будет 65536 элементов.
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852198
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
а сколько может быть индексов в таком векторе?
у меня скорее наоборот - 1 вектор с индексами (но на лям индексов), а не 255
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852200
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
1 байт - 8 бит, т.е. в индекс до 2^8 (0...255), в значении до 8 элементов.
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852203
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
полудухстрока может иметь более миллиона 0/1

Сугубо всё равно, только цикл будет уже по строке, а внутри него куча if-ов по таблице
масок. Плюс можно распараллелить по кускам строки.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852212
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakovвнутри него куча if-ов

И да, по байту будет тормозить, лучше сразу данные держать в uintptr_t.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852277
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ну а так если:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
vector<int> cnt_num_f_str01(string &str01)
{
    int cnt = 1;
    vector<int> idV;
    for (char &c : str01)
    {
//      cout << c << ' ' << cnt << endl;
        if (c == '1')   {idV.push_back(cnt);}
        ++cnt;
    }

    return idV;
}

//##############################################################################
int main(int argc, char *argv[])
{
    system("clear");

    string str = "010101010101";
    cnt_num_f_str01(str);

    return 0;
}
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852361
PetroNotC Sharp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
полудух,
Критерии эффективности? Память, скорость?
Ну и с двумя циклами я не понял. Это как?
Вроде ваш код с которого начинать надо.
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852366
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
полудухну а так если
Это как бы не битмап вовсе, а строка ноликов и единичек, т.е. 1 байт отображает 1 бит, избыточность в 256 раз. Я бы для начала поковырял откуда это недоразумение взялось и там бы порядок навел.
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852376
PetroNotC Sharp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima Tполудухну а так если
Это как бы не битмап вовсе, а строка ноликов и единичек, т.е. 1 байт отображает 1 бит, избыточность в 256 раз. Я бы для начала поковырял откуда это недоразумение взялось и там бы порядок навел.+1))
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852385
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T1 байт отображает 1 бит, избыточность в 256 раз.

8 раз.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852387
L.Otujktd
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
полудухну а так если:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
vector<int> cnt_num_f_str01(string &str01)
{
    int cnt = 1;
    vector<int> idV;
    for (char &c : str01)
    {
//      cout << c << ' ' << cnt << endl;
        if (c == '1')   {idV.push_back(cnt);}
        ++cnt;
    }

    return idV;
}

//##############################################################################
int main(int argc, char *argv[])
{
    system("clear");

    string str = "010101010101";
    cnt_num_f_str01(str);

    return 0;
}


Имхо неэффективно с точки зрения выделения памяти-при разных входных значениях будет теряться разное время на реалллокацию/копирование. Можете промерять время выполения на разных наборах м убедиться. Я бы сделал буфер размером с макс.длину строки и работал бы с ним(записывал/читал бы результат), и никаких stl-классов
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852388
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima Tизбыточность в 256 раз
опять накурился

Я бы для начала поковырял откуда это недоразумение взялось и там бы порядок навел.
отсюда
порядок там не навести
можно кое-что улучшить, например, ф-ю в постгрю перенести, чтобы не гонять туда огромный список ID
ну и вроде всё.
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852389
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
L.OtujktdЯ бы сделал буфер размером с макс.длину строки и работал бы с ним(записывал/читал бы результат), и никаких stl-классов
вот только операция одноразовая
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852441
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
полудух,

А ты хитрый манипулятор! С 1 поста было всем очевидно что ты подсчитываешь биты в регистре.
Потом мы узнали что "аж до миллиона битов". Потом мы узнали что тебе нормлёк и строковыми
операциями посчитать. А потом ты вообще проговорился что дескыть под постгрес да под интернет
магазины.

Ну что. Может мы сразу это перенесем в Разработку Инфо систем ?
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852443
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
я спрашиваю здесь, потому что тут самые эффективные алгоритмы
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852444
Фотография Малыхин Сергей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
данные же не пересекаются написать пиксельный шейдер для видеокарты и оно те распаралелит аутоматом на все конвейеры видеокарты.
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852463
PetroNotC Sharp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
полудухя спрашиваю здесь, потому что тут самые эффективные алгоритмыон прав. Эффективность всегда относительная.
Вот нолики и единички в символьном виде передавать неэффективно). Согласись.
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852464
PetroNotC Sharp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Малыхин Сергей,
+1))
Можно разбить стринг на куски и потоками пройтись параллельно в кусках.
Странная задача, поэтому лень думать.
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852466
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
полудух отсюда
порядок там не навести
можно кое-что улучшить, например, ф-ю в постгрю перенести, чтобы не гонять туда огромный список ID
ну и вроде всё.
Почитай про EAV модель , обычно ее для этих целей применяют.
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852499
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
самый эффективный способ посчитать позиции в битмапе?
    #39852523
PetroNotC Sharp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
)) все в мире уже давно написанно, и решения найдены).
По теме можно сказать что код выше от ТС годен к употреблению.
А оптимизацию раньше времени не проводят. Нет ограничений.
...
Рейтинг: 0 / 0
25 сообщений из 85, страница 1 из 4
Форумы / C++ [игнор отключен] [закрыт для гостей] / самый эффективный способ посчитать позиции в битмапе?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]