Алгоритм определения, перекрываются ли ступенчатые массивы?

Question

В библиотеке, над которой я работаю, у нас есть наборы данных (которые могут быть подмножествами других наборов данных), которые распределены в памяти в трехмерных прямоугольных пошаговых массивах. То есть массив A может быть подписан как A(i,j,k), где каждый индекс находится в диапазоне от нуля до некоторой верхней границы, а расположение каждого элемента в памяти определяется как:

A(i,j,k) = A0 + i * A_stride_i + j * A_stride_j + k * A_stride_k

, где A0 - базовый указатель, а A_stride_i и др. - размерные шаги.

Теперь, поскольку эти наборы данных могут представлять собой подмножества других наборов данных, а не каждый, занимающий их собственный независимый блок памяти, выделенный malloc, вполне возможно, что они могут перекрываться (где перекрытие означает, что A(i,j,k) < B(m,n,p) не всегда является истинным или всегда ложно), и если они перекрываются, они могут чередоваться друг с другом или могут сталкиваться друг с другом (где столкновение означает, что A(i,j,k) == B(m,n,p) для некоторого секстета индексов).

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

Существует ли существующий алгоритм, позволяющий сделать это достаточно эффективным и простым способом?

Довольно легко проверить, перекрываются ли наборы данных или нет, поэтому ключевой вопрос: если два набора данных этой формы перекрываются, какой эффективный алгоритм позволяет определить, чередуются ли они или сталкиваются?

Пример: * ** 1022 тысячу двадцать одна * В качестве простого примера, предположим, что у нас есть области памяти от 0 до F (в шестнадцатеричном формате):

0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F

Я также рассмотрю здесь только 2D-массивы, для простоты. Предположим, у нас есть один с размером 2,3 (то есть 0 <= i < 2 и 0 <= j < 3), с stride_i = 1 и stride_j = 4, с базовым адресом 2. Это займет (с занятыми местоположениями, обозначенными их i , j пара):

0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
      *  *        *  *        *  *

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

0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
            o  o        o  o        o  o

В терминологии, которую я использовал при описании проблемы, эти массивы "перекрываются", но не сталкиваются.

Ограничения и предположения:

Мы можем предположить, что шаги являются положительными и, при желании, что они в порядке возрастания. Ни одна из вещей не является истинной в реальной библиотеке, но достаточно просто изменить определение массива, чтобы добраться до этой точки.

Можно предположить, что массивы не перемежаются самостоятельно. Это также не обеспечивается библиотекой, но будет патологическим случаем, о котором можно предупредить отдельно. То есть (при условии, что шаги идут в порядке возрастания, а i колеблется от нуля до max_i и т. Д.):

• stride_j >= max_i * stride_i
• stride_k >= max_j * stride_j

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

Нельзя предполагать, что два массива имеют одинаковые размеры или шаги.

Я не думаю, что стоит отслеживать вещи во время строительства - нет никакой информации, возникающей при строительстве, которая отсутствует при выполнении теста. Кроме того, «конструкция» может быть просто «учитывать подмножество этого большего массива с этим базовым указателем, этими шагами и этими размерами».

Худшие вероятные случаи

ответ svick напоминает мне, что я, вероятно, должен добавить кое-что о некоторых типичных «худших» случаях, которые я ожидаю увидеть. Одним из худших будет случай, когда у нас будет массив, представляющий очень большое количество комплексных значений, хранящихся в последовательных парах (real, imag), а затем у нас будет два подмассива, содержащих соответственно действительные и мнимые части - так, у вас есть несколько миллионов элементов в массиве, чередующихся между массивами. Поскольку это не маловероятный случай, он должен быть тестируемым с чем-то отличным от ужасной производительности.

Answer 1

Я думаю, что следующая программа на C # должна работать. Он использует метод ветвей и границ и работает для массивов любого числа измерений.

    using System;
    using System.Collections.Generic;

    namespace SO_strides
    {
        sealed class Dimension
        {
            public int Min { get; private set; }
            public int Max { get; private set; }
            public int Stride { get; private set; }

            private Dimension() { }

            public Dimension(int max, int stride)
            {
                Min = 0;
                Max = max;
                Stride = stride;
            }

            public Dimension[] Halve()
            {
                if (Max == Min)
                    throw new InvalidOperationException();

                int split = Min + (Max - Min) / 2;

                return new Dimension[]
                {
                    new Dimension { Min = Min, Max = split, Stride = Stride },
                    new Dimension { Min = split + 1, Max = Max, Stride = Stride }
                };
            }
        }

        sealed class ArrayPart
        {
            public int BaseAddr { get; private set; }
            public Dimension[] Dimensions { get; private set; }
            public int FirstNonconstantIndex { get; private set; }

            int? min;
            public int Min
            {
                get
                {
                    if (min == null)
                    {
                        int result = BaseAddr;
                        foreach (Dimension dimension in Dimensions)
                            result += dimension.Min * dimension.Stride;
                        min = result;
                    }
                    return min.Value;
                }
            }

            int? max;
            public int Max
            {
                get
                {
                    if (max == null)
                    {
                        int result = BaseAddr;
                        foreach (Dimension dimension in Dimensions)
                            result += dimension.Max * dimension.Stride;
                        max = result;
                    }
                    return max.Value;
                }
            }

            public int Size
            {
                get
                {
                    return Max - Min + 1;
                }
            }

            public ArrayPart(int baseAddr, Dimension[] dimensions)
                : this(baseAddr, dimensions, 0)
            {
                Array.Sort(dimensions, (d1, d2) => d2.Stride - d1.Stride);
            }

            private ArrayPart(int baseAddr, Dimension[] dimensions, int fni)
            {
                BaseAddr = baseAddr;
                Dimensions = dimensions;
                FirstNonconstantIndex = fni;
            }

            public bool CanHalve()
            {
                while (FirstNonconstantIndex < Dimensions.Length
                    && Dimensions[FirstNonconstantIndex].Min == Dimensions[FirstNonconstantIndex].Max)
                    FirstNonconstantIndex++;

                return FirstNonconstantIndex < Dimensions.Length;
            }

            public ArrayPart[] Halve()
            {
                Dimension[][] result = new Dimension[2][];

                Dimension[] halves = Dimensions[FirstNonconstantIndex].Halve();

                for (int i = 0; i < 2; i++)
                {
                    result[i] = (Dimension[])Dimensions.Clone();
                    result[i][FirstNonconstantIndex] = halves[i];
                }

                return new ArrayPart[]
                {
                    new ArrayPart(BaseAddr, result[0], FirstNonconstantIndex),
                    new ArrayPart(BaseAddr, result[1], FirstNonconstantIndex)
                };
            }
        }

        sealed class CandidateSet
        {
            public ArrayPart First { get; private set; }
            public ArrayPart Second { get; private set; }

            public CandidateSet(ArrayPart first, ArrayPart second)
            {
                First = first;
                Second = second;
            }

            public bool Empty
            {
                get
                {
                    return First.Min > Second.Max || Second.Min > First.Max;
                }
            }

            public CandidateSet[] Halve()
            {
                int firstSize = First.Size;
                int secondSize = Second.Size;

                CandidateSet[] result;

                if (firstSize > secondSize && First.CanHalve())
                {
                    ArrayPart[] halves = First.Halve();
                    result = new CandidateSet[]
                    {
                        new CandidateSet(halves[0], Second),
                        new CandidateSet(halves[1], Second)
                    };
                }
                else if (Second.CanHalve())
                {
                    ArrayPart[] halves = Second.Halve();
                    result = new CandidateSet[]
                    {
                        new CandidateSet(First, halves[0]),
                        new CandidateSet(First, halves[1])
                    };
                }
                else
                    throw new InvalidOperationException();

                return result;
            }

            public static bool HasSolution(ArrayPart first, ArrayPart second)
            {
                Stack<CandidateSet> stack = new Stack<CandidateSet>();
                stack.Push(new CandidateSet(first, second));

                bool found = false;

                while (!found && stack.Count > 0)
                {
                    CandidateSet candidate = stack.Pop();
                    if (candidate.First.Size == 1 && candidate.Second.Size == 1)
                        found = true;
                    else
                    {
                        foreach (CandidateSet half in candidate.Halve())
                            if (!half.Empty)
                                stack.Push(half);
                    }
                }

                return found;
            }
        }

        static class Program
        {
            static void Main()
            {
                Console.WriteLine(
                    CandidateSet.HasSolution(
                        new ArrayPart(2, new Dimension[] { new Dimension(1, 1), new Dimension(2, 4) }),
                        new ArrayPart(4, new Dimension[] { new Dimension(1, 1), new Dimension(2, 4) })
                        )
                    );
            }
        }
    }