Одно очевидное решение:
int n = 2134;
while(n > 9)
n /= 10;
которая принимает линейное время. Можем ли мы сделать быстрее?
Является ли это быстрее, чем линейное время:
char s[100];
sprintf(s, "%d", n);
n = s[0]-'0';
Какими другими способами (эффективность является первоочередной задачей)?
Я видел этот, за исключением того, что мне нужно найти только первую цифру.
(Кроме того, я не понимаю ответа).
Некоторые процессоры имеют инструкции, которые очень быстро вычисляют "насколько большой" число (см. http://en.wikipedia.org/wiki/Leading_zero_count). Это можно использовать для быстрого выбора мощности 10 и деления на нее вместо деления на 10.
Предположим, вам дана функция clz, которая вычисляет количество начальных нулевых битов в двоичном представлении числа (0... 32). Затем вы можете использовать таблицу поиска, которая дает правильную мощность 10 для каждого числа ведущих нулей.
uint32_t powers_of_10[33] = {
1000000000, 1000000000,
100000000, 100000000, 100000000,
10000000, 10000000, 10000000,
1000000, 1000000, 1000000, 1000000,
100000, 100000, 100000,
10000, 10000, 10000,
1000, 1000, 1000, 1000,
100, 100, 100,
10, 10, 10,
1, 1, 1, 1, 1
};
int CalcFirstDecimalDigit(uint32_t x)
{
int leading_zeros = clz(x);
x /= powers_of_10[leading_zeros];
if (x >= 10)
return 1;
else
return x;
}
например. для 32 бит без знака:
Шаг 1: определите (по бинарному поиску), в каком из следующих интервалов значение:
0 .. 9
10 .. 99
100 .. 999
1000 .. 9999
10000 .. 99999
100000 .. 999999
1000000 .. 9999999
10000000 .. 99999999
100000000 .. 999999999
1000000000 .. 4294967295
принимает максимум 4 сравнения
Шаг 2:
Затем вычислите начальную цифру на одно деление.
Второй пример должен использовать sprintf. Во всяком случае, он не может быть быстрее, так как все число печатается, поэтому все цифры просматриваются.
Связанный вопрос/ответ использует свойство логарифма: для числа x цифр он основывается на 10 логарифмах между x и x+1. Но из-за ошибок с плавающей запятой этот метод в некоторых случаях не работает должным образом. Кроме того, учтите, что выполнение с плавающей запятой происходит медленнее, чем выполнение целочисленной арифметики.
Таким образом, самое простое решение также быстрее.
Я уверен, что sprintf (как я предполагаю) будет ЗНАЧИТЕЛЬНО медленнее. Вы можете сделать некоторую оптимизацию, чтобы уменьшить количество операций деления (что является одной из самых медленных инструкций почти для всех процессоров).
Итак, можно сделать что-то вроде этого:
while(n > 10000)
n /= 1000;
while(n >= 9)
n /= 10;
Это, конечно, если скорость действительно важна.
вы можете сделать это в O (1) постоянном времени, но за счет очень большого использования памяти. Это то же самое время, что и время/память.
Вы можете создать таблицу поиска из 2 ^ 31 записей (подписанный int), 4 бита на запись (с 4 битами вы можете кодировать первую цифру 1-9 числа в десятичном представлении).
то вы можете использовать int для доступа к таблице поиска и получения первой цифры в O (1). таблица поиска займет 2 ^ 31 * 4 бит → 1024 Мбайт
это самый быстрый способ, о котором я могу думать...
Вот несколько вариантов бинарного поиска. Как двоичный поиск, это O (log n). Будет ли это быстрее будет зависеть от того, насколько быстро вы можете сделать целочисленное деление.
if (n >= 100000000)
n /= 100000000
if (n >= 10000)
n /= 10000
if (n >= 100)
n /= 100
if (n >= 10)
n /= 10
Метод легко расширяется для целых чисел с большим диапазоном.
Вы можете сделать это просто:
//Shashank Jain
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int num,fdigit;
cin>>num;
if(num<0)
num*=-1;
int l=log10(num); // l = (length of number -1)
fdigit=num/pow(10,l);
cout<<fdigit<<endl;
return 0;
}
int FirstDigit ( int Number ) {
// to obtain the <number of digits -1> use this math formula:
int DigitsInNumber = (int) lg(Number);
long TenExpon = pow(10, DigitsInNumber);
return (Number / TenExpon); //first digit
}
также: lg(n) = ln(n) / ln(10);
Ваше первое решение (предполагая, что n известно как >= 0) является почти оптимальным, и я думаю, что его можно было бы существенно улучшить, используя язык ассемблерной сборки. Но это было бы полезно, если бы вы обрабатывали миллионы таких чисел.
Ваше второе решение - как я могу это поместить? - более явный подход: производительность? Ла-ди-да, кто заботится...
for(int i=0; i<n; i++)
{
e=5; //Specify the number of digits in the number OR Exponential value of 10
while(e>=0)
{
tenp=pow(10,e); //#include <math.h>
if(arr[i]/tenp!=0)
{
q[i][e]=arr[i]/tenp%10;
}
e--;
}
}Другое решение: хранить все ваши значения в формате BCD, с прямым порядком байтов. Получите первый клев, чтобы получить первую цифру
Es.
Decimal value: 265
BCD format: 0010-0110-0101
если вы номер x9x8x7x6x5x4x3x2x1, тогда вы просто разделите на 10 ^ 8 так что вам нужно: лучший способ узнать, сколько цифр число. Вы можете использовать двоичный поиск/
Сначала сделайте двойную переменную, в которой сохранено число. Затем разделите это число на 10 в цикле, чтобы число непрерывно теряло цифру, пока оно не станет 1-значным числом. приведите двойную переменную к int, чтобы округлить ее. Результатом будет первая ранее десятичная цифра.
Код будет работать в O (log (n)).
#include <iostream>
using namespace std;
int main() {
double a;
cin >> a;
while (true) {
a /= 10;
if (a < 10) {
a = int(a);
cout << a;
break;
}
}
return 0;
}