logo标签列表

如何高效地获取一个数的第一位小数

c++calgorithm
14

一个显而易见的解决方案是：

int n = 2134;
while(n > 9)
    n /= 10;

它需要线性时间。我们能做得更快吗？

这比线性时间更快吗：

char s[100];
sprintf(s, "%d", n);
n = s[0]-'0';

还有其他方法吗（效率是主要考虑因素）？
我看了这个，但我只需要找到第一个数字。 （我也不理解答案。）

1
你的第二个例子可能应该使用sprintf而不是scanf？ - Mats Petersson
4
格式化输入/输出肯定比除法慢得多（数量级）。但是你做过基准测试吗？此外，那个 sscanf() 应该真的改成 snprintf() 吗？ - user529758
4
“我不明白答案”不是发表新问题的好理由，除非那个答案真的很糟糕。而事实上它并不糟糕，它更多地是 digits = floor(log10(n)); firstDigits = n/10^digits; 和将double类型强制转换为整型所组成的代码。 - millimoose
3
你能否给出一个“首位数字”的定义，而不是对数函数的线性关系 ？ - Kerrek SB
5
关于算法和复杂度的一个有趣之处是，你可以针对完全相同的算法陈述不同的渐近复杂度。对于除法方法，你可以说它是线性的，或者如果你考虑数字个数受限（在sizeof(int)==4的平台上最多有10个十进制数字），也可以被视为是常数的。仅仅说“线性的”可能听起来比实际情况更糟糕... - David Rodríguez - dribeas
显示剩余7条评论
13个回答
23

有些处理器拥有能够快速计算数字“大小”的指令（参见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;
}
1
这似乎是最快的解决方案，适用于支持此操作的处理器。 - TonyK
非常小的建议：使用uint32_t powers_of_10[33]。 - chux - Reinstate Monica
3
恕我直言，查找表并不快。通常它们需要访问 RAM，在最好的情况下是在缓存中 - 这仍然比寄存器中的工作慢得多。 - einpoklum
14

例如，对于32位无符号数：

步骤1：通过二分查找确定该值在以下哪个区间内：

0 .. 9
10 .. 99
100 .. 999
1000 .. 9999
10000 .. 99999
100000 .. 999999
1000000 .. 9999999
10000000 .. 99999999
100000000 .. 999999999
1000000000 .. 4294967295

最多需要4次比较。

步骤2：

然后通过一次除法计算出前导数字。

你可以硬编码二分查找 Step 1，以避免循环并提高速度。 - MrSmith42
6

我相信，sprintf函数（我猜测是这个函数）的速度会显著变慢。你可以进行一些优化来减少除法操作的次数（这通常是几乎所有处理器上最慢的指令之一）。

因此，可以尝试如下操作：

 while(n > 10000)
   n /= 1000;

 while(n >= 9)
   n /= 10;

当然，如果速度确实很重要。
看起来这正是libdivide所设计用来解决的情况。 - millimoose
5
如果速度非常重要，那么在十的幂 {1, 10, 100,...} 等上执行二分查找可能更快。之后您只需要进行一次除法运算。您可以将二分查找硬编码为一系列测试和跳转，最好使用汇编语言实现。 - TonyK
1
对于32位，第一个循环最多进行3次迭代。对于64位数字，减少除法的数量更有意义。 - Mats Petersson
当 n 大于等于 9 时，对于 n=9 的情况，输出为 0，因为 9/10=0，而不是 9。应该改为当 n 大于等于 10 时。 - Arjun Sunil Kumar
5
你的第二个例子应该使用sprintf函数。因为整个数字都被打印出来，所以会搜索所有数字，因此也不会更快。
链接的问题/答案使用了对数的一个特性：对于一个有x位数的数字，它的十进制对数介于x和x+1之间。但由于浮点误差，在某些情况下这种方法并不能正常工作。此外，请考虑到执行浮点运算比执行整数运算要慢。
因此，最简单的解决方案也是最快的。
那个对数解决方案不可能更快，因为它使用了对数函数。在现代处理器上，这比任何浮点算术都要昂贵得多。因此，是的，那个小循环肯定比sprintf或log()更快，甚至可能比MrSmith42的答案还要快。 - cmaster - reinstate monica
4

这是一种二分查找的变体。像二分查找一样，它的时间复杂度为O(log n)。但它的速度快不快取决于你能够多快地进行整数除法。

if (n >= 100000000)
    n /= 100000000
if (n >= 10000)
    n /= 10000
if (n >= 100)
    n /= 100
if (n >= 10)
    n /= 10

该方法可轻松扩展至更大范围的整数。
3
你可以简单地执行以下操作：

只需这样做：

//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;
}
谢谢，但有时候它并不起作用。请参阅Mihai Maruseac的上面的答案。 - mohit
3
您可以在常数时间 O(1) 内完成，但代价是非常大的内存使用。这是一个老生常谈的时间/内存权衡。
您可以创建一个 2^31 条目（有符号整数）的查找表，每个条目占用 4 位（用 4 位可以编码十进制表示中的第一位数字 1-9）。
然后，您可以使用整数来访问查找表并在 O(1) 的时间内获取第一位数字。 查找表将占用 2^31 * 4 位 -> 1024 Mbytes
这是我能想到的最快的方法...
3
由于内存膨胀会抵消由于内存延迟所带来的性能提升，因此这句话的意思是减少内存使用量。 - cmaster - reinstate monica
4
“内存膨胀”是显而易见的，并且可以通过达到O(1)来展示。这种方法在某些情况下非常实用。比如说，如果int范围被限制在0到1000之间，那么这样的表格大小就是可行的。通常在需要高性能例程时，存在这样的限制。我不希望OP列出所有条件 - 只需列出主要条件即可。虽然这种方法对于GP库没有用处，但它可能正好适合OP或未来的评论者。 - chux - Reinstate Monica
1
没错，我只是想展示一个人可以很容易地用时间来换取内存。 - Gianluca Ghettini
此外，使用重复除法的朴素方法在空间上是O(1)。@chux：OP是什么？GP是什么？ - Gianluca Ghettini
@chux OP = 原帖发布者; GP = 通用目的（可能） - anatolyg
4
我知道可以通过牺牲内存来换取性能，但这并不适合在这里这么做。正如其他答案所指出的那样，你可以通过四个步骤找到完整整数范围内的正确答案，而不必触及L1缓存，这肯定比等待内存子系统提供答案要快。缩小数字范围实际上会削弱你的论点，因为对于9999以内的范围，只需要两个步骤就可以得出答案。这不是一个应该用大量内存去解决的问题。 - cmaster - reinstate monica
1
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
}

also: lg(n) = ln(n) / ln(10);

1
浮点数计算不是精确的，舍入误差可能会导致10的幂产生错误结果（例如，在我的机器上，10000会产生错误的结果）。幸运的是，修复这个问题很容易。 - anatolyg
1
由于“_edit not accepted_”的格式不被接受，建议您重命名变量并进行改进。 - greybeard
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--;
        }
    }

然而，这段代码的复杂度应该是O（n ^ 2），这是不可取的。

0

你的第一个解决方案（假设已知 n >= 0）几乎是最优的，我认为只有通过使用内联汇编语言才能实现实质性改进。但这只有在处理数百万个这样的数字时才值得。

你的第二个解决方案 -- 怎么说呢？ -- 更像是一种 Java 风格的方法：性能？哦，谁在乎...

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接