Оценка( критика ) кода

Здравствуйте.

Не так давно( в исторической перспективе ) товарищ Alf придумал неплохую «рубрику» «Оценка кода». Его идея мне очень понравилась, и мне тоже захотелось узнать, какого вы мнения о моём коде, что я делаю не так, и как это что-то сделать лучше.

Код — моя реализация игры «жизнь». Сначала я прочитал статью о создании игры «жизнь». В конце было предложено реализовать фичу по давлению истории. Я пытался реализовать эту фичу, но потом код разросся до таких размеров, что я решил переписать заново но уже полностью свою версию.

В общем, здесь лежит qt-проект игры.

porshe, ты хорошо подумал перед тем, как начинать тему под флагом «Оценка( критика ) кода»? ;-) Ну, тогда держись! ))

(1) Код оформлен в непривычной для меня манере, однако, всё красиво и аккуратно. Такой код приятно читать.

(2)

Сначала я прочитал статью о создании игры «жизнь».

Ты про эту статью? А комментарии к статье ты прочитал? Видимо нет. Поскольку в противном случае ты бы избежал парочки граблей. Если мы имеем ввиду разные статьи, то всё равно рекомендую прочитать статью по ссылке выше.

Грабли №1. См. первую половину комментария к статье. У тебя тоже при генерации следующего поколения изменяется текущее.

Грабли №2. Конечно, по нынешним временам и 10, и 100Кб памяти — не деньги, но заливать в историю полное состояние мира... я бы сказал, расточительно. Тем более, что в этом комментарии реализована идея гораздо более компактная: с вычислением хэша для мира и запоминанием его в истории. Реализация требует допила, но это уже другой вопрос.

(3) В main.cpp есть

const int KEY_ESC = 27;
// ...
            while ( true )
            {
                game.print();
                game.nextGeneration();
                if ( getch() == KEY_SEND )
                    break;
            }

Я что-то не понял как эти две константы соотносятся. И как это вообще работает.
Впрочем, это — мелочь.

(4) Не понравилось обильное использование исключений в коде. Исключение к месту, когда оно сигнализирует о нештатной ситуации при работе программы. Реализовывать выход из основного цикла жизни через исключение — не лучшее решение.

И это тоже ненормально:

                    catch( ... )
                    { /*Если программа зайдёт сюда. Значит координаты получились "плохими", это нормально */ }

(5) Не совсем понравилось распределение функций между классами GameMan и LifeMap.

За что отвечает GameMan? За управление процессом игры на высоком уровне.
За что отвечает LifeMap? За реализацию процесса игры на низком уровне. И, в частности, за отображение игровой ситуации на экране.

Правильно? Тогда что делают в GameMan следующие члены класса?

        char symbolLife;            //Символ, обозначающий живую клетку
        char symbolEmpty;          //Символ, обозначающий пустую клетку

Это всё должно относиться к LifeMap. И если уж каким-то боком появляется в GameMan, то только транзитом, по пути к LifeMap.

Ещё хорошо бы отправить в LifeMap и screen. Как минимум, в виде копии, дабы не передавать при отрисовке как параметр, как максимум — вообще всю отрисовку перенести в LifeMap.

(6) Зачем в LifeMap LifeMap::operator()()? Метод LifeMap::at() надёжнее. А про эффективность кода пока речи вообще нет.

Кстати, вообще вопрос очень спорный на счёт разрешения полного доступа к данным закрытого члена класса. Я бы сделал здесь «сладкую парочку» getter/setter (см. далее п.8).

(7) Косметика. В методе getLifeNeib() я бы перенёс одно условие:

//Получение количества живых соседей
int LifeMap :: getLifeNeib( size_t x, size_t y )
{
    int counter = 0;
    for ( int i = -1; i < 2; i++ ) //Цикл проходится по соседям клетки
        for ( int j = -1; j < 2; j++ )
            if ( actuallyCoord( x + i, y + j )  && ( i || j ) )  // <-- сюда
                if ( map[x+i][y+j] )                             // отсюда
                    counter++;
    return counter;
}

Поскольку первый if отвечает за допустимость проверки клетки, а второй — за подсчёт соседей. Так вроде логичнее.

Название метода LifeMap::actuallyCoord() немножко сбивает. Я бы назвал validCoord() или isValidCoord(). («actually» — 1) фактически, на самом деле, в действительности; 2) как ни странно, как ни удивительно).

Аналогичное пожелание на счёт LifeMap::clear(). Я бы назвал этот метод remove(). И добавил бы метод clear(), который только очищает поле (т.е. делает killAll).

(8) Ты не думал над идеей хранить количество живых клеток в члене класса LifeMap? И изменять это значение при изменении позиции извне через сеттер и в методе расчёта нового поколения. А то каждый раз шарашить по всему массиву для подсчёта живых клеток — как-то не очень.

(9) Ещё одно замечание к организации истории. В данном случае, вектор — не лучший выбор. Удаление первого элемента — это очень невыгодная операция для вектора. Сюда лучше подойдёт deque или list.

Вот. Вроде всё. Правда я программу не компилил и не гонял. Так что все мои вышеизложенные замечания основаны только на исходном тексте. Где-то с чем-то мог и ошибиться.

Ух ты, не ожидал такого быстрого ответа :)

ты хорошо подумал перед тем, как начинать тему под флагом «Оценка( критика ) кода»?

Да. А как ещё учиться? Просто писать код, не зная правильный ли он( пусть даже он работает ), мне кажется глупым и бессмысленным.

Код оформлен в непривычной для меня манере

А если не секрет, то что для вас привычнее?( просто, любопытства ради )

Ты про эту статью?

Статью то я читал, а вот комментарии... Впрочем, уже прочитал и понял, где ошибка.

Я что-то не понял как эти две константы соотносятся.

Никак). Я хотел реализовать выход по нажатию какой-нибудь клавиши, идеально было бы esc, но программа в упор отказывалась работать.

И это тоже ненормально:

Мне это показалось нормальным, поскольку реализовывать проверку координат, как то затруднительно, но, впрочем, вы правы.

Не совсем понравилось распределение функций между классами GameMan и LifeMap.
...
Правильно? Тогда что делают в GameMan следующие члены класса?

Ну да, правильно. Просто функция print из LifeMap в качестве параметра рисования принимала символы для живой и неживой клетки. И, как мне казалось, хранить эти символы в LifeMap было как то не логично. Поэтому они «транзитом» были в GameMan.

Зачем в LifeMap LifeMap::operator()()?

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

Я бы сделал здесь «сладкую парочку» getter/setter

Что то я не очень понял, что имеется ввиду. Доступ к клеткам или доступ ко всему полю?

В данном случае, вектор — не лучший выбор

Да, я тоже думал над этим. Но ведь deuque и list не дают доступ ко всем данным, а только к крайним, а мне нужно ко всем.

Ух ты, не ожидал такого быстрого ответа :)

Мне интересно, когда задают интересные вопросы. А тем более, когда их задают постоянные обитатели форума. Отвечать «в никуда» в 1001-й раз на вопрос «зачем надо setlocale?»... сам понимаешь.

Оформление кода в стиле VC++ — привычно, т.к. многие пользуются настройками по умолчанию.

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

На твоём оформлении у меня глаз спотыкался о пробелы вокруг сдвоенных двоеточий между именем класса и именем метода (это совсем нестандартное оформление). И ещё, но в гораздо меньшей степени, о пробелы между круглыми скобками и текстом внутри них.

Но, повторюсь, это дело вкуса и привычки. Твой код вполне читабелен.

А если ориентироваться на будущее, на работу программером в большой софтверной компании, то там в каждой конторе свои корпоративные стандарты разной степени жёсткости. Не угадаешь.

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

Заметил. Но не стал на это реагировать, поскольку решил, что ты планируешь дальнейшее развитие программы. Иначе зачем в GameMan 10 открытых методов, когда реально ты используешь 4? Если же дальнейшего развития не планируется, то лучше не увеличивать энтропию вселенной и не писать лишнего кода.

Дело в том, что классы я старался реализовывать, не привязывая их к конкретной задаче.

В этом нужен творческий подход. Если ты делаешь библиотеку для общего пользования (например, библиотеку векторной алгебры), то там, конечно, надо предусматривать функционал по максимуму. А в данном случае у тебя есть два сугубо специализированных класса, которые ни кто и никогда не будет использовать где-либо ещё. Эти классы у тебя априори привязаны к конкретной задаче. Значит и спроектировать их нужно так, что бы они были «необходимы и достаточны» для решения конкретной задачи. Но, с другой стороны, желательно, что бы классы были спроектированы так, что бы допускали возможность беспроблемной модификации и наращивание функционала. Так что тоже думать надо.

Я бы сделал здесь «сладкую парочку» getter/setter

Что то я не очень понял, что имеется ввиду. Доступ к клеткам или доступ ко всему полю?

Доступ ко всему полю. Но доступ контролируемый. Сейчас у тебя через operator()() и at() сделан доступ неконтролируемый: вернули ссылку на клетку — и делай с ней что хочешь.

Я бы сделал вместо этих методов два других:

    bool getCell(size_t x, size_t y) const  throw(LMOutOfRange);
    void setCell(size_t x, size_t y, bool newValue) throw(LMOutOfRange);

Тогда, посредством этих методов, а также, предложенного мной, clear() (который killAll) и calculate() можно будет чётко контролировать количество живых клеток на каждое поколение. См. п.8 предыдущего поста. Да и аккуратнее будет иметь контролируемый доступ к информации, хранящейся в закрытом члене класса.

Но ведь deuque и list не дают доступ ко всем данным, а только к крайним, а мне нужно ко всем.

Ошибаешься.

Дек (deque) — вообще очень похож на вектор, за исключением того, что вектор имеет начало, а дек начала не имеет. Т.е. с обоими концами «массива» можно работать. Но, говорят, дек чуть медленнее вектора.

Для list тоже нет ограничения доступа ко всем данным. Просто для того, что бы добраться до n-ного члена, нужно просмотреть предшествующие n-1 членов. А ты этим собственно и занимаешься: последовательным перебором объектов в контейнере, хотя адресуешься к ним (сейчас!) через произвольный доступ.

porshe, а хочешь я тебе совсем мозг порушу? ;-)

Как тебе идея написать «Жизнь» для бесконечного (ну или почти бесконечного, скажем, long long) игрового поля? И что бы на экране отображалось «окно», которое можно было бы перемещать (нажатиями клавиш управления курсором) по игровому полю для наблюдения за жизнью «Жизни».

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

Кстати, код в книге Дейтела тоже так оформлен.

Грабли №2

Я тут, кстати, подумал над хэшированием. Если я правильно понял суть этой штуки, то всё поле можно занести в массив типа int, и устанавливать биты в 1, если данная точка содержит в себе живую клетку и в 0 в противном случае. Так получим экономию памяти, но мне кажется, что так же в придачу мы получим плохо переносимый код + долгое время хэширования\дехэширования. А я этого не хочу. Как ещё можно сделать хэш? ( или я ничего не понимаю в хэшировании? )

Просто для того, что бы добраться до n-ного члена, нужно просмотреть предшествующие n-1 членов

Это как? Единственные методы доступа, которые я вижу в справочнике это front и back, которые предоставляют доступ только к первому и последнему элементу. Или это делается при помощи итераторов?

Как тебе идея...

Неплохая идея, только мне надо подумать, как это реализовать. И вообще, возможно ли такое в консольном режиме?

Между тем, большое спасибо за ответы.

Я тут, кстати, подумал над хэшированием. Если я правильно понял суть этой штуки, ... ( или я ничего не понимаю в хэшировании? )

Вот, вот последняя мысль была правильной.

Хеширование (иногда «хэширование», англ. hashing) — преобразование по определённому алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины.
Цитата из Википедии.

Там ещё много чего интересного написано по этому поводу. Рекомендую почитать эту статью и далее по ссылкам.

Я в своей реализации использовал в виде «битовой строки фиксированной длины» значение типа unsigned int и достаточно слабенькую хэш-функцию. Но ни кто не мешает использовать и более длинную битовую последовательность, и более продвинутую хэш-функцию.

«Дехэширование» невозможно. Хэширование — необратимый процесс.

Смысл в том, что каждой позиции игры «Жизнь» ставится в соответствие некое значение (хэш-код). Если позиции совпадают, то и хэш-коды равны. А восстановить позицию по хэшу — невозможно.

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

Это как? Единственные методы доступа, которые я вижу в справочнике это front и back, которые предоставляют доступ только к первому и последнему элементу. Или это делается при помощи итераторов?

<про list> Истину глаголишь. Именно при помощи итераторов.

Неплохая идея, только мне надо подумать, как это реализовать. И вообще, возможно ли такое в консольном режиме?

(1) Идея не моя.
(2) Реализовать возможно.
(3) А при чём тут консольный режим? Если с масштабированием не заморачиваться, всё решается достаточно просто.

для бесконечного (ну или почти бесконечного, скажем, long long) игрового поля

Стоп, а как в память влезет, в случае long long, 0xFFFFFFFFFFFFFFFF*0xFFFFFFFFFFFFFFFF байт под карту( размер bool ).

Стоп, а как

Во! Вот над этим-то и стоит подумать ;-)

Во! Вот над этим-то и стоит подумать ;-)

Первое, что приходит в голову, это использовать операции над битами, но после небольших расчётов становиться ясно, что это не подходит. Или всё-таки как-то можно?

Второе, немного поискав в интернете по запросу «хранение больших объёмов данных», нашёл такое понятие, как разреженная матрица, то есть хранить координаты только живых клеток. Но опять же при большом количестве живых клеток, может получиться,что память закончится( получается, что на хранение информации об одной живой клетке, мы будем тратить sizeof(long long)*2 байт, то есть 16 байт ).

Улучшить разреженную матрицу можно так: хранить массив массивов, в каждый массив будет содержать в себе индексы тех элементов, значение которых != 0. Правда, опять же при большом количестве живых клеток, память, скорее всего, закончится :(

Отлично! Именно хранить координаты только живых клеток. Молодец! И ведь как быстро накопал решение.

Конфликт интересов бесконечного (поля) и конечного (памяти) конечно когда-то будет наступать. Это естественно.

Но при найденном тобой решении

(1) Реализация очень большого поля возможна.

(2) Память будет заканчиваться достаточно редко, если не создавать экстремальные ситуации искусственно. Как показывают наблюдения (а может кто-то и теоретически обосновал) за конечным полем, даже при плотном начальном посеве через какое-то время остаётся в живых только небольшая часть клеток.

С массивом массивов, не очень понял, что ты имел ввиду. Но в этом твоём описании я не увидел где хранятся сами координаты. Ещё в одном массиве?

С массивом массивов, не очень понял, что ты имел ввиду

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

То есть, как то так:

typedef unsigned long long lsize_t;

vector<lsize_t> *map;

...
map = new vector<lsize_t>[n_size];
//Теперь в map[i] будем хранить индексы живых клеток только для строки i

Во-первых, я бы предложил использовать signed long long. Тогда точка с координатами (0, 0) попадает аккурат в середину поля. А от нуля как-то проще плясать. Хотя это и не принципиально.

Во-вторых, в твоём эскизе кода чему равно n_size?

Во-вторых, в твоём эскизе кода чему равно n_size?

Количество строк. То есть та же функция, что и в первом варианте LifeMap у nSize.

Т.е. n_size равно наибольшему числу типа unsigned long long? Не хреновый получается вектор!

Не хреновый получается вектор!

А, ну да :\

У меня появился вопрос:
Как организовать хеш-функцию? Если запихивать всё в одну переменную, допустим её тип будет unnsigned long long, то при размерах карты( от (0X0) до (0xFFFFFFFFFFFFFFFF X 0xFFFFFFFFFFFFFFFF) ) ставиться ясно, что вероятность так называемых коллизий становится велика. То есть такую функцию использовать уже будет нельзя:

//map - список живых точек. lsize_t - unsigned long long
lsize_t LifeMap::getHash() const
    {
        lsize_t hash = 0;
        hash = nSize-0xFEF;
        hash &= mSize-0xABC;
        for ( std::list<coord>::const_iterator it = map.begin(); it != map.end(); it++ )
            hash ^= ~(std::max(it->x, it->y) * (std::max(it->x, it->y) - std::min(it->x, it->y))) | 0xF0;
        return hash;
    }

Нужно ли придумывать свой тип для хеша или как то всё таки возможно обойтись подобной хеш-функцией?

Свой тип надёжной хэш-функции придумывать не надо — всё уже придумано. Покопайся в Википедии. Ссылку я уже давал. Там внизу страницы есть ссылки на хэш-функции.

Вероятность коллизий не так велика, как тебе кажется. Да, размеры поля велики, но размер истории относительно мал.

По твоему варианту хэш-функции:

(1) Подмешивать в хэш размеры поля не надо. Они не изменяются от позиции к позиции.

(2) Выражение std::max(it->x, it->y) * (std::max(it->x, it->y) легко может давать переполнение. Это, фактически, квадрат большей из двух координат.

Вообще, сейчас ты решаешь очень второстепенный вопрос. Можно и без истории обойтись.

Действительно важный вопрос: как генерировать новое поколение. Поскольку сейчас у тебя список только живых клеток, то умертвление клеток достаточно тривиально (вопрос только в скорости). А вот рождение новых — проблема. При хранении полного поля было всё просто: для каждой пустой клетки проверяем соседей. Конечно для очень большого поля тоже так можно сделать (вопрос времени, да и такое решение «в лоб» не интересно), а для бесконечного поля так нельзя сделать в принципе. Значит надо осматривать только окрестности живых клеток.