Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 153, средняя оценка - 4.83
Evg
Эксперт CАвтор FAQ
17411 / 5649 / 355
Регистрация: 30.03.2009
Сообщений: 15,465
Записей в блоге: 26
#1

Что такое compile-time алгоритмы и для чего они нужны? - C++

28.12.2011, 14:54. Просмотров 18627. Ответов 45
Метки нет (Все метки)

Цитата Сообщение от niXman Посмотреть сообщение
compile-time алгоритмы
А есть от них хоть какая-то практическая польза? По-моему нет
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2011, 14:54     Что такое compile-time алгоритмы и для чего они нужны?
Посмотрите здесь:

C++ Что такое hash-таблицы, и зачем они нужны?
C++ Compile-time алгоритмы. сборник
C++ Что за векторы и зачем они нужны
Что такое полис и конечные автоматы и для чего используются в с++? C++
Битовые поля структур: что такое и зачем они нужны? C++
C++ Что такое h -файл и obj-файл?Зачем они нужны?
Что такое векторы, и для чего нужны? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
28.12.2011, 15:02     Что такое compile-time алгоритмы и для чего они нужны? #2
Evg, Во всем есть польза, смотря как это использовать.
Ради примера : http://www.boost.org/doc/libs/1_48_0...tml/ratio.html
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.12.2011, 15:18     Что такое compile-time алгоритмы и для чего они нужны? #3
Цитата Сообщение от Evg Посмотреть сообщение
есть от них хоть какая-то практическая польза? По-моему нет
ну ты чего?.. как же без компайл-тайм в двух случаях?:
1. алгоритмы оперирующие типами.
2. вынесение ран-тайм задач оперирующих константными данными в компайл-тайм.

Добавлено через 1 минуту
Цитата Сообщение от ForEveR Посмотреть сообщение
Во всем есть польза
тут еще нужно уметь мыслить типами, а не значениями.
Evg
Эксперт CАвтор FAQ
17411 / 5649 / 355
Регистрация: 30.03.2009
Сообщений: 15,465
Записей в блоге: 26
28.12.2011, 15:24  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #4
Цитата Сообщение от ForEveR Посмотреть сообщение
Evg, Во всем есть польза, смотря как это использовать.
Ради примера : http://www.boost.org/doc/libs/1_48_0...tml/ratio.html
Если честно, я не понял, что это пример демонстрирует

Цитата Сообщение от niXman Посмотреть сообщение
ну ты чего?.. как же без компайл-тайм в двух случаях?:
1. алгоритмы оперирующие типами.
2. вынесение ран-тайм задач оперирующих константными данными в компайл-тайм.

Добавлено через 1 минуту

тут еще нужно уметь мыслить типами, а не значениями.
Давай всё-таки не путать писюн с гусиной шеей. Не надо мне рассказывать про полезность шаблонов. Я говорю лишь об алгоритмах, которые через хитроумно написанные шаблоны что-то, зависящее от констант, превращают в другие константы. Какая от этого практическая польза? Желательно с примерами
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
28.12.2011, 15:48     Что такое compile-time алгоритмы и для чего они нужны? #5
Evg,
http://habrahabr.ru/blogs/cpp/86651/

Где-то видео некий большой проект с огромным кол-вом использования буста, в частности mpl/fusion. Ссылку не найду.

Но в продакшне mpl довольно редко используется, что есть то есть.

Добавлено через 8 минут
Пример использования как раз mpl-а есть в либе Arabica - С++ обертка над разными xml-парсерами,
схема DOM, поддержка XSLT, Xpath.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#ifdef HAVE_BOOST
template <typename BaseT, typename DefaultT, typename T0, typename T1>
struct get_param
{
  typedef typename boost::mpl::if_<
      boost::is_base_and_derived<BaseT, T0>
      , T0
      , typename boost::mpl::if_<
            boost::is_base_and_derived<BaseT, T1>
          , T1
          , DefaultT
        >::type
    >::type type;
}; // get_param
#else
Используется к примеру так.

C++
1
2
3
4
5
6
7
8
template <typename string_type, typename T0, typename T1>
struct get_string_adaptor
{
  typedef typename get_param<Locale::string_adaptor_tag, 
                             Locale::default_string_adaptor<string_type>, 
                             T0, 
                             T1>::type type;
};
Таким образом нам пофигу каким параметром передавать адаптер для работы со строками, хоть в первом, хоть во втором, а можем и вообще не передавать (используя структуру nil_t).
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.12.2011, 16:02     Что такое compile-time алгоритмы и для чего они нужны? #6
Цитата Сообщение от Evg Посмотреть сообщение
об алгоритмах, которые через хитроумно написанные шаблоны что-то, зависящее от констант, превращают в другие константы.
в одном моем проекте распределенной сети вычислительных единиц, я использовал компайл-тайм генерацию хеш сумм имен процедур для того, чтоб эту хеш сумму использовать в mpl::map<> для получения типа сериализатора/десериализатора для каждой конкретной процедуры.

можно было это все перенести в ран-тайм, но тогда бы пришлось столкнуться с двумя проблемами:
1. снижение производительности.
2. отлов ошибок в ран-тайм. что не очень приятно.

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

Добавлено через 4 минуты
еще, меня постоянно веселят записи в чьем-то коде типа "var = sqrt(1.7)"
спрашивается, для чего постоянно считать значение, если оно неизменно?
Evg
Эксперт CАвтор FAQ
17411 / 5649 / 355
Регистрация: 30.03.2009
Сообщений: 15,465
Записей в блоге: 26
28.12.2011, 16:13  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #7
ForEveR, из всего того, что ты привёл, я не увидел того, что является compile-time алгоритмом в том смысле, в котором его понимает ТС (если я правильно его понял). "Технология, построенная на шаблонах" и "compile-time алгоритмы, построенные на шаблонах" - это как бэ две разные вещи

Цитата Сообщение от niXman Посмотреть сообщение
1. снижение производительности
На сколько сотых долей процента это дело ускорило работу программы?

Цитата Сообщение от niXman Посмотреть сообщение
2. отлов ошибок в ран-тайм. что не очень приятно.
Отлов ошибок в наношаблоных алогритмах, которые как бы чего-то считают в compile-time - ещё более сложная задача, потому что этот процесс работы компилятора ты не можешь ни оттрасировать, ни отладочными печатами пощупать

Все эти алогритмы работают исключительно в случаях, когда одну константу надо перевести в другую, что на практике используется редко, потому как на практике обычно работают с заранее неизвестными величинами. А редкие случаи с константами, на мой взгляд, не дадут существенного прироста. А потому мне кажется, что вместо того, чтобы извращаться с шабонами, можно делать по простому, чтобы это вычислялось в run-time, но зато было понятно и просто.

Единственный полезный случай, который с ходу лезет в голову - это вычисление инициализатора для const переменных. Очень часто хочется сделать так, чтобы записать что-то в переменную один раз и чтобы больше переменную не менять. Для автоматических переменных это всё нормально рулится квалификатором const, а вот для статических не всегда получается. При этом бывают случаи, что значение переменной в приницпе можно было бы вот через такие пляски с бубнами вычислить. Но а других полезных практических применений я с ходу не вижу.

Добавлено через 50 секунд
Цитата Сообщение от niXman Посмотреть сообщение
еще, меня постоянно веселят записи в чьем-то коде типа "var = sqrt(1.7)"
спрашивается, для чего постоянно считать значение, если оно неизменно?
И как же это сделать через compile-time алгоритмы?
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.12.2011, 16:18     Что такое compile-time алгоритмы и для чего они нужны? #8
почитай Александреску.

Добавлено через 1 минуту
Цитата Сообщение от Evg Посмотреть сообщение
И как же это сделать через compile-time алгоритмы?
соответствующим шаблоном.
вот только записываться это будет как "var = sqrt<1,7>::value"

Добавлено через 51 секунду
Цитата Сообщение от Evg Посмотреть сообщение
На сколько сотых долей процента это дело ускорило работу программы?
на 6 процентов.

Добавлено через 39 секунд
Цитата Сообщение от Evg Посмотреть сообщение
Отлов ошибок в наношаблоных алогритмах, которые как бы чего-то считают в compile-time - ещё более сложная задача
но это делается один раз при написании шаблона. а не каждый раз при его использовании.
Evg
Эксперт CАвтор FAQ
17411 / 5649 / 355
Регистрация: 30.03.2009
Сообщений: 15,465
Записей в блоге: 26
28.12.2011, 16:20  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #9
Цитата Сообщение от niXman Посмотреть сообщение
соответствующим шаблоном.
вот только записываться это будет как "var = sqrt<1,7>::value"
А готовый пример написать можно?

Цитата Сообщение от niXman Посмотреть сообщение
на 6 процентов
На каком интервале времени? Если 6% на времени в 1 секунду, то это не показатель, если 6% на времени исполнения в 1 час, то тут речь может идти только о плохой первоначальной реализации

Добавлено через 48 секунд
Цитата Сообщение от niXman Посмотреть сообщение
но это делается один раз при написании шаблона. а не каждый раз при его использовании
Ой не факт... Вполне можно доизголяться до того, что при одних константах у тебя будет нормально работать, а при других будет работать ненормально. Да и run-time принормальной работе тоже делается только один раз
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.12.2011, 16:30     Что такое compile-time алгоритмы и для чего они нужны? #10
Цитата Сообщение от Evg Посмотреть сообщение
На каком интервале времени? Если 6% на времени в 1 секунду, то это не показатель, если 6% на времени исполнения в 1 час, то тут речь может идти только о плохой первоначальной реализации
в 1 секунду.
дело в том, что каждый узел сети имеет производительность на пустых операциях - ~740 000. теперь это значение умнож на два(запрос/ответ).

изначально в реализации я использовать std::map<>. затраты на получения конкретного сериализатора/десериализатора составляли 13 процентов. при замене его на std::unordered_map<> затраты составили 6 процентов. с компайл-тайм картой - 0 процентов.

Добавлено через 1 минуту
Цитата Сообщение от Evg Посмотреть сообщение
при одних константах у тебя будет нормально работать, а при других будет работать ненормально.
ну дык! шаблон значит криво закожен. (если мы все еще о нем)

Добавлено через 2 минуты
Цитата Сообщение от Evg Посмотреть сообщение
А готовый пример написать можно?
сходу не получится. ибо нужно продумать способ сохранения лидирующих нулей в обеих составляющих...
Evg
Эксперт CАвтор FAQ
17411 / 5649 / 355
Регистрация: 30.03.2009
Сообщений: 15,465
Записей в блоге: 26
28.12.2011, 16:37  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #11
Цитата Сообщение от niXman Посмотреть сообщение
в 1 секунду
Не показатель. Это всего лишь говорит о том, что в программе слишком маленькая полезная нагрузка. Т.е. условно говоря можно сравнить коды

C
1
x = sqrt (4.0);
и

C
1
x = 2.0;
и сказать, что подстановка константы ускорила программу в сотни раз. Но проблема в том, что такой фрагмент кода он вычисляется всего лишь один раз и в большой длинной программе стократная разница времени работы этих двух фрагментов будет не ощутима.

Кстати, ты так и не написал кода с compile-time вычислением корня

Цитата Сообщение от niXman Посмотреть сообщение
ну дык! шаблон значит криво закожен. (если мы все еще о нем)
А чем принципиально отличается криво закоженный шаблон от криво закоженного run-time алогритма? По-моему ничем
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.12.2011, 16:37     Что такое compile-time алгоритмы и для чего они нужны? #12
Evg, если кратко: посмотри на этот список. как ты думаешь, этому нет применения?
Evg
Эксперт CАвтор FAQ
17411 / 5649 / 355
Регистрация: 30.03.2009
Сообщений: 15,465
Записей в блоге: 26
28.12.2011, 16:39  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #13
Цитата Сообщение от niXman Посмотреть сообщение
сходу не получится. ибо нужно продумать способ сохранения лидирующих нулей в обеих составляющих...
Ну вот о чём и я. Зачем извращаться и из принципа что-то делать в compile-time, когда по простому это можно сделать в run-time. Благо язык Си++ тут даёт больше возможностей, чем Си

Добавлено через 32 секунды
Цитата Сообщение от niXman Посмотреть сообщение
Evg, если кратко: посмотри на этот список. как ты думаешь, этому нет применения?
Там нет compile-time алгоритмов

Добавлено через 55 секунд
Если я правильно понимаю твой термин "compile-time алгоритм"
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.12.2011, 16:39     Что такое compile-time алгоритмы и для чего они нужны? #14
Цитата Сообщение от Evg Посмотреть сообщение
ты так и не написал кода с compile-time вычислением корня
читай предыдущий пост.

Цитата Сообщение от Evg Посмотреть сообщение
чем принципиально отличается криво закоженный шаблон от криво закоженного run-time алогритма?
тем что шаблон пишется один раз, а используется множество раз. а т.к. существует проверка в компайл-тайм, то при ошибке использования ты и получишь ошибку компиляции, а не в ран-тайм.
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
28.12.2011, 16:40     Что такое compile-time алгоритмы и для чего они нужны? #15
Evg, http://habrahabr.ru/blogs/cpp/124963/ на тему корня.
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.12.2011, 16:42     Что такое compile-time алгоритмы и для чего они нужны? #16
Цитата Сообщение от Evg Посмотреть сообщение
Там нет compile-time алгоритмов
Добавлено через 55 секунд
Если я правильно понимаю твой термин "compile-time алгоритм"
mpl::find() не алгоритм?
а std::find() тоже не алгоритм?

Добавлено через 49 секунд
ForEveR, спасибо за ссылку.
Evg
Эксперт CАвтор FAQ
17411 / 5649 / 355
Регистрация: 30.03.2009
Сообщений: 15,465
Записей в блоге: 26
28.12.2011, 16:44  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #17
Цитата Сообщение от niXman Посмотреть сообщение
тем что шаблон пишется один раз, а используется множество раз. а т.к. существует проверка в компайл-тайм, то при ошибке использования ты и получишь ошибку при компиляции, а не при запуске
Только при извращённо написанной системе шаблонов ты,особенно если ты не автор этого изврата, долго будешь пытаться понять, из-за чего возникла ошибка. Потому что здесь можно только прощёлкать всё это в уме и никак нельзя оттрасировать, чего можно было бы в случае compile-time'а. К тому же область того, что реализуемо через compile-time алгоритмы, она ну очень узкая, а всё это через run-time алогритмы будет выглядеть не в пример проще.
niXman
Эксперт C++
3134 / 1446 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.12.2011, 16:50     Что такое compile-time алгоритмы и для чего они нужны? #18
Цитата Сообщение от Evg Посмотреть сообщение
при извращённо написанной системе шаблонов ты,особенно если ты не автор этого изврата, долго будешь пытаться понять, из-за чего возникла ошибка.
это субъективно.

Цитата Сообщение от Evg Посмотреть сообщение
Потому что здесь можно только прощёлкать всё это в уме и никак нельзя оттрасировать, чего можно было бы в случае compile-time'а.
ну ты знаешь, без юнит тестирования сейчас вообще никак. что для ран-там, что для компайл-тайм.
Evg
Эксперт CАвтор FAQ
17411 / 5649 / 355
Регистрация: 30.03.2009
Сообщений: 15,465
Записей в блоге: 26
28.12.2011, 16:57  [ТС]     Что такое compile-time алгоритмы и для чего они нужны? #19
Цитата Сообщение от ForEveR Посмотреть сообщение
Evg, http://habrahabr.ru/blogs/cpp/124963/ на тему корня.
Если не затруднит, из всего этого напиши ГОТОВЫЙ ТЕСТОВЫЙ ПРИМЕР, который можно скопилировать и запустить.

Цитата Сообщение от niXman Посмотреть сообщение
mpl::find() не алгоритм?
а std::find() тоже не алгоритм?
А они compile-time? Я просто не большой специалист в Си++, но, насколько я это понимаю, compiletime'ность относится только к типам, а не к константам, что есть "технология", а не "алгоритм". Даже если и compile-time, то опять-таки какая от них польза там, где все структуры данных динамические (т.е. появляются лишь в процессе испольнения программы). А ведь именно такими являются подавляющее большинство задач

Добавлено через 5 минут
Цитата Сообщение от niXman Посмотреть сообщение
ну ты знаешь, без юнит тестирования сейчас вообще никак. что для ран-там, что для компайл-тайм
На у тогда зачем делать сложным то, что можно сделать простым. Вернее зачем - это понятно. Я написал про переменные const (ну или элементы enum'а, что принципиальной разницы не имеет). Но это очень узкое место, в том плане, что многого на нём не сэкономишь.

Ну а то, что практической пользы нет - я это я погорячился. Польза, конечно, есть, но, на мой взгляд, очень не большая и в очень редких случаях оно действительно обосновано
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.12.2011, 17:01     Что такое compile-time алгоритмы и для чего они нужны?
Еще ссылки по теме:

C++ Compile - time алгоритмы
C++ .elf и для чего они нужны
Allocator_traits propagate_on_container_ - для чего они нужны C++
C++ Compile-time и run-time методы и функции
Культура оформления кода: что такое enum? Где, когда и для чего уместно применять этот тип? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
28.12.2011, 17:01     Что такое compile-time алгоритмы и для чего они нужны? #20
Evg,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
 
template <int64_t A, int64_t B>
struct rational_t
{
  const static int64_t a = A, b = B;
  static double get() { return (double)a/b; }
};
 
#define RATIONAL(A1, A2) rational_t<(int)(A1##A2), pow<10, sizeof(#A2)-1>::value>
 
template <int V, unsigned D>
struct pow
{
  const static int value = V * pow<V, D - 1>::value;
};
template <int V>
struct pow<V, 0>
{
  const static int value = 1;
};
 
template <class R>
struct require_reduce
{
  const static int64_t max = (1ll<<31);
  const static bool value = (R::a >= max) || (R::b >= max);
};
 
template<bool, class R>
struct reduce_accurate;
 
template <bool, class R>
struct reduce_inaccurate
{
  typedef rational_t<(R::a >> 1), (R::b >> 1)> type_;
  typedef typename reduce_accurate<require_reduce<type_>::value, type_>::type type;
};
 
template <class R>
struct reduce_inaccurate<false, R>
{
  typedef R type;
};
 
template <int64_t m, int64_t n>
struct gcd;
template <int64_t a>
struct gcd<a, 0>
{
  static const int64_t value = a;
};
template <int64_t a, int64_t b>
struct gcd
{
  static const int64_t value = gcd<b, a % b>::value;
};
 
 
template <bool, class R>
struct reduce_accurate
{
   const static int64_t new_a = R::a / gcd<R::a, R::b>::value;
   const static int64_t new_b = R::b / gcd<R::a, R::b>::value;
 
   typedef rational_t<new_a, new_b> new_type;
   typedef typename reduce_inaccurate<require_reduce<new_type>::value, new_type>::type type;
};
 
template <class R>
struct reduce_accurate<false, R>
{
  typedef typename reduce_inaccurate<require_reduce<R>::value, R>::type type;
};
 
template <class R>
struct reduce
{
   typedef typename reduce_accurate<require_reduce<R>::value, R>::type type;
};
 
template <class R1, class R2>
struct plus
{
  typedef rational_t<R1::a * R2::b + R2::a * R1::b, R1::b * R2::b> type1;
  typedef typename reduce<type1>::type type;
};
 
template <class R1, class R2>
struct minus
{
  typedef rational_t<R1::a * R2::b - R2::a * R1::b, R1::b * R2::b> type1;
  typedef typename reduce<type1>::type type;
};
template <class R1, class R2>
struct mult
{
  typedef rational_t<R1::a * R2::a, R1::b * R2::b> type1;
  typedef typename reduce<type1>::type type;
};
template <class R1, class R2>
struct divide
{
  typedef rational_t<R1::a * R2::b, R1::b * R2::a> type1;
  typedef typename reduce<type1>::type type;
};
 
template <int64_t p, class res, class x>
struct sqrt_eval
{
  typedef typename divide<x, res>::type t1;
  typedef typename plus<res, t1>::type t2;
  typedef typename divide<t2, rational_t<2,1> >::type tmp;
  typedef typename sqrt_eval<p-1, tmp, x>::type type;
};
template <class res, class x>
struct sqrt_eval<0, res, x>
{
  typedef res type;
};
 
template <class x>
struct sqrt
{
  typedef typename divide< typename plus<x, rational_t<1,1> >::type, rational_t<2,1> >::type res;
  typedef typename sqrt_eval<15, res, x>::type type;
};
template <int64_t a>
struct sqrt< rational_t<0, a> >
{
  static const int64_t value = 0;
};
 
int main()
{
   std::cout.precision(15);
   const double s = sqrt<RATIONAL(2, 0)>::type::get();
   std::cout << s << std::endl;
   const double t = sqrt<RATIONAL(1, 75)>::type::get();
   std::cout << t << std::endl;
}
Yandex
Объявления
28.12.2011, 17:01     Что такое compile-time алгоритмы и для чего они нужны?
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru