А мораль сей басни такова: даже если взять, на первый взгляд, примитивную учебную задачку, то, при некотором шевелении мозгами, можно обнаружить что решение может быть далеко не единственное, а выбор лучшего (оптимального) решения может быть и самостоятельной задачей.
Персональное спасибо porshe за участие в обсуждении и проделанную работу.
Жаль, что новички, для которых и была эта задача, как всегда отсиделись в кустах. (Если в кустах вообще кто-то был.) Если же всё-таки у новичков есть интерес к таким исследованиям, покопайтесь в «готовых решениях» на Паскале. Там ещё есть неоптимальные решения.
Egogorka, к сожалению проверить твой вариант не получается: код не полный. И если о том, какие заголовочные файлы сюда надо подключить и каков тип переменных, можно догадаться, то с инициализацией всё не так однозначно.
Кроме того в последнем вызове scanf (который в общем-то и не нужен) ошибка.
И как-то очень запутанно всё у тебя получилось. При неполных входных данных я до конца так и не втыкнул.
Cranium, уж извините что представил неполную программу. Сильно спешил, и не полностью выделил код). scanf в конце я использовал в роли остановки программы (ибо это единственная команда,которую я знаю и которая останавливает ход программы до того, как человек не нажмёт кнопку возврата каретки(enter)). Вот полная версия кода:
#include <stdio.h>
#include <clocale>
#include <math.h>
float num; // Число, вводимое нами
float numr; // Это же число
float step=0; // Значение степени
float detect=0; // Понятно из названия переменной
float bin=0; // Наше число в двоичном варианте
int main(void)
{
setlocale(LC_CTYPE, "rus");
printf("Введите число для обработки\n");
scanf("%f",&num); numr = num;
while(detect != 1) // Цикл, занимающийся созданием двоичного числа
{
while(detect != 1 || num < 0) // Важный цикл, сердце программы
{
num = num - pow(2,step);
if(num < 0){
step--;
num = numr - pow(2,step);
if(num == 0){detect=1;}
break;
}
else if(num == 0){ detect=1; break;}
else {step++; num = numr;}
}
bin = bin + pow(10,step);
numr = num; step = 0;
}
printf("Вот ваше число в двоичном варианте: %8.0f\n", bin);
scanf("%f",num);
return 0;
}
P.S. Число. вводимое нами, может быть только до 256 (дальше, непонятно почему, козлячит) и неотрицательным, ибо изначально не задано кол-во битов. Дальше хотел преобразовать прогу, изменив некоторые детали.
P.S.S. Не буду говорить, на чём основан этот способ, так-как из кода всё понятно)
P.S.S.S. Вообще, этот код должен работать и на C#
Egogorka, теперь, с полным кодом, всё встало на свои места.
scanf в конце я использовал в роли остановки программы
Это было понятно. Но ошибка в этом операторе всё-таки есть. Попробуй найти сам.
Под виндой вместо такого финта лучше использовать system("pause"); (может потребоваться #include <cstdlib>).
Твой алгоритм наглухо циклится при вводе числа 0.
P.S. Число. вводимое нами, может быть только до 256 (дальше, непонятно почему, козлячит)
Если куцый тип float заменить на более длинный и точный double, то программа будет работать до 4194304 (2 в 22 степени).
В твоём подходе к решению задачи есть один серьёзный недостаток: использование чисел с плавающей точкой. Во-первых, это потеря точности (что ты и получил). Во-вторых, плавающая арифметика гораздо медленнее, чем целочисленная.
Ещё один момент: ты невнимательно проанализировал входные условия задачи, поэтому и пошёл не той дорогой. В исходнике на Паскале указано, что (1) входное значение — число целого типа и (2) выходное значение — строка. Ты использовал для результата число, а не строку, поэтому максимальное входное значение, при котором программа работает правильно, оказалось сильно ограниченным разрядностью выходного значения. Если на выходе строка, такого не может произойти в принципе.
Для возведения в степень есть большое искушение использовать библиотечную функцию pow. Однако, она определена только для плавающей арифметики. Но ни что не мешает написать свою функцию возведения целого числа в целую степень. (А если принять во внимание, что нам нужны только степени числа 2 и что арифметический сдвиг на один разряд влево приводит к умножению числа на 2, то можно обойтись вообще одной строчкой.) К тому же библиотечная функция излишне мощна для нашей задачи и, как следствие, не очень быстра.
Вообще изначально я и хотел использовать целые числа, но из-за функции pow мне пришлось переходить на вещественные. Строчки: я пока не сильно понимаю как с ними работать, ибо это новое для меня. На счёт сдвига я сразу не допёр, а функцию было лень делать. Вообще, я лишь достигал цели задачи, и исходник на Паскале не смотрел.
Сделал проверку для всех вариантов вот таким скриптом run.sh
Не есть хорошо. Это же время исполнения всей программы, а нам такое не надо.
Здесь могут сыграть роль занятость системы, время создания процесса, время инициализации,
также ввод/вывод данных не есть быстрая операция, да и вообще по времени не стабильная,
как следствие, отклонения могут быть в разы даже для одной и той же программы.
Итак, для всех алгоритмов выше наихудший случай — когда все биты числа равны 1.
Поэтому для теста было выставлено значение ~0
Для теста взято три функции из этой темы, также одна функция слегка переделана,
в ней я избавился от std::string
Код тестирования:
#include <iostream>
#include <limits>
#include <type_traits>
#include <chrono>
#include <cassert>
template<typename T>
const char *valToBinStr(T val){
static_assert(std::is_integral<T>::value, "value must have integral type");
static constexpr char digits[2] = {'0', '1'};
using UT = typename std::make_unsigned<T>::type;
thread_local char buffer[std::numeric_limits<UT>::digits + 1];
UT value = static_cast<UT>(val);
char *ptr = buffer + std::numeric_limits<UT>::digits;
*ptr = 0;
do{
--ptr;
*ptr = digits[value&1];
value >>= 1;
}while(value!=0);
return ptr;
}
template<typename Func, typename ... Args>
void testFunc(Func &&func, size_t count, Args &&...args){
for(size_t i = 0; i < count; ++i){
std::forward<Func>(func)(std::forward<Args>(args)...);
}
}
template <typename T>
std::string intToBin_00(T val)
{
if (val == 0)
return "0";
std::string bin;
bool meetOne = false;
for (int i = sizeof(T) * 8 - 1; i >= 0; i--)
{
if (val & (1 << i))
{
meetOne = true;
bin += '1';
}
else
{
if (meetOne)
{
bin += '0';
}
}
}
return bin;
}
template <typename T>
std::string intToBin_01(T val) {
if (val == 0)
return "0"; // здесь сработает конструктор std::string
char bary[sizeof(T) * 8 + 1];
int idigit = 0;
bool meetOne = false;
for (int i = sizeof(T) * 8 - 1; i >= 0; i--) {
if (val & (1 << i)) {
meetOne = true;
bary[idigit++] = '1';
}
else {
if (meetOne) {
bary[idigit++] = '0';
}
}
}
bary[idigit] = '\0';
return bary; // или здесь сработает конструктор std::string
}
template <typename T>
const char *intToBin_02(T val) {
if (val == 0)
return "0"; // здесь сработает конструктор std::string
thread_local char bary[sizeof(T) * 8 + 1];
int idigit = 0;
bool meetOne = false;
for (int i = sizeof(T) * 8 - 1; i >= 0; i--) {
if (val & (1 << i)) {
meetOne = true;
bary[idigit++] = '1';
}
else {
if (meetOne) {
bary[idigit++] = '0';
}
}
}
bary[idigit] = '\0';
return bary; // или здесь сработает конструктор std::string
}
void dec2bin_r(unsigned int num, std::string & str) {
if (num != 0) {
dec2bin_r(num >> 1, str);
str += (num & 1) + '0';
}
}
std::string dec2bin(int num) {
if (num == 0) {
return "0";
}
else {
std::string str;
dec2bin_r(static_cast<unsigned int>(num), str);
return str;
}
}
template<typename Func, typename ... Args>
auto getExecutionTimeAsMillisecons(Func &&func, Args &&...args){
auto start = std::chrono::high_resolution_clock::now();
testFunc(std::forward<Func>(func), std::forward<Args>(args)...);
auto finish = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast<std::chrono::milliseconds>(finish-start).count();
}
//size_t(x) - количество итераций
//~0 - переводимое число
#define TEST_FUNCTION(func) \
std::cout << "time " #func " : " << getExecutionTimeAsMillisecons(func, size_t(100000000), ~0) << " ms" << std::endl
int main()
{
TEST_FUNCTION(intToBin_00<int>);//Первый вариант intToBin (везде std::string)
TEST_FUNCTION(intToBin_01<int>);//Второй вариант intToBin (std::string при возврате)
TEST_FUNCTION(intToBin_02<int>);//Третий вариант intToBin (без std::string)
TEST_FUNCTION(dec2bin);//Какая-то "альтернативная реализация"
TEST_FUNCTION(valToBinStr<int>);//Функция из моего поста выше
}
Тест проводился на старенькой машине, нагруженной на 60%, компилятор MinGW 5.3.0
так что результаты лучше проверьте у себя (перепроверю, когда доберусь до дома).
Результаты теста:
time intToBin_00<int> : 91081 ms
time intToBin_01<int> : 35896 ms
time intToBin_02<int> : 7669 ms
time dec2bin : 97903 ms
time valToBinStr<int> : 7036 ms
Как видим, основные тормоза идут от std::string.
Оно и не удивительно, ведь std::string постоянно
что-то копирует, проверяет, дергает new,
всё это накладывает свой отпечаток.
Если кому-то не нравится отказ от std::string,
мол это Cи'шный подход и тому подобное,
то увы, я с вами не согласен.
Как можно использовать данное значение на практике?
Вывод? Тогда здесь не нужен std::string.
Какая-то обработка этого числа?
Тогда пользователь сам может выбрать,
нужен ему здесь std::string или нет.
ИМХО, отказ в данном случае от std::string — прекрасная идея.
Как придет C++17, поменяем на std::string_view,
для удобства и «очистки совести».
Я делал несколько запусков и пытался выбирать скрины со средним значением времени.
Это понятно, но всё же это тест всего приложения, а не отдельной функции.
Я вот небольшую портянку здесь составил, чтобы протестировать функции,
думаю, это более корректные результаты, хотя здесь тоже может быть не всё ладно.
В силу того, что возвращаемое значение нигде не используется,
компилятор может «наоптимизировать» лишнего :)
Запустил с -O0:
time intToBin_00<int> : 101599 ms
time intToBin_01<int> : 43399 ms
time intToBin_02<int> : 7968 ms
time dec2bin : 97516 ms
time valToBinStr<int> : 7613 ms
Что касается разницы во времени для функций intToBin_02<int> и valToBinStr<int>,
она составляет менее секунды, но возьмем одну секунду, условно.
Производится 100000000 итераций, поэтому это разница 0.00000001 секунды на итерацию.
Это может быть что угодно, например, система в каких-то случаях отбирала управление и т.д.
Просто так попало, можно смело считать,
что функции по производительности одинаковые, ну или почти одинаковые.
В результате тестов выяснилось,
что ВСЕ приведенные выше шаблонные функции, кроме моей,
выдают неверные результаты для типов, отличных по размеру от int.
Во всех ваших функциях один и тот же косяк:
(1 << i) — всегда дает int, со всеми вытекающими.
По факту, здесь вообще UB.
Изменить на: (T(1) << i) для корректной работы.
Также немного похимичил еще.
Сделал на половину табличный вариант:
template<typename T>
const char *valToBinStr_01(T val){
static_assert(std::is_integral<T>::value, "value must have integral type");
static_assert(CHAR_BIT%4==0, "CHAR_BIT must be a multiple of four");
static constexpr char const *digits[16] = {
"0000",
"0001",
"0010",
"0011",
"0100",
"0101",
"0110",
"0111",
"1000",
"1001",
"1010",
"1011",
"1100",
"1101",
"1110",
"1111",
};
static constexpr unsigned int lastShifts[16] = {
4,
3,
2,
2,
1,
1,
1,
1,
0,
0,
0,
0,
0,
0,
0,
0
};
using UT = typename std::make_unsigned<T>::type;
constexpr size_t typeSizeInBits = sizeof(UT)*CHAR_BIT;
thread_local char buffer[typeSizeInBits + 1];
if(val==0){
return "0";
}
constexpr UT mask(0xF);
char *ptr = buffer + typeSizeInBits;
*ptr = 0;
UT workValue = static_cast<UT>(val);
UT lastIndex = 1;
do{
ptr-=4;
lastIndex = workValue&mask;
memcpy(ptr, digits[lastIndex], 4);
workValue >>= 4;
}while(workValue!=0);
ptr += lastShifts[lastIndex];
return ptr;
}
тест на той же машине, в тех же условиях, правда убрал «тормозные» функции, смотреть их результаты не интересно, и увеличил кол-во итераций в десять раз (теперь их 1000000000).
TEST_FUNCTION(intToBin_02<int>);//Третий вариант intToBin (без std::string)
TEST_FUNCTION(valToBinStr_00<int>);//Начальная версия моей функции
TEST_FUNCTION(valToBinStr_01<int>);//Полу табличная
Результаты:
time intToBin_02<int> : 93530 ms
time valToBinStr_00<int> : 86504 ms
time valToBinStr_01<int> : 55675 ms
Результаты для size_t:
time intToBin_02<size_t> : 89383 ms
time valToBinStr_00<size_t> : 75507 ms
time valToBinStr_01<size_t> : 56655 ms
Результаты для char:
time intToBin_02<char> : 45905 ms
time valToBinStr_00<char> : 58078 ms
time valToBinStr_01<char> : 42390 ms
Croessmah, по поводу (T(1) << i) — ты абсолютно прав. Я недосмотрел, когда обычную функцию переделывал под шаблонную. Грешен ))
Теперь по обеим, предложенным тобой функциям.
Во-первых, я уже писал выше, что возврат из функции ссылки на статическую переменную функции — зло. Ты возвращаешь указатель, который указывает на данные, которые находятся в статической (фактически) переменной. Такое же зло, только вид сбоку. Спецификатор хранения thread_local — это тот же static, только потокобезопасный. Пробуем?
Во-вторых, ты схитрил, полностью отказавшись от std::string. Поэтому сразу обеспечил себе прирост скорости. Если же мы приведём сигнатуру функции к общему, для остальных функций, виду template<typename T> string f(T val) и последнюю строку функции исправим на return string(ptr);, попутно избавившись от бага, описанного выше, то время выполнения функции станет почти таким же, как и у варианта 3.
Если всё-таки не применять std::string, то тогда возникает проблема где хранить полученный результат. Решения два: либо в функции брать память из кучи, в надежде, что вызывающий код её потом освободит, либо получать буфер в качестве параметра с риском, что его размера может не хватить. Как-то очень небезопасно получается. Плюс копирование результата из временного буфера в выходной, что бы начало строки результата совпадало с началом буфера.
PS. У меня (MS Visual Studio 2015 Community) почему-то неправильно компилируется конструкция static constexpr char const *digits[16] = {...}. Ошибку компиляции не даёт, но при запуске при доступе к элементу массива выдаёт какую-то хрень. И под отладкой дебаггер не ловит концы строк. Вылечилось изъятием constexpr.
По поводу конструкции static constexpr char const *digits[16] = {...}.
MS VS2015 компилирует её не как массив указателей на указатели на char, а как двумерный массив char, т.е. char const digits[16][5] = {...}. Это как бы самое близкое определение, хотя и не точное.
В памяти должно быть: digits — это массив из 16 указателей; каждый указатель содержит адрес памяти, где хранится последовательность символов (строка), заканчивающаяся '\0'. Причём строки могут располагаться в памяти не вместе и не последовательно.
Реально имеем: массива указателей нет; строки с завершающим '\0' из списка инициализации располагаются в памяти последовательно. digits указывает на начало этой области памяти. Причём строки могут быть разной длины. Поэтому определение char const digits[16][5] некорректно.
При этом обращение к элементам массива через индекс работает как и положено: digits[0] должно содержать значение адреса, по которому должна находиться строка, а реально туда попадают первые 4 байта (для x86) первой строки. Как результат — обращение к запрещённой области памяти. digits[1] сдвинут относительно digits[0], как и положено, на размер указателя, т.е. на 4 байта, из расчёта, что digits — это массив указателей. Я тихо фалломорфирую.
Такое же зло, только вид сбоку. Спецификатор хранения thread_local — это тот же static, только потокобезопасный. Пробуем?
Вообще, это достаточно частая практика.
И хороша она тем, что не нужно дергать динамическую.
Конечно, в документации должно быть отражен данный факт.
А сломать можно что угодно.
Вы же используете конкретные функции опираясь
на документацию и интерфейс, а не «как хочу».
И да, thread_local — это как static, только для потока,
так что по факту вызов функции в разных потоках возможен.
Во-вторых, ты схитрил, полностью отказавшись от std::string. Поэтому сразу обеспечил себе прирост скорости.
Эм, я же написал, что от этого как раз все тормоза.
при этом, я исправил и другую (не мою функцию), чтобы показать различия.
Если же мы приведём сигнатуру функции к общему
Зачем? Если любую из этих функций изменить до неузнаваемости,
то получим вообще что угодно.
Я сделал некий интерфейс,
будьте добры следовать соглашениям,
которые установил я — разработчик данной библиотеки.
Не нравится? Не используйте или напишите обертку,
при этом у Вас есть выбор,
в отличии от варианта с std::string — где выбора нет.
Решения два: либо в функции брать память из кучи, в надежде, что вызывающий код её потом освободит
Удивили. Возврат std::unique_ptr отменили?
Сам всё почистит при надобности.
Но здесь будет одна неувязочка,
если захотим построить std::string,
то придется всё это дело копировать заново.
либо получать буфер в качестве параметра с риском, что его размера может не хватить
Для этого можно использовать обертку, как это делается в boost,
причем буфером может быть тот же std::string.
Кстати, почти готов еще один вариант,
но еще нужно будет протестировать его на big-engian архитектуре.
Расчет тот же, только только вместо сдвигов и тому подобного напрямую
берутся байты из памяти и строка выбирается уже из таблицы.
Также можно соорудить еще один читерский вариант.
Он лишен всех перечисленных Вами «недостатков»,
но требует построения отдельного класса для работы.
Суть такова. Есть таблица байт, класс хранить массив с указателями.
Далее всё просто — парсим байтики числа, берем указатели из таблицы.
new дергается только при необходимости получить непрерывный буфер.
Но здесь тоже придется на big-engian проверять.
Пока «изобрел» один способ проверки архитектуры в compile-time,
чтобы получить значение constexpr на стадии компиляции,
хотя оно может быть не переносимо.
Ну или использовать всё-таки сдвиги и маски, но это медленнее.
по поводу (T(1) << i) — ты абсолютно прав. Я недосмотрел, когда обычную функцию переделывал под шаблонную. Грешен
Такие ошибки можно часто встретить, причем даже в «продвинутых» проектах.
Возможно, у меня побольше опыта в шаблонах, поэтому я это сразу увидел,
конечно, после того, как получил не верные результаты :)
Так что это не грех, а не досмотр + премия я исправление баги в софте )))
Зачем? Если любую из этих функций изменить до неузнаваемости, то получим вообще что угодно.
Тут ситуация как бэ полностью обратная: начинали мы обсуждение с функции, принимающей int и возвращающей std::string. Потом, с лёгкой руки porshe, обобщили до шаблона, принимающего любой целый знаковый тип. Проецируем на реальную ситуацию: есть большой проект, и есть функция, которую нужно оптимизировать. Менять сигнатуру функции в такой ситуации, сам понимаешь, ну никак.
Вообще, это достаточно частая практика.
Я бы не стал к этому апеллировать. Говнокод — тоже достаточно частая практика. А gets(), scanf(), strcpy(), etc. пользовали больше 30 лет, а потом таки чухнулись, что не кошерно.
Я сделал некий интерфейс, будьте добры следовать соглашениям, которые установил я — разработчик данной библиотеки. Не нравится? Не используйте или напишите обертку, при этом у Вас есть выбор
Библиотека должна быть надёжной и простой в использовании. Если использование библиотеки подобно хождению по канату с завязанными глазами, когда предварительно надо как-то обустроить страховочную лонжу и сетку внизу, то это плохая библиотека.
Следуя твоему совету, сделал обёртку для твоей первой функции, что бы возвращаемое значение было std::string. Таймирование показало, что от скорострельности оригинальной функции остались рожки да ножки: функция-обёртка работает медленнее, чем та же функция, допиленная до возврата std::string. Что неудивительно: появился лишний вызов функции.
Проецируем на реальную ситуацию: есть большой проект, и есть функция, которую нужно оптимизировать. Менять сигнатуру функции в такой ситуации, сам понимаешь, ну никак.
Так в том-то и дело, что я не оптимизировал,
я написал другую реализацию для нового проекта.
А потом функцию из старого проекта протестировал в своем новом проекте,
но в двух вариантах и выбрал понравившийся.
Библиотека должна быть надёжной и простой в использовании.
А еще достаточно быстрой.
Врядли кто-то будет ждать полгода,
пока библиотека разродится и выдаст ответ,
когда рядом есть другая библиотека, которая,
может не так удобна, но выдаст результат через месяц.
Следуя твоему совету, сделал обёртку для твоей первой функции
А вы хотели, чтобы обертка работала быстрее?
Думаю, объяснять не стоит, что не реально :)
Что касается возврата std::string,
не ясно, а нужен ли он мне вообще?
Может мне нужен вектор char'ов?
А может вообще ничего не нужно.
Да и new дергать не хочется.
Я не знаю как Вам, а мне std::string
не нравится вообще никак,
поэтому я предпочту вариант без него.
Хоть и приходится его использовать частенько.
Не будем спорить, мы друг друга всё равно не переспорим.
Угу... Только сколько информации улетело на сторону через эти «стандартные» дыры в безопасности.
Так в том-то и дело, что я не оптимизировал, я написал другую реализацию для нового проекта.
Значит в этом треде мы обсуждали разные задачи. Изначально имелось ввиду, что возвращаться будет std::string. Да, он тормозит. Но интерес был в том, как свести к минимуму эти тормоза.
А вы хотели, чтобы обертка работала быстрее?
Не-а. Хотел посмотреть на сколько обёртка замедлит работу «быстрой» функции.
Я тут ещё немного поэкспериментировал и оказалось, что быстродействие существенно зависит от компилятора и реализации STL.
Далее выдача тестовой программы. Первая колонка — название функции, вторая — время выполнения функции в секундах, третья — производительность в долях от времени выполнения первой функции (если умножить на 100, получим проценты).
ничесе задачка для новичков
на первой странице я еще что-то понимал в коде
на второй моск уже стал отключаться
я даже не подозревал что в с++ есть такие слова
Не обращайте на нас внимания, мы в своей песочнице )))
Я тут ещё немного поэкспериментировал и оказалось, что быстродействие существенно зависит от компилятора и реализации STL.
Конечно. И от оптимизаций.
Например, если компилятор сможет применить SSO,
то вызовов new, фактически, вообще не будет.
А gcc мне вообще умудрился повырезать
все циклы к чертовой бабушке в новой функции,
пришлось ему костылей напихать,
чтобы он так резво не оптимизировал.
Но интерес был в том, как свести к минимуму эти тормоза.
А я думал оптимизировать алгоритм перевода.
Хм, а как на счет не стандартного аллокатора?
Внимание! Это довольно старый топик, посты в него не попадут в новые, и их никто не увидит. Пишите пост, если хотите просто дополнить топик, а чтобы задать новый вопрос — начните новый.
Да будет так ))
А мораль сей басни такова: даже если взять, на первый взгляд, примитивную учебную задачку, то, при некотором шевелении мозгами, можно обнаружить что решение может быть далеко не единственное, а выбор лучшего (оптимального) решения может быть и самостоятельной задачей.
Персональное спасибо porshe за участие в обсуждении и проделанную работу.
Жаль, что новички, для которых и была эта задача, как всегда отсиделись в кустах. (Если в кустах вообще кто-то был.) Если же всё-таки у новичков есть интерес к таким исследованиям, покопайтесь в «готовых решениях» на Паскале. Там ещё есть неоптимальные решения.
Egogorka, к сожалению проверить твой вариант не получается: код не полный. И если о том, какие заголовочные файлы сюда надо подключить и каков тип переменных, можно догадаться, то с инициализацией всё не так однозначно.
Кроме того в последнем вызове
scanf(который в общем-то и не нужен) ошибка.И как-то очень запутанно всё у тебя получилось. При неполных входных данных я до конца так и не втыкнул.
Cranium, уж извините что представил неполную программу. Сильно спешил, и не полностью выделил код). scanf в конце я использовал в роли остановки программы (ибо это единственная команда,которую я знаю и которая останавливает ход программы до того, как человек не нажмёт кнопку возврата каретки(enter)). Вот полная версия кода:
P.S. Число. вводимое нами, может быть только до 256 (дальше, непонятно почему, козлячит) и неотрицательным, ибо изначально не задано кол-во битов. Дальше хотел преобразовать прогу, изменив некоторые детали.
P.S.S. Не буду говорить, на чём основан этот способ, так-как из кода всё понятно)
P.S.S.S. Вообще, этот код должен работать и на C#
Egogorka, теперь, с полным кодом, всё встало на свои места.
Это было понятно. Но ошибка в этом операторе всё-таки есть. Попробуй найти сам.
Под виндой вместо такого финта лучше использовать
system("pause");(может потребоваться#include <cstdlib>).Твой алгоритм наглухо циклится при вводе числа 0.
Если куцый тип
floatзаменить на более длинный и точныйdouble, то программа будет работать до 4194304 (2 в 22 степени).В твоём подходе к решению задачи есть один серьёзный недостаток: использование чисел с плавающей точкой. Во-первых, это потеря точности (что ты и получил). Во-вторых, плавающая арифметика гораздо медленнее, чем целочисленная.
Ещё один момент: ты невнимательно проанализировал входные условия задачи, поэтому и пошёл не той дорогой. В исходнике на Паскале указано, что (1) входное значение — число целого типа и (2) выходное значение — строка. Ты использовал для результата число, а не строку, поэтому максимальное входное значение, при котором программа работает правильно, оказалось сильно ограниченным разрядностью выходного значения. Если на выходе строка, такого не может произойти в принципе.
Для возведения в степень есть большое искушение использовать библиотечную функцию
pow. Однако, она определена только для плавающей арифметики. Но ни что не мешает написать свою функцию возведения целого числа в целую степень. (А если принять во внимание, что нам нужны только степени числа 2 и что арифметический сдвиг на один разряд влево приводит к умножению числа на 2, то можно обойтись вообще одной строчкой.) К тому же библиотечная функция излишне мощна для нашей задачи и, как следствие, не очень быстра.Cranium, я же говорю, что я новичёк)
Вообще изначально я и хотел использовать целые числа, но из-за функции pow мне пришлось переходить на вещественные. Строчки: я пока не сильно понимаю как с ними работать, ибо это новое для меня. На счёт сдвига я сразу не допёр, а функцию было лень делать. Вообще, я лишь достигал цели задачи, и исходник на Паскале не смотрел.
Egogorka, все когда-то были новичками. Читай книжки, пиши программы и всё получится.
Кстати, ещё одно замечание по твоей программе. Переменную
detectлучше делать типаbool, поскольку она выполняет роль флага.Такой вариант подойдет?
P.S. Заголовок темы не соответствует задаче, которую Вы предлагаете решить
Не есть хорошо. Это же время исполнения всей программы, а нам такое не надо.
Здесь могут сыграть роль занятость системы, время создания процесса, время инициализации,
также ввод/вывод данных не есть быстрая операция, да и вообще по времени не стабильная,
как следствие, отклонения могут быть в разы даже для одной и той же программы.
Я делал несколько запусков и пытался выбирать скрины со средним значением времени.
Итак, для всех алгоритмов выше наихудший случай — когда все биты числа равны 1.
Поэтому для теста было выставлено значение ~0
Для теста взято три функции из этой темы, также одна функция слегка переделана,
в ней я избавился от std::string
Код тестирования:
Тест проводился на старенькой машине, нагруженной на 60%, компилятор MinGW 5.3.0
так что результаты лучше проверьте у себя (перепроверю, когда доберусь до дома).
Результаты теста:
Как видим, основные тормоза идут от std::string.
Оно и не удивительно, ведь std::string постоянно
что-то копирует, проверяет, дергает new,
всё это накладывает свой отпечаток.
Если кому-то не нравится отказ от std::string,
мол это Cи'шный подход и тому подобное,
то увы, я с вами не согласен.
Как можно использовать данное значение на практике?
Вывод? Тогда здесь не нужен std::string.
Какая-то обработка этого числа?
Тогда пользователь сам может выбрать,
нужен ему здесь std::string или нет.
ИМХО, отказ в данном случае от std::string — прекрасная идея.
Как придет C++17, поменяем на std::string_view,
для удобства и «очистки совести».
Это понятно, но всё же это тест всего приложения, а не отдельной функции.
Я вот небольшую портянку здесь составил, чтобы протестировать функции,
думаю, это более корректные результаты, хотя здесь тоже может быть не всё ладно.
В силу того, что возвращаемое значение нигде не используется,
компилятор может «наоптимизировать» лишнего :)
Запустил с -O0:
Что касается разницы во времени для функций intToBin_02<int> и valToBinStr<int>,
она составляет менее секунды, но возьмем одну секунду, условно.
Производится 100000000 итераций, поэтому это разница 0.00000001 секунды на итерацию.
Это может быть что угодно, например, система в каких-то случаях отбирала управление и т.д.
Просто так попало, можно смело считать,
что функции по производительности одинаковые, ну или почти одинаковые.
В результате тестов выяснилось,
что ВСЕ приведенные выше шаблонные функции, кроме моей,
выдают неверные результаты для типов, отличных по размеру от int.
Результаты:
Во всех ваших функциях один и тот же косяк:
(1 << i) — всегда дает int, со всеми вытекающими.
По факту, здесь вообще UB.
Изменить на: (T(1) << i) для корректной работы.
Также немного похимичил еще.
Сделал на половину табличный вариант:
тест на той же машине, в тех же условиях, правда убрал «тормозные» функции, смотреть их результаты не интересно, и увеличил кол-во итераций в десять раз (теперь их 1000000000).
Результаты:
Результаты для size_t:
Результаты для char:
Конечно же, всё это достаточно условно.
Croessmah, по поводу
(T(1) << i)— ты абсолютно прав. Я недосмотрел, когда обычную функцию переделывал под шаблонную. Грешен ))Теперь по обеим, предложенным тобой функциям.
Во-первых, я уже писал выше, что возврат из функции ссылки на статическую переменную функции — зло. Ты возвращаешь указатель, который указывает на данные, которые находятся в статической (фактически) переменной. Такое же зло, только вид сбоку. Спецификатор хранения
thread_local— это тот жеstatic, только потокобезопасный. Пробуем?Во-вторых, ты схитрил, полностью отказавшись от
std::string. Поэтому сразу обеспечил себе прирост скорости. Если же мы приведём сигнатуру функции к общему, для остальных функций, видуtemplate<typename T> string f(T val)и последнюю строку функции исправим наreturn string(ptr);, попутно избавившись от бага, описанного выше, то время выполнения функции станет почти таким же, как и у варианта 3.Если всё-таки не применять
std::string, то тогда возникает проблема где хранить полученный результат. Решения два: либо в функции брать память из кучи, в надежде, что вызывающий код её потом освободит, либо получать буфер в качестве параметра с риском, что его размера может не хватить. Как-то очень небезопасно получается. Плюс копирование результата из временного буфера в выходной, что бы начало строки результата совпадало с началом буфера.PS. У меня (MS Visual Studio 2015 Community) почему-то неправильно компилируется конструкция
static constexpr char const *digits[16] = {...}. Ошибку компиляции не даёт, но при запуске при доступе к элементу массива выдаёт какую-то хрень. И под отладкой дебаггер не ловит концы строк. Вылечилось изъятиемconstexpr.По поводу конструкции
static constexpr char const *digits[16] = {...}.MS VS2015 компилирует её не как массив указателей на указатели на char, а как двумерный массив char, т.е.
char const digits[16][5] = {...}. Это как бы самое близкое определение, хотя и не точное.В памяти должно быть:
digits— это массив из 16 указателей; каждый указатель содержит адрес памяти, где хранится последовательность символов (строка), заканчивающаяся '\0'. Причём строки могут располагаться в памяти не вместе и не последовательно.Реально имеем: массива указателей нет; строки с завершающим '\0' из списка инициализации располагаются в памяти последовательно.
digitsуказывает на начало этой области памяти. Причём строки могут быть разной длины. Поэтому определениеchar const digits[16][5]некорректно.При этом обращение к элементам массива через индекс работает как и положено:
digits[0]должно содержать значение адреса, по которому должна находиться строка, а реально туда попадают первые 4 байта (для x86) первой строки. Как результат — обращение к запрещённой области памяти.digits[1]сдвинут относительноdigits[0], как и положено, на размер указателя, т.е. на 4 байта, из расчёта, чтоdigits— это массив указателей. Я тихо фалломорфирую.Вообще, это достаточно частая практика.
И хороша она тем, что не нужно дергать динамическую.
Конечно, в документации должно быть отражен данный факт.
А сломать можно что угодно.
Вы же используете конкретные функции опираясь
на документацию и интерфейс, а не «как хочу».
И да, thread_local — это как static, только для потока,
так что по факту вызов функции в разных потоках возможен.
Эм, я же написал, что от этого как раз все тормоза.
при этом, я исправил и другую (не мою функцию), чтобы показать различия.
Зачем? Если любую из этих функций изменить до неузнаваемости,
то получим вообще что угодно.
Я сделал некий интерфейс,
будьте добры следовать соглашениям,
которые установил я — разработчик данной библиотеки.
Не нравится? Не используйте или напишите обертку,
при этом у Вас есть выбор,
в отличии от варианта с std::string — где выбора нет.
Удивили. Возврат std::unique_ptr отменили?
Сам всё почистит при надобности.
Но здесь будет одна неувязочка,
если захотим построить std::string,
то придется всё это дело копировать заново.
Для этого можно использовать обертку, как это делается в boost,
причем буфером может быть тот же std::string.
Кстати, почти готов еще один вариант,
но еще нужно будет протестировать его на big-engian архитектуре.
Расчет тот же, только только вместо сдвигов и тому подобного напрямую
берутся байты из памяти и строка выбирается уже из таблицы.
Также можно соорудить еще один читерский вариант.
Он лишен всех перечисленных Вами «недостатков»,
но требует построения отдельного класса для работы.
Суть такова. Есть таблица байт, класс хранить массив с указателями.
Далее всё просто — парсим байтики числа, берем указатели из таблицы.
new дергается только при необходимости получить непрерывный буфер.
Но здесь тоже придется на big-engian проверять.
Пока «изобрел» один способ проверки архитектуры в compile-time,
чтобы получить значение constexpr на стадии компиляции,
хотя оно может быть не переносимо.
Ну или использовать всё-таки сдвиги и маски, но это медленнее.
Такие ошибки можно часто встретить, причем даже в «продвинутых» проектах.
Возможно, у меня побольше опыта в шаблонах, поэтому я это сразу увидел,
конечно, после того, как получил не верные результаты :)
Так что это не грех, а не досмотр + премия я исправление баги в софте )))
Тут ситуация как бэ полностью обратная: начинали мы обсуждение с функции, принимающей
intи возвращающейstd::string. Потом, с лёгкой руки porshe, обобщили до шаблона, принимающего любой целый знаковый тип. Проецируем на реальную ситуацию: есть большой проект, и есть функция, которую нужно оптимизировать. Менять сигнатуру функции в такой ситуации, сам понимаешь, ну никак.Я бы не стал к этому апеллировать. Говнокод — тоже достаточно частая практика. А
gets(),scanf(),strcpy(), etc. пользовали больше 30 лет, а потом таки чухнулись, что не кошерно.Библиотека должна быть надёжной и простой в использовании. Если использование библиотеки подобно хождению по канату с завязанными глазами, когда предварительно надо как-то обустроить страховочную лонжу и сетку внизу, то это плохая библиотека.
Следуя твоему совету, сделал обёртку для твоей первой функции, что бы возвращаемое значение было
std::string. Таймирование показало, что от скорострельности оригинальной функции остались рожки да ножки: функция-обёртка работает медленнее, чем та же функция, допиленная до возвратаstd::string. Что неудивительно: появился лишний вызов функции.Однако, всё работает, живет и приносит прибыль :)
Так в том-то и дело, что я не оптимизировал,
я написал другую реализацию для нового проекта.
А потом функцию из старого проекта протестировал в своем новом проекте,
но в двух вариантах и выбрал понравившийся.
А еще достаточно быстрой.
Врядли кто-то будет ждать полгода,
пока библиотека разродится и выдаст ответ,
когда рядом есть другая библиотека, которая,
может не так удобна, но выдаст результат через месяц.
А вы хотели, чтобы обертка работала быстрее?
Думаю, объяснять не стоит, что не реально :)
Что касается возврата std::string,
не ясно, а нужен ли он мне вообще?
Может мне нужен вектор char'ов?
А может вообще ничего не нужно.
Да и new дергать не хочется.
Я не знаю как Вам, а мне std::string
не нравится вообще никак,
поэтому я предпочту вариант без него.
Хоть и приходится его использовать частенько.
Не будем спорить, мы друг друга всё равно не переспорим.
Угу... Только сколько информации улетело на сторону через эти «стандартные» дыры в безопасности.
Значит в этом треде мы обсуждали разные задачи. Изначально имелось ввиду, что возвращаться будет
std::string. Да, он тормозит. Но интерес был в том, как свести к минимуму эти тормоза.Не-а. Хотел посмотреть на сколько обёртка замедлит работу «быстрой» функции.
Я тут ещё немного поэкспериментировал и оказалось, что быстродействие существенно зависит от компилятора и реализации STL.
Далее выдача тестовой программы. Первая колонка — название функции, вторая — время выполнения функции в секундах, третья — производительность в долях от времени выполнения первой функции (если умножить на 100, получим проценты).
MS Visual Studio 2015 Community
gcc version 5.1.0 (tdm64-1 Windows)
ничесе задачка для новичков
на первой странице я еще что-то понимал в коде
на второй моск уже стал отключаться
я даже не подозревал что в с++ есть такие слова
Не обращайте на нас внимания, мы в своей песочнице )))
Конечно. И от оптимизаций.
Например, если компилятор сможет применить SSO,
то вызовов new, фактически, вообще не будет.
А gcc мне вообще умудрился повырезать
все циклы к чертовой бабушке в новой функции,
пришлось ему костылей напихать,
чтобы он так резво не оптимизировал.
А я думал оптимизировать алгоритм перевода.
Хм, а как на счет не стандартного аллокатора?