Самый быстрый способ преобразовать двоичный файл в десятичное число?
Функторы довольно прохладны. Они достаточно близки к указателю функции, который все обычно быстры для высказывания, невозможно в Java.
5 ответов
Это зависит от того, что еще вы делаете с числами. Вы можете компенсировать небольшую потерю эффективности использования пространства и умеренную потерю эффективности арифметики с высокой точностью в обмен на очень эффективное преобразование в десятичную форму и обратно. Ключ состоит в том, чтобы выполнять арифметические операции с высокой точностью с основанием, которое является степенью 10, а не степенью 2.
Например, вы можете использовать базу 10 000, где вы упаковываете одну цифру в 16-битное слово и выполняете свою арифметика цифр в 32-битных целых числах. (Если вы работаете на 64-битной машине, вы можете удвоить это количество и использовать базу 1 000 000 000.) Этот вид кода относительно эффективен по времени, хотя и не так быстр, как использование собственной мощности двойки, потому что вы не можете воспользоваться преимуществами бит переноса на оборудовании. И вы не можете представить столько же целых чисел в одном и том же количестве битов. Но он гений в преобразовании в десятичное и обратно, потому что вы можете преобразовывать отдельные цифры без какого-либо деления в столбик.
Если вам нужно представить полный диапазон чисел от нуля до ((1 << 128) - 1) , вы все равно можете это сделать, но добавьте дополнительную цифру, чтобы ваши числа были больше.
Если окажется, что вам действительно нужно дополнительное пространство / скорость (возможно, вы делаете много криптографические 128-битные вычисления), то метод одновременного деления / модуляции на 10 - самый быстрый из известных мне методов. Единственный другой трюк заключается в том, что если маленькие целые числа являются обычным явлением, вы можете обрабатывать их специально. (То есть, если все три наиболее значимых 32-битных слова равны нулю, просто используйте собственное деление для преобразования.)
Есть ли хитрый способ реализовать эту функцию, которого я не вижу?
Дэйв Хэнсон ' s Интерфейсы и реализации C содержит длинную главу по арифметике с высокой точностью. Разделение большого числа на одну цифру - особый случай, в котором есть такая эффективная реализация:
int XP_quotient(int n, T z, T x, int y) {
int i;
unsigned carry = 0;
for (i = n - 1; i >= 0; i--) {
carry = carry*BASE + x[i];
z[i] = carry/y;
carry %= y;
}
return carry;
}
Для полного понимания полезно иметь книгу, но исходный код по-прежнему намного легче понять чем исходный код GNU. И вы можете легко адаптировать его для использования базы 10 000 (в настоящее время она использует базу 256).
Резюме: если ваше узкое место в производительности - преобразование в десятичную систему, реализуйте арифметику с множественной точностью с базой в степени 10 . Если собственный размер слова вашей машины равен 32, и вы используете код C, используйте 10 000 в 16-битном слове.
Разделение большого числа на одну цифру - особый случай, в котором есть такая эффективная реализация:int XP_quotient(int n, T z, T x, int y) {
int i;
unsigned carry = 0;
for (i = n - 1; i >= 0; i--) {
carry = carry*BASE + x[i];
z[i] = carry/y;
carry %= y;
}
return carry;
}
Для полного понимания, действительно полезно иметь книгу, но исходный код все же намного легче понять чем исходный код GNU. И вы можете легко адаптировать его для использования базы 10 000 (в настоящее время она использует базу 256).
Резюме: если ваше узкое место в производительности - преобразование в десятичную систему, реализуйте арифметику с множественной точностью с базой в степени 10 . Если собственный размер слова вашей машины равен 32, и вы используете код C, используйте 10 000 в 16-битном слове.
Разделение большого числа на одну цифру - особый случай, в котором есть такая эффективная реализация:int XP_quotient(int n, T z, T x, int y) {
int i;
unsigned carry = 0;
for (i = n - 1; i >= 0; i--) {
carry = carry*BASE + x[i];
z[i] = carry/y;
carry %= y;
}
return carry;
}
Для полного понимания полезно иметь книгу, но исходный код по-прежнему намного легче понять чем исходный код GNU. И вы можете легко адаптировать его для использования базы 10 000 (в настоящее время она использует базу 256).
Резюме: если ваше узкое место в производительности - преобразование в десятичную систему, реализуйте арифметику с высокой точностью с основанием, равным степени 10 . Если собственный размер слова вашей машины равен 32, и вы используете код C, используйте 10 000 в 16-битном слове.
000 (в настоящее время используется основание 256).Резюме: если ваше узкое место в производительности - преобразование в десятичное, реализуйте арифметику с множественной точностью с основанием, равным степени 10 . Если собственный размер слова вашей машины равен 32, и вы используете код C, используйте 10 000 в 16-битном слове.
000 (в настоящее время используется база 256).Резюме: если ваше узкое место в производительности - преобразование в десятичное, реализуйте арифметику с множественной точностью с основанием, равным степени 10 . Если собственный размер слова вашей машины равен 32, и вы используете код C, используйте 10 000 в 16-битном слове.
If your values are mostly less than ULLONG_MAX (18446744073709551615) I'd try to use for them sprintf(buf,"%llu",ullong_val). I bet this is rather well optimized in standard library, but parsing of format will take some cycles though.
Otherwise I'd create a bigint_divmod1000000000 (or better name mod10to9) function and use that. It would need 9 times less divides than bigint_divmod10.
Lookup table of 8 bits. You can have 4 lookup tables of 256 numbers. First is from 0-256 for LSB bytes, Second table is first table multiplied by 256 and so on.
SO when you need your number sum up numbers from lookup table. When you adding you can add as bunary and go later one pass over each byte to fix owerflows.
Example number 0x12345678 In first lookup table there is under addres (0x78 = 120) so 0x010200 is first number in second table under(0x56=87) is 0x0202000106 (0x56 in dec is 22016) in third table you hou would have 0x03040007080702 and under last lable at 0x12 you have 0x030001090809080808 (this does not fit in 32 bit arithmetic, but that you allredy know)
Then sum up this numbers (as binary bumbers) and go one pass, byte by byte for overflow код в цикле for выглядит примерно как
s=carry+val[i];
val[i]=val[i]&10
carry=s/10;
//you can put last two operations in table
Если мы посчитаем необходимые для этого операции.
1. (просмотр в таблицах и добавление) 4 таблицы поиска. 16 дополнений (имейте в виду, что когда вам не нужно носить с собой owerflow, потому что они не могут произойти)
2. one pass in each step 3 operatins 16 steps to pass.
passimistic upper bound 6*16 = 100 operations.
EDIT:
Here is c++ code, and is 30% faster than naive implementation.
#include <iostream>
#include <stdint.h>
#include <array>
static uint64_t lu[4][256];
constexpr uint64_t lookup_value(uint64_t n) {
uint64_t r = 0;
uint64_t t = 1;
while (n) {
uint64_t rem = n % 10;
n /= 10;
r += rem * t;
t *= 256;
}
return r;
}
void make_lu() {
uint64_t step = 1;
for (int j = 0; j < 4; ++j) {
uint64_t n = 0;
for (int i = 0; i < 256; ++i) {
lu[j][i] = lookup_value(n);
n += step;
}
step *= 256;
}
}
struct DivMod {
uint8_t div;
uint8_t rem;
};
static DivMod dm[256];
void make_dm() {
for (int i = 0; i < 256; ++i) {
dm[i].div = i / 10;
dm[i].rem = i % 10;
}
}
void init() {
make_lu();
make_dm();
}
uint64_t b2d(uint64_t n) {
uint64_t r = 0;
for (int i = 0; i < 4; ++i) {
r += lu[i][(n >> (i * 8)) & 0xff];
}
uint64_t r2 = 0;
uint64_t of = 0;
for (int i = 0; i < 8; ++i) {
uint64_t v = ((r >> (i * 8)) & 0xff) + of;
DivMod &x = dm[v];
of = x.div;
r2 += uint64_t(x.rem) << (i * 8);
}
return r2;
}
int main() {
init();
uint64_t n;
std::cin >> n;
std::cout << std::hex << b2d(n) << "\n";
return 0;
}
Для справки в будущем, вместо реализации типа uint128, я просто использовал символы строки напрямую. Это оказалось намного быстрее, чем переход от строки к uint128 и обратно.
Наиболее быстрое ускорение будет происходить за счет встраивания преобразования, а не вызова функций ; это может быть так же просто, как пометить bigint_divmod10 () inline или использовать оптимизацию на основе профиля, предлагаемую вашим компилятором.