|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
какой самый эффективный способ в таком битмапе: 101011101000110 определить, что 1 находится на позициях: 1,3,5,6,7,9,13,14 ? итерацией там аж 2 for + 1 if получается ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 14:29 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 14:35 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
Замени один for на таблицу масок. Никак ты не получишь N результатов быстрее чем за O(N). Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 14:36 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
забыл упомянуть, что 64 битами тут не ограничивается строка может иметь более миллиона 0/1 ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 15:18 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
ИМХО быстрее всего таблицу использовать из 256 элементов, где каждый элемент это вектор с индексами. Индекс Значение0102130 14250 2......255 0 1 2 3 4 5 6 7 Дальше побайтно прогонять через таблицу. Можно по два байта за раз, тогда таблица будет 65536 элементов. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 15:27 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
а сколько может быть индексов в таком векторе? у меня скорее наоборот - 1 вектор с индексами (но на лям индексов), а не 255 ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 16:03 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
1 байт - 8 бит, т.е. в индекс до 2^8 (0...255), в значении до 8 элементов. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 16:06 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
полудухстрока может иметь более миллиона 0/1 Сугубо всё равно, только цикл будет уже по строке, а внутри него куча if-ов по таблице масок. Плюс можно распараллелить по кускам строки. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 16:12 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakovвнутри него куча if-ов И да, по байту будет тормозить, лучше сразу данные держать в uintptr_t. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 16:17 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
ну а так если: Код: 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 17:20 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
полудух, Критерии эффективности? Память, скорость? Ну и с двумя циклами я не понял. Это как? Вроде ваш код с которого начинать надо. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 20:19 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
полудухну а так если Это как бы не битмап вовсе, а строка ноликов и единичек, т.е. 1 байт отображает 1 бит, избыточность в 256 раз. Я бы для начала поковырял откуда это недоразумение взялось и там бы порядок навел. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 20:26 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
Dima Tполудухну а так если Это как бы не битмап вовсе, а строка ноликов и единичек, т.е. 1 байт отображает 1 бит, избыточность в 256 раз. Я бы для начала поковырял откуда это недоразумение взялось и там бы порядок навел.+1)) ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 20:54 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
Dima T1 байт отображает 1 бит, избыточность в 256 раз. 8 раз. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 21:36 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
полудухну а так если: Код: 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.
Имхо неэффективно с точки зрения выделения памяти-при разных входных значениях будет теряться разное время на реалллокацию/копирование. Можете промерять время выполения на разных наборах м убедиться. Я бы сделал буфер размером с макс.длину строки и работал бы с ним(записывал/читал бы результат), и никаких stl-классов ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 21:39 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
Dima Tизбыточность в 256 раз опять накурился Я бы для начала поковырял откуда это недоразумение взялось и там бы порядок навел. отсюда порядок там не навести можно кое-что улучшить, например, ф-ю в постгрю перенести, чтобы не гонять туда огромный список ID ну и вроде всё. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 21:40 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
L.OtujktdЯ бы сделал буфер размером с макс.длину строки и работал бы с ним(записывал/читал бы результат), и никаких stl-классов вот только операция одноразовая ... |
|||
:
Нравится:
Не нравится:
|
|||
21.08.2019, 21:44 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
полудух, А ты хитрый манипулятор! С 1 поста было всем очевидно что ты подсчитываешь биты в регистре. Потом мы узнали что "аж до миллиона битов". Потом мы узнали что тебе нормлёк и строковыми операциями посчитать. А потом ты вообще проговорился что дескыть под постгрес да под интернет магазины. Ну что. Может мы сразу это перенесем в Разработку Инфо систем ? ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 01:04 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
я спрашиваю здесь, потому что тут самые эффективные алгоритмы ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 01:25 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
данные же не пересекаются написать пиксельный шейдер для видеокарты и оно те распаралелит аутоматом на все конвейеры видеокарты. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 01:47 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
полудухя спрашиваю здесь, потому что тут самые эффективные алгоритмыон прав. Эффективность всегда относительная. Вот нолики и единички в символьном виде передавать неэффективно). Согласись. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 07:16 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
Малыхин Сергей, +1)) Можно разбить стринг на куски и потоками пройтись параллельно в кусках. Странная задача, поэтому лень думать. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 07:19 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
полудух отсюда порядок там не навести можно кое-что улучшить, например, ф-ю в постгрю перенести, чтобы не гонять туда огромный список ID ну и вроде всё. Почитай про EAV модель , обычно ее для этих целей применяют. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 07:29 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
Напомнило мой топик https://www.sql.ru/forum/1242903/tyapnichnyy-poisk-tovarov-po-naboru-atributov ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 09:11 |
|
самый эффективный способ посчитать позиции в битмапе?
|
|||
---|---|---|---|
#18+
mayton, )) все в мире уже давно написанно, и решения найдены). По теме можно сказать что код выше от ТС годен к употреблению. А оптимизацию раньше времени не проводят. Нет ограничений. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.08.2019, 09:51 |
|
|
start [/forum/topic.php?fid=57&fpage=12&tid=2017579]: |
0ms |
get settings: |
10ms |
get forum list: |
13ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
27ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
60ms |
get tp. blocked users: |
2ms |
others: | 273ms |
total: | 405ms |
0 / 0 |