for each user we have 0 or N lists of cities, list contains unique values only.

what is the efficient way to check if user lists are identical (order doesn't matter, all values are case insensitive) ?

this is user model:

  @Getter
  @Setter
  @AllArgsConstructor
  @NoArgsConstructor
  @ToString
  static class User{

     private Map<Integer, List<String>> cities;

  }

this method should compare all user List:

  private static boolean isListsIdentical(User user) {
      user.getCities().values().forEach(cities -> {
         // if all list are identical return true
         });
      return false;
  }

here is the main method for test:

  public static void main(String[] args) {
     User user = new User();
     Map<Integer, List<String>> cities = new HashMap<>();
     cities.put(1, Arrays.asList("New York City", "London", "Paris", "Tokyo", "LA" ));
     cities.put(2, Arrays.asList("Beijing", "Hong Kong", "Chicago"));
     cities.put(3, Arrays.asList("New York City", "London", "Paris", "Tokyo", "LA" ));
     cities.put(4, null);
     user.setCities(cities); //user may have 0 or N lists

     System.out.println(isListsIdentical(user)); //should return false in this case

  }

CodePudding user response：

Map.values() returns a collection so you need to use an Iterator<List<String>> to loop over the lists. Since you want to see if the lists are all equal, you just need to compare the first to each of the rest. For two lists to be considered equal, equal values must occur in the same position and have the same size. Otherwise, use a Set (i.e Map<Integer, Set<String>>. First, test to ensure the lists are the same size, then check to see if the contents are the same and in the same order.

private static boolean isListsIdentical(User user) {
    Collection<List<String>> values = user.cities.values();
    if (values.size() == 0) {
        return true;
    }
    Iterator<List<String>> iter = values.iterator();
    List<String> baseList = iter.next();
    while (iter.hasNext()) {
        // return false on first mismatch.
        List<String> test = iter.next();
        if (test.size() != baseList.size() || !test.equals(baseList)) {
            return false;
        }
    }
    return true;
}

Updated due to change in requirements. Similar to the above answer but assumes a Map<Integer, Set<String>> is used.

    Collection<Set<String>> values = user.cities.values();
    if (values.size() == 0) {
        return true;
    }
    Iterator<Set<String>> iter = values.iterator();
    Set<String> baseList = iter.next();
    while (iter.hasNext()) {
        // return false on first mismatch.
        Set<String> test = iter.next();
        if (test.size() != baseList.size() || !test.equals(baseList)) {
            return false;
        }
    }
    return true;    
}

CodePudding user response：

How about this?

private static boolean isListsIdentical(User user) {
     final List<List<String>> nonNullCities = user.getCities()
             .values()
             .stream()
             .filter(Objects::nonNull)
             .collect(Collectors.toList());
     Set<Integer> set = new HashSet<>();
     set.add(nonNullCities.get(0).hashCode());
     for (int i = 1; i < nonNullCities.size(); i  ) {
         boolean isNewValue = set.add(nonNullCities.get(i).hashCode());
         if (isNewValue) {
             System.out.println("Non Identical values found");
             return false;
         }
     }
     return true;
  }
}

CodePudding user response：

Since the comments clarified that order inside the lists/collections does not matter, the easiest is probably to copy to a Set and simply check the sets for equality.

  private static boolean isListsIdentical(User user) {
      final Collection<List<String>> allCities = user.getCities().values();

      if (allCities.isEmpty()) return true;

      final Set<String> cities = nullOrSet(allCities.iterator().next());
      for (final List<String> cityList : allCities) {
        if (!Objects.equals(cities, nullOrSet(cityList))) {
          return false;
        }
      }
      return true;
  }

  private static <T> Set<T> nullOrSet(final Collection<T> collection) {
    return collection != null ? new HashSet<>(collection) : null;
  }

Because your map contained null values, the code has to become a bit more complicated. Avoid nulls if possible!

A simple optimization could be checking sizes before copying to sets (but probably not worth the effort for small collections).

NB. This will not work if one of the lists has a duplicated city entry, e.g. [[London, New York], [London, London, New York]] will still return true.

Regarding efficiency:

• Copying a list/collection to a set is O(n) (n being the size of the list
• Comparing a set with another set is O(m) (m being the size of the larger of the two sets)
• You have k lists in your map, giving you a total runtime complexity of approximately O(k*m), or naively O(n) (n here being the total number of cities). In other words: this scales linearly with your input size