Более быстрый способ обрезания 0s от long вместо% 10

Question

Я ищу "усечь" 0 из длинных значений.

Например, для длинного значения "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

Обновите вашу 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 2

Немного быстрее заменить '%' на '*'

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;
}

Answer 3

Очень маловероятно, что он будет работать эффективно со сдвигом битов, поскольку он идеально подходит для деления на степени двух, из которых 10 равно , а не единица.

Возможностьдля улучшения, когда вы можете часто получать числа с большим количеством конечных нулей, используйте несколько циклов для выполнения работы большими кусками, например:

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.

Очевидно, это займет больше места для хранения, но вы часто обнаружите, что оптимизация - это компромисс времени и пространства.