Достаточно написать stream << value << " ";, чтобы всё починить. На деле такой способ не очень хорош (зачем совать пробел в двоичный буфер?), поэтому я делаю так:
// манипуляторы!11
template< class CharT, class Traits >
std::basic_ostream<CharT, Traits>& delimiter( std::basic_ostream<CharT, Traits>& os ) {
return os << CharT(' ');
}
template< class CharT, class Traits >
std::basic_istream<CharT, Traits>& delimiter( std::basic_istream<CharT, Traits>& is ) {
return is; // при чтении париться о пробелах уже не надо
}
BitStream& delimiter(BitStream& bs) {
return bs; // ничего не надо делать -- ни при чтении, ни при записи
}
И, соответственно, в коде будет вроде
serialize(...) {
F::serialize(out, ...);
out << delimiter;
NextSerializer::serialize(out, ...);
}
deserialize(...) {
if(!F::deserialize(in, ...)) return false;
in >> delimiter; // вдруг будет вид потока, требующий считать разделитель?
return !in.rdstate() // ничего не сломалось при считывании разделителя
&& NextDeserializer::deserialize(in, ...); // ничего не сломалось в рекурсии
}
Возможно, этот кусок кода действительно не следовало опускать.
Хотелось минимальный оверхед. Насколько я понял, протобуф кучу всего делает динамически. А мы здесь фактически генерируем последовательность cout << something (или, в случае десериализатора, который я опустил, in >> something; if(in.rdstate()) return false;).
Спасибо! За ссылкой на github приглашаю в личку (это же не «Я пиарюсь», в самом деле!). Выслушаю все замечания к статье, починю всё, что можно, и ссылку всем отдам.
Экономится не только и не столько процессорное время. Например, вы пишете программу, делающую нечто над конечным полем. Значит, где-то глобально должна быть выделена память как минимум под порядок этого поля. Значит, где-то её надо предварительно выделить. Вот такую неприятную необходимость можно устранить.
К тому же, не зря это помещено в Ненормальное программирование. :)
Когда исследователи, работающие с многомерными массивами, переходят от проб и ошибок к написанию реальных быстрых расчётных программ, им, как правило, уже не нужны ленивые вычисления. Там начинаются пляски с кэшем, параллельностью и прочие оптимизации, где крайне важно знать, что, где и когда реально выполняется. Многие вообще пишут на Фортране и радуются, как он умно оптимизирует циклы. (Ну а качество кода, к сожалению, редко интересует их в эти моменты.)
Ну вот в учебнике "Матричный анализ и линейная алгебра" Е. Е. Тыртышникова, например, определитель вводится как индикатор линейной зависимости векторов, а потом уже выводится для него формула. Учебники разные бывают.
UPD. Ниже вот Morozov_5F уже упомянул эту книгу.
И в первом, и в этом варианте выглядит так, будто новый сигнал — зеркальное отражение исходного. Не знаю, на каком языке вы пишете, но вы уверены, что вам нужно fft(x, -1), а не что-то вроде ifft(x)? Дело в том, что дважды применённое прямое преобразование — это в точности разворот вектора.
Вы иронизируете про запуск на устаревшем 68060, но ведь не можете знать, на каком процессоре код, который вы пишете, рискнут запустить в будущем. Срок жизни кода умеет удивлять.
Хм, вообще относительная ошибка порядка 1E-7 (как в вашем случае) при работе с float'ами — это нормально. Она такая примерно всегда получается. Просто если у вас вещественные вычисления, то воспроизводимость результатов надо мерить не тупым равенством, а приближённым.
Нет, то, что я написал, значит другое. Чем вы читаете? Я говорю, что вы не можете найти собственные значения матрицы над конечным полем, используя существующие итерационные алгоритмы для вещественных/комплексных матриц. (На всякий случай: они не совпадают с собственными значениями этих же матриц, рассмотренных как вещественных.) Не можете ни с какой точностью, повторяю это специально для вас, хотя для меня это звучит как бессмыслица — поскольку в конечном поле нет понятия приближения.
Ну, например, потому, что у вас не будет в распоряжении понятия «точность».
Рассмотрите для простоты итерационный метод решения системы какой-нибудь. Вот вы итерируете, итерируете, и по величине невязки ||Axn-b|| и числу обусловленности вашей матрицы можете прикинуть, насколько вы уже близки к решению. А теперь представьте, что вы итерируете над GF(2) (поле из нуля и единицы). Вы считаете невязку, и это вектор из нулей и единиц. В нём может быть только одна единица, но вы можете быть сколь угодно далеки от решения (по Хэммингу, например). Он может быть весь из единиц, а итерационный метод — взять и сойтись на следующей итерации.
При этом, например, итерационные методы для линейных систем, основанные на подпространствах Крылова (тот же метод Ланцоша), у вас всё равно приведут к решению — поскольку это в глубине души прямые методы: за n итераций метод Ланцоша гарантированно сходится. Он считается итерационным, потому что в вещественном случае итерации можно оборвать на пол-пути, когда достигнута необходимая точность. Но для собственных чисел таких прямых алгоритмов не существует. Например, если бы вы построили такой прямой алгоритм, использующий только арифметические операции и взятие корней, вы бы пришли к нахождению корней многочленов в радикалах (потому что любому многочлену соответствует матрица, для которой он является характеристическим), что гарантированно невозможно.
Все существующие алгоритмы поиска собственных значений матриц общего вида — какими бы быстрыми и надёжными они ни были — итерационные, а это значит, что вы не можете просто взять и применить их над конечным полем. Поэтому ваше утверждение о сложности в O(n3) в конечном поле голословно и нуждается либо в ссылке, либо (что более вероятно) в широкомасштабном исследовании.
stream << value << " ";
, чтобы всё починить. На деле такой способ не очень хорош (зачем совать пробел в двоичный буфер?), поэтому я делаю так:И, соответственно, в коде будет вроде
Возможно, этот кусок кода действительно не следовало опускать.
(это если не нужно нигде никаких дополнительных проверок и нужно прям все данные в лоб передать)
cout << something
(или, в случае десериализатора, который я опустил,in >> something; if(in.rdstate()) return false;
).Собственно, TerraDon ниже уже это отметил.
К тому же, не зря это помещено в Ненормальное программирование. :)
UPD. Ниже вот Morozov_5F уже упомянул эту книгу.
fft(x, -1)
, а не что-то вродеifft(x)
? Дело в том, что дважды применённое прямое преобразование — это в точности разворот вектора.Рассмотрите для простоты итерационный метод решения системы какой-нибудь. Вот вы итерируете, итерируете, и по величине невязки ||Axn-b|| и числу обусловленности вашей матрицы можете прикинуть, насколько вы уже близки к решению. А теперь представьте, что вы итерируете над GF(2) (поле из нуля и единицы). Вы считаете невязку, и это вектор из нулей и единиц. В нём может быть только одна единица, но вы можете быть сколь угодно далеки от решения (по Хэммингу, например). Он может быть весь из единиц, а итерационный метод — взять и сойтись на следующей итерации.
При этом, например, итерационные методы для линейных систем, основанные на подпространствах Крылова (тот же метод Ланцоша), у вас всё равно приведут к решению — поскольку это в глубине души прямые методы: за n итераций метод Ланцоша гарантированно сходится. Он считается итерационным, потому что в вещественном случае итерации можно оборвать на пол-пути, когда достигнута необходимая точность. Но для собственных чисел таких прямых алгоритмов не существует. Например, если бы вы построили такой прямой алгоритм, использующий только арифметические операции и взятие корней, вы бы пришли к нахождению корней многочленов в радикалах (потому что любому многочлену соответствует матрица, для которой он является характеристическим), что гарантированно невозможно.
Все существующие алгоритмы поиска собственных значений матриц общего вида — какими бы быстрыми и надёжными они ни были — итерационные, а это значит, что вы не можете просто взять и применить их над конечным полем. Поэтому ваше утверждение о сложности в O(n3) в конечном поле голословно и нуждается либо в ссылке, либо (что более вероятно) в широкомасштабном исследовании.