Эти три дня с субботы по понедельник были не очень продуктивными в плане программирования. За вечера сб и пн удалось реализовать Undo & Redo с запоминанием до 100 ходов и провести очередную небольшую оптимизацию кода. Идеи по оптимизации так спонтанно приходят - вроде ничего, ничего, а потом хоп - "а вот тут можно же..." Undo & Redo оказались в реализации сложнее, чем ожидалось. Вроде херня хернёй, а как начинаешь писать, куча неочевидных моментов всплывает. И не один я так думаю, погуглил уже ))) Это у меня ещё простой случай - однотипные элементы хранятся.
читать дальше
Пришлось создать ещё один класс - растём! Прикольно наблюдать, как при добавлении очередного класса все остальные классы тоже чуток меняются - где-то кусок кода становится самостоятельной функцией, где-то сами функции чуть меняются. Осталось реализовать ещё сохранение и может, запоминание комбинаций, чтоб не самому крутить одно и то же, а нажал кнопку и оно само. И тогда настанет время переходить к той херне, из-за чего всё и затевалось - дереву решений. Сначала я думал записать всё в базу данных - они как раз заточены под такие штуки - хранение и поиск больших массивов. Но потом подумал, хер ли? Там две таблицы всего, справимся и сами! Ведь есть же шахматные и шашечные программы, там тоже дерево решений - и они обходятся без СУБД! А щас чо-то опять подумал и приуныл - пожалуй, наверное, лучше всё-таки в БД.
Там буит три таблицы. Первая это стек состояний, которые ещё предстоит разветвить в дерево, вторая список вообще всех найденных состояний (из первой потихоньку переписываются во вторую) и третья это связи между этими состояниями (т.к. там многие-ко-многим). С первой и третьей - никаких сложностей, надо только память выделять по мере роста. А вот со второй сложности. Там будет много записей - возможно больше миллиона. Чтобы быстро вставлять - надо писать в конец, тогда массив будет несортированный, и в нём не получится быстро искать. Чтобы быстро искать - нужен сортированный массив, а если он сортированный, в него не получится быстро вставлять - надо будет перемещать элементы.
Варианты решения:
1) Сделать "хоть как-то". Да, мож линейный поиск или вставка в сортированный массив с перемещением кучи элементов за раз. Мож оно не так медленно буит работать, как кажется.
2) Запилить-таки это в базу данных
3) Погуглить и чо-то всё-таки намутить с помощью связных списков индексов и прочей херни. Всего одна сраная таблица, неужто не осилим? Может даже удастся спиздить готовый код.
4) Можно сделать промежуточный вариант - разреженный сортированный массив, он позволяет быстро вставлять в пустые места и не каждый раз перемещать алименты
Но тогда он будет занимать гораздо больше места, чем обычный.
В MFC есть класс CArray, но меня смущает, шо там чо-то может не работать сравнение для элементов, которые созданы с помощью конструктора, а у меня именно такие элементы и будут.
update: почитал я про CArray, в общем, это вариант с перемещением кучи элементов за раз. Из плюсов только то, что он сам, типа, растёт и в середину элементы вставляет сам. А сортировку надо самому делать. Зато я сам от себя офигел - залез в исходники MFC (они там прилагаются), позырил всё. Помню, в 2001м пытался я освоить всю эту хрень, читал книжку про Winapi. Там товарищ советовал читать заголовочные файлы, типа много чего можно узнать. Я посмотрел список этих файлов, погрустнел, открыл, посмотрел пару файлов и дальше этого дело не пошло. А щас чо-то чих-пых и всё ясно. Может, одно дело изучать некие заголовочные файлы хуй знает для чего - с неясными намерениями и таким же результатом, и другое - искать конкретное решение среди нескольких возможных вариантов. Когда точно известно, что надо получить, всё как-то проще становится.