| Вопрос: Оптимизация, морской бой, List<T> | Добавлено: 09.05.12 21:04 |
Автор вопроса:  Programmer
|
|
Добрый день!
Подскажите, может быть есть более оптимальное решение моей задачи. Сетевая многопользовательская игра. Игровое поле делится на ячейки аля морской бой. Размер одной ячейки - максимальная дистанция видимости. Каждая ячейка содержит список объектов, находящихся внутри неё. Естественно, активны только те ячейки, в которых в данный момент времени находятся объекты. При перемещение объекта, когда он выходит за границы текущей ячейки, он удаляется из её списка и добавляется в список "новой". Так вот, каждая ячейка отправляет данные о объектах внутри неё на удаленный компьютер случайно выбранного игрока (для проверки "кого он видит на радаре" - это достаточно ресурсоёмкая задача). Кроме того, каждая ячейка имеет список объектов, которые находятся в соседних ячейках. Это нужно для корректного определения зоны видимости, когда на компьютере "эмулятора" объект находится на границе ячейки. Фактически, "эмулятор" одной ячейки видит объекты этой и всех соседних ячеек, но производит обработку только для главной, центральной ячейки. Суть вопроса в том, что внутри каждой ячейки у меня есть List<T>, где я храню список объектов-соседей. Так вот, судя по профайлеру, большинство ресурсов ЦП (79% от общего расхода) уходит на удаление элемента из списка. Очень бы хотелось это оптимизировать. Может быть, за счет памяти? Только как? |
| Ответы | Всего ответов: 17 |
|
Номер ответа: 1 Автор ответа:  EROS Вопросов: 58 Ответов: 4255  |
Профиль | | #1 | Добавлено: 09.05.12 23:42 |
| Если объектов много то используй Dictionary или HashSet<T>, там удаление вообще ничего не будет стоить.. | ||
|
Номер ответа: 2 Автор ответа: AgentFireICQ: 192496851 Вопросов: 75 Ответов: 3178 |
Профиль | | #2 | Добавлено: 10.05.12 10:05 |
|
Точно, как раз за счет памяти, HashSet будет давать максимальную скорость удаления элемента из списка.
Но, возможно, нужно переработать всю систему. Ты уверен, о профессиональный программер на VB, что нужно именно к каждой ячейке присобачить список? Можно чуть проще - иметь Dictionary<Cell, HashSet<T>>, но что-то мне подсказывает, что можно лучше. |
||
|
Номер ответа: 3 Автор ответа: Programmer Вопросов: 71 Ответов: 246 |
Профиль | | #3 | Добавлено: 10.05.12 15:24 |
AgentFire, это было в прошлом 
Я нашел довольно хитрый способ, как не присобачивать список к каждой ячейке. Это было нужно для присвивания новых идентификаторов для каждого объекта, чтобы удаленный игрок не мог узнать по id, какие объекты он "эмулирует". Теперь каждая ячейка имеет фиктивные идентификаторы (8 штук), которые используются в зависимости от делимости координат текущей ячейки на 2. А что ты можешь посоветовать? Я кое-что уже переделал, думаю, получилось оптимально. И все-таки, интересно, что скажешь ты... |
||
|
Номер ответа: 4 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #4 | Добавлено: 10.05.12 16:09 |
|
Стооп, Dictionary и правда быстрее! Насколько я знаю, внутри List<T> обычный массив. Судя по всему, тормоза при удалении элемента от того, что он сдвигает полмассива на элемент выше. А Dictionary этого не делает.
Спасибо. |
||
|
Номер ответа: 5 Автор ответа: AgentFireICQ: 192496851 Вопросов: 75 Ответов: 3178 |
Профиль | | #5 | Добавлено: 10.05.12 17:26 |
| Что было в прошлом? Профессиональность? | ||
|
Номер ответа: 6 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #6 | Добавлено: 10.05.12 18:22 |
|
AgentFire, к чему этот троллинг? Да, было, что я так про себя говорил.
К слову, на VB я уже ничего не делаю, а сайт vbcoding продал. Может быть, вернемся к теме топика? |
||
|
Номер ответа: 7 Автор ответа: EROSВопросов: 58 Ответов: 4255 |
Профиль | | #7 | Добавлено: 10.05.12 20:04 |
|
Разве сравнение хешей (который представляют собой int) при удалении элемента будет происходить быстрее, чем сравнение указателей на объекты (те же самые int-ы)?
Там дело не только в хешах, но и в алгоритме поиска нужного элемента и механизме удаления. В любом случае это будет на порядок быстрее чем работа с листом. Но несравнимо большее ускорение дает правильное проектирование и оптимизация логики и алгоритмов. Советую копать именно в эту сторону.. |
||
|
Номер ответа: 8 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #8 | Добавлено: 10.05.12 23:44 |
|
Я посмотрел как в Mono устроен Dictionary: там используется хэш таблица, индекс в которой вычисляется как остаток от деления хэша объекта на количество элементов таблицы.
Вообще, "исследование" устройства Mono полезно для общего развития
У Вас есть какие-то конкретные мысли по поводу архитектуры, которую я описал в шапке? Что бы Вы посоветовали почитать на тему проектирования? |
||
|
Номер ответа: 9 Автор ответа: AgentFireICQ: 192496851 Вопросов: 75 Ответов: 3178 |
Профиль | | #9 | Добавлено: 11.05.12 09:38 |
|
Programmer пишет:
А что, уже не профессиональный чтоль?
Да, было, что я так про себя говорил. Programmer пишет:
Есть.. и есть несколько вопросов. Ячейки то у тебя квадратные? И все поле - квадрат? Или что, хексагон? ..
У Вас есть какие-то конкретные мысли по поводу архитектуры, которую я описал в шапке? |
||
|
Номер ответа: 10 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #10 | Добавлено: 11.05.12 11:57 |
| Вообще куб, а не квадрат. Все поле бесконечное, так как в один момент могут существовать ячейки на любом удалении друг от друга, но между ними будет пустота. | ||
|
Номер ответа: 11 Автор ответа: AgentFireICQ: 192496851 Вопросов: 75 Ответов: 3178 |
Профиль | | #11 | Добавлено: 11.05.12 17:18 |
| ндо, ну тогда графы, графы .. ) | ||
|
Номер ответа: 12 Автор ответа: ProgrammerВопросов: 71 Ответов: 246 |
Профиль | | #12 | Добавлено: 11.05.12 18:56 |
| ээ? а конкретнее? | ||
|
Номер ответа: 13 Автор ответа: AgentFireICQ: 192496851 Вопросов: 75 Ответов: 3178 |
Профиль | | #13 | Добавлено: 11.05.12 20:29 |
| Ну, по сути ты все правильно делаешь. У каждой "клетки" хешсет из того, что в ней находится. | ||
|
Номер ответа: 14 Автор ответа: ArtyomРазработчик Вопросов: 130 Ответов: 6602 |
Профиль | | #14 | Добавлено: 13.05.12 12:04 |
| о, на митуй затусили эксперты в области архитектуры и алгоритмов | ||
|
Номер ответа: 15 Автор ответа: ArtyomРазработчик Вопросов: 130 Ответов: 6602 |
Профиль | | #15 | Добавлено: 13.05.12 12:32 |
|
по поводу скорости работы всего этого...
List.Add выполняется за O(1) времени. List.Insert за O(n) List.Remove за O(n) Dictionary.Add, Dictionary.Remove, Dictionary.TryGetValue, Dictionary.ContainsKey а также индексатор Dictionary[...] работают за O(1) времени. Dictionary.ContainsValue работает за O(n) времени. HashSet.Add, HashSet.Remove, HashSet.Contains - O(1). O(1) занчит что время фиксировано и практически не зависит от количества элементов в наборе (на практике, конечно, зависит, но не так сильно как с случае O(n). Более того O(1) будет достигнут только если хеш-функций, применяемая к ключам, будет хорошо работать. Если посчитаные хеши будут очень часто повторятсяь, то скорость работы сильно упадет. Programmer пишет:
Разве сравнение хешей (который представляют собой int) при удалении элемента будет происходить быстрее, чем сравнение указателей на объекты (те же самые int-ы)? Во-первых, указатели на объекты это не int'ы. Это IntPtr. И если длина int 4 байта, то длина IntPtr это 4 или 8 байт, в зависимости от архитектуры (32-битная или 64-битная). Во-вторых, никаких сравнений хешей не выполняется. Хеш считается один раз за любую операцию. Причем если метод GetHashCode не переопределен, то для ссылочных типов хеш даже не считается, а берется готовый, это вообще не занимает никаокго времени. Programmer пишет:
Я посмотрел как в Mono устроен Dictionary: там используется хэш таблица, индекс в которой вычисляется как остаток от деления хэша объекта на количество элементов таблицы. Вообще, "исследование" устройства Mono полезно для общего развития OMG если б открытое сообщество не сделало Mono, то Microsoft бы не откуда было копипастить код в .NET Framework. Для общего развития могу посоветовать исследовать устройство самого .NET Framework, его исходники внезапно были открыты еще со 2-й версии. А также читать документацию на него же, тем более там расписана скорость выполнения операций там где ее уместно указывать. |
||