.NET에 희소 행렬을 저장하는 가장 좋은 방법

StackOverflow https://stackoverflow.com/questions/756329

  •  09-09-2019
  •  | 
  •  

문제

희소 행렬을 저장하는 애플리케이션이 있습니다.이 행렬에는 행렬의 주대각선 주위에 대부분 존재하는 항목이 있습니다.이런 종류의 희소 행렬을 효율적으로 처리할 수 있는 효율적인 알고리즘(또는 기존 라이브러리)이 있는지 궁금합니다.바람직하게는 이는 각 행렬 항목이 사용자 정의 유형이 될 수 있는 일반적인 구현입니다.

질문/응답에 대한 응답으로 편집:

내가 주로 주대각선 주위에 있다고 말할 때, 나는 대부분의 행렬의 특징이 대부분의 항목이 주대각선에서 떨어져 클러스터되어 있지만 대각선에 가까운 곳에 0이 있을 수 있고 멀리 떨어진 곳에 0이 아닌 값이 있을 수 있다는 것을 의미합니다. 대각선.나는 여기서 '대부분'의 경우에 효율적인 것을 원합니다.

나는 이것을 무엇에 사용할 것인가?행의 모든 ​​값 또는 열의 모든 값에 효율적으로 액세스할 수 있어야 합니다.저장된 값은 부울 값입니다.예는 다음과 같습니다:

  1. 행의 모든 ​​true 값에 대해 각 열에 true가 나타나 열의 모든 항목을 다음과 같이 설정합니다.
  2. 행의 모든 ​​거짓 값에 대해 항목을 다음과 같이 설정하십시오.

이전에는 연결 목록을 사용하여 이 모든 작업을 수행했지만 구현하기가 매우 혼란스러웠습니다.나는 희소 행렬을 사용하여 알고리즘을 개선할 수 있기를 바랐지만 '올바른' 유형의 희소 행렬 알고리즘을 찾는 것이 어려웠습니다.

추신.지금까지 응답해 주셔서 감사합니다.

도움이 되었습니까?

해결책

셀의 [row,col]을 기반으로 인덱스를 사용할 수 있습니다.데이터가 대각선에 있으므로 행 인덱스 및 데이터와 연관된 열 인덱스를 저장하는 일반적인 접근 방식은 최적이 아닙니다.이를 수행하는 데 사용할 수 있는 몇 가지 코드는 다음과 같습니다.

    public class SparseMatrix<T>
    {
        public int Width { get; private set; }
        public int Height { get; private set; }
        public long Size { get; private set; }

        private Dictionary<long, T> _cells = new Dictionary<long, T>();

        public SparseMatrix(int w, int h)
        {
            this.Width = w;
            this.Height = h;
            this.Size = w * h;
        }

        public bool IsCellEmpty(int row, int col)
        {
            long index = row * Width + col;
            return _cells.ContainsKey(index);
        }

        public T this[int row, int col]
        {
            get
            {
                long index = row * Width + col;
                T result;
                _cells.TryGetValue(index, out result);
                return result;
            }
            set
            {
                long index = row * Width + col;
                _cells[index] = value;
            }
        }
    }

    static void Main()
    {
        var sm = new SparseMatrix<int>(512, 512);
        sm[42, 42] = 42;
        int val1 = sm[13, 13];
        int val2 = sm[42, 42];

        Console.WriteLine("VAL1 = " + val1); // prints out 0
        Console.WriteLine("VAL2 = " + val2); // prints out 42

        Console.ReadLine();
    }

T가 구조체인 경우 셀의 내용을 가져오는 것이 null이 아니고 해당 유형에 대한 기본값을 갖기 때문에 IsCellEmpty를 호출해야 할 수도 있습니다.또한 코드를 확장하여 다음을 기반으로 빠른 "SparseRatio"를 제공할 수도 있습니다. Size 재산과 _cells.Count.

편집하다:

음, 속도에 관심이 있다면 공간과 속도의 균형을 맞출 수 있습니다.사전을 하나만 갖는 대신 세 개를 만드세요!공간이 3배로 늘어나지만 원하는 방식으로 쉽게 열거할 수 있습니다.다음은 이를 보여주는 몇 가지 새로운 코드입니다.

    public class SparseMatrix<T>
    {
        public int Width { get; private set; }
        public int Height { get; private set; }
        public long MaxSize { get; private set; }
        public long Count { get { return _cells.Count; } }

        private Dictionary<long, T> _cells = new Dictionary<long, T>();

        private Dictionary<int, Dictionary<int, T>> _rows = 
            new Dictionary<int, Dictionary<int, T>>();

        private Dictionary<int, Dictionary<int, T>> _columns = 
            new Dictionary<int, Dictionary<int, T>>();

        public SparseMatrix(int w, int h)
        {
            this.Width = w;
            this.Height = h;
            this.MaxSize = w * h;
        }

        public bool IsCellEmpty(int row, int col)
        {
            long index = row * Width + col;
            return _cells.ContainsKey(index);
        }

        public T this[int row, int col]
        {
            get
            {
                long index = row * Width + col;
                T result;
                _cells.TryGetValue(index, out result);
                return result;
            }
            set
            {
                long index = row * Width + col;
                _cells[index] = value;

                UpdateValue(col, row, _columns, value);
                UpdateValue(row, col, _rows, value);
            }
        }

        private void UpdateValue(int index1, int index2, 
            Dictionary<int, Dictionary<int, T>> parent, T value)
        {
            Dictionary<int, T> dict;
            if (!parent.TryGetValue(index1, out dict))
            {
                parent[index2] = dict = new Dictionary<int, T>();
            }
            dict[index2] = value;
        }
    }

모든 항목을 반복하려면 다음을 사용하십시오. _cells.특정 열의 모든 행을 사용하려면 _columns.주어진 행의 모든 ​​열을 원하면 다음을 사용하십시오. _rows.

정렬된 순서로 반복하려면 LINQ를 혼합에 추가하거나 항목을 캡슐화하는 내부 클래스가 있는 정렬된 목록을 사용할 수 있습니다(행이나 열을 저장하고 구현해야 함). IComparable<T> 작업을 정렬하기 위해).

다른 팁

내 생각엔 Dictionary<int, Dictionary<int, object >> 충분할 것입니다.

여기에는 두 가지 질문이 있습니다.

  • "주로 주대각선 주위"는 너무 모호합니다.요소가 밴드에 있는 경우 주 대각선에서 오프셋된 벡터로서 밴드 자체의 밴드 저장을 사용합니다.요소가 주 대각선 근처에 무작위로 흩어져 있는 경우 밴드에 일부 0을 포함할 수 있는 줄무늬 형식을 사용하거나 배열의 요소와 해당 위치만 저장하는 순수 희소 형식을 사용합니다.

  • 매트릭스로 무엇을 할 것인가?목표가 단순히 효율적인 저장이라면 모든 요소에 빠르게 액세스할 수 있는 줄무늬 형식이 효율적입니다.행렬을 사용하여 선형 대수학을 수행하지만 행렬 이상은 수행하지 않는 경우벡터가 곱해지면 줄무늬 형태가 여전히 훌륭하게 작동합니다.매트릭스로 작업하는 경우채우기가 문제가 되는 행렬 곱셈 또는 행렬 인수분해의 경우 순수 희소 형식이 더 적합할 수 있습니다.예를 들어, 두 개의 줄무늬 행렬의 곱에는 추가 밴드가 있으므로 두 개의 삼중대각선 행렬의 곱은 오대각선이 됩니다.인수분해의 경우 채우기를 최소화하는 데 재정렬이 유용한 경우가 있습니다.(AMD는 대략적인 최소 학위 순열 중 하나이지만 다른 방식도 있습니다.)

저는 사용해보지 않았지만 Nmath 행렬 이를 처리합니다(무료는 아님).

또한, .NET용 극한 최적화 수치 라이브러리 (무료는 아닙니다).

다음은 무료입니다. Math.NET 프로젝트 (구체적으로 MathNet.Numerics.LinearAlgebra.Sparse 네임스페이스)

나는 이것이 일반 배열을 보유하는 클래스를 사용하고, 행렬 행 사이에 적용된 수평 오프셋을 저장하고 행의 스트라이프를 정의함으로써 수행될 수 있다고 생각합니다.유효한 항목의 수.따라서 대각선과 두 개의 인접 요소만 정의된 큰 행렬의 경우 3 * 행 수의 배열을 만들고 3을 스트라이프 너비로 저장합니다.오프셋은 행렬의 크기에 따라 달라집니다.

나는 이미 이 작업을 수행하는 무료 항목을 알지 못합니다.

일반 목록은 다음과 같습니다. 데이터 구조 스키마.각각은 장점과 단점이 있으며 희소 행렬이 발생하는 약간 다른 종류의 문제에 적합합니다.List<> 및 Dictionary<>와 같은 기존 데이터 구조 위에 이를 구현하고 싶을 수도 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top