Цитата(Amp @ 4.9.2012, 22:47  ) |
| даст константное время поиска адреса перехода |
не всегда. иногда может быть логарифмическое.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > быстрый, самодельный "std::map" |
| Автор: semibug 4.9.2012, 20:45 |
| Стоит задача отрисовать строку текста (UTF-8) с помощью PNG текстуры с глифами. Есть массив с описанием положения каждого глифа на текстуре. Пока работал с символами со значением до 128 проблем небыло - на этапе инициализации создавался массив с информацией по глифам, и при выводе символа его код играл роль индекса. С переходом на Unicode вариант с индексом отпадает из-за слишком больших возможных значений кода символа. Пока попробовал два варианта - в первом просто перебираю по очереди данные о глифах пока не наткнусь на нужный (брутально и некрасиво), во втором составляю std::map, и выбираю данные уже через него (и здесь видимо есть какая-то закулисная работа, требующая процессорного времени). В итоге хочу попробовать набросать простой генератор кода, который напишет большой switch () со всеми используемыми кодами unicode. Надеюсь на сообразительность компилятора. Как считаете, будет ли это самый оптимальный по производительности вариант? |
| Автор: Amp 4.9.2012, 21:31 |
| У тебя unicode и при этом ты еще на этапе компиляции знаешь какой набор символов использует программа и с каким шрифтом? То есть текстура генерируется заранее, а не динамически заполняется в процессе работы программы? |
| Автор: bsa 4.9.2012, 21:36 |
| Обычно рисуют один раз, а показывают много. Поэтому, сначала подготовь строку к выводу (например, в OpenGL можно использовать для этого display list), а уже затем выводи каждый раз. В итоге у тебя ресурсы на мэп будут тратиться только перед показом первого кадра, а все остальные будет значительно быстрее проскакивать. |
| Автор: Amp 4.9.2012, 21:47 |
| switch-case в случае, если будет оптимизация через jump/lookup-таблицы, даст константное время поиска адреса перехода. Всевозможные hashmap-ы тоже. Кстати одна из возможных оптимизаций - кэшировать текст не отдельными глифами, а прямо кусками слов. Это если текстура генерируется по ходу работы приложения. |
| Автор: bsa 4.9.2012, 22:17 | ||
не всегда. иногда может быть логарифмическое. |
| Автор: semibug 4.9.2012, 23:02 | ||||
| Ок, спасибо за ответы! Ковыряюсь в ассемблерном коде switch, пока видно, что компилятор (vs2010) довольно умело строит набор lookup-ов на последовательности и отдельные сравнения для единичных величин стоящих далеко от других.
В каких ситуациях, подскажите пожалуйста. Чтобы навсегда отбросить бредовые идеи с генератором свичей )).
Движок в моем случае черный ящик, умеет только рисовать заданые куски заданой текстуры по заданой координате ). |
| Автор: Amp 4.9.2012, 23:05 | ||
Да, наверное постоянный O(1) для целых чисел возможен, когда не требуется генерация здорового массива с "пустышками" вместо переходов на неиспользуемых индексах. Хотя задача вроде и подходит под такой частный случай, но кто его знает, как компилятор себя поведет. |
| Автор: bsa 4.9.2012, 23:10 | ||
Когда набор ключей очень разрозненный. Т.е. очень сильно друг от друга отличаются. Я тебе уже сказал, что строка формируется один раз, а отображается множество. Поэтому тебе нужно с мэпом работать только один раз при формировании строки (массива текстур), а при отображении уже использовать готовый массив текстур. |
| Автор: Amp 4.9.2012, 23:13 | ||
Учти такую вещь, что смена версии компилятора компилятора, выпущенный SP к студии может все взять и поменять. Поэтому все же лучше не стоит полагаться на оптимизации. А массив-таблицу с переходами можешь сгенерировать сам. |
| Автор: math64 5.9.2012, 07:36 | ||
Можно создать массив структур:
отсортировать его с помощь qsort а затем искать в нем с помощью bsearch. или использовать их аналоги из stl. |
| Автор: semibug 5.9.2012, 21:39 |
| Спасибо всем. Как предлагал bsa, кэширование видимо даст наиболее высокую производительность. Но что бы не требовать дополнительной памяти на кэш, оставил выбор за пользователем и сделал так: одна функция перекодирует строку Unicode во внутреннюю кодировку, которая соответствует индексам массива информации о глифах ( поиск по совету math64 ), а другая рисует уже перекодированую строку. |