Программирование для математиков: класс Polynomial

[photon]

Потом я открыл ваш CppVector.pdf. Это ужас какой-то.

Совет использования векторов не ограничивался заменой аргумента в конструкторе. Если решили пользоваться векторами, то пользуйтесь полноценно, а не лепите одно с другим:

Используется синтаксис C++

Polynomial::Polynomial(const std::vector<double>& V): simpleCopy(false)
 {unsigned sz = V.size();
   if(!sz)
    {deg = 0;
     coef = NULL;
     return; 
    } 
  deg = sz - 1; 
///// Watcom 
   coef = (double *)malloc(sz * sizeof(double)); 
   memcpy(coef, (void *)V.begin(), sz * sizeof(double));
/////
  Cut0();
 } 

Во-первых, если вы переходите на векторы, то никаких malloc и memcopy - сделайте ваши coef тоже вектором и десять строк кода заменится двумя строками, во-вторых, в приведенном коде просто ошибка - в случае непустого входного вектора вы заходите в if, а должно быть наоборот. Кстати, как по мне, это дурной тон писать if(!sz), когда можно написать if(0 != sz) или if(!V.empty()).

Далее, вы рассуждаете об опасности-безопасности, что, дескать, векторы дают те же возможности по выстрелу себе в ногу. Но это не так, при правильном их использовании:
во-первых, вы полностью освобождаетесь от необходимости контролировать выделение и очистку памяти, в отличие от вашего подхода, где забытое высвобождение памяти приведет к утечке; во-вторых, у вас появляется возможность в большинстве случаев не обращаться к элементам массива по индексам, а даже если такая необходимость возникла, то края - они всегда под рукой, встроены в вектор - вы в каждый момент можете проверить, влезет ли индекс в ваш массив или он мимо, а тянуть и исправлять дополнительные переменные, которые хранят эту информацию и, которые вы можете забыть где-то поменять, нет необходимости, соответственно, и шансов сделать ошибку и вылезти за пределы массива существенно меньше, в-третьих, вы пишете, что большие проблемы из-за того, что что-то не поддерживает компилятор - так возьмите современный компилятор, а не пережиток из девяностых. Когда-то он был неплох, но студенты, которых вы сейчас учите, тогда только родились - помотрите, как они выросли, вот и компиляторы тоже на месте не стояли - росли. В-четвертых, вы осуждаете вектор за выделение бОльшего объема памяти, чем надо, но 1) лишние несколько байт могут повлиять, если у вас будет программа, в которой понадобятся миллионы объектов Polynomial - действительно ли есть такая необходимость? 2) Выделение бОльшего объема осмысленное - ради так любимого вами быстродействия - оно позволяет не перевыделять память каждый раз, когда вам надо нарастить длину вектора; 3) если вы заранее знаете, сколько у вас будет элементов, то можете зарезервировать вызовом reserve()

-- Thu Apr 04, 2019 09:13:51 --

warlock66613 в сообщении #1385886 писал(а):

А мы в любом случае можем вылезти за пределы вектора - не влево, так вправо.

Проверка на выход вправо в том коде есть.

-- Thu Apr 04, 2019 09:15:08 --

VTsalyuk в сообщении #1385877 писал(а):

Уверен, что дебажная версия.

Тогда в топку эти результаты - они не представляют никакой ценности.

[warlock66613]

photon в сообщении #1385887 писал(а):

Проверка на выход вправо в том коде есть.

Да, точно. Ну, это не совсем проверка - это, очевидно, логика программы требует, чтобы возвращался ноль в таком случае. Но тогда получается, что operator[] принимает именно степень переменной, а значит всё правильно - она и должна быть int (если она будет unsigned, в вызывающем коде будет микс из знаковых и беззнаковых, что плохо), и проверки на отрицательное значение делать, конечно, не надо. Я считаю, код идеален.

[photon]

warlock66613 в сообщении #1385889 писал(а):

и проверки на отрицательное значение делать, конечно, не надо

Если функция позволяет передать отрицательное число, то рано или поздно может возникнуть ситуация, что придет отрицательное. В местах, некритичных по времени выполнения, проверка лишней не будет. Если вдруг она все-таки критична, то имеет смысл поставить assert - как минимум, при отладке можно будет на нем выпасть, а на релизной производительности не скажется.

-- Thu Apr 04, 2019 09:45:58 --

warlock66613 в сообщении #1385889 писал(а):

если она будет unsigned, в вызывающем коде будет микс из знаковых и беззнаковых

Не вижу проблемы - номера индексов по своей логике не могут быть отрицательными, так что вполне можно их и в вызывающем коде делать беззнаковыми. И я не вижу ситуации, где эти индексы должны пересекаться с другими обязательно знаковыми переменными. Вот сравнение индексов с общим их количеством, возвращаемым функцие size() вполне может иметь место, а size() возвращает size_t - беззнаковый результат, который как раз, может случиться, придется сравнивать со знаковым индексом, что не есть хорошо.

[warlock66613]

photon в сообщении #1385890 писал(а):

В местах, некритичных по времени выполнения, проверка лишней не будет.

Согласен. Но если мы почему-либо хотим, чтобы этот оператор был noexcept, остаётся только assert.

[photon]

warlock66613 в сообщении #1385889 писал(а):

Я считаю, код идеален.

Я бы не был столь категоричен, но он, действительно, и на мой вкус весьма неплох и вполне мог бы быть взят автором этой темы за основу. Если какого-то требуемого функционала нет - можно расширить, а Cutting() для типов с плавающей точкой подправить.

[realeugene]

photon в сообщении #1385860 писал(а):

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

Согласен - assert на входе в функцию тут обязателен для такого метода объекта. Но и гнусные 8-символьные отступы мне лично категорически не нравятся. Беззнаковый аргумент в данном случае в интерфейс полинома лучше не выносить. Он неявно превратит -1 в очень большую степень, что нехорошо. Но можно assert заменить проверкой на неотрицательность, введя в семантику объекта соглашение, что в полиноме все степени целые, но коэффициенты при отрицательных степенях $x$ (которые для полинома над полем определены) всегда нулевые. Делать ли потом внутри функции трюк с преобразованием индекса в беззнаковый перед проверкой - на мой взгляд, не нужно, особенно, в учебном примере.

-- 04.04.2019, 12:17 --

photon в сообщении #1385887 писал(а):

Это ужас какой-то.

Ужас-ужас.

-- 04.04.2019, 12:37 --

photon в сообщении #1385887 писал(а):

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

Самое важное, что с 90-х сильно изменился стандарт языка. Старый код, конечно, в основном компилируется. Но появилось много новых вкусностей. На старом компиляторе показать те же constexpr не получится (и лучше их показывать начиная с C++14). Да и STL в 90-е был ещё в зачаточном состоянии. В MSVC 6.0, которым пользуется ТС, это глюкало было, просто, неработоспособно.

[VTsalyuk]

Спасибо за указания на ошибки. Проверю.

Но, господа, тут надо понять одну вещь. Есть разработчик и пользователь. Безопасность разработчика не принципиальна -- пусть отлаживает и тестирует. Поэтому разработчик может пользоваться векторами, если это не влияет отрицательно на быстродействие. И может ради быстродействия писать сколь угодно длинные коды. Именно это я пытаюсь донести до читателя.

А безопасность пользователя... Надо представить его образ. Это не заточенный на чудеса программирования математик-вычислитель. Он пользуется не новейшей системой программирования, а той, к которой привык. Он прошел начальный курс программирования и умеет писать циклы, пользоваться индексами и... это почти все. И не надо представлять, что ваше образование и умение доступно пользователю. Я, как проектировщик, являюсь "уполномоченным представителем" такого пользователя. Раз уж он производит какие-то рассчеты на заказчика, то он имеет приличное фундаментальное образование и ему-таки немало лет

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

Если разработчик может потрафить вкусам и привычкам такого пользователя, то он должен это сделать.

photon, повторю тесты на быстродействие сложения обязательно -- на своем "допотопном" компиляторе (парой абзацев выше я объяснил, почему). Что еще, кроме debug, отключить/включить?

[photon]

VTsalyuk в сообщении #1386067 писал(а):

Что еще, кроме debug, отключить/включить?

Ваш компилятор/современный студийный, gcc или clang.

VTsalyuk в сообщении #1386067 писал(а):

Безопасность разработчика не принципиальна -- пусть отлаживает и тестирует.

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

VTsalyuk в сообщении #1386067 писал(а):

Надо представить его образ. Это не заточенный на чудеса программирования математик-вычислитель.

Если ставить в план выпустить не специалиста, а нечто серое, то да, можно не трудиться, но для меня такие цели странны.

VTsalyuk в сообщении #1386067 писал(а):

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

Во-первых, получается, что вы учите людей не программировать (становиться разработчиками), а лишь, в вашей классификации, пользователями, хотя это странные пользователи - они пользуются не готовым продуктом, а каким-то классом, который кто-то написал, но при этом сами не должны нормально программировать. В жизни вообще-то так не бывает: или человек пользуется готовым продуктом и вообще не знает, что там за начинка внутри, или, если он пользуется сторонними библиотеками на уровне вызова отдельных функций, то происходит это при написании его собственного кода, то есть он тоже является разработчиком. Во-вторых, даже для этого "пользователя", точнее, в первую очередь для этого пользователя, а не разработчика, лучше, если в интерфейсе будут векторы (или другие удобоваримые объекты), а не голые массивы или указатели - ему будет меньше шансов на ошибку.

VTsalyuk в сообщении #1386067 писал(а):

Он пользуется не новейшей системой программирования, а той, к которой привык.

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

-- Fri Apr 05, 2019 09:38:24 --

VTsalyuk в сообщении #1386067 писал(а):

и ему-таки немало лет

Мы ведь говорим не о вас - мне, по большому счету, плевать, будете вы пользоваться или нет современными подходами и инструментами - вы, вероятно, уже никогда не станете профессиональным программистом; я говорю о студентах, которых вы готовите, и которым после вашего обучения, если они захотят стать программистами, будет сложнее, чем если бы этого обучения не было, потому что сначала из них надо будет выбить ту дурь, которую запихнули, а потом научить "как надо" - лучше с нуля учить "как надо", чем потом переучиваться - у нас тут уже есть яркий тому пример "программиста", который в попытках научиться новому после старого (хотя сама попытка похвальна) подает в конструктор вектор, а потом внутри вызывает malloc со всеми сопутствующими (Хотя это, ИМХО, не самая шедевральная функция в вашем коде. Я нашел получше: деление, в котором часть результата возвращается функцией, а часть пишется в статическую переменную - за такое, пользуясь преферансной терминологией, вообще надо канделябром по голове).

[VTsalyuk]

photon в сообщении #1386077 писал(а):

деление, в котором часть результата возвращается функцией, а часть пишется в статическую переменную - за такое, пользуясь преферансной терминологией вообще надо канделябром по голове).

Все остальное потом, после экспериментов...

А насчет этого: я не нашел другого способа избежать повторного вызова операции деления. Может, подскажете? Чур, pair или самопальные его аналоги не предлагать: нужно, чтобы

 
P = Q + A / B;
Z = Remainder;

ну, или

 
P = Q + A / B;
Z = A % B;

1) работало, 2) без повторного деления (никак не избавлюсь от впечатления, что деление -- самая длинная из арифметических операций). Так "хочет пользователь".

Сейчас я пытаюсь переписать класс в шаблон и обнаруживаю, что статическая переменная (в старых стандартах, до C++14) действительно очень неуклюжая вещь и требует много возни, чтобы ее реализовать.

[Pphantom]

VTsalyuk в сообщении #1386067 писал(а):

Надо представить его образ. Это не заточенный на чудеса программирования математик-вычислитель. Он пользуется не новейшей системой программирования, а той, к которой привык. Он прошел начальный курс программирования и умеет писать циклы, пользоваться индексами и... это почти все.

А почему он тогда, собственно, "математик-вычислитель", если, исходя из предложенного описания, он едва знает лишь азы своей профессии?

VTsalyuk в сообщении #1386067 писал(а):

И не надо представлять, что ваше образование и умение доступно пользователю. Я, как проектировщик, являюсь "уполномоченным представителем" такого пользователя. Раз уж он производит какие-то рассчеты на заказчика, то он имеет приличное фундаментальное образование и ему-таки немало лет

Тут, я, возможно, ошибусь, но вроде бы все (или почти все) ваши активные собеседники в этой теме "имеют приличное фундаментальное образование" (и не являются по этому образованию программистами) и в среднем не так уж и молоды. Т.е. вы пытаетесь спорить с теми самыми людьми, "уполномоченным представителем" которых себя считаете.

[Munin]

VTsalyuk в сообщении #1386067 писал(а):

Безопасность разработчика не принципиальна -- пусть отлаживает и тестирует.

Это грубая ошибка.

VTsalyuk в сообщении #1386067 писал(а):

Поэтому разработчик может пользоваться векторами, если это не влияет отрицательно на быстродействие. И может ради быстродействия писать сколь угодно длинные коды. Именно это я пытаюсь донести до читателя.

Это ещё одна грубейшая ошибка.

Доносить такое до читателя - преступление.

VTsalyuk в сообщении #1386067 писал(а):

Это не заточенный на чудеса программирования математик-вычислитель. Он пользуется не новейшей системой программирования, а той, к которой привык.

Тут есть рациональное зерно. Но видимо, вы не понимаете, что разные люди привыкли к разному. Кто-то к древнему C++. Кто-то к ещё более древнему Fortran. Кто-то к Matlab. Кто-то к Maple. Кто-то к Python. Кто-то к Excel. Кто-то к Turbo Pascal. Кто-то к BASIC - и попробуй его в чём переубеди.

VTsalyuk в сообщении #1386067 писал(а):

Я, как проектировщик, являюсь "уполномоченным представителем" такого пользователя.

Для этого надо
1. Лучше представлять себе его нужды.
2. Уметь превращать их в грамотные архитектурные решения.
И то и другое у вас не получается, так что ваша претензия на представительство необоснована.

VTsalyuk в сообщении #1386067 писал(а):

Раз уж он производит какие-то рассчеты на заказчика, то он имеет приличное фундаментальное образование и ему-таки немало лет :-)

Надо сказать, что тех, кому "немало лет", как раз всё меньше и меньше. Людей под 30-40 встретить можно не реже, чем людей под 70-80, и в общем, и те и другие - переучивались за свою жизнь, часто не раз, просто потому, что были вынуждены. Чтобы кому-то повезло просидеть без изменений на тех же аппаратно-программных средствах, что и в 90-е годы - это как раз редкое исключение.

VTsalyuk в сообщении #1386067 писал(а):

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

Ровно наоборот. Векторы рекомендуются начинающим потому, что они безопасней именно для начинающих. А для опытного разработчика разница уменьшается (но не до нуля).

VTsalyuk в сообщении #1386067 писал(а):

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

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

----------------

photon в сообщении #1386077 писал(а):

я говорю о студентах, которых вы готовите, и которым после вашего обучения, если они захотят стать программистами, будет сложнее, чем если бы этого обучения не было

Я надеюсь, что всё-таки студенты сталкиваются с таким "мастером-ломастером" по касательной, а основные навыки и представления получают в другом месте из других источников. Так что это общение будет хоть и травматичным, но не судьбоносным.

VTsalyuk в сообщении #1386082 писал(а):

Чур, pair или самопальные его аналоги не предлагать

pair в данном случае наиболее очевидный и естественный способ достичь желаемого. На функциональном языке однозначно именно так бы и было сделано.

Разумеется, в интерфейсе должно быть как минимум три операции деления: возвращающая только частное, возвращающая только остаток, и возвращающая пару (частное, остаток). Ну и до кучи можно четвёртую булеву: "разделилось нацело".

[mihaild]

VTsalyuk в сообщении #1386082 писал(а):

Так "хочет пользователь".

Нет, не хочет. Пользователь хочет в первую очередь чтобы работало

Используется синтаксис C++

A = X / Y;
B = U / V;
C = X % Y;

(если сильно надо, то можно придумать конструкцию, которая сохраняет остаток для каждого деления и в какой-то момент его выдает, но это довольно нетривиальный код получается, и прежде чем его писать нужно убедиться что повторные деления действительно заметно влияют на производительность)

[Munin]

VTsalyuk в сообщении #1386082 писал(а):

(никак не избавлюсь от впечатления, что деление -- самая длинная из арифметических операций)

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

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

-- 05.04.2019 12:23:58 --

https://stackoverflow.com/a/8833627

Используется синтаксис C++

#include <tuple>

std::tuple<int, int> DFS (int a, int b, int c, int d)
{
    return std::make_tuple(a + b, c + d);
}

...

int solution, cost_limit;
std::tie(solution, cost_limit) = DFS(a, b, c, d);

-- 05.04.2019 12:25:52 --

https://stackoverflow.com/a/31792928

Используется синтаксис C++

#include <tuple>
#include <iostream>

std::pair<bool, int> foo()
{
    return std::make_pair(false, 3);
}

int main()
{
    int x;
    bool y;

    std::tie(y, x) = foo();
    std::cout << x << ',' << y << '\n';
}

// Output: 3,0

-- 05.04.2019 12:29:53 --

https://stackoverflow.com/a/15365938

Используется синтаксис C++

#include <utility>

std::pair<double, double> foo()
{
  return std::make_pair(42., 3.14);
}

#include <iostream>
#include <tuple> // C++11, for std::tie
int main()
{
  std::pair<double, double> p = foo();
  std::cout << p.first << ", " << p.second << std::endl;

  // C++11: use std::tie to unpack into pre-existing variables
  double x, y;
  std::tie(x,y) = foo();
  std::cout << x << ", " << y << std::endl;

  // C++17: structured bindings
  auto [xx, yy] = foo(); // xx, yy are double
}

Цитата:

Also now you may do return { 42., 3.14 }; which is even prettier and faster (avoids the construction of a pair if you have a tie(x,y) on the other side

-- 05.04.2019 12:36:44 --

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

[realeugene]

Munin в сообщении #1386097 писал(а):

Чтобы кому-то повезло просидеть без изменений на тех же аппаратно-программных средствах, что и в 90-е годы - это как раз редкое исключение.

От тоски можно было бы повеситься.

(Оффтоп)

По-моему, главная ошибка этого курса программироавания - это обучение студентов C++. В результате, для задач, для которых нужны плюсы, они их всё равно не смогут применять с тем уровнем знаний, на котором они его изучают под руководством ТС (и до которого вообще можно обучить непрофессионального программиста). А для более простых задач лучше использовать более дружелюбные к программисту и менее требовательные к его квалификации языки. Тот же C#, из нескриптовых.

[Pphantom]

(Оффтоп)

realeugene в сообщении #1386123 писал(а):

По-моему, главная ошибка этого курса программироавания - это обучение студентов C++. В результате, для задач, для которых нужны плюсы, они их всё равно не смогут применять с тем уровнем знаний, на котором они его изучают под руководством ТС (и до которого вообще можно обучить непрофессионального программиста).

Можно сделать даже более радикальное утверждение: людям, у которых программирование не является основным занятием (в частности, "предметникам", занимающимся вычислительным моделированием) C++ просто не нужен. Безотносительно квалификации преподавателя.