@gribozavr19 июл 2011 в 17:11

Вычисление простых чисел на шаблонах C++

4 мин

23K

Ненормальное программирование * C++ *

+38

Комментарии 44

@Wo1f 19 июл 2011 в 17:28

Интересно только для новичков в Шаблонах С++…

@tucnak 19 июл 2011 в 17:34

Я лично никогда не мог понять фишку шаблонов. Теперь я понял все. Спасибо

НЛО прилетело и опубликовало эту надпись здесь

@GraD_Kh 19 июл 2011 в 19:28

Проблема только в том, что подобного рода фишки в реальной жизни используются крайне редко. Что впрочем не отменяет факта, что они являются отличной разминкой для ума.

@skor 19 июл 2011 в 18:10

скорость компиляции (вычисления) можно значительно повысить в ~2 раза, если начинать проверять хотя бы с n/2:

templatestruct is_prime
{
static const bool value = is_prime_rec<n, (n+1)/2 — 1>::value;
};

@IlyaPodkopaev 20 июл 2011 в 05:52

достаточно до n^0.5

@GraD_Kh 20 июл 2011 в 05:56

Вычисление квадратного корня во время компиляции — это круто :)

@jcmvbkbc 20 июл 2011 в 10:36

Ну так а что, на тех же самых шаблонах, каким-нибудь делением пополам. Числа-то целые.

@skor 20 июл 2011 в 11:42

да, действительно несложно =)

template  struct while_f {

 template <int res, int x>

 struct calc_res {

 const static int tmp = (res+x/res)/2;

 typedef typename while_f<(res > tmp)>::template calc_res<tmp<res?tmp:res, x> a;

 static const int value = a::value;

 };

};



template <> struct while_f {

 template <int res, int x>

 struct calc_res {

 static const int value = res;

 };

};



template  struct sqrt {

 static const int value = while_f::calc_res<(x+1)/2, x>::value;

};



template <> struct sqrt<0> {

 static const int value = 0;

};



// assert(sqrt<81>::value == 9);

@jcmvbkbc 20 июл 2011 в 13:24

Я-то имел в виду что-то такое:

template<unsigned V>
struct Sqrt
{
    template<unsigned L, unsigned R>
    struct Sqrt_eval
    {
        static const unsigned M = (L + R + 1) / 2;
        static const bool D = M * M < V;
        static const bool Stop = L + 1 >= R;
        static const unsigned N = R * R > V ? L : R;
        static const unsigned value = Sqrt_eval<Stop ? N : D ? M : L, Stop ? N : D ? R : M>::value;
    };
    template<unsigned M>
    struct Sqrt_eval<M, M>
    {
        static const unsigned value = M;
    };
    static const unsigned value = Sqrt_eval<0, V>::value;
};

@skor 20 июл 2011 в 13:38

красота

@skor 20 июл 2011 в 09:20

абсолютно согласен

@jcmvbkbc 19 июл 2011 в 19:24

Шаблоны C++ позволяют обрабатывать некоторые значения параметров шаблона особым образом (частичная специализация).

Если при этом использованы все параметры шаблона, то это не частичная, а полная специализация.
«Частичность» специализации в том, что она фиксируя или вводя зависимости между какими-то параметрами шаблона оставляет и независимые шаблонные параметры, формируя шаблон с меньшим количеством параметров.

@f0rbidik 20 июл 2011 в 15:40

// Primary template
template<class T>
  class A {};

template<class T1, class T2>
  class B {};

// A's partial specialization
template<class T1, class T2>
  class A<B<T1, T2> > {};

@GraD_Kh 19 июл 2011 в 19:24

Списки типов, вычисление простых чисел на шаблонах… День Александреску на хабре?

@burjui 19 июл 2011 в 21:01

Коллеги, на минутку отодвиньте в сторонку старый, весь поросший обратной совместимостью C++, и обратите внимание на более современные языки, где не надо так извращаться. В разработке D и его стандартной библиотеки активно участвует Андрей Александреску — даже ему, мастеру template-fu, надоело плести шаблонные интриги в C++

@valerypride 19 июл 2011 в 22:04

Спасибо, но мы уж как-нибудь с С++ справимся. Да и в реальном проекте никто не даст заменить С++ на D.

@burjui 20 июл 2011 в 07:05

А я и не уговариваю бросаться писать в production на D прямо сейчас, просто призываю не стоять на месте и изучать новые технологии; можно же и для души написать что-нибудь, поиграться с языком, чтобы знать его сильные и слабые стороны. Компилятор D медленно, но верно избавляется от багов, и когда он дойдёт до кондиции — грех не попробовать этот язык в новом проекте, благо что из него выкинули львиную долю C++ных костылей, косяков и шероховатостей. Ну а если вы работаете «на дядю», и «дядя» — упрямый, то у вас выбора, конечно, нет.

@VoidEx 20 июл 2011 в 09:02

Ну D-то недалеко от C++ ушёл. Если действительно интересуют современные языки, можно посмотреть на Nemerle, Haskell, Coq, Agda2.

@burjui 20 июл 2011 в 09:18

Ну так D — язык системного программирования, а из более высокоуровневых я пока отдаю предпочтение Common Lisp и Python.
Nemerle сразу отброшу как платформозависимый (да, я знаю про mono, но: наезд Oracle на Google из-за Java, политика Microsoft), Haskell мне не нравится сильным уклоном в чистое ФП (я хочу программировать, используя разные парадигмы, и все — одинаково легко), а про остальные не слышал — посмотрю, что за звери.

@VoidEx 20 июл 2011 в 12:31

я хочу программировать, используя разные парадигмы, и все — одинаково легко

А зачем?

@ShapovalovTS 19 июл 2011 в 23:28

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

@Shedal 19 июл 2011 в 22:46

Хехе, относительно недавно была статья про вычисление факториалов схожим способом. Вообще, это довольно интересно. Спасибо за статью :)

@cblp 20 июл 2011 в 09:56

Про факториал — то классическая задачка, а это нетривиальщина уже.

@AxisPod 20 июл 2011 в 03:56

Надо реализовать решето Эратосфена :-) Правда вот на шаблонах это будет тяжко сделать.

@boxfrommars 20 июл 2011 в 10:39

тогда уж сразу Сундарама :)

@gribozavr 20 июл 2011 в 10:44

Не так уж и сложно. Нужно всего лишь передать номер простого числа, которое сейчас ищем в is_prime_rec и там перебирать все простые числа, меньшие по номеру.

@gridem 20 июл 2011 в 04:14

Мне кажется, в этой статье был мощный подтекст. А именно — сравнение со Scheme: типа посмотрите какое убожество C++ и как все красиво и понятно на функциональном языке Scheme, разбухший синтаксис с костылями в виде шаблонов против изящного функционального стиля. Хотя кому-то могут не понравиться скобки.

@sdramare 20 июл 2011 в 07:48

А Scheme в приведенных примерах тоже все считает на этапе компляции? Я честно не в курсе. Ну и лично мне красивым и понятным показался как раз вариант на С++. А в Scheme больше напрягают не скобочки, а обратная польская запись.

@EvilShadow 20 июл 2011 в 08:21

Только она не обратная.

@sdramare 20 июл 2011 в 08:23

Да, перепутал.

@burjui 20 июл 2011 в 09:49

Скобочки и префиксная запись напрягают, когда на Scheme и других диалектах Lisp не пишешь, а только теоретизируешь о них. Да и назвать шаблонную магию объёмом в несколько раз больше, чем соответствующий код на Scheme, красивой… Такой код — просто proof of concept: использовать его в повседневной разработке — бессмысленно и беспощадно.

@sdramare 20 июл 2011 в 10:43

Скобочки и префиксная запись напрягают, когда на Scheme и других диалектах Lisp не пишешь, а только теоретизируешь о них.

Не сомневаюсь. Более того, думаю, что если бы в школе меня учили писать не z=2*x + 3*y, а что-то типа (setq z (+ (* 2 x) (* 3 y))), то Scheme была бы мне близка и понятна. Что характерно, на С++ я тоже особо не пишу в последние годы, что не мешает мне спокойно читать его код.

Да и назвать шаблонную магию объёмом в несколько раз больше, чем соответствующий код на Scheme, красивой…
Ну во-первых красота измеряется не объемом. Во-вторых само понятие красоты очень субъективно, поэтому постом выше я написал «лично мне». А в-третьих, на мой взгляд, тут сравнивать не совсем корректно. Код на Scheme в статье описан в императивном стиле, а на шаблонах — в декларативном(что-то близкое к pattern matching из функциональных языков).

@gribozavr 20 июл 2011 в 10:46

Код на обоих языках в функциональном стиле. От того, что в шаблонах на C++ есть немного pattern matching, меняется способ записи, а не идея алгоритма.

@sdramare 20 июл 2011 в 10:55

Ну так про идею алгоритма я ничего и не говорил. Речь идет об отсутствии управляющих конструкций типа if в шаблоном коде статье, т.е. об элементах декларативности. Впрочем, не сомневаюсь, что и пример на Scheme можно переписать соответствующим образом.

@gribozavr 20 июл 2011 в 10:57

Тот факт, что нет явных if не делает код декларативным. Декларативным был бы код, где явно написано, что простое число это число, обладающее такими-то свойствами, и т. д. В шаблонном коде идёт перебор чисел и явная проверка этих свойств.

@sdramare 20 июл 2011 в 11:10

Смотрите, я пишу «т.е. об элементах декларативности.»
Вы отвечаете — «Тот факт, что нет явных if не делает код декларативным.»

Вам не кажется, что наши утверждения не вступают в противоречие и таким образом нет предмета спора?

@gribozavr 20 июл 2011 в 11:21

Я считаю, что тут нет даже элемента декларативности.

@sdramare 20 июл 2011 в 11:43

Ну а я и некоторые другие, считаю что pattern matching это элемент декларативности. Предлагаю на этом остановиться.

@gribozavr 20 июл 2011 в 11:53

Императивный код:

def imperative(x: Int) {
  if(x == 1) {
    println("one")
  } else if(x == 2) {
    println("two")
  } else {
    println("many")
  }
}

Лёгким движением руки:

def declarative(x: Int) = x match {
  case 1 => println("one")
  case 2 => println("two")
  case _ => println("many")
}

становится декларативным?

@sdramare 20 июл 2011 в 12:10

На самом деле да, несмотря на неудачный пример(правильней сравнить, например, разбор списка). Ибо в первом варианте вы просто описывает поток выполнения с операторами перехода. Неймон в полный рост. А во втором случает вы по сути задаете набор «предикат — значение функции». По сути описываете какая ваша функция.

Можно шагнуть чуть дальше и писать что-то типа

declarative(1) = "one"

declarative(2) = "two"

declarative(_) = "many"

@gribozavr 20 июл 2011 в 10:11

В Scheme можно вызывать произвольные функции на этапе компиляции (в том числе и пользовательские).

@gribozavr 20 июл 2011 в 09:59

Scheme был использован потому что у него семантика управляющих конструкций и модель вычислений схожа с шаблонами.

@Woodroof 16 мар 2012 в 16:26

Реализация BOOST_STATIC_ASSERT в чём-то близка к описанному, хотя уже и используется в реальных задачах.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий