aka*_*okd 12 java arrays algorithm
我需要对两个可能包含它们的Object []数组进行结构比较:
Object[] o1 = new Object[] { "A", null };
o1[1] = o1;
Object[] o2 = new Object[] { "A", null };
o2[1] = o2;
Arrays.deepEquals(o1, o2); // undefined behavior
不幸的是,deepEquals在这种情况下不起作用.上面的例子应该是真的.
有算法可以可靠地计算出来吗？
我的想法大致如下:
List<Object> xs = new ArrayList<>();
List<Object> ys = new ArrayList<>();
boolean equal(Object[] o1, Object[] o2, List<Object> xs, List<Object> ys) {
xs.add(o1);
ys.add(o2);
boolean result = true;
for (int i = 0; i < o1.length; i++) {
if (o1[i] instanceof Object[]) {
int idx1 = xs.lastIndexOf(o1[i]);
if (idx1 >= 0) { idx1 = xs.size() - idx1 - 1; }
if (o2[i] instanceof Object[]) {
int idx2 = xs.lastIndexOf(o2[i]);
if (idx2 >= 0) { idx2 = ys.size() - idx2 - 1; }
if (idx1 == idx2) {
if (idx1 >= 0) {
continue;
}
if (!equal(o1[i], o2[i], xs, ys)) {
result = false;
break;
}
}
}
}
}
xs.removeLast();
ys.removeLast();
return result;
}
正如我在上面的评论中提到的，您的代码有一些编译错误，并且您遗漏了很多错误，这使得很难 100% 确定代码完成后它应该如何工作。但是在完成代码之后，修复了一个明显的拼写错误（您写了idx2 = xs.lastIndexOf(o2[i])，但我确定您的意思是idx2 = ys.lastIndexOf(o2[i])）和一件事我认为是一个拼写错误（我不认为您打算if (!equal(o1[i], o2[i], xs, ys))嵌套在其中if (idx1 == idx2)），删除一些不-op 代码，并进行了一些重组（到我认为更清晰的风格；YMMV），我得到了这个：
boolean equal(final Object[] o1, final Object[] o2)
{
return _equal(o1, o2, new ArrayList<Object>(), new ArrayList<Object>());
}
private static boolean _equal(final Object[] o1, final Object[] o2,
final List<Object> xs, final List<Object> ys)
{
if(o1.length != o2.length)
return false;
xs.add(o1);
ys.add(o2);
try
{
for(int i = 0; i < o1.length; i++)
{
if(o1[i] == null && o2[i] == null)
continue;
if(o1[i] == null || o2[i] == null)
return false;
if(o1[i].equals(o2[i]))
continue;
if(! (o1[i] instanceof Object[]) || ! (o2[i] instanceof Object[]))
return false;
final int idx1 = xs.lastIndexOf(o1[i]);
if(idx1 >= 0 && idx1 == ys.lastIndexOf(o2[i]))
continue;
if(! _equal((Object[])o1[i], (Object[])o2[i], xs, ys))
return false;
}
return true;
}
finally
{
xs.remove(xs.size() - 1);
ys.remove(ys.size() - 1);
}
}
这大部分有效。逻辑是，每当它获得两个Object[]s 时，它都会检查当前是否正在比较堆栈中较高位置的每一个，如果是，它会检查正在比较其中一个的最顶层堆栈帧是否也是正在比较另一个的最顶层堆栈框架。（这就是你想要的逻辑，对吗？）
我能看到的唯一严重的错误是在这种情况下：
// a one-element array that directly contains itself:
final Object[] a = { null }; a[0] = a;
// a one-element array that contains itself via another one-element array:
final Object[][] b = { { null } }; b[0][0] = b;
// should return true (right?); instead, overflows the stack:
equal(a, b, new ArrayList<Object>(), new ArrayList<Object>());
您会看到，在上面， 的最后一个元素xs将始终是a，但 的最后一个元素将在和 之间ys交替。在每次递归调用中，始终是 的最大索引，而or （无论需要哪个）始终比的最大索引小一。bb[0]xs.lastIndexOf(a)xsys.lastIndexOf(b)ys.lastIndexOf(b[0])ys
问题是，逻辑不应该是“最顶层的比较o1[i]与最顶层的比较位于同一堆栈帧中o2[i]”；相反，它应该是，“存在一些堆栈框架 - 任何堆栈框架 - 与o1[i]”进行比较o2[i]。但为了效率，我们实际上可以使用逻辑“存在或曾经存在一个正在/正在比较的堆栈帧o1[i]” o2[i]；我们可以使用一Set对数组而不是两个List数组。为此，我写了这样的内容：
private static boolean equal(final Object[] a1, final Object[] a2)
{
return _equal(a1, a2, new HashSet<ArrayPair>());
}
private static boolean _equal
(final Object[] a1, final Object[] a2, final Set<ArrayPair> pairs)
{
if(a1 == a2)
return true;
if(a1.length != a2.length)
return false;
if(! pairs.add(new ArrayPair(a1, a2)))
{
// If we're here, then pairs already contained {a1,a2}. This means
// either that we've previously compared a1 and a2 and found them to
// be equal (in which case we obviously want to return true), or
// that we're currently comparing them somewhere higher in the
// stack and haven't *yet* found them to be unequal (in which case
// we still want to return true: if it turns out that they're
// unequal because of some later difference we haven't reached yet,
// that's fine, because the comparison higher in the stack will
// still find that).
return true;
}
for(int i = 0; i < a1.length; ++i)
{
if(a1[i] == a2[i])
continue;
if(a1[i] == null || a2[i] == null)
return false;
if(a1[i].equals(a2[i]))
continue;
if(! (a1[i] instanceof Object[]) || ! (a2[i] instanceof Object[]))
return false;
if(! _equal((Object[]) a1[i], (Object[]) a2[i], pairs))
return false;
}
return true;
}
private static final class ArrayPair
{
private final Object[] a1;
private final Object[] a2;
public ArrayPair(final Object[] a1, final Object[] a2)
{
if(a1 == null || a2 == null)
throw new NullPointerException();
this.a1 = a1;
this.a2 = a2;
}
@Override
public boolean equals(final Object that)
{
if(that instanceof ArrayPair)
if(a1 == ((ArrayPair)that).a1)
return a2 == ((ArrayPair)that).a2;
else
if(a1 == ((ArrayPair)that).a2)
return a2 == ((ArrayPair)that).a1;
else
return false;
else
return false;
}
@Override
public int hashCode()
{ return a1.hashCode() + a2.hashCode(); }
}
应该清楚的是，上述不会导致无限递归，因为如果程序有有限数量的数组，那么它有有限数量的数组对，并且一次只能有一个堆栈帧可以比较给定的一对数组（因为，一旦开始比较一对数组，它就会被添加到pairs，并且以后任何比较该对的尝试都将立即返回true），这意味着总堆栈深度在任何给定时间都是有限的。（当然，如果数组的数量很大，那么上面的代码仍然会溢出堆栈；递归是有限的，但最大堆栈大小也是有限的。实际上，我建议将 -loop 分成for两个for-循环，一个接一个：第一次，跳过所有属于数组的元素，第二次，跳过所有不是数组的元素。这在许多情况下可以避免昂贵的比较。）
false还应该清楚的是，上面的内容在应该返回时永远不会返回true，因为它仅false在发现实际差异时才返回。
最后，我认为应该清楚的是，上面的内容true在应该返回时永远不会返回false，因为对于每一对对象，总是对所有元素进行一个完整的循环。这部分的证明比较棘手，但本质上，我们定义结构相等的方式是，如果我们能找到两个数组之间的差异，那么它们在结构上只是不相等；上面的代码最终会检查它遇到的每个数组的每个元素，因此如果存在可发现的差异，它就会找到它。
笔记：
int[]等等double[]。Adam 的回答提出了您也希望对它们进行元素比较的可能性；如果需要的话，很容易添加（因为它不需要递归：基元数组不能包含数组），但上面的代码仅用于Object.equals(Object)它们，这意味着引用相等。Object.equals(Object)实现了对称关系，正如其合同所指定的那样。然而，实际上，该合同并不总是得到履行。例如，new java.util.Date(0L).equals(new java.sql.Timestamp(0L))是true，而new java.sql.Timestamp(0L).equals(new java.util.Date(0L))是false。如果顺序对您的目的很重要（如果您想要equal(new Object[]{java.util.Date(0L)}, new Object[]{java.sql.Timestamp(0L)})成为true并且equal(new Object[]{java.sql.Timestamp(0L)}, new Object[]{java.util.Date(0L)})想要成为false），那么您将需要更改ArrayPair.equals(Object)，并且可能ArrayPair.hashCode()还需要关心哪个数组是哪个数组。