programacion - En Java(1.5 o posterior), ¿cuál es la mejor forma de obtener un elemento(cualquiera) de un conjunto?

manual de programacion android pdf

Question

En el siguiente código, necesitaba obtener un elemento, cualquier elemento, de toSearch. No pude encontrar un método útil en la definición de interfaz de conjunto para devolver solo un único miembro (aleatorio, pero no obligatorio) del conjunto. Entonces, utilicé la técnica toArray () [0] (presente en el código a continuación).

private Set<Coordinate> floodFill(Value value, Coordinate coordinateStart)
{
    Set<Coordinate> result = new LinkedHashSet<Coordinate>();

    Set<Coordinate> toSearch = new LinkedHashSet<Coordinate>();
    toSearch.add(coordinateStart);
    while (toSearch.size() > 0)
    {
        Coordinate coordinate = (Coordinate)toSearch.toArray()[0];
        result.add(coordinate);
        toSearch.remove(coordinate);
        for (Coordinate coordinateAdjacent: getAdjacentCoordinates(coordinate))
        {
            if (this.query.getCoordinateValue(coordinateAdjacent) == value)
            {
                if (!result.contains(coordinateAdjacent))
                {
                    toSearch.add(coordinateAdjacent);
                }
            }
        }
    }

    return result;
}

La otra técnica que he visto es la de reemplazar " (Coordinate) toSearch.toArray () [0] " con " toSearch.iterator (). Next () ". ¿Qué técnica, toArray () o iterator (), es la que tiene mayor probabilidad de ejecutarse más rápidamente con el menor impacto de GC (Garbage Collection)?

Mi intuición (después de componer esta pregunta) es que la segunda técnica que usa el iterador será más rápida en la ejecución y menor en el overhead para el GC. Dado que no sé la implementación del conjunto que se aprobó (suponiendo que HashSet o LinkedHashSet es más probable), ¿cuánto sobrecarga se incurre en cada uno de los métodos toArray () o iterator ()? Cualquier idea sobre esto sería muy apreciada.

Preguntas (repetidas desde arriba):

1. ¿Qué técnica, toArray () o iterator (), es la que tiene mayor probabilidad de ejecutarse más rápidamente con el menor impacto de GC (Garbage Collection)?
2. Dado que no sé la implementación del conjunto que se aprobó (suponiendo que HashSet o LinkedHashSet es más probable), ¿cuánto sobrecarga se incurre en cada uno de los métodos toArray () y el iterador ()?

Answer 1

toSearch.iterator().next() será más rápido y requerirá menos memoria porque no necesita copiar ningún dato, mientras que toArray asignará y copiará el contenido del conjunto en la matriz. Esto es independientemente de la implementación real: toArray siempre tendrá que copiar datos.

Answer 2

Así es como implementaría esto:

private Set<Coordinate> floodFill(Value value, Coordinate start) {
    Set<Coordinate> result = new LinkedHashSet<Coordinate>();
    LinkedList<Coordinate> toSearch = new LinkedList<Coordinate>();
    toSearch.add(start);
    do {
        Coordinate coordinate = toSearch.removeFirst();
        if (result.add(coordinate)) {
            for (Coordinate ajacent: getAdjacentCoordinates(coordinate)) {
                if (this.query.getCoordinateValue(adjacent) == value) {
                    toSearch.add(adjacent);
                }
            }
        }
    } while (!toSearch.isEmpty());
    return result;
}

Notas:

1. Si lo piensas, la estructura de datos de toSearch no necesita contener elementos únicos.
2. Usar LinkedList para toSearch significa que hay un método simple para obtener un elemento y eliminarlo de una vez.
3. Podemos usar el hecho de que Set.add(...) devuelve un boolean para tener el número de búsquedas en el conjunto de result ... en comparación con el uso de Set.contains() .
4. Sería mejor utilizar HashSet lugar de LinkedHashSet para los resultados ... a menos que necesite saber el orden en el que se agregaron las coordenadas por el relleno.
5. Usar == para comparar instancias de Value es potencialmente un poco dudoso.

Answer 3

Después de la respuesta de Petro, copié el método y lo volví a implementar de acuerdo con sus sugerencias. Se parece a esto:

private Set<Coordinate> floodFind2(Value value, Coordinate coordinateStart)
{
    Set<Coordinate> result = new LinkedHashSet<Coordinate>();

    Queue<Coordinate> toSearch = new LinkedList<Coordinate>();
    toSearch.add(coordinateStart);
    while (!toSearch.isEmpty())
    {
        Coordinate coordinate = toSearch.remove();
        result.add(coordinate);
        for (Coordinate coordinateAdjacent: getAdjacentCoordinates(coordinate))
        {
            if (getCoordinateValue(coordinateAdjacent).equals(value))
            {
                if (!result.contains(coordinateAdjacent))
                {
                    if (!toSearch.contains(coordinateAdjacent))
                    {
                        toSearch.add(coordinateAdjacent);
                    }
                }
            }
        }
    }

    return result;
}

Al pasar de Establecer a cola, mis preguntas de eficiencia cambiaron a la nueva comprobación condicional que tuve que agregar, " if (! ToSearch.contains (coordinateAdjacent)) ". Usando la interfaz Set, silenciosamente me impidió agregar duplicados. Usando la interfaz Queue, tengo que verificar para asegurarme de no agregar un duplicado.

Y ahora me preocupa que la implementación del método contains () en LinkedList pueda hacer un escaneo completo de los contenidos antes de devolver la respuesta. Entonces, comparando este método con el que originalmente publiqué, que probablemente sea más eficiente (¿antes de pasar una buena cantidad de tiempo haciendo las pruebas empíricas)?

Answer 4

Por lo que puedo ver, estás haciendo la primera búsqueda de ancho

A continuación se muestra el ejemplo de cómo podría implementarse sin utilizar toArray:

    private Set<Coordinate> floodFill(Value value, Coordinate coordinateStart) {
    final Set<Coordinate> visitedCoordinates = new LinkedHashSet<Coordinate>();
    final Deque<Coordinate> deque = new ArrayDeque<Coordinate>();

    deque.push(coordinateStart);

    while (!deque.isEmpty()) {
        final Coordinate currentVertex = deque.poll();
        visitedCoordinates.add(currentVertex);
        for (Coordinate coordinateAdjacent : getAdjacentCoordinates(currentVertex)) {
            if (this.query.getCoordinateValue(coordinateAdjacent) == value) {
                if (!visitedCoordinates.contains(coordinateAdjacent)) {
                    deque.add(coordinateAdjacent);
                }
            }
        }
    }

    return visitedCoordinates;
}

Notas de implementación:

Y ahora me preocupa que la implementación del método contains () en LinkedList pueda hacer un escaneo completo de los contenidos antes de devolver la respuesta.

Tiene razón acerca del escaneo completo (también conocido como búsqueda lineal). Sin embargo, en su caso, es posible tener un conjunto adicional para el seguimiento de vértices ya visitados (por cierto, ¡es su resultado!), Que resolvería el problema con el método contiene en O (1) tiempo.

Aclamaciones

Answer 5

De acuerdo, a continuación se muestra mi última implementación que incorpora retroalimentación (principalmente de Stephen, Cameron y Petro) que incluye eliminar por completo el conflicto toArray () [] - vs-interator (). Next (). Y he salpicado de comentarios para distinguir con más precisión qué está ocurriendo y por qué. Y para aclarar mejor por qué concretamente implementé el consejo original de Petro "use a tracking set" (secundado por Cameron). Y justo después del fragmento de código, lo contrastaré con las otras soluciones propuestas.

private Set<Coordinate> floodFind3(Coordinate coordinate)
{
    Set<Coordinate> area = new LinkedHashSet<Coordinate>(); //includes only area of value (which is the same as at coordinate)

    area.add(coordinate);
    Value value = getCoordinateValue(coordinate); //value upon which to expand area
    Set<Coordinate> checked = new LinkedHashSet<Coordinate>(); //every coordinate evaluated regardless of value
    checked.add(coordinate);
    Queue<Coordinate> candidates = new LinkedList<Coordinate>(); //coordinates evaluated, were of value, and are queued to iterate through their adjacents
    candidates.add(nordinate);
    while (!candidates.isEmpty())
    {
        for (Nordinate coordinateAdjacent: this.query.getNordinates().getAdjacent(candidates.remove()).getOrthogonal())
        {
            if (checked.add(coordinateAdjacent)) //only expands containing value and !value
            {
                if (getCoordinateValue(coordinateAdjacent) == value)
                {
                    area.add(coordinateAdjacent); //only expands containing value
                    candidates.add(coordinateAdjacent); //expands and contracts containing value
                }
            }
        }
    }

    return area;
}

He actualizado el método de varias maneras significativas:

1. Un parámetro de método menos: eliminé un parámetro porque era derivable de la búsqueda y eliminé un posible problema lógico en el que la coordenada de inicio apunta a una ubicación que contiene el valor!
2. Tres colecciones rastrean la búsqueda; área (conjunto), marcada (conjunto) y candidatos (cola). Los comentarios del código aclaran el uso específico de cada uno. Se utiliza LinkedHashSet para una reproducibilidad confiable mientras se persiguen errores y problemas de rendimiento (http://.com/questions/2704597/iteration-order-of-hashset). Una vez estable, probablemente regrese a una implementación más rápida de HashSet.
3. Reordenó la prueba "verificar si ya se evaluó" ​​antes de la prueba "es valor" para visitar solo cada coordenada exactamente una vez. Esto evita volver a visitar! Valor las coordenadas adyacentes más de una vez. También se incorporó el inteligente uso doble de Stephen del método Set add (). Esto se vuelve muy importante ya que el área a inundar se vuelve más laberíntica (snakely / spidery).
4. Mantuvo "==" para verificar el valor forzando una comparación de referencia. El valor se define como Java 1.5 Enum y no deseaba depender de HotSpot para alinear la llamada al método .equals () y reducirla a una comparación de referencia. Si Value alguna vez cambiara de ser un Enum, esta elección podría volver a afectarme. Tyvm a Stephen por señalar esto.

Las soluciones de Petro y Stephan visitan las coordenadas que contienen el valor solo una vez, pero requieren revisar las coordenadas que contienen! Valor más de una vez, lo que puede dar lugar a bastantes chequeos duplicados de valores recuperados para áreas que consisten en túneles largos como laberintos. Si bien los "túneles largos tipo laberinto" pueden considerarse un caso patológico, es más típico del dominio particular para el que necesito este método. Y mi "segunda" solución intentada (que tuvo el mal rendimiento LinkedList contiene () llamada) fue cuestionable como una respuesta real ({asentimiento} a Stephen en ese caso).

Gracias por todos tus comentarios.

A continuación, una gran cantidad de pruebas empíricas con variaciones individuales / cambios en cientos de millones de invocaciones. Actualizaré esta respuesta con detalles en algún momento de este fin de semana.