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

ProgramBox

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

Post author:admin
Запись опубликована:16 апреля, 2023
Post category:Вопросы по программированию

#c #algorithm #data-structures #game-boy-advance

#c #алгоритм #структуры данных #game-boy-advance

Вопрос:

Мне нужна некоторая помощь в реализации более быстрого способа выполнения полного сдвига в двумерном массиве.

Моя проблема в том, что у меня есть двумерный массив, содержащий данные карты игры. Эта игра похожа на Geometry Dash, но на Game Boy Advance. Пока у меня есть карта, которая выглядит примерно так:

 int map1[9][40] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 0, 0 },
    {0, 0, 0, 0, 2, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0 },
    {0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
    {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 },
};

Но чтобы прочитать эту карту, я должен перебрать каждый отдельный элемент и посмотреть, следует ли его выводить на экран (x> = 0 amp;amp; x <= screen_width).

Немного подумав, я думаю, мне следует использовать двусвязный список. Таким образом, я мог бы изменить список, переместив узел заголовка в трейлер, а затем просто нарисовать данные первых 15 узлов (или около того). Будет ли это улучшением производительности по сравнению с циклическим перебором каждого элемента в 2D-массиве? Хотя циклическое прохождение не обязательно является недостатком производительности, снижающим производительность игры, я действительно хочу ее оптимизировать.

Если да, то как бы мне реализовать этот двусвязный список, содержащий те же данные, что и 2d-массив?

1. Если все ячейки представлены в одинаковом размере (количество пикселей на ячейку = постоянное) Я не понимаю, почему вам было бы лучше использовать список, чем массив. Представьте прямоугольник над двумерным массивом, который отображает область карты, подлежащую визуализации. Тогда все, что вам нужно, — это top,left,right,bottom индексы этого прямоугольника. И затем вы можете выполнить цикл только по этим ячейкам в массиве карты.

2. Кажется, я неправильно понимаю ваш подход. Я понимаю, что вы намерены прочитать весь массив и с условием решить, выводить его или нет. Не было бы намного проще просто настроить ваши циклы так, чтобы они охватывали только ту часть, которая выполняла бы условие?

3. Вау, я даже не подумал об этом. Спасибо!

Ответ №1:

Во-первых, использование двусвязного списка ухудшит производительность. Ваш текущий подход — самый быстрый, который приходит мне на ум прямо сейчас. Сначала вам нужно понять, как массивы и как связанные списки работают под капотом. Что касается массивов, я бы настоятельно рекомендовал вам посмотреть это 5-минутное видео, потому что объяснение этого в тексте заняло бы слишком много времени. После того, как вы поняли, как работают массивы, вам нужно сравнить его со связанным списком. При доступе к элементу в массиве все, что компьютер делает, это просто увеличивает адрес памяти на индекс, умноженный на размер типа массива, а затем удаляет ссылку на этот адрес. При доступе или, лучше сказать, циклическом просмотре связанного списка вы сделаете гораздо больше. Сначала вы удаляете ссылку на элемент, затем обрабатываете данные, затем смотрите, имеет ли следующий элемент значение NULL, затем вы переходите к следующему элементу, удаляете ссылку на него и так далее.

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

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

 struct LinkedList {
    struct LinkedList* data;
    struct LinkedList* prev;
    struct LinkedList* next;

prev и next будут просто указателями на предыдущий и следующий элемент. Где в качестве данных будут фактические данные.

Вот рисунок, который, надеюсь, объяснит, что я имею в виду:

Таким образом, в целом ваш метод синтаксического анализа лучше, чем связанный список. Однако я думаю, что самым быстрым синтаксическим анализом был бы синтаксический анализ на лету.