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

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

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

И да, по байту будет тормозить, лучше сразу данные держать в uintptr_t.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
21.08.2019, 17:20
    #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
21.08.2019, 20:19
    #39852361
PetroNotC Sharp
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный способ посчитать позиции в битмапе?
полудух,
Критерии эффективности? Память, скорость?
Ну и с двумя циклами я не понял. Это как?
Вроде ваш код с которого начинать надо.
...
Рейтинг: 0 / 0
21.08.2019, 20:26
    #39852366
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный способ посчитать позиции в битмапе?
полудухну а так если
Это как бы не битмап вовсе, а строка ноликов и единичек, т.е. 1 байт отображает 1 бит, избыточность в 256 раз. Я бы для начала поковырял откуда это недоразумение взялось и там бы порядок навел.
...
Рейтинг: 0 / 0
21.08.2019, 20:54
    #39852376
PetroNotC Sharp
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный способ посчитать позиции в битмапе?
Dima Tполудухну а так если
Это как бы не битмап вовсе, а строка ноликов и единичек, т.е. 1 байт отображает 1 бит, избыточность в 256 раз. Я бы для начала поковырял откуда это недоразумение взялось и там бы порядок навел.+1))
...
Рейтинг: 0 / 0
21.08.2019, 21:36
    #39852385
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный способ посчитать позиции в битмапе?
Dima T1 байт отображает 1 бит, избыточность в 256 раз.

8 раз.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
21.08.2019, 21:39
    #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
21.08.2019, 21:40
    #39852388
полудух
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
самый эффективный способ посчитать позиции в битмапе?
Dima Tизбыточность в 256 раз
опять накурился

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

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

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


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