代码之家 › 专栏 › 技术社区 › Brooks Moses

确定跨步阵列是否重叠的算法?

algorithm arrays

Brooks Moses · 技术社区 · 14 年前

在我正在研究的库中,我们有数据集(可能是其他数据集的子集),这些数据集以三维矩形跨步数组的形式分布在内存中。也就是说,一个数组 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'ed内存块,所以它们完全有可能重叠(重叠意味着 A(i,j,k) < B(m,n,p) A(i,j,k) == B(m,n,p) 一些指数的六分之一)。

这就是问题所在。对两个数据集(例如,一个副本)的某些操作只有在数组彼此不冲突的情况下才有效,但如果它们以交错的非冲突方式重叠,则这些操作才有效。我想为两个数据集添加一个函数,不管两个数据集是否冲突。

有没有一个现有的算法来以一种合理有效和直接的方式来实现这一点?

检查数据集是否重叠相当容易,因此关键问题是:给定两个这种形式的数据集重叠,什么是确定它们是否交错或碰撞的有效算法?

例子:

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

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

当然,对于不需要这些假设的方法来说,将数组定义重新排列成规范顺序是一项理想情况下可以避免的工作。

不能假定这两个数组具有相同的大小或步长。

我不认为在构建过程中跟踪事物是有价值的——在构建过程中发生的任何信息在进行测试时都是不存在的。而且,“构造”可能只是“考虑这个较大数组的子集,这个基指针,这些步长,和这些大小。”

斯维克的回答提醒我,我可能应该补充一些关于一些典型的“更糟糕”的情况,我希望看到这一点。最糟糕的情况之一是,我们有一个数组,它代表了大量的复数,以连续的(实的,imag)对存储,然后我们有两个子数组,分别包含实的和虚的部分——所以,数组中有几百万个元素,在数组之间交替。由于这不是一个不太可能的情况,它应该是可以测试的东西以外的糟糕表现。

1 回复 | 直到 14 年前

svick bala 14 年前

我认为下面的C程序应该能起作用。它使用 branch and bound method

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