Como aperfeiçoar um código de busca de elemento dentro de um ArrayList

Programação Java
#1

Estou buscando um objeto dentro de um ArrayList. Pensei em fazer um FOR padrão para correr os elementos da lista e encontrar o objeto.

List<ObjetoX> listaDeObjetos = new ArrayList<>();
for (ObjetoX objeto : listaDeObjetos) {
    if (objeto.propriedadeY.equals("teste")) {
        System.out.println(objeto.toString);
    }
}

Sei que o método acima não é o mais rápido, e quando a lista começa a ter muitos elementos, a busca fica realmente lenta.

Na realidade aqui chegou a estourar a memória disponível.

A minha dúvida é: vocês recomendariam algum método mais eficaz para encontrar objetos dentro de uma lista? (Ou talvez recomendariam empregar outro tipo de lista)

Obrigado.

#2

Se estiver com Java >= 1.8 tenta utilizar um stream e aplica um filter, dependendo do cenário tu pode até testar um parallel stream.

1 curtida
#3

Vc poderia usar uma Busca Binária.

A classe Collections tem o método binarySearch para te ajudar nisso, vc só precisa fazer o ObjetoX implementar a interface Comparable.

Vc só precisa assegurar que a lista esteja organizada antes de invocar o método binarySearch.

Olha como ficaria:

import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class ObjetoX implements Comparable<ObjetoX> {
  String propriedadeY;

  ObjetoX(int propriedadeY) {
    this.propriedadeY = "Objeto " + propriedadeY;
  }

  @Override
  public String toString() {
    return propriedadeY;
  }

  @Override
  public int compareTo(ObjetoX o) {
    return this.propriedadeY.compareTo(o.propriedadeY);
  }
}

public class App {
  public static void main(String... args) {
    int max = 10_000_000;

    List<ObjetoX> list = IntStream.range(0, max).mapToObj(ObjetoX::new).collect(Collectors.toList());

    int index = Collections.binarySearch(list, new ObjetoX(max / 2));

    System.out.println(list.get(index));
  }
}

Para vc ter uma ideia do poder deste algoritmo, para encontrar o ObjetoX 500000 ele leva apenas coisa de 23 passos!

Um ponto que pode ser inconveniente pra vc é que tem que criar um objeto que vai representar o valor que vc está procurando, por isso eu criei aquele new ObjetoX(max / 2).

Se preferir implementar o algoritmo “na mão”, seria algo assim:

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class ObjetoX {
  String propriedadeY;

  ObjetoX(int propriedadeY) {
    this.propriedadeY = "Objeto " + propriedadeY;
  }

  @Override
  public String toString() {
    return propriedadeY;
  }
}

public class Main {
  public static void main(String... args) {
    int max = 10_000_000;

    List<ObjetoX> list = IntStream.range(0, max).mapToObj(ObjetoX::new).collect(Collectors.toList());

    String goal = "Objeto " + max / 2;

    ObjetoX result = binarySearch(list, goal);

    System.out.println(result);
  }

  protected static ObjetoX binarySearch(List<ObjetoX> list, String goal) {
    ObjetoX[] array = list.toArray(new ObjetoX[0]);

    Arrays.sort(array, (a, b) -> a.propriedadeY.compareTo(b.propriedadeY));

    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
      int mid = (low + high) / 2;
      String propriedadeY = array[mid].propriedadeY;

      if (propriedadeY.equals(goal))
        return array[mid];
      else if (propriedadeY.compareTo(goal) > 0)
        high = mid - 1;
      else
        low = mid + 1;
    }

    return null;
  }
}

Eu não sei se há uma opção melhor, mas vale a pena considerar a sugestão.

1 curtida
#4

Obrigado pelas orientações. Estou tentando simplificar os laços que estou usando no código, e depois vou testar essa ideia.

2 curtidas
#5

Só para dar um feedback…

Eu estava usando o sistema de busca para identificar objetos repetidos, porque meu código é para análise de logs e ele precisa tratar mais de mil linhas por arquivo. O que for repetido, ele só atualiza o horário da ocorrência, e o que for novo ele cria um objeto novo. Esses objetos depois são descarregados num relatório específico.

Bem… às vezes voltar ao básico sempre joga uma nova luz sobre o problema. Fui rever as apostilas de collections, e vi que LinkedList não aceita objetos repetidos, então ao invés de correr toda a lista testando (com um algoritmo mais lento que o original), simplesmente coloquei pra adicionar o objeto:

if (!lista.add(objeto)) {
    lista.get(lista.indexOf(objeto))).setMaisRecente(atualizacao);
    }

Pronto… a análise de cada arquivo reduziu de um tempo significativo para um segundo por cada.
:sweat_smile:

Novamente agradeço a todos pela ajuda e pelas orientações.

2 curtidas