LINUX.ORG.RU

Менеджер ресурсов «игровой» поиск реализации/архитектуры

 , , ,


0

2

Продолжаю пилить велосипед.

Вообщем так дошло до управления ресурсами выхода два велосипедить или рыться в сторонних движках.

Предпочитаю первый вариант так как тут не код важен, а архитектура хотя и реализация тоже если найдется будет годно.

При первом варианте думается следующее.

Смотрел как делают велосипедисты на специфичных форумах и абсолютно все сводят к передачи указателя на файл, который и должен использовать пользователь, а работа менеджера сводится к предотвращению дублирования данных и выгрузке не используемых данных.

Может это так принято или удобно разрабам? Обычно делают как передают менеджеру на прямую или косвенно(конфиг например), файл, менеджер регистрирует его выделяет память загружает отдаёт указатель на объект и всё далее сам или по запросу удаляет его и при повторном запросе объекта проверяет есть ли он в индексе своём и если есть снова просто отдаёт указатель на то что уже есть.

Разраб далее работает с указателем как с объектом передавая его туда сюда.

А что если:

Переложить на плечи менеджера загрузку, выгрузку, учёт и помимо этого всего и передачу данных подсистемам.

То есть грузим ---> менеджер регистрирует, грузит, создаёт указатель заносит его в базу генерит идентификатор(просто число int) и отдаёт его разрабу.

Разраб будет иметь просто переменную с идентификатором скажем переменная int monstr. Далее передаёт её скажем рендеру render(monstr,-10,0,0); рендер передаёт значение обратно менеджеру тот ведёт поиск по идентификатору указателя на объект и уже реально передаёт настоящему рендеру косвенно или на прямую производя все необходимые операции.

Вообщем думаю ясно что я хочу нормальный менеджер, но незнаю как его спроектировать, написать то напишу, а вот спроектировать по путному не знаю как.

Жду пинков по ссылкам, примерам, статьям.

★★★★★
Ответ на: комментарий от annulen

1) Де факто поиск по хэш-значению экививалентен поиску по rb-tree, занимает O(log2(N)) и основан на половинном делении. Или Вы знаете более шустрые алгоритмы поиска по разреженному целому ключу? В unordered_map поиск оптимизирован с учетом того что ключ int, но яйцы те же, тока в профиль.

2) Да хоть список пар. Я повторю вопрос, Вы знаете алгоритм поиска по разреженному ключу работающий быстрее чем O(log2(N))?

AIv ★★★★★
()
Ответ на: комментарий от AIv

Вдогонку - учтите еще обработку коллизий.

AIv ★★★★★
()
Ответ на: комментарий от AIv

Насколько я знаю, в классической хэш-таблице осуществляется отображение i = f(x) % N, где x - ключ, f - некоторая функция (для инта обычно тождественная), N - размер таблицы (обычно простое число). В результате, разреженный интервал отображается в неперерывный, в котором поиск осуществляется за О(1). В случае коллизий все, конечно же, усложняется, но в простом случае никакого логарифма нет.

annulen ★★★★★
()
Ответ на: комментарий от annulen

Да, и еще кэширование последнего запроса в каждой из N ячеек для ускорения разрулирования коллизий. Но в unordered_map поиск половинным делением по хэшу, а в описанном Вами случае гарантированные коллизии в ячейках за счет укороченного интервала, и еще неизвестно что хуже.

ИМНО тут нужно ограничивать диапазон ID (скажем short, 2^16) и юзать обычный вектор, а пустые ID хранить в set для ускорения выделения. Если конечно ТС-у 2^16 объектов хватит;-)

AIv ★★★★★
()
Последнее исправление: AIv (всего исправлений: 1)
Ответ на: комментарий от annulen

Я не верю в чудеса. Скорей всего там что нить в этом роде и замутили...

AIv ★★★★★
()
Ответ на: комментарий от AIv

1) Де факто поиск по хэш-значению экививалентен поиску по rb-tree, занимает O(log2(N)) и основан на половинном делении.

Не знаю, откуда у вас такие факты, но у меня поиск по хешу такой:

index = hash_value % hash_table_size

Поиск получается быстрый, приложение получает указатель на объект, если тот уже загружен.
Одна «проблема» - нужна утилита, которая подготовит ресурсы и создаст файл с хешами или расскажет о коллизиях (тут уже ручная работа - тупо меняем имя ресурса, хотя можно заставить и утилиту сделать это по некому правилу).

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

Не знаю, откуда у вас такие факты

Посмотрите сырцы или потестите скорость доступа в unordered_map зависимости от числа записей. Очень поучительно.

у меня поиск по хешу такой

Если у Вас хватает свободных слотов в таблице, то нафига тут хэш таблица? Достаточно обычного вектора. Если у Вас не хватает слотов, то расскажите как Вы будете искать среди объектов с одинаковым index = hash_value % hash_table_size.

AIv ★★★★★
()
Ответ на: комментарий от anonymous

А как же коллизии?

Я же написал, как решать коллизии.

andreyu ★★★★★
()
Ответ на: комментарий от AIv

Посмотрите сырцы или потестите скорость доступа в unordered_map зависимости от числа записей. Очень поучительно.

К чему вы это вообще сказали?

Если у Вас хватает свободных слотов в таблице, то нафига тут хэш таблица? Достаточно обычного вектора.

Кто сказал, что индексы все будут идти подряд? Хеш универсальнее.

Если у Вас не хватает слотов, то расскажите как Вы будете искать среди объектов с одинаковым index = hash_value % hash_table_size.

Во-пепрвых, все это решается на этапе сборки. Во-вторых, проблему коллезий решают давно и непринужденно.

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

К чему вы это вообще сказали?

Во первых к тому, как реализован unordered_map. Во вторых, если Вы не заметили, обращения к этой таблице на чтение являются узким местом по производительности для всего проекта.

Кто сказал, что индексы все будут идти подряд? Хеш универсальнее.

А вектор кардинально быстрее. Индексы пойдут так, как их выделят, тут полна свобода, и они не обязаны идти подряд - в векторе могут быть дырки тащем то.

Во-пепрвых, все это решается на этапе сборки.

А это Вы к чему сказали O_O?

Во-вторых, проблему коллезий решают давно и непринужденно.

Как именно? И сколько такие решения стоят с т.з. производительности?

AIv ★★★★★
()
Ответ на: комментарий от AIv

Во первых к тому, как реализован unordered_map. Во вторых, если Вы не заметили, обращения к этой таблице на чтение являются узким местом по производительности для всего проекта.

Таблица не помещается в кеш?

А это Вы к чему сказали O_O?

Мы в этой ветке ведем речь о том, как организовать работу с ресурсами в движке.

Как именно? И сколько такие решения стоят с т.з. производительности?

Зависит от ситуации, но это все решается на этапе сборки.

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

Таблица не помещается в кеш?

ТС не знает сколько у него объектов. Но если таблица влезает в кэш, то однозначно это должен быть вектор.

Мы в этой ветке ведем речь о том, как организовать работу с ресурсами в движке.

Спасибо К.О. И как этому относится Ваша фраза что все решается на этапе сборки? Она применима тащем то к 99% проектов.

Зависит от ситуации, но это все решается на этапе сборки.

Вы повторяетесь. Или давайте конкретные решения по разрешению коллизий применительно к данной ситуации с оценкой их накладных расходов, или не надо ля-ля.

AIv ★★★★★
()
Ответ на: комментарий от AIv

ТС не знает сколько у него объектов. Но если таблица влезает в кэш, то однозначно это должен быть вектор.

Есть truetype. Есть текст, который использует этот фонт. Есть инпут от пользователя. Какие глифы понадобятся в данный момент не известно. Растеризовать все глифы глупо. Хранить индексы в векторе накладно. Вот тут хеш будет очень хорош. И таблица будет небольшая, и текстура минимальная.

Спасибо К.О. И как этому относится Ваша фраза что все решается на этапе сборки? Она применима тащем то к 99% проектов.

Тогда с чем вы спорите?

Вы повторяетесь. Или давайте конкретные решения по разрешению коллизий применительно к данной ситуации с оценкой их накладных расходов, или не надо ля-ля.

Вам нужны конкретно мои решения по коллизиям или общепринятые решения?

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

Хранить индексы в векторе накладно. Вот тут хеш будет очень хорош. И таблица будет небольшая, и текстура минимальная.

Следите за руками. На каждый ID, а каком бы контейнере он не лежал, требуется держать некую структура данных - состояние объекта, тип объекта и т.д. и т.п. У вектора самая большая скорость доступа, памяти под него (под не используемые ID) при известном и разумном числе объектов потребуется немного. Про кэширование - ОС лучше Вас знает что и как кэшировать. И в чем профит от хэш-таблицы, которая при отсутствии коллизий ничем не лучше вектора длиной N (кроме вызова операции %N на каждый доступ) а при наличии коллизий по сравнению с вектором аццки тормозит?

Тогда с чем вы спорите?

Мы не спорим, тем более не спорим с тем что «все решаестя на этапе сборки». Это Вы тут пропагандируете хэш-таблицы;-)

Вам нужны конкретно мои решения по коллизиям или общепринятые решения?

Мне нужны магические решения, которые обеспечивают доступ к хэш таблице с той же скоростью, что и к вектору. У Вас такие еcть?

AIv ★★★★★
()
Ответ на: комментарий от AIv

Следите за руками. На каждый ID, а каком бы контейнере он не лежал, требуется держать некую структура данных - состояние объекта, тип объекта и т.д. и т.п. У вектора самая большая скорость доступа, памяти под него (под не используемые ID) при известном и разумном числе объектов потребуется немного.

Не много? Ну-ну. Ну а теперь последите и вы за руками. Код символа в юникоде лежит в достаточно большом диапазоне. Вы предлагаете вектор для хранения этого набора. Зачем в векторе те символы, которые не используются в приложении? Каков размер вектора будет в вашем случае?

Про кэширование - ОС лучше Вас знает что и как кэшировать.

Вообще не понял, каким боком тут кеширование на уровне ОС?

а при наличии коллизий по сравнению с вектором аццки тормозит?

От коллизий нужно избавляться. Это же очевидно.

Мне нужны магические решения, которые обеспечивают доступ к хэш таблице с той же скоростью, что и к вектору. У Вас такие еcть?

Я же уже приводил свое решение выше.

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

Не много? Ну-ну. Ну а теперь последите и вы за руками. Код символа в юникоде лежит в достаточно большом диапазоне. Вы предлагаете вектор для хранения этого набора. Зачем в векторе те символы, которые не используются в приложении? Каков размер вектора будет в вашем случае?

А кто и где сказал, что в качестве ID используется код символа??? Те символы которые используются попадают в вектор (добавляются по мере использования). Те которые не используются - не попадают.

Я же уже приводил свое решение выше.

Это с hash%N? Ну и чем это лучше вектора длины N с 0<=ID<N ?

AIv ★★★★★
()
Ответ на: комментарий от AIv

А кто и где сказал, что в качестве ID используется код символа??? Те символы которые используются попадают в вектор (добавляются по мере использования). Те которые не используются - не попадают.

Ага, а в мапке хранится соответствие индекса в векторе коду символа? :)

Это с hash%N? Ну и чем это лучше вектора длины N с 0<=ID<N ?

Тем, что при ID может быть много больше N. Неужели не очевидно?

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

Ага, а в мапке хранится соответствие индекса в векторе коду символа? :)

Зачем??? ID - непосредственно индекс в векторе.

Тем, что при ID может быть много больше N. Неужели не очевидно?

Не очевидно. Если число ID много больше N имеем коллизии, и rb-tree оказывается быстрее.

AIv ★★★★★
()
Ответ на: комментарий от AIv

Да просто «товарищ не понимает»;-)

Ну пусть так. Мне от вашего мнения холоднее не стало.

Не бывает серебряных пуль, и хэш-таблицы не исключение.

Кто говорил, что хеши - это серебрянная пуля?

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

Просто я привык по нескольку раз объяснять студентам одно и то же, пока до них не дойдет;-) Меня вот удивляет, что Вы с первого раза не поняли. Или есть какие то прЫнципиальные возражения супротив вектора, не связанные с религией?

Кто говорил, что хеши - это серебрянная пуля?

А зачем же Вы тогда их не к месту лепите? Озвучьте все таки вариант данной задачи, когда хэш будет лучше вектора и лучше rb-tree. Правда интересно.

AIv ★★★★★
()
Ответ на: комментарий от AIv

Вы снова по кругу пошли. Может и студентам вы по нескольку раз поясняете не потому, что они не понимают, а потому, что что то у вас не так?

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

Вы по делу что нить можете сказать не переходя на личности, или у Вас и это «решается на этапе сборки»? Если нет - до свиданья, слив засчитан.

AIv ★★★★★
()
Ответ на: комментарий от AIv

Вы по делу что нить можете сказать не переходя на личности,

По делу и не переходя на личности я уже несколько раз говорил. Но вы ходите по кругу. Извините, но мне ваш хоровод не интересен, водите его со своими студентами.

или у Вас и это «решается на этапе сборки»?

Читайте выше.

Если нет - до свиданья, слив засчитан.

Вы преподаватель или сантехник, о каких сливах вы говорите?

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

По делу

«По делу» Вы ни слова ни сказали о разрешении коллизий, ни слова ни сказали о накладных расходах по разрешению коллизий, упорно считаете что диапазон ID обязательно превышает размер вектора (с чего Вы это взяли мне неясно), и наконец если это действительно так ни слова не сказали о том, как скорость доступа хэш таблицы с учетом разрешения коллизий соотносится с rb-tree.

Вы преподаватель или сантехник, о каких сливах вы говорите?

О Вашем балабольстве в этом треде.

AIv ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.