как посчитать ненулевые элементы в матрице?

Question

У меня есть матрица с двумя значениями (0,1), мне нужно посчитать количество «1» в этой матрице, поэтому я попытался проверить все элементы, но для матрицы [1000,1000] это занимает слишком много времени и другая проблема заключается в том, что я должен делать это много раз для разных матриц, поэтому я надеюсь, что кто-нибудь сможет мне помочь с более быстрым режимом.

вот мой код:

for (int i = 0; i < matrix.height; i++)
{
    for (int j = 0; j < matrix.width; j++)
    {
        if (matrix[j, i] == 1)
        {
            count++;
        }
    }
}

Answer 1

У вас есть несколько вариантов, если вы сами реализуете матричный класс:

public class BoleanMatrix
{
     public bool this[int i, int j] {get;set;}
}

1. Кэшируйте это. Это просто. При любой модификации просто обновите кэшированное значение старших бит. Реализация не имеет значения.

   public class BoleanMatrix
   {
       private int _highBitCount = 0;
       public bool this[int i, int j] 
       {
           get;
           set
           {
               if(prev != value)
               { 
                   if(value)
                       _highBitCount++;
                   else
                       _highBitCount--;
               }
               //set here
            }
       }
   }
   

2. Измените реализацию на любой разреженный вариант, например, вы можете хранить значения матрицы в виде битов в массиве byte []. Если это все еще слишком много - сожмите это с Кодированием Длины Выполнения. Это связано с недостатками, такими как проблемы с обновлением и распространением этой матрицы, и обычно они намного медленнее, чем у матрицы с широким объемом памяти. Эффективный алгоритм сильно зависит от природы вашей матрицы (распределение значений) и от того, как вы их используете (умножение, деление, вычитание и т. Д.).

Answer 2

Попробуйте параллель для цикла?Если это не может быть кэшировано.

        object mylock = new object();
        int count = 0;

        Parallel.For(0, matrix.height, i =>
        {
            int forcount = 0;

            for (int j = 0; j < matrix.width; j++)
            {
                if (matrix[j, i] == 1)
                {
                    forcount++;
                }
            }

            lock (mylock)
            {
                count += forcount;
            }
        }
        );

Answer 3

Учитывая, что вы храните только биты, вы можете улучшить использование хранилища, сохранив биты, упакованные в значения uint, что уменьшит объем пространства, требуемый в 32 раза, по сравнению с использованием int для каждого значения .

Если вы сделаете это, то вы также можете более эффективно подсчитать количество установленных битов, используя один из множества различных «Вес Хэмминга» алгоритмов.

Недостаток этого подхода заключается в том, что доступ к отдельным битам с помощью индексатора массива BitMatrix может быть медленнее, но вычисление количества установленных битов происходит намного быстрее (более чем в 90 раз быстрее для режима RELEASE, основанного на мой компьютер).

Вот пример кода; важный класс BitMatrix:

using System;
using System.Diagnostics;

namespace Demo
{
    class Program
    {
        static void Main()
        {
            int[,] matrix = new int[1000, 1000];
            BitMatrix bitMatrix = new BitMatrix(1000, 1000);

            // Randomly populate matrices and calculate expected count.

            var rng = new Random(985912);
            int expected = 0;

            for (int r = 0; r < 1000; ++r)
            {
                for (int c = 0; c < 1000; ++c)
                {
                    if ((rng.Next() & 1) == 0)
                        continue;

                    ++expected;
                    matrix[r, c]    = 1;
                    bitMatrix[r, c] = true;
                }
            }

            Console.WriteLine("Expected = " + expected);

            // Time the explicit matrix loop.

            var sw = Stopwatch.StartNew();

            for (int i = 0; i < 1000; ++i)
                if (count1(matrix) != expected)
                    Console.WriteLine("count1() failed");

            var elapsed1 = sw.ElapsedTicks;
            Console.WriteLine(sw.Elapsed);

            // Time the hamming weight approach.

            sw.Restart();

            for (int i = 0; i < 1000; ++i)
                if (bitMatrix.NumSetBits() != expected)
                    Console.WriteLine("NumSetBits() failed");

            var elapsed2 = sw.ElapsedTicks;
            Console.WriteLine(sw.Elapsed);

            Console.WriteLine("BitMatrix matrix is " + elapsed1 / elapsed2 + " times faster");
        }

        static int count1(int[,] matrix)
        {
            int h = 1 + matrix.GetUpperBound(0);
            int w = 1 + matrix.GetUpperBound(1);

            int c = 0;

            for (int i = 0; i < h; ++i)
                for (int j = 0; j < w; ++j)
                    if (matrix[i, j] == 1)
                        ++c;

            return c;
        }
    }

    public sealed class BitMatrix
    {
        public BitMatrix(int rows, int cols)
        {
            Rows = rows;
            Cols = cols;
            bits = new uint[(rows*cols+31)/32];
        }

        public int Rows { get; }
        public int Cols { get; }

        public int NumSetBits()
        {
            int count = 0;

            foreach (uint i in bits)
                count += hammingWeight(i);

            return count;
        }

        public bool this[int row, int col]
        {
            get
            {
                int n = row * Cols + col;
                int i = n / 32;
                int j = n % 32;

                uint m = 1u << j;

                return (bits[i] & m) != 0;
            }

            set
            {
                int n = row * Cols + col;
                int i = n / 32;
                int j = n % 32;

                uint m = 1u << j;

                if (value)
                    bits[i] |= m;
                else
                    bits[i] &= ~m;
            }
        }

        static int hammingWeight(uint i)
        {
            i = i - ((i >> 1) & 0x55555555);
            i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
            return (int)((((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24);
        }

        readonly uint[] bits;
    }
}

Если вы используете 64-битный код, то на самом деле более эффективно использовать массив ulong и вычислять 64-битный вес Хэмминга.

Когда я попробовал это на моем ПК, это было более чем в 120 раз быстрее.

Вот 64-битная версия BitMatrix:

public sealed class BitMatrix
{
    public BitMatrix(int rows, int cols)
    {
        Rows = rows;
        Cols = cols;
        bits = new ulong[(rows*cols+63)/64];
    }

    public int Rows { get; }
    public int Cols { get; }

    public int NumSetBits()
    {
        int count = 0;

        foreach (ulong i in bits)
            count += hammingWeight(i);

        return count;
    }

    public bool this[int row, int col]
    {
        get
        {
            int n = row * Cols + col;
            int i = n / 64;
            int j = n % 64;

            ulong m = 1ul << j;

            return (bits[i] & m) != 0;
        }

        set
        {
            int n = row * Cols + col;
            int i = n / 64;
            int j = n % 64;

            ulong m = 1ul << j;

            if (value)
                bits[i] |= m;
            else
                bits[i] &= ~m;
        }
    }

    static int hammingWeight(ulong i)
    {
        i = i - ((i >> 1) & 0x5555555555555555UL);
        i = (i & 0x3333333333333333UL) + ((i >> 2) & 0x3333333333333333UL);
        return (int)(unchecked(((i + (i >> 4)) & 0xF0F0F0F0F0F0F0FUL) * 0x101010101010101UL) >> 56);
    }

    readonly ulong[] bits;
}

Наблюдение: Оказывается, немного быстрее использовать for() вместо foreach в цикле в NumSetBits(), например:

public int NumSetBits()
{
    int count = 0;

    for (var index = 0; index < bits.Length; index++)
        count += hammingWeight(bits[index]);

    return count;
}

На моем ПК это меняет производительность со 120 раз быстрее до 130 раз быстрее.

Наконец: если вы хотите воспользоваться преимуществами многопоточности, вы можете сделать это следующим образом (обратите внимание на использование Partitioner - это увеличивает размер блока данных, вычисляемых каждым потоком, чтобы сделать его намного более эффективным ):

public int NumSetBits()
{
    int count = 0;
    var partitioner = Partitioner.Create(0, bits.Length);

    Parallel.ForEach(partitioner, (range, loopState) =>
    {
        int subtotal = 0;

        for (int i = range.Item1; i < range.Item2; ++i)
        {
            subtotal += hammingWeight(bits[i]);
        }

        Interlocked.Add(ref count, subtotal);
    });

    return count;
}

С этим изменением подход Хемминга почти в 200 раз быстрее (и почти в 300 раз быстрее для матрицы 2000x2000), но учтите, что величина, на которую он быстрее, зависит от установленной пропорции 1 бита.