从 long 中截断 0 代替 % 10 的更快方法

Question

我正在从 long 值中寻找 "truncate" 0。

例如，对于 long 值“1234560000”，我想删除最后四个 0（到 123456）并且还需要知道删除了多少个 0。

我可以通过 % 10 次操作实现：

void Main()
{
    Console.WriteLine(Truncate(1234560000));
}

public static long Truncate(long mantissa)
{
    int droppedZeros = 0;

    while (mantissa % 10 == 0)
    {
        mantissa /= 10;
        droppedZeros++;
    }

    return mantissa;
}

这段代码被调用了数百万次并且对性能至关重要，我正在寻找提高性能的方法以在没有模数的情况下实现相同的效果（这可以通过位移来完成吗？）。

根据请求，我添加了一些基准测试数字，包括执行除法的基准测试，编译时间已知常量以展示模运算的相对开销：

          Method |      Mean |     Error |    StdDev |    Median | Gen 0/1k Op | Gen 1/1k Op | Gen 2/1k Op | Allocated Memory/Op |
---------------- |----------:|----------:|----------:|----------:|------------:|------------:|------------:|--------------------:|
  DivideNoModulo |  1.863 ms | 0.0431 ms | 0.1272 ms |  1.855 ms |           - |           - |           - |                   - |
     ModuloBasic | 21.342 ms | 0.8776 ms | 2.5876 ms | 20.813 ms |           - |           - |           - |                   - |
   DivisionBasic | 18.159 ms | 1.7218 ms | 5.0768 ms | 15.937 ms |           - |           - |           - |                   - |
 DivisionSmarter |  7.510 ms | 0.5307 ms | 1.5649 ms |  7.201 ms |           - |           - |           - |                   - |
   ModuloSmarter |  8.517 ms | 0.1673 ms | 0.2886 ms |  8.531 ms |           - |           - |           - |                   - |
  StringTruncate | 42.370 ms | 1.7358 ms | 5.1181 ms | 40.566 ms |   1000.0000 |           - |           - |           8806456 B |

基准代码：

 [SimpleJob(RunStrategy.ColdStart, 1)]
    [MemoryDiagnoser]
    public class EncoderBenchmark
    {
        private long _mantissa;

        [Benchmark]
        public void DivideNoModulo()
        {
            for (var i = 0; i < 100000; i++)
            {
                _mantissa = 12345600000000;

                _mantissa /= 100000000;
            }
        }

        [Benchmark]
        public void ModuloBasic()
        {
            for (var i = 0; i < 100000; i++)
            {
                _mantissa = 12345600000000;

                while (_mantissa % 10 == 0)
                {
                    _mantissa /= 10;
                }
            }
        }

        [Benchmark]
        public void DivisionBasic()
        {
            for (var i = 0; i < 100000; i++)
            {
                _mantissa = 12345600000000;

                for (;;)
                {
                    long temp = _mantissa / 10;
                    if (temp * 10 != _mantissa)
                        break;

                    _mantissa = temp;
                }
            }
        }


        [Benchmark]
        public void DivisionSmarter()
        {
            for (var i = 0; i < 100000; i++)
            {
                _mantissa = 12345600000000;


                for (; ; )
                {
                    long temp = _mantissa / 1000000;
                    if (temp * 1000000 != _mantissa)
                        break;

                    _mantissa = temp;
                }

                for (; ; )
                {
                    long temp = _mantissa / 10;
                    if (temp * 10 != _mantissa)
                        break;

                    _mantissa = temp;
                }
            }
        }

        [Benchmark]
        public void ModuloSmarter()
        {
            for (var i = 0; i < 100000; i++)
            {
                _mantissa = 12345600000000;

                while (_mantissa % 1000000 == 0)
                {
                    _mantissa /= 1000000;
                }

                while (_mantissa % 10 == 0)
                {
                    _mantissa /= 10;
                }
            }
        }

        [Benchmark]
        public void StringTruncate()
        {
            for (var i = 0; i < 100000; i++)
            {
                _mantissa = 12345600000000;

                _mantissa = long.Parse(_mantissa.ToString().TrimEnd('0'));
            }
        }
    }

Answer 1

您不太可能通过位移使其高效工作，因为它非常适合除以 2 的幂，其中 10 是 而不是 1。

改进的可能性是使用多个循环以更大的块来完成工作，例如：

if (mantissa != 0) {
    while (mantissa % 1000000 == 0) {
        mantissa /= 1000000;
        droppedZeros += 6;
    }
    while (mantissa % 1000 == 0) {
        mantissa /= 1000;
        droppedZeros += 3;
    }
    while (mantissa % 10 == 0) {
        mantissa /= 10;
        droppedZeros++;
    }
}

这通常会导致执行的指令更少，但是，与所有优化一样，测量，不要猜测！ 可能是增加的代码复杂性不值得你得到的收益（如果有的话）。

请注意，我也发现了 mantissa == 0 的情况，因为这会导致您的原始代码出现无限循环。

您可能要考虑的另一种可能性是，如果您多次对相同项目执行此操作。例如，假设您有一组整数，每次需要处理其中一个时，您都必须剥离并计算尾随零。

在那种情况下，您实际上可以用不同的方式存储它们。例如，考虑（伪代码）结构：

struct item:
    int originalItem
    int itemWithoutZeroes
    int zeroCount

基本上，每当您第一次收到一个项目（例如1234560000）时，您会立即将其转换为结构一次且仅一次:

{ 1234560000, 123456, 4 }

这提供了零剥离项的缓存版本，因此您无需再次计算它。

因此，如果您想要去除尾数，只需使用 item.itemWithoutZeros。如果要以原始形式输出数字，可以使用item.originalItem。而且，如果你想要零的数量，请使用 item.zeroCount.

显然，这会占用更多存储空间 space，但您经常会发现优化是一种 time/space 权衡。

Answer 2

更新您的 Truncate 逻辑如下。

public static long Truncate(long mantissa)
{
    if (mantissa == 0)
      return 0;
    var mantissaStr = mantissa.ToString();
    var mantissaTruncated = mantissaStr.TrimEnd('0');
    int droppedZeros = mantissaStr.Length - mantissaTruncated.Length;
    return Convert.ToInt64(mantissaTruncated);
}

Answer 3

快一点用“*”替换“%”

public static long T(long mantissa)
{
    if (mantissa == 0)
        return 0;

    int droppedZeros = 0;

    for (; ; )
    {
        long temp = mantissa / 1000000;
        if (temp * 1000000 != mantissa)
            break;

        mantissa = temp;
        droppedZeros += 6;
    }

    for (; ; )
    {
        long temp = mantissa / 1000;
        if (temp * 1000 != mantissa)
            break;

        mantissa = temp;
        droppedZeros += 3;
    }

    for (; ; )
    {
        long temp = mantissa / 10;
        if (temp * 10 != mantissa)
            break;

        mantissa = temp;
        droppedZeros++;
    }

    return mantissa;
}

从 long 中截断 0 代替 % 10 的更快方法

Faster way of truncating 0s from long in lieu of % 10

c#

modulo