Разбить число на байты и проверить их последовательность

Romeo · 13 ноя 2015, 15:46

Сионист, если ты говоришь, что обёртка - это плохо, то ты просто ничего не смыслишь в коммерческой разработке - это раз. Во-вторых, если тебя волнует оптимизация лишнего вызова, то напиши в каждой перегруженной функции квалификатор inline. И вообще, я удивляюсь, почему ты придираешься к дословной и добуквенной моей имплементации, ведь я привёл абстрактный код, который работает для всех целых чисел. Если тебе абстракция не нужна, то мою имплементацию можно легко переделать на int, убрав абстракцию, тем самым сэкономив несколько процессорных тактов на дополнительный вызов, о котором ты так печёшься. Ты что, не понимаешь, что я делаю логический акцент на оптимальность алгоритма который я выбрал, а не конкретной имплементации. Даже в той имплеменатции, которая у меня сейчас есть (предположим я не написал inline или не переделал код сугубо на int, как это сделано у тебя), мой код проиграет твоему в момент вызова (а это всего несколько процессорных тактов), но зато потом "сделает" во время работы основного алгоритма, отработав минимум в 100 раз быстрее. Ты прямо, как маленький. Твои доводы звучат наподобие "Ну и катайся на своей Феррари, зато у моего жигулёнка быстрее двери открываются".

А часть твоего дальнейшего "развернутого" ответа я перестал читать после строки "Байт может состоять и из 16-ти, и из 48-ми и даже из 96-ти бит". Иди лучше поспорь с википедией, что такое байт.

Сионист · 14 ноя 2015, 06:45

Не обёртка - это плохо, а лишняя обёртка - это плоховато.

ведь я привёл абстрактный код, который работает для всех целых чисел.

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

но зато потом "сделает" во время работы основного алгоритма, отработав минимум в 100 раз быстрее.

Не понял. За счёт чего? Счётчик в худшем случае отстаёт в 16 раз, даже если его инкремировать побайтно на машине, чьё слово равно байту. Но на современных машинах скорей байт будет расширен до слова, обработан и снова ужат, на что тратится в три раза больше времени, чем на инкремент слова. Ну ещё проверка значения. В худшем случае займёт в 8 раз больше времени проверка счётчика, чем флага. В лучшем в 3 раза меньше. Это вторая операция. А сам цикл один и тот же и выражение, по которому смещение считается, одно.

Сионист · 14 ноя 2015, 07:07

Romeo писал(а):А часть твоего дальнейшего "развернутого" ответа я перестал читать после строки "Байт может состоять и из 16-ти, и из 48-ми и даже из 96-ти бит". Иди лучше поспорь с википедией, что такое байт.

Ну в викепидию и я пишу. А байт - это не 8 бит, а минимально адресуемая ячейка двоичной памяти, обычно состоящая из 8-ми значащих бит. Обычно, а не всегда, так что ни какой стандарт конкретной платформы не может гарантировать, что не появится какая нибудь экзотика, или что она не могла существовать в прошлом. Байт, равный восьми битам, - это лишь совпадающая часть стандартов многих, но вполне конкретных платформ. Они ни как не могут запретить реализовать в какой нибудь экзотике адресацию хоть каждого бита, хоть минимум килобита. Сам же предлагаешь спаять свой комп с иной адресацией. А байт - единица именно адресации, так что на таком чудеюде байт будет другим. Память сетуни вообще состояла из трайтов по 6 трит.

Сионист · 14 ноя 2015, 07:39

Кстати, почему по-твоему скорость сетей указывается именно в битах в секунду, а не в байтах в секунду? Не ради же больших чисел. А фокус прост: на случай, если в одной сети присутствуют машины с не равным размером байта, тогда скорость, выраженная в байтах в секунду, окажется не определена. Ни кто ведь не запрещает для какой то узкой области применения сократить разрядность байта до четырёх бит, проблем с кодировкой URL от этого не возникнет, просто те же коды символов будут на этих машинах двухбайтными, а на остальных однобайтными и их можно будет подключить к одному и тому же интернету. Или, наоборот, отменить адресацию октетов и поднять разрядность байта до 32-х бит. В интернете будет проблематично обратиться к DNS, но в локалке на том же IP4 проблем может не быть, просто на части машин IP4 будет однобайтным, всё равно ведь по частям не передаётся, а внутрисетевой вариант адреса предусматривает не отсутствие номера сети, а ноли в номере сети. А бит и трит - это единицы информации, от платформы не зависящие.

Romeo · 14 ноя 2015, 10:25

Сионист писал(а):Не обёртка - это плохо, а лишняя обёртка - это плоховато.

Я ещё раз говорю, что предоставил наиболее общее решение для всех случаев жизни. А всё потому, что никак не мог от тебя добиться вопроса о том, как у тебя хранится это входное число. Если оно будет из 255 байт (что позволено по условиям задачи), то положить его в int у тебя точно не получится. Нужен будет создавать вручную массив байтов - это самое простое, что делается в таких случаях. Если у тебя есть гарантия, что число лежит в int, из моего кода можно повыкидывать лишнее, лишив его абстрактности и никаких лишних вызовов обёрток не будет. Ты пойми, я публике не обёртки предоставлял на обозрение и не абстракциями хвастался. Самое главное в моем коде - это алгоритм. Он супер быстр.

Сионист писал(а):Не понял. За счёт чего?

За счёт операций "делить" и "остаток от деления". Операции с вещественными числами выполняются в среднем в 50-100 раз медленнее, чем целочисленные операции.

Сионист писал(а):Обычно, а не всегда, так что ни какой стандарт конкретной платформы не может гарантировать, что не появится какая нибудь экзотика, или что она не могла существовать в прошлом.

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

Сионист · 14 ноя 2015, 12:36

За счёт операций "делить" и "остаток от деления". Операции с вещественными числами выполняются в среднем в 50-100 раз медленнее, чем целочисленные операции.

Ну ка найди эти операции.

Сионист · 14 ноя 2015, 12:40

За счёт операций "делить" и "остаток от деления". Операции с вещественными числами выполн

Найди их. Кстати, я уже ужал вспомогательный массив до sizeof(x):

Код: Выделить всё

const unsigned char *Digit;
int Counts;
unsigned char *Count;
Counts=0;
for (Digit=(const unsigned char*)(&x)+sizeof(x)-1; Digit>=(const unsigned char*)(&x); --Digit)
{
 if ((*Digit)<sizeof(x))
 {
  Count=((unsigned char*)(&Counts))+(*Digit);
  if ((*Count)!=0)
  {
   return false;
  }
  ++(*Count);
 }
 else
 {
  return false;
 }
}
return true;

.

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

Звать этот тип могут и long long int, и даже hyper.

Я тебе скажу по секрету, что на тех редких и по большей части древних машинах, твою программу всё равно нужно будет переписывать, так как на тех машинах и платформах не было вообще компилятора С++

1. Для древностей можно написать кроскомпилятор, который сам будет работать на AMD64. Проблема здесь не в языке, а в памяти: сама прога в них тупо не влезет.
2. Октет в роли байта не только не сразу был принят. Нет гарантии, что экзотика не появится снова. С компилятором.

Absurd · 14 ноя 2015, 13:15

Romeo писал(а):За счёт операций "делить" и "остаток от деления". Операции с вещественными числами выполняются в среднем в 50-100 раз медленнее, чем целочисленные операции.

Корреспондент phoronix недавно нашел автора гениальной формулы из этого кода. Автор сказал что к счастью, после появления SSE2/SSE3 такие извраты больше не нужны.

Код: Выделить всё

float Q_rsqrt( float number )
{
	long i;
	float x2, y;
	const float threehalfs = 1.5F;

	x2 = number * 0.5F;
	y  = number;
	i  = * ( long * ) &y;                       // evil floating point bit level hacking
	i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
	y  = * ( float * ) &i;
	y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//	y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

	return y;
}

Сионист · 14 ноя 2015, 13:25

Кстати, если уж любишь автомобильные аналогии, то скажи, что лучше: просто лабмраждина диабло, или ферари с навесной маскировкой под ламбраджину диаблу? При условии, что двигатель и трансмиссия у них одного качества. Целевая функция в паре с оболочечной - это не феррари с заржавевшей дверью, а машина с навесной маскировкой под другую.

somewhere · 14 ноя 2015, 16:02

За счёт операций "делить" и "остаток от деления". Операции с вещественными числами выполняются в среднем в 50-100 раз медленнее, чем целочисленные операции.

Это было во времена 486-го процессора. Сейчас это время сократилось на порядок.

Корреспондент phoronix недавно нашел автора гениальной формулы из этого кода. Автор сказал что к счастью, после появления SSE2/SSE3 такие извраты больше не нужны.

Они были не нужны уже году так в 2002. От поколения к поколению скорость вычислительных операций FPU по отношению к целочисленным - росла. Сейчас подобный изврат с вычислением квадратного корня будет работать ощутимо медленнее аналогичной инструкции FPU, даже без SSE