java - teoria - La forma correcta de devolver el único elemento de un conjunto

teoria de conjuntos pdf

Question

Tengo el siguiente tipo de situación:

Set<Element> set = getSetFromSomewhere();
if (set.size() == 1) {
    // return the only element
} else {
    throw new Exception("Something is not right..");
}

Suponiendo que no puedo cambiar el tipo de getSetFromSomewhere() de getSetFromSomewhere() , ¿hay una forma mejor o más correcta de devolver el único elemento en el conjunto que

• Iterando sobre el conjunto y regresando de inmediato
• Crear una lista del conjunto y llamar a .get(0)

Answer 1

La mejor solución general (donde no se conoce la clase real establecida) es:

Element first = set.iterator().next();

Si se sabe que la clase establecida es un SortedSet (por ejemplo, un TreeSet o ConcurrentSkipListSet ), entonces una mejor solución es:

Element first = ((SortedSet) set).first();

En ambos casos, se lanzará una excepción si el conjunto está vacío; revisa los javadocs. La excepción se puede evitar utilizando Collection.isEmpty() .

La primera solución es O(1) en tiempo y espacio para un HashSet o LinkedHashSet , pero normalmente es peor para otros tipos de conjuntos.

El segundo es O(logN) a tiempo, y no usa espacio para TreeSet o ConcurrentSkipListSet .

El enfoque de crear una lista a partir de los contenidos establecidos y luego llamar a List.get(0) ofrece una solución deficiente ya que el primer paso es una operación O(N) , tanto en tiempo como en espacio.

No me di cuenta de que N es en realidad 1 . Pero aun así, crear un iterador es menos costoso que crear una lista temporal.

Answer 2

Podrías agarrar el iterador:

Element firstEl = set.iterator().next();

Answer 3

Puede usar un Iterator para obtener el único elemento y también para verificar que la colección solo contenga un elemento (evitando así la llamada al size() y la creación innecesaria de la lista):

Iterator<Element> iterator = set.iterator();

if (!iterator.hasNext()) {
    throw new RuntimeException("Collection is empty");
}

Element element = iterator.next();

if (iterator.hasNext()) {
    throw new RuntimeException("Collection contains more than one item");
}

return element;

Normalmente, debes resumir esto en su propio método:

public static <E> E getOnlyElement(Iterable<E> iterable) {
    Iterator<E> iterator = iterable.iterator();

    // The code I mentioned above...
}

Tenga en cuenta que esta implementación ya forma parte de las bibliotecas Guava de Google (que recomiendo encarecidamente, incluso si no la usa para este código en particular). Más específicamente, el método pertenece a la clase Iterables :

Element element = Iterables.getOnlyElement(set);

Si tiene curiosidad acerca de cómo se implementa, puede ver el código fuente de la clase Iterators (los métodos en Iterables menudo llaman a métodos en Iterators ):

  /**
   * Returns the single element contained in {@code iterator}.
   *
   * @throws NoSuchElementException if the iterator is empty
   * @throws IllegalArgumentException if the iterator contains multiple
   *     elements.  The state of the iterator is unspecified.
   */
  public static <T> T getOnlyElement(Iterator<T> iterator) {
    T first = iterator.next();
    if (!iterator.hasNext()) {
      return first;
    }

    StringBuilder sb = new StringBuilder();
    sb.append("expected one element but was: <" + first);
    for (int i = 0; i < 4 && iterator.hasNext(); i++) {
      sb.append(", " + iterator.next());
    }
    if (iterator.hasNext()) {
      sb.append(", ...");
    }
    sb.append(''>'');

    throw new IllegalArgumentException(sb.toString());
  }

Answer 4

if(set.size()==1){
   set.toArray(new Element[0])[0];
}