Wie binär Suche auf einem Feld eines Elemente der Liste

Question

C Lassen Sie eine Klasse definiert werden (teilweise) durch

private static class C { 
    private final int x; 
    // lots more fields be here 

    public C(int x, /* lots more arguments here */) { 
     this.x = x; 
     // lots more fields initialized here 
    } 

    public int getX(){ 
     return x; 
    } 
} 

und lassen cs ein List<C> sein RandomAccess Implementierung und sortiert auf C.getX().

Was wäre der Standardansatz für eine binäre Suche in cs für x1 unter C.getX()? (Mit anderen Worten vorgeben, dass jedes Element c durch c.getX() ersetzt wird und dann suchen wir nach x1 unter diesen Zahlen.)

---

Collections.binarySearch(
    cs, 
    new C(x1,/* dummy arguments */), 
    (a,b) -> Integer.compare(a.getX(),b.getX()) 
); 

hat den Nachteil, dass es Bau eines neuen C erfordert (die erfordern viele Dummy-Argumente und Wissen über C).

hat den Nachteil, dass es eine ganze neue Liste erstellt und vermutlich O (n) ist.

---

Gibt es eine Möglichkeit, im Stream direkt zu suchen, ohne es zu sammeln? Oder vielleicht eine andere Möglichkeit, die ursprüngliche Liste zu durchsuchen, ohne ein Dummy-Objekt konstruieren zu müssen?

---

In Ermangelung eines besseren Ansatz, würde ich dies tun:

public class MappedView<T,E> extends AbstractList<E> { 

    public static <T,E> MappedView<T,E> of(List<T> backingList, Function<T,E> f){ 
     return new MappedView<>(backingList, f); 
    } 

    private final List<T> backingList; 
    private final Function<T,E> f; 

    private MappedView(List<T> backingList, Function<T,E> f){ 
     this.f = f; 
     this.backingList = backingList; 
    } 

    @Override 
    public E get(int i) { 
     return f.apply(backingList.get(i)); 
    } 

    @Override 
    public int size() { 
     return backingList.size(); 
    }  
} 

und dann

Collections.binarySearch(
    MappedView.of(cs, c -> c.getX()), 
    x1 
); 

Answer 1

Ein anderer Ansatz könnte dies sein:

private static class C { 
    private final int x; 
    // lots more fields be here 

    private C() { 
    } 

    public C(int x, /* lots more arguments here */) { 
     this.x = x; 
     // lots more fields initialized here 
    } 

    public int getX(){ 
     return x; 
    } 

    public static C viewForX(int x) { 
     C viewInstance = new C(); 
     viewInstance.x = x; 
     return viewInstance; 
    } 
} 

Collections.binarySearch(cs, 
    C.viewForX(x1), 
    (a,b) -> Integer.compare(a.getX(),b.getX())); 

Or Wenn es Ihnen nichts ausmacht, können Sie dies tun mit Guava:

List<Integer> xs = Lists.transform(cs, C::getX()); 
Collections.binarySearch(xs, x1); 

Answer 2

Da Sie die Kontrolle über die Comparator Implementierung sind, können Sie eine symmetrische Vergleichsfunktion implementieren, die Instanzen von C mit Werten der gewünschten Eigenschaft, dh int Werte (gewickelt als Integer) vergleichen können im Falle Ihrer x Eigenschaft. Es hilft, die Fabrikmethoden comparing… im Comparator interface zu wissen, was Sie von der Wiederholung des Codes für beiden Seiten des Vergleichs sparen:

int index = Collections.binarySearch(cs, x1, 
    Comparator.comparingInt(o -> o instanceof C? ((C)o).getX(): (Integer)o)); 

diese Weise können Sie für den int Wert suchen x1 ohne es in einer C Instanz gewickelt wird.