3
\$\begingroup\$

I have n Objects, Each Object has a Set of "nested" "Neighboring Objects". I need to check if there are duplicates between the "Neighboring Objects" Sets (there are no duplicates inside a single Set of "Neighboring Objects", but there might be between Sets).

At the end I need a new List of shared "Neighboring Objects"

In order to qualify, an Object must be present in every "Neighboring Set"

public List<Object> getOverlapingNeighbors(Object... d) {

    Objects.requireNonNull(d);

    List<Object> overlapingNeighbores = new ArrayList<Object>();

    Set<Object> neighbores = d[0].getNeighboringObjects(); // returns the "Neighboring Objects" Set

    for (Object candidate : neighbores) {

        boolean flag1 = true;

        for (int i = 1; i < d.length; i++) {

            boolean flag2 = false;

            for (Object other : d[i].getNeighboringObjects()) {
                if (candidate.equals(other)) {
                    flag2 = true;
                    break;
                }
            }

            if (!flag2) {
                flag1 = false;
                break;
            }

        }

        if (flag1) {
            overlapingNeighbores.add(candidate);
        }

    }

    return overlapingNeighbores;
} 

I don't feel comfortable with this approach...
I was hoping some one smarter has implemented a way of doing this better

\$\endgroup\$
  • \$\begingroup\$ The nearest neighbor part of the problem is a little weird, I'm not really sure what to make of it. Normally to intersect N sets, you start with the two smallest sets, since intersecting them will likely produce the smallest resulting set (and therefore it's faster). Then take the resulting small set and intersect again with the next smallest set. Etc. I've got a white paper somewhere on Google's search engine and this is basically how it winnows down search results. \$\endgroup\$ – markspace Nov 25 '17 at 23:05
  • \$\begingroup\$ May I ask what the use-case for this is? How are you using/applying this? In what context? \$\endgroup\$ – Simon Forsberg Nov 29 '17 at 8:31
  • 1
    \$\begingroup\$ @SimonForsberg Thees are Departments with employees, with a Set of "Neighboring Departments" from witch I can take replacement Employees if needed. I need to be aware of potential shared "Neighboring Departments" in order to find the best employee replacement solution. \$\endgroup\$ – Dima Nov 29 '17 at 14:54
2
\$\begingroup\$

First off, I'm assuming Object isn't java.lang.Object, but your own class. In that case you really should find a better name for it. Even if java.lang.Object didn't exist, "Object" is a terribly generic name giving absolutely no clue on what it represents.


The variable names flag1 and flag2 are beyond terrible, plus I believe you only need one boolean flag, if at all. Reading the algorithm gave me a headache, so I gave up after a while, so I can't say if it does what it should correctly.


Considering the method is working with sets it should return a Set and not a List.


Is the use of variable arguments really a valid usage pattern? That is usually only sensible if you call the method with separate arguments in code. This seems more like a situation where you have a Collection of objects to start with.


d is a bad variable name (again).


You should check if d actually contains at least one object (and return an empty list/set, if not), otherwise the user of the method will get an unhelpful IndexOutOfBoundsException.


In your method you only access the "neighboring objects" property of your Object and no other property. Instead of giving the method a list/array of your Objects, it would make sense to instead just give it a list/array of the sets of neighboring objects.


As @markspace says, the algorithm you are describing seems to simply be the intersection of all sets, which you can get using the method .retainAll() of Set.


Based on this the simplest attempt would be something like this (using Java 8 Streams):

// This first method is only needed if you really need the varargs:
public static Set<Object> getOverlapingNeighbors(Object... objects) {
   return getOverlapingNeighbors(Arrays.asList(d));
}

public static Set<Object> getOverlapingNeighbors(List<Object> objects) {
   return intersectionOf(objects.stream().map(Object::getNeighboringObjects).collect(Collectors.toList()));
}

// These are two generic methods that calculate the intersection of Sets of any (java.utils.)Objects. 
// It could/should be placed in a general utility class. 
public static <T> Set<T> intersectionOf(Collection<Set<T>> sets) {
    // It may be useful to first sort the list of sets by size, to optimize 
    // runtime. 
    // It is not the most optimal implementation, since it creates a new HashSet 
    // in each call of intersectionOf(Set<T> a, Set<T> b)
    return sets.stream().reduce((r, s) -> intersectionOf(r, s)).orElse(Collections.emptySet());
}


public static <T> Set<T> intersectionOf(Set<T> a, Set<T> b) {
    Set<T> newA = new HashSet<>(a);
    newA.retainAll(b);
    return newA;
}
\$\endgroup\$
1
\$\begingroup\$

Set.contains

            boolean flag2 = false;

            for (Object other : d[i].getNeighboringObjects()) {
                if (candidate.equals(other)) {
                    flag2 = true;
                    break;
                }
            }

            if (!flag2) {

You can replace this entire block with just

            if (!d[i].getNeighboringObjects().contains(candidate)) {

Sets will typically have a more efficient way of implementing contains than iteration. For example, a HashSet will use a hashing function. Or a TreeSet does a tree (binary) search.

Helper method

Beyond that, we can do better by adding a helper method. Consider

public List<Object> getOverlappingNeighbors(Object reference, Object... d) {
    List<Object> overlappingNeighbors = new ArrayList<>();

    for (Object candidate : reference.getNeighboringObjects()) {
        if (isInAll(candidate, d)) {
            overlappingNeighbors.add(candidate);
        }
    }

    return overlappingNeighbors;
}

public static boolean isInAll(Object candidate, Object... d) {
    for (Object o : d) {
        if (!o.getNeighboringObjects().contains(candidate)) {
            return false;
        }
    }

    return true;
}

Now we don't need flag variables. We get rid of one by using contains. We get rid of the other with the helper method. Now we just have two simple methods.

Using reference and candidate allows us to use the simpler form of the for loop. No manual maintenance of a loop index variable.

\$\endgroup\$
  • \$\begingroup\$ Indeed this is better, thank you. I already used the approach from my answer though. \$\endgroup\$ – Dima Dec 29 '17 at 11:31
0
\$\begingroup\$

After some pen and pencil scratches I came up with this approach:

public List<Object> getOverlapingNeighbors(Object... d) {

    Objects.requireNonNull(d);

    List<Object> overlapingNeighbores = new ArrayList<Object>();

    Map<Object, Integer> histogram = new HashMap<Object, Integer>();

    for (Object entry : d) {
        for (Object neighbor : entry.getNeighboringObjects()) {
            if (histogram.containsKey(neighbor)) {
                histogram.put(neighbor, histogram.get(neighbor) + 1);
            } else {
                histogram.put(neighbor, 1);
            }
        }
    }

    histogram.entrySet().forEach( e -> {
        if(e.getValue() == d.length) {
            overlapingNeighbores.add(e.getKey());
        }
    } );

    return overlapingNeighbores;
}  

I like it a lot better, but please feel free to advise on an even better one.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.