Подтвердить что ты не робот

Самосогласованный массив глубины равен

Мне нужно выполнить структурное сравнение двух массивов 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 в этом случае не работает. Приведенный выше пример должен иметь значение true.

Есть ли алгоритм, который может достоверно рассчитать это?

Моя идея примерно такова:

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;
}
4b9b3361

ОТВЕТЫ

Ответ 1

Как я уже упоминал в своих комментариях выше, ваш код имеет некоторые ошибки компиляции, и вы оставили его много, что затрудняет 100-процентную уверенность в том, как именно он должен работать после завершения кода, Но после завершения кода, исправляя одну четкую опечатку (вы написали idx2 = xs.lastIndexOf(o2[i]), но я уверен, что вы имели в виду idx2 = ys.lastIndexOf(o2[i])), и одна вещь, о которой я думаю, является опечаткой (я не думаю, что вы имели в виду if (!equal(o1[i], o2[i], xs, ys)) для вставки внутри if (idx1 == idx2)), удаления некоторого кода no-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 будет чередоваться между b и b[0]. В каждом рекурсивном вызове xs.lastIndexOf(a) всегда будет наибольшим индексом xs, а ys.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 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), что означает, что общая глубина стека равна любое время. (Конечно, если количество массивов огромно, то вышеупомянутое может все еще переполнять стек, рекурсия ограничена, но максимальный размер стека. Я бы рекомендовал, чтобы for -loop был разделен в два for -loops, один за другим: в первый раз пропустите все элементы, которые являются массивами, а во второй раз пропустите все элементы, которые не являются. Это во многих случаях может избежать дорогостоящих сравнений.)

Также должно быть ясно, что указанное выше никогда не вернет false, когда оно должно вернуться true, так как оно возвращает только false, когда оно находит фактическую разницу.

Наконец, я думаю, должно быть ясно, что выше не вернется true, когда он должен вернуться false, так как для каждой пары объектов один полный цикл всегда выполняется по всем элементам. Эта часть сложнее доказать, но в сущности мы определили структурное равенство таким образом, чтобы два массива были только структурно неравными, если мы можем найти некоторую разницу между ними; и вышеприведенный код в конечном итоге исследует каждый элемент каждого массива, с которым он сталкивается, поэтому, если бы была найденная разница, он бы нашел его.

Примечания:

  • Я не беспокоился о массивах примитивов, int[] и double[] и так далее. Адам отвечает, что вы хотите, чтобы их сравнивали пополам; если это необходимо, оно легко добавляется (поскольку для него не требуется рекурсия: массивы примитивов не могут содержать массивы), но приведенный выше код просто использует для них 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(), чтобы заботиться о том, какой массив является.

Ответ 2

Вы можете добавить все посещенные объекты во временную структуру Map<Object, Object>, чтобы убедиться, что вы не посещаете/не проверяете их снова. Значение всегда представляет собой новый объект, который будет использоваться для замены уже посещенных экземпляров в ваших списках результатов.

Каждый раз, когда вы видите объект,

  • Проверьте, содержит ли карта экземпляр
  • если нет, поместите его на карту, значение карты - это новый объект
  • если да, используйте в своем списке значение карты (уникальный, новый объект) (xs или ys)

В вашем примере списки результатов должны выглядеть так (псевдоязык):

xs == {o1, "A", obj2}     // obj2 == map.get(o2);
ys == {o2, "A", obj1}     // obj1 == map.get(o1);

Это предотвратит бесконечные циклы.

Ответ 3

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

private List<Object> flatten(Object[] array, Map<Object, String> map, int level) {
    List<Object> list = new ArrayList<>();
    for (Object o : array) {
        if (o instanceof Object[]) {
            if (map.get(o) != null) {
                list.add(map.get(o));
            } else {
                map.put(array, "level"+level);
                List<Object> flattened = flatten((Object[]) o, map, level+1);
                for (Object obj : flattened)
                    list.add(obj);
            }
        } else {
            list.add(o);
        }
    }
    return list;
}

надеюсь, что это поможет.

Ответ 4

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

Не знаю, как обращаться с вложенными массивами других примитивов, таких как int [] и т.д. Я добавил случай для int [], но есть добавление float, double, byte, short, long, boolean.

public static boolean deepEquals(Object [] o1, Object [] o2) {
    return deepEquals(o1, o2, new IdentityHashMap<Object, Integer>());
}

public static boolean deepEquals(Object o1, Object o2, IdentityHashMap<Object, Integer> visited) {
    if (! visited.containsKey(o1)) {
        visited.put(o1, 0);
    } else {
        visited.put(o1, visited.get(o1) + 1);
    }
    if (! visited.containsKey(o2)) {
        visited.put(o2, 0);
    } else {
        visited.put(o2, visited.get(o2) + 1);
    }
    boolean ret = false;
    if (o1 == o2) {
        ret = true; 
    } else if (o1 instanceof Object[] && o2 instanceof Object[]){
        Object [] a1 = (Object[]) o1;
        Object [] a2 = (Object[]) o2;
        if (a1.length != a2.length ) {
            ret = false; // different length, can't be equal
        } else if (visited.get(o1) > 0 || visited.get(o2) > 0) {
            ret = true; // been here before, stop searching
        } else {
            ret = true;
            for (int i = 0; i < a1.length; i++) {
                if (! deepEquals(a1[i], a2[i], visited)) {
                    ret = false;
                    break;
                }
            }
        }
    } else if (o1 instanceof int[] && o2 instanceof int[]){
        ret = Arrays.equals((int[])o1, (int[])o2);
    } else if (o1 == null && o2 == null){
        ret = true; // null = null?
    } else {
        ret = o1.equals(o2); // just use equals
    }
    return ret;
}