Отражение в C++
Просто хочу прояснить, что хвостовая рекурсия не имеет ничего общего с тем, что делает вторую программу быстрой. Ниже я переписываю вашу первую программу, чтобы использовать правильный хвостовой вызов, и мы сравниваем время выполнения со второй программой. Я также переписал этот, потому что он может быть несколько упрощен -
fib1 n = slow n id
where
slow 0 k = k 0
slow 1 k = k 1
slow n k = slow (n - 1) (\a ->
slow (n - 2) (\b ->
k (a + b)))
fib2 n = fast n 0 1
where
fast 0 a _ = a
fast n a b = fast (n - 1) b (a + b)
Воздействие на крошечные числа, такие как n = 10 незначительно -
fib1 10
-- 55
-- (0.01 secs, 138,264 bytes)
fib2 10
-- 55
-- (0.01 secs, 71,440 bytes)
Но даже вокруг n = 20 мы замечаем огромный спад в fib1 производительности -
fib1 20
-- 6765
-- (0.70 secs, 8,787,320 bytes)
fib2 20
-- 6765
-- (0.01 secs, 76,192 bytes)
В n = 30, воздействие смешно. Обе программы все еще достигают одного и того же результата, так что это хорошо, но fib1 занимает более 30 секунд. fib2 все еще занимает долю секунды -
fib1 30
-- 832040
-- (32.91 secs, 1,072,371,488 bytes) LOL so bad
fib2 30
-- 832040 (0.09 secs, 80,944 bytes)
Причина этого в том, что первая программа, fib1, делает два рекурсивных вызова. Процесс для этой функции использует экспоненциальное время и пространство по мере роста n. В n = 30 медленная программа выполнит 1 073 741 824 (2 30 ) рекурсивных вызова. Быстрая программа будет повторяться только 30 раз.
На n = 1000 мы столкнулись с серьезной проблемой с fib1. Основываясь на производительности fib1 30, мы оцениваем, что потребуется 1.041082353242204e286 лет для завершения 2 1000 рекурсивных вызовов. Между тем, fib2 1000 легко обрабатывает 1000 рекурсий -
fib2 1000
-- 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
-- (0.13 secs, 661,016 bytes)
Исходное переписывание вашей первой программы может быть затруднено с добавленным параметром k. Использование Cont позволяет нам увидеть четкую последовательность шагов в знакомой нотации Хаскелла do -
import Control.Monad.Cont
fib1 n = runCont (slow n) id
where
slow 0 = return 0
slow 1 = return 1
slow n = do
a <- slow (n - 1)
b <- slow (n - 2)
return (a + b)
8 ответов
Если вы ищете совершенно общий способ манипулирования объектами во время выполнения, когда вы не знаете их типы во время компиляции в C ++, вам необходимо:
- Определить интерфейс ( абстрактный базовый класс со всеми чистыми виртуальными методами и без членов) для каждой возможности, которую может поддерживать класс.
- Каждый класс должен наследовать практически от всех интерфейсов, которые он хочет реализовать (возможно, среди других классов).
Теперь предположим, что pFoo содержит указатель интерфейса типа IFoo * на некоторый объект x (вам не нужно знать конкретный тип x ). Вы можете увидеть, поддерживает ли этот объект интерфейс IBar , сказав:
if (IBar* pBar = dynamic_cast<IBar*>(pFoo)) {
// Do stuff using pBar here
pBar->endWorldHunger();
} else {
// Object doesn't support the interface: degrade gracefully
pFoo->grinStupidly();
}
Этот подход предполагает, что вы знаете все соответствующие интерфейсы во время компиляции - если вы этого не сделаете, вы выиграете » В любом случае нельзя использовать обычный синтаксис C ++ для вызова методов. Но трудно представить ситуацию, когда вызывающая программа не знает, какие интерфейсы ей нужны - я могу думать только о том, что вы хотите открыть объекты C ++ через интерактивный интерпретатор. Даже в этом случае вы можете разработать (уродливый, требующий больших затрат времени на обслуживание) способ впихнуть это в приведенную выше парадигму, чтобы методы можно было вызывать, указав их имена и аргументы в виде строк.
Другой аспект, который следует учитывать, - это создание объекта . Чтобы достичь этого без знания конкретных типов, вам понадобится фабричная функция, а также уникальные идентификаторы для классов, чтобы указать, какой конкретный класс вам нужен. Можно организовать регистрацию классов в глобальной фабрике при запуске, , как описано здесь экспертом по C ++ Хербом Саттером - это позволяет избежать поддержки гигантского оператора switch , что значительно упрощает обслуживание. Можно использовать одну фабрику, хотя это подразумевает, что существует единый интерфейс, который должен реализовывать каждый объект в вашей системе (фабрика вернет указатель или ссылку на этот тип интерфейса).
В конце дня, то, что вы получаете, в основном (изоморфно) COM - dynamic_cast выполняет ту же работу, что и QueryInterface (IID_IFoo) , а базовый интерфейс, реализованный всеми объектами, эквивалентен IUnknown .
Поскольку стандарт C ++ не охватывает такое понятие, как «метаданные», не существует переносимого (для разных компиляторов и платформ, если на то пошло) метода отражения во время выполнения, кроме уже упомянутого RTTI.
В C ++ существует также возможность отражения во время компиляции (подумайте boost :: type_traits и boost :: type_of ), но она также ограничена по сравнению, скажем, с Nemerle или LISP.
Большинство основных фреймворков (MFC, Qt и т. Д.) Позволяют извлекать метаинформацию во время выполнения, но для их работы требуются всевозможные специальные аннотации (см. RUNTIME_CLASS et al. al в качестве примера).
Посмотрите мой ответ на аналогичный вопрос . Оба предложенных решения (XRTTI и OpenC ++) основаны на внешних инструментах, которые генерируют метаданные отражения для вас в процессе сборки.
Вам необходимо использовать шаблон посетителя. Любой класс, который может быть отражен, должен унаследовать базовый класс, который дал ему функцию-член Reflect , которая будет принимать класс посетителя. Затем функция Reflect будет передавать посетителю информацию или возможности других членов.
Многие популярные библиотеки используют этот шаблон для конкретных случаев, например, функция Serialize в MFC делает это, но специально для сериализации.
Вы, вероятно, могли бы разработать систему таким образом, чтобы посетитель мог выполнять динамические вызовы функций-членов, получать или устанавливать значения элементов-данных и т. д. Но это было бы ответственность каждого класса за поддержание функции Reflect , написанной от руки,
RTTI - это решение (как вы думаете, какой части Java нет в RTTI?), в противном случае вы можете реализовать свою собственную объектную структуру - пусть каждый ваш собственный объект C ++ наследует некоторый интерфейс отражения, и тогда он должен работать.
Отражение это процесс, с помощью которого компьютерная программа может наблюдать и изменять свою собственную структуру и поведение. Я не понимаю, как можно отражать в C ++. RTTI полезен только для типа данных объекта в памяти во время выполнения.
если все, что вы используете для этого, это внедрение зависимостей (реализация некоторого интерфейса ^ H ^ H ^ H ^ H ^ H ^ чистый абстрактный класс), вы можете попробовать динамическую загрузку .dll или файлы .so, которые содержат текущую реализацию для любого подключаемого модуля.
Вероятно, просто цепляние за соломинку, так как это не сработает для нескольких реализаций вещей одновременно.
Что вам нужно делать в C ++ и с какой платформой вы работаете? Я знаю один способ получить полные определения классов и вызывать функции, используя эти данные, он работает в Windows, но я не знаю о других платформах. Идея состоит в том, чтобы взять данные из таблицы экспорта DLL или exe. Это непросто - нам потребовалось несколько месяцев работы, чтобы получить достойную реализацию, - но она сделает все, что делают языки, поддерживающие отражение.