es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Obteniendo un elemento aleatorio de una Colección

26 Jul, 2023 Programación

En java me gustaría poder mantener mi colección de peces ordenados por especie en todo momento (por eso el uso de un HashMap) al mismo tiempo que puedo seleccionar un elemento aleatorio de todas las especies excepto una, con una complejidad de tiempo constante. Por ejemplo, el siguiente código hace el trabajo pero con una complejidad de O(número de elementos):

import java.util.*;

HashMap<string,></string,><fish>> pecesPorEspecie = new HashMap<>();

// Insertar algunos peces...
// Fish tiene un atributo de tipo String que describe su especie
// Ahora queremos seleccionar un pez aleatorio que no sea de la especie no deseada

String noDeseada = "especie no deseada";
ArrayList<fish> especiesDeseadas = new ArrayList<>();
for (String especie : pecesPorEspecie.keySet()) {
    if (!Objects.equals(especie, noDeseada)) {
        especiesDeseadas.addAll(pecesPorEspecie.get(especie));
    }
}

// ¡Finalmente!
int indiceAleatorio = new Random().nextInt(especiesDeseadas.size());
Fish elementoAleatorio = especiesDeseadas.get(indiceAleatorio);

¿Alguna idea de cómo hacer esto con complejidad de tiempo constante, si es posible? ¡Gracias!

Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Sí, una forma de lograr esto con una complejidad temporal constante sería mantener dos estructuras de datos:
    1. Un HashMap que mapea cada especie a su correspondiente ArrayList de objetos Fish (similar a la implementación actual).
    2. Un ArrayList que contiene todos los objetos Fish excepto los de la especie no deseada.

    Cada vez que se agrega un nuevo pez, debe agregarse a ambas estructuras de datos. Cada vez que se elimina un pez, debe eliminarse de ambas estructuras de datos.

    Para seleccionar un pez aleatorio de todas las especies excepto la especie no deseada, simplemente puedes generar un índice aleatorio de 0 al tamaño de la segunda estructura de datos y obtener el objeto fish correspondiente a ese índice. Dado que la segunda estructura de datos contiene todos los objetos fish excepto los de la especie no deseada, esta operación siempre tendrá una complejidad temporal constante.

    Aquí tienes un código que demuestra este enfoque:

    import java.util.*;

public class FishTank {
    private HashMap<string,></string,><fish>> fishesBySpecies = new HashMap<>();
    private ArrayList<fish> allFishesExceptUnwanted = new ArrayList<>();

    public void addFish(Fish fish) {
        String species = fish.getSpecies();

        // Actualizar fishesBySpecies
        if (!fishesBySpecies.containsKey(species)) {
            fishesBySpecies.put(species, new ArrayList<>());
        }
        ArrayList<fish> fishes = fishesBySpecies.get(species);
        fishes.add(fish);

        // Actualizar allFishesExceptUnwanted
        if (!species.equals(unwantedSpecies)) {
            allFishesExceptUnwanted.add(fish);
        }
    }

    public void removeFish(Fish fish) {
        String species = fish.getSpecies();

        // Actualizar fishesBySpecies
        ArrayList<fish> fishes = fishesBySpecies.get(species);
        fishes.remove(fish);
        if (fishes.isEmpty()) {
            fishesBySpecies.remove(species);
        }

        // Actualizar allFishesExceptUnwanted
        if (!species.equals(unwantedSpecies)) {
            allFishesExceptUnwanted.remove(fish);
        }
    }

    public Fish getRandomFishExceptUnwanted() {
        int randomIndex = new Random().nextInt(allFishesExceptUnwanted.size());
        return allFishesExceptUnwanted.get(randomIndex);
    }
}

    Ten en cuenta que hay algunas suposiciones realizadas en esta implementación, como el hecho de que cada pez tiene un método getSpecies() que devuelve una cadena que representa su especie. Es posible que debas modificar el código para adaptarlo a tus necesidades específicas.

Comments are closed.