Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / C++ Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl      все
 самый эффективный способ посчитать позиции в битмапе?  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 935
какой самый эффективный способ в таком битмапе: 101011101000110
определить, что 1 находится на позициях: 1,3,5,6,7,9,13,14
?
итерацией там аж 2 for + 1 if получается
21 авг 19, 14:29    [21954450]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
Dima T
Member

Откуда:
Сообщений: 14078
Выбирай
21 авг 19, 14:35    [21954462]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48611

Замени один for на таблицу масок. Никак ты не получишь N результатов быстрее чем за O(N).

Posted via ActualForum NNTP Server 1.5

21 авг 19, 14:36    [21954464]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 935
забыл упомянуть, что 64 битами тут не ограничивается
строка может иметь более миллиона 0/1
21 авг 19, 15:18    [21954520]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
Dima T
Member

Откуда:
Сообщений: 14078
ИМХО быстрее всего таблицу использовать из 256 элементов, где каждый элемент это вектор с индексами.
Индекс Значение
0
10
21
30 1
42
50 2
......
255 0 1 2 3 4 5 6 7

Дальше побайтно прогонять через таблицу.

Можно по два байта за раз, тогда таблица будет 65536 элементов.
21 авг 19, 15:27    [21954534]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 935
а сколько может быть индексов в таком векторе?
у меня скорее наоборот - 1 вектор с индексами (но на лям индексов), а не 255
21 авг 19, 16:03    [21954562]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
Dima T
Member

Откуда:
Сообщений: 14078
1 байт - 8 бит, т.е. в индекс до 2^8 (0...255), в значении до 8 элементов.
21 авг 19, 16:06    [21954565]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48611

полудух
строка может иметь более миллиона 0/1

Сугубо всё равно, только цикл будет уже по строке, а внутри него куча if-ов по таблице
масок. Плюс можно распараллелить по кускам строки.

Posted via ActualForum NNTP Server 1.5

21 авг 19, 16:12    [21954572]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48611

Dimitry Sibiryakov
внутри него куча if-ов

И да, по байту будет тормозить, лучше сразу данные держать в uintptr_t.

Posted via ActualForum NNTP Server 1.5

21 авг 19, 16:17    [21954584]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 935
ну а так если:
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;
}
21 авг 19, 17:20    [21954674]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
PetroNotC Sharp
Member

Откуда:
Сообщений: 2446
полудух,
Критерии эффективности? Память, скорость?
Ну и с двумя циклами я не понял. Это как?
Вроде ваш код с которого начинать надо.
21 авг 19, 20:19    [21954814]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
Dima T
Member

Откуда:
Сообщений: 14078
полудух
ну а так если

Это как бы не битмап вовсе, а строка ноликов и единичек, т.е. 1 байт отображает 1 бит, избыточность в 256 раз. Я бы для начала поковырял откуда это недоразумение взялось и там бы порядок навел.
21 авг 19, 20:26    [21954820]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
PetroNotC Sharp
Member

Откуда:
Сообщений: 2446
Dima T
полудух
ну а так если

Это как бы не битмап вовсе, а строка ноликов и единичек, т.е. 1 байт отображает 1 бит, избыточность в 256 раз. Я бы для начала поковырял откуда это недоразумение взялось и там бы порядок навел.
+1))
21 авг 19, 20:54    [21954842]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48611

Dima T
1 байт отображает 1 бит, избыточность в 256 раз.

8 раз.

Posted via ActualForum NNTP Server 1.5

21 авг 19, 21:36    [21954860]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
L.Otujktd
Member

Откуда:
Сообщений: 81
полудух
ну а так если:
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-классов
21 авг 19, 21:39    [21954862]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 935
Dima T
избыточность в 256 раз

опять накурился Картинка с другого сайта.
Я бы для начала поковырял откуда это недоразумение взялось и там бы порядок навел.

отсюда
порядок там не навести
можно кое-что улучшить, например, ф-ю в постгрю перенести, чтобы не гонять туда огромный список ID
ну и вроде всё.
21 авг 19, 21:40    [21954863]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 935
L.Otujktd
Я бы сделал буфер размером с макс.длину строки и работал бы с ним(записывал/читал бы результат), и никаких stl-классов

вот только операция одноразовая
21 авг 19, 21:44    [21954865]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
mayton
Member

Откуда: loopback
Сообщений: 42861
полудух,

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

Ну что. Может мы сразу это перенесем в Разработку Инфо систем ?
22 авг 19, 01:04    [21954956]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 935
я спрашиваю здесь, потому что тут самые эффективные алгоритмы
22 авг 19, 01:25    [21954958]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
Малыхин Сергей
Member

Откуда: г. Курск
Сообщений: 729
данные же не пересекаются написать пиксельный шейдер для видеокарты и оно те распаралелит аутоматом на все конвейеры видеокарты.
22 авг 19, 01:47    [21954960]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
PetroNotC Sharp
Member

Откуда:
Сообщений: 2446
полудух
я спрашиваю здесь, потому что тут самые эффективные алгоритмы
он прав. Эффективность всегда относительная.
Вот нолики и единички в символьном виде передавать неэффективно). Согласись.
22 авг 19, 07:16    [21954997]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
PetroNotC Sharp
Member

Откуда:
Сообщений: 2446
Малыхин Сергей,
+1))
Можно разбить стринг на куски и потоками пройтись параллельно в кусках.
Странная задача, поэтому лень думать.
22 авг 19, 07:19    [21954998]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
Dima T
Member

Откуда:
Сообщений: 14078
полудух
отсюда
порядок там не навести
можно кое-что улучшить, например, ф-ю в постгрю перенести, чтобы не гонять туда огромный список ID
ну и вроде всё.

Почитай про EAV модель, обычно ее для этих целей применяют.
22 авг 19, 07:29    [21955000]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
mayton
Member

Откуда: loopback
Сообщений: 42861
Напомнило мой топик https://www.sql.ru/forum/1242903/tyapnichnyy-poisk-tovarov-po-naboru-atributov
22 авг 19, 09:11    [21955054]     Ответить | Цитировать Сообщить модератору
 Re: самый эффективный способ посчитать позиции в битмапе?  [new]
PetroNotC Sharp
Member

Откуда:
Сообщений: 2446
mayton,
)) все в мире уже давно написанно, и решения найдены).
По теме можно сказать что код выше от ТС годен к употреблению.
А оптимизацию раньше времени не проводят. Нет ограничений.
22 авг 19, 09:51    [21955098]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl      все
Все форумы / C++ Ответить