Сравнение итераций для того же контента, но не относительно порядка - PullRequest
Новая
       12

Сравнение итераций для того же контента, но не относительно порядка

2 голосов
/ 12 июня 2019

Я пытаюсь сравнить два Iterables в Java одинакового размера.Мне нужно только знать, что содержимое одинаково.Однако что-то вроде [1, 2] и [1, 2, 2] не должно быть равным, а [1, 2, 2, 4] должно равняться [1, 2, 4, 2]. 

boolean functionName() {
    boolean pvk;
    ... setup ...
    for(Edge e : pMST.edges()) {
      pvk = false;
      for(Edge f : kMST.edges()) {
        if(e == f) {
          pvk = true;
          System.out.println("True.");
        }
      }
      if(!pvk) return false;
    }
return true;
}

Это моя первоначальная паршивая попытка, но она не только всегда возвращает false, она не учитывает дубликаты должным образом.

Ответы [ 3 ]

2 голосов
/ 12 июня 2019

Вы могли бы сортировать элементы и сравнивать результирующие списки, но это потенциально медленный O (n lg n), и он полагается на то, что элементы либо сопоставимы, либо имеют общий порядок, наложенный на нихКомпаратор.Это может быть неосуществимо.

Этот другой ответ предлагает использовать мультисеть Guava.Это имеет смысл, так как отслеживает элементы и количество вхождений, что важно для вашего вопроса.Это должно быть O (n) для разумных реализаций, таких как HashMultiset .Другие библиотеки, такие как Apache Commons ( MultiSet ) и Eclipse Collections ( Bag ), имеют реализации коллекций, которые функционально эквивалентны мультисети Guava.

Если вы не хотитечтобы включить зависимость от любой из этих библиотек, вы можете сделать это в JDK самостоятельно.К сожалению, в Java нет реализации Bag , но для этой цели ее легко эмулировать, используя карту из типа вашего элемента в число, целое или длинное.

Если у вас естьСписки, вы можете сделать это: 

boolean unorderedEquals(List<Item> list1, List<Item> list2) {
    Map<Item, Long> freq1 = list1.stream().collect(groupingBy(i -> i, counting()));
    Map<Item, Long> freq2 = list2.stream().collect(groupingBy(i -> i, counting()));
    return freq1.equals(freq2);
}

Если у вас есть Iterables, вам нужно построить карты, используя forEach вместо: 

boolean unorderedEquals(Iterable<Item> iter1, Iterable<Item> iter2) {
    Map<Item, Integer> freq1 = new HashMap<>();
    iter1.forEach(it -> freq1.merge(it, 1, (a, b) -> a + b));
    Map<Item, Integer> freq2 = new HashMap<>();
    iter2.forEach(it -> freq2.merge(it, 1, (a, b) -> a + b));
    return freq1.equals(freq2);
}
2 голосов
/ 12 июня 2019

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

static boolean unorderedEquals(Collection<?> coll1, Collection<?> coll2) {
    if(coll1.size() != coll2.size()) return false;
    Map<Object, Integer> freq = new HashMap<>();
    for(Object o: coll1) freq.merge(o, 1, Integer::sum);
    for(Object o: coll2)
        if(freq.merge(o, -1, Integer::sum) < 0) return false;
    return true;
}

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

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

Поддержка произвольных Iterable с, которые отличаются от Collection необязательным использованием метода size(), немного сложнее, так кактогда мы не можем выполнить предварительную проверку и, следовательно, должны поддерживать счет: 

static boolean unorderedEquals(Iterable<?> iter1, Iterable<?> iter2) {
    Map<Object, Integer> freq = new HashMap<>();
    int size = 0;
    for(Object o: iter1) {
        freq.merge(o, 1, Integer::sum);
        size++;
    }
    for(Object o: iter2)
        if(--size < 0 || freq.merge(o, -1, Integer::sum) < 0) return false;
    return size == 0;
}

Если мы хотим избежать накладных расходов на бокс, мы должны прибегнуть к изменчивому значению для карты, например 

static boolean unorderedEquals(Collection<?> coll1, Collection<?> coll2) {
    if(coll1.size() != coll2.size()) return false;
    Map<Object, int[]> freq = new HashMap<>();
    for(Object o: coll1) freq.computeIfAbsent(o, x -> new int[1])[0]++;
    int[] absent = { 0 };
    for(Object o: coll2) if(freq.getOrDefault(o, absent)[0]-- == 0) return false;
    return true;
}

Но я не думаю, что он окупится.Для небольшого числа вхождений бокс будет повторно использовать экземпляры Integer, тогда как нам нужен отдельный объект int[] для каждого отдельного элемента при использовании изменяемых значений.

Но использование compute может быть интересно для Iterable решение, при использовании его как 

static boolean unorderedEquals(Iterable<?> coll1, Iterable<?> coll2) {
    Map<Object, int[]> freq = new HashMap<>();
    for(Object o: coll1) freq.computeIfAbsent(o, x -> new int[1])[0]++;
    int[] absent = {};
    for(Object o: coll2)
        if(freq.compute(o, (key,c) -> c == null || c[0] == 0? absent:
                                      --c[0] == 0? null: c) == absent) return false;
    return freq.isEmpty();
}

, которое удаляет записи с карты, когда их количество достигает нуля, поэтому нам нужно только проверить карту на пустоту в конце.

1 голос
/ 12 июня 2019

Я бы их отсортировал. Но сначала я бы сравнил размеры, прежде чем делать сортировку. Вам нужно будет предоставить Comparator<T> для использования методом сортировки. Если вы сортируете целые числа, вы можете использовать: 

      List<Integer> a = new ArrayList<>(List.of(1, 2, 3, 3, 3, 3, 4, 5, 6));
      List<Integer> b = new ArrayList<>(List.of(2, 3, 1, 3, 4, 5, 6, 3, 3));
      System.out.println(compareLists(a, b, Comparator.naturalOrder()));

   public static <T> boolean compareList(List<T> list1, List<T> list2,
         Comparator<T> comp) {

      if (list1 == list2) {
          return true;
      }
      if (list1.size() != list2.size()) {
         return false;
      }
      Collections.sort(list1, comp);
      Collections.sort(list2, comp);

      return list1.equals(list2);
   }
...