Java, ricerca all’interno di un elenco di oggetti?

Sono un po ‘ perso sul modo per rendere questo accada il più veloce. Ho una lunga lista di oggetti che hanno di base variabile attributi (getter /setter) e ho bisogno di fare una ricerca in questo elenco per trovare gli oggetti nella lista che corrispondono a un dato parametro

Ho trovato come fare una normale ricerca, ma ho bisogno di, per esempio, cercare il valore del risultato di fare una chiamata getName() per ogni oggetto della lista e ottenere oggetti che hanno un risultato che corrisponde al mio ingresso.

Qualcosa di simile al di sotto, dove il terzo argomento è il risultato della chiamata al metodo e il secondo è quello che sto cercando di trovare.

   int index = Collections.binarySearch(myList, "value", getName());

Ogni consiglio è apprezzato

InformationsquelleAutor Rick | 2011-03-03



6 Replies
  1. 10

    Se è solo come un one-off funzionamento bisogno di trovare l’oggetto(s) di cui getName() è un valore particolare, quindi c’è probabilmente non è molta magia possibile: scorrere l’elenco, chiamare getName() su ogni oggetto, e per quelli che corrispondono, aggiungere alla vostra lista dei risultati.

    Se getName() è un’operazione costosa e c’è qualche altro modo di a-priori di lavoro se un dato oggetto, sicuramente non restituiscono un valore corrispondente, poi, ovviamente, si può costruire in questo ‘filtro’ come si passa attraverso.

    Se avete spesso bisogno di recuperare oggetti per un dato getName(), quindi avere un indice (ad esempio, in una HashMap) di [risultato di getName()->oggetto -> lista delle partite]. Avrete bisogno di decidere come e se è necessario mantenere questo “indice” in sintonia con l’elenco effettivo.

    Vedere anche l’altra proposta di utilizzare binarySearch (), ma per mantenere la lista mantenuto. In questo modo, gli inserti sono più costosi di quelli con una mappa e l’elenco non ordinato, ma se gli inserti sono frequenti rispetto per le ricerche, quindi ha il vantaggio di essere solo la necessità di mantenere una struttura.

    • Così l’hashmap sarebbe rendere questo più veloce? I dati cambiano raramente nell’elenco di oggetti (come solo una volta alla settimana), io l’ho già fatto nel modo che ti ha suggerito inizialmente, ma non sono felice con la velocità, quindi in pratica sto cercando di capire un modo per rendere questo più veloce.. grazie
    • Se cambi spesso ordinare solo quando cambia. Vorrei utilizzare una Mappa<String, Pippo> me, piuttosto che una ricerca binaria. Probabilmente è più veloce usare la Mappa, ma solo un modo per scoprirlo 🙂
    • Sto pensando che se ho appena messo il “foreignkey” che ho bisogno di una Mappa come Map <String foreignkey, foo> questo renderebbe se più veloce, dato che non c’è sostanzialmente un campo chiave esterna dove ho solo bisogno di controllare i valori se corrisponde che, in questo modo sarebbe più veloce solo in bicicletta attraverso l’intero elenco, giusto?
    • Sulla carta, la mappa è più veloce, e più scalabile. Essenzialmente, il tempo per recuperare, tutto ciò che è sul vostro sistema, sarà costante, tuttavia molti elementi con una cartina con la ricerca binaria, il tempo aumenterà di alcune quantità costante per ogni raddoppio del numero di elementi. Ma se uno è abbastanza veloce per i vostri scopi, quindi si tratta di vedere quale struttura è più facile da gestire per voi.
    • Penso che sarebbe davvero molte mappe, ad esempio Mappe<String, Pippo> per getName() e Mappa<Integer, Pippo> per il getAge ecc… si potrebbe anche voler prendere in considerazione una sorta di database in memoria come hsqldb, per questo, se davvero si sta facendo un sacco di ricerche di diverse “chiavi”.
  2. 10

    Dare un’occhiata al binarySearch che prende un comparatore:

    public static int binarySearch(Elenco,
    Tasto T,
    Comparatore c)

    Così si potrebbe fare qualcosa di simile:

    class FooComparator
        implements Comparator<Foo>
    {
        public int compare(T a, T b)
        {
            return (a.getName().compareTo(b.getName());
        }
    }
    
    int index = Collections.binarySearch(myList, "value", new FooComparator());

    È necessario ordinare l’elenco di corso (Collezioni.sorta prende un Comaprator così…).

    • E, naturalmente, se la lista viene aggiunto, è necessario aggiungere in un luogo adeguato, basato anche su questo comparatore in modo che la lista è mantenuto in ordine. Se le aggiunte sono frequenti, questa potrebbe essere una soluzione migliore che con una mappa, è solo mantenere una struttura.
    • In particolare, questo funziona solo se si ordina l’elenco in prima utilizzando la stessa Comparatore potrai utilizzare per la ricerca.
  3. 9

    So anonymous inner class non è di moda più, ma mentre Java 8 arriva, è possibile creare qualcosa di simile a questo:

    1.- Creare un metodo di ricerca che si ripeta la raccolta e passare un oggetto che ti dice se un oggetto deve essere restituito o non.

    2.- Richiamare il metodo e creare un anonimo classe interna con i criteri

    3.- Ottenere il nuovo elenco separato variabile.

    Qualcosa di simile a questo:

    result = search( aList, new Matcher(){ public boolean matches( Some some ) { 
      if( some.name().equals("a")) { 
         return true;
      }
    }});

    Qui un demo:

    import java.util.*;
    class LinearSearchDemo { 
      public static void main( String ... args ) { 
          List<Person> list = Arrays.asList(
                                      Person.create("Oscar", 0x20),
                                      Person.create("Reyes", 0x30),
                                      Person.create("Java", 0x10)
                              );
    
          List<Person> result = searchIn( list, 
                  new Matcher<Person>() { 
                      public boolean matches( Person p ) { 
                          return p.getName().equals("Java");
                  }});
    
          System.out.println( result );
    
          result = searchIn( list, 
                  new Matcher<Person>() { 
                      public boolean matches( Person p ) { 
                          return p.getAge() > 16;
                  }});
    
          System.out.println( result );
    
      }
      public static <T> List<T> searchIn( List<T> list , Matcher<T> m ) { 
          List<T> r = new ArrayList<T>();
          for( T t : list ) { 
              if( m.matches( t ) ) { 
                  r.add( t );
              }
          }
          return r;
      }
    }
    
    class Person { 
      String name;
      int age;
    
      String getName(){ 
          return name;
      }
      int getAge() { 
          return age;
      }
      static Person create( String name, int age ) { 
          Person p = new Person();
          p.name = name;
          p.age = age;
          return p;
      }
      public String toString() { 
          return String.format("Person(%s,%s)", name, age );
      }    
    }
    interface Matcher<T> { 
      public boolean matches( T t );
    }

    Di uscita:

    [Person(Java,16)]
    [Person(Oscar,32), Person(Reyes,48)]
    • +1 per esempio.bella spiegazione.
    • Questo è bello e io plussed si, ma in pratica non è molto più breve rispetto al “verbose” codice.. per(n:elenco){if(n.getAge()>16 t.add(n);} è inferiore alla classe anonima in alcuni casi..
  4. 1

    Se gli oggetti sono immutabili (o almeno sapere i loro nomi non cambia) si potrebbe creare un indice di utilizzo di una HashMap.

    Si dovrebbe riempire la Mappa e tenerlo aggiornato.

    Map map = new HashMap();
    
    map.put(myObject.getName(), myObject);
    ... repeat for each object ...

    Quindi è possibile utilizzare map.get("Some name"); fare ricerca utilizzando l’indice.

  5. 0

    Una libreria che ho familiarità con è Guava-si può comporre la sua Predicato per estrarre elementi da un Iterable. Non c’è bisogno per la collezione pre-ordinati. (Questo significa che, a sua volta, che è O(N), ma è comodo.)

Lascia un commento