Связанная 2D матрица в C #

Question

Мне нужно реализовать этот сценарий на C #:

Матрица будет очень большой, возможно, 10000x10000 или больше.Я буду использовать это для матрицы расстояний в алгоритме иерархической кластеризации.На каждой итерации алгоритма матрица должна обновляться (объединяя 2 строки в 1 и 2 столбца в 1).Если я использую простую матрицу double [,] или double [] [], эти операции будут очень «дорогими».Пожалуйста, кто-нибудь может предложить C # реализацию этого сценария?

Answer 1

Невозможно «объединить» две строки или два столбца, вам придется скопировать всю матрицу в новую, меньшую, что действительно недопустимо дорого.

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

массивы массивов: double [] [] на самом деле быстрее, чем double [,]. Но занимает больше памяти.

Слияние всего массива может не понадобиться, если вы немного измените алгоритм, но это может помочь вам:

    public static void MergeMatrix()
    {
        int size = 100;
        // Initialize the matrix
        double[,] matrix = new double[size, size];
        for (int i = 0; i < size; i++)
            for (int j = 0; j < size; j++)
                matrix[i, j] = ((double)i) + (j / 100.0);

        int rowMergeCount = 0, colMergeCount = 0;
        // Merge last row.
        for (int i = 0; i < size; i++)
            matrix[size - rowMergeCount - 2, i] += matrix[size - rowMergeCount - 1, i];
        rowMergeCount++;
        // Merge last column.
        for (int i = 0; i < size; i++)
            matrix[i, size - colMergeCount - 2] += matrix[i, size - colMergeCount - 1];
        colMergeCount++;

        // Read the newly merged values.
        int newWidth = size - rowMergeCount, newHeight = size - colMergeCount;
        double[,] smaller = new double[newWidth, newHeight];
        for (int i = 0; i < newWidth; i++)
            for (int j = 0; j < newHeight; j++)
                smaller[i, j] = matrix[i, j];

        List<int> rowsMerged = new List<int>(), colsMerged = new List<int>();
        // Merging row at random position.
        rowsMerged.Add(15);
        int target = rowsMerged[rowMergeCount - 1];
        int source = rowsMerged[rowMergeCount - 1] + 1;
        // Still using the original matrix since it's values are still usefull.
        for (int i = 0; i < size; i++)
            matrix[target, i] += matrix[source, i];
        rowMergeCount++;

        // Merging col at random position.
        colsMerged.Add(37);
        target = colsMerged[colMergeCount - 1];
        source = colsMerged[colMergeCount - 1] + 1;
        for (int i = 0; i < size; i++)
            matrix[i, target] += matrix[i, source];
        colMergeCount++;

        newWidth = size - rowMergeCount;
        newHeight = size - colMergeCount;
        smaller = new double[newWidth, newHeight];
        for (int i = 0, j = 0; i < newWidth && j < size; i++, j++)
        {
            for (int k = 0, m = 0; k < newHeight && m < size; k++, m++)
            {
                smaller[i, k] = matrix[j, m];
                Console.Write(matrix[j, m].ToString("00.00") + " ");

                // So merging columns is more expensive because we have to check for it more often while reading.
                if (colsMerged.Contains(m)) m++;
            }

            if (rowsMerged.Contains(j)) j++;
            Console.WriteLine();
        }

        Console.Read();
    }

Answer 2

Как упомянуто выше, простой double [,] будет наиболее эффективным способом обработки этого в C #.

Помните, что C # находится на вершине управляемой памяти, и поэтому у вас меньше штрафовзернистый контроль над низкоуровневыми (с точки зрения памяти) операциями в отличие от чего-то вроде базового C. Создание собственных объектов в C # для добавления функциональности будет использовать только больше памяти в этом сценарии и, вероятно, также замедлит алгоритм.

Если вы еще не выбрали алгоритм, CURE , кажется, хорошая ставка.Выбор алгоритма может повлиять на выбор структуры данных, но это маловероятно.

Вы обнаружите, что алгоритм в любом случае определяет теоретические пределы «стоимости».Например, вы прочтете, что для CURE вы ограничены временем выполнения O (n2 log n) и использованием памяти O (n).

Надеюсь, это поможет.Если вы можете предоставить более подробную информацию, мы могли бы помочь в дальнейшем!

N.

Answer 3

Есть ли у вас алгоритм на данный момент? А что ты имеешь в виду под дорогим? Память или время дорого? Если память дорогая: в c # мало что можно сделать. Но вы можете рассмотреть выполнение расчета внутри базы данных с использованием временных объектов. Если время дорого: Вы можете использовать параллелизм для объединения столбцов и строк.

Но помимо этого я думаю, что простой массив double[,] является самым быстрым и экономящим память способом, который вы можете получить в c #, потому что доступ к значениям массива является операцией o (1), а массивы имеют наименьший объем памяти и издержки на управление (по сравнению со списками и словарями).

Answer 4

Спасибо за ответы.

В данный момент я использую это решение:

public class NodeMatrix
{

    public NodeMatrix Right { get; set;}
    public NodeMatrix Left { get; set; }
    public NodeMatrix Up { get; set; }
    public NodeMatrix Down { get; set; }
    public int I  { get; set; }
    public int J  { get; set; }
    public double Data { get; set; }

    public NodeMatrix(int I, int J, double Data)
    {
        this.I = I;
        this.J = J;
        this.Data = Data;
    }
}

List<NodeMatrix> list = new List<NodeMatrix>(10000);

Затем я строю соединения между узлами.После этого матрица готова.

Это будет использовать больше памяти, но операции, такие как добавление строк и столбцов, объединение строк и столбцов, я думаю, будут намного быстрее.

Answer 5

Хм, для меня это выглядит как простое двоичное дерево. Левый узел представляет следующее значение в строке, а правый узел представляет столбец.

Так что должно быть легко перебирать строки и столбцы и объединять их.

Answer 6

В этом коде я использую два вспомогательных списка 1D для вычисления индекса в большой массив, содержащий данные.Удаление строк / столбцов действительно дешево, так как мне нужно только удалить этот индекс из списков помощников.Но, конечно, память в большом массиве остается, т. Е. В зависимости от вашего использования у вас есть утечка памяти.

public class Matrix
{
    double[] data;
    List<int> cols;
    List<int> rows;

    private int GetIndex(int x,int y)
    {
        return rows[y]+cols[x];
    }

    public double this[int x,int y]
    {
        get{return data[GetIndex(x,y)];}
        set{data[GetIndex(x,y)]=value;} 
    }

    public void DeleteColumn(int x)
    {
        cols.RemoveAt(x);
    }

    public void DeleteRow(int y)
    {
        rows.RemoveAt(y);
    }

    public Matrix(int width,int height)
    {
        cols=new List<int>(Enumerable.Range(0,width));
        rows=new List<int>(Enumerable.Range(0,height).Select(i=>i*width));
        data=new double[width*height];
    }
}