to post messages and comments.

← All posts tagged programming

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

Итак, конкурс "наверни говна^W костылей 2012" продолжается. Сегодня задумался над такой проблемой — есть у меня класс вида
class myClass {
<...>
myClass operator + (const myClass&);
<...>
};
от которого я наследую класс inhClass:
class inhClass : public myClass { <...> };
Проблема в том, что operator+ я inhClass'у переопределять не хочу, да и вообще inhClass это такой myClass только с ещё парой-другой методов. А operator+ применённый к двум inhClass'ам вовзращает мне myClass, у которого этой самой пары методов нет. Вызывать inhClass(myClass) — нехорошо, ибо конструктор повлечёт за собой копирование довольно толстых внутренних данных.
Пока что решение проблемы выглядит так:
template < class T > myClass {
<...>
T operator+ (const T&);
<...>
};

class inhClass : public myClass <inhClass> {<...>};
А this в методах myClass приводится к T* reinterpret_cast'ом, угу.

Нашёл два относительно красивых костыля для решения проблемы из #1773614. Думаю они вообще говоря боянисты, но на изобретение их в качестве велосипедов пришлось изрыть полгугла (видимо не то искал, но бесполезно) и потратить полдня.
Объясню, зачем мне хотелось получить всякие стандартные операторы — есть у меня функция вида
template < class A, class B, class Func >
void joinMap ( map < A, B >* result, const map < A, B >& other, Func join);
И этот joinMap, например, берёт и применяет join ко всем ((*result)[it->first], it->second). Возвращаясь к проблеме — на получение operator-= придётся забить, ибо невозможно. Поэтому пишется темплейтная функция T& SubEq < T > (T&, const T&) и подобные ей (естественно они пихаются в личный неймспейс для костылей). Дальнейшее решение проблемы зависит от любви пользователя к извращениям.
Вариант 1 — пилим шаблонную функцию, которая принимает какой-либо шаблонный класс и другую шаблонную функцию, и возвращает эту функцию с уже использованным шаблоном. Нечто вроде
template < class T >
T& () ( T&, const T&) getEqOperator(vector < T >, T& () ( T&, const T&) oper) { return oper; }
Конечно не помешают темплейтные тайпдефы, дабы всё это выглядело получше (а они сами по себе уже большой костыль, который реализуется через struct).
Минусы — надо напилить по функции на каждую сигнатуру. С другой стороны альтернатива мне кажется несколько более кривой.
Вариант 2 — уточняем тип параметра-функции для нашего абстрактного joinMap.
template < class A, class B >
void joinMap ( map < A, B >* result, const map < A, B >& other, B& (*join) (B&, const B&));
Работает, но ровно до тех пор, пока нам не вздумается послать в качестве join что-нибудь, не влияющее на суть, но отличное от шаблона. И к величайшему несчастью
template < class A, class B, class C >
void joinMap ( map < A, B >* result, const map < A, B >& other, C (*join) (B&, const B&));
ппочему-то мешает g++ нормально определить типы.

А где бы почитать о том, как хаскелль оптимизирует код? Хотя бы для понимания "вот этот кусок кода эффективен, а вот этот — не очень". Например я не понимаю, работает ли maximum $ map fst за один или два прохода по списку, и меня это удручает.

Сегодня завалились на четвертьфинал. Слили, что логично, ибо лузеры и нифига не готовы. Когда после олимпиады искали столовку, встретился @lexszero и сказал, что та не работает. Мы как наивные чурки поверили на слово... Как оказалось — зря.
Мораль: Пейсать код — хорошо. Верить @lexszero на слово — плохо.