在我正在使用的库中，我们有数据集（可能是其他数据集的子集），这些数据集以三维矩形跨步数组分布在内存中。也就是说，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_iet al是尺寸跨度。
现在，由于这些数据集可能是其他数据集的子集，而不是每个数据集都占用各自独立的malloc分配的内存块，因此它们完全有可能重叠（其中重叠意味着A(i,j,k) < B(m,n,p)既不总是true也不总是false），并且如果它们重叠，它们可能彼此交错，或者它们可能彼此碰撞（其中碰撞表示A(i,j,k) == B(m,n,p)某些六分之一索引）。
问题就在这里。对两个数据集（例如，副本）的某些操作仅在数组彼此不冲突时才有效，但在它们以交错非冲突方式重叠时才有效。我想为两个数据集添加一个函数，无论两个数据集是否冲突。
是否存在以合理有效且直接的方式执行此操作的算法？
检查数据集是否重叠是很容易的，所以关键问题是：给定这种形式的两个数据集重叠，有什么有效的算法来确定它们是交织还是冲突？
例：
举一个简单的例子，假设我们的存储位置是从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_istride_k >= max_j * stride_j当然，对于不需要这些假设的方法来说，要点很重要，因为将数组定义重新排列为规范的顺序是一件可以避免的工作。
不能假定两个数组的大小或步幅相等。
我认为在构建过程中跟踪事物没有任何价值-在构建过程中不会发生测试时不存在的信息。同样，“构造”可以简单地是“考虑具有此基本指针，这些步幅和这些大小的此更大数组的子集”。
最坏的情况
svick的答案提醒我，我可能应该添加一些我希望看到的典型“更差”案例。最糟糕的情况之一是，当我们有一个表示大量复数值的数组存储在连续的（实数，imag）对中，然后又有两个分别包含实数部分和虚数部分的子数组时，-您在数组中有几百万个元素，在数组之间交替。由于这种情况不太可能发生，因此应该可以用非凡的性能来测试。
我认为下面的 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) })
)
);
}
}
}