Java merge 2 collections in O(1)

Najprostszym rozwiązaniem jest tutaj lista list. Oznacza to, że potrzebujesz prostych funkcji owijania, ale nic skomplikowanego.

W teorii, możesz połączyć 2 połączone listy W O(1), Ponieważ wszystko, co musisz zrobić, to skierować ostatni węzeł pierwszego do pierwszego węzła drugiego (zakładając, że masz te odniesienia).

Metoda zbioru addAll wydaje się sugerować czas działania O(n), ponieważ mówią o iteratorach. Szczegóły mogą być specyficzne dla JVM...

Myślę, że nie ma żadnych zbiorów, które połączyłyby się w O (n). Może sam będziesz musiał to zrobić.

Myślę, że najlepiej byłoby stworzyć implementację listy, która jako swoje argumenty przyjmuje List>, a następnie deleguje. Innymi słowy, mieć listę list i połączyć je, aby działać jako jedna lista. Kiedy przechodzisz obok elementów listy 1, zaczynasz patrzeć na listę 2.

Z jakiegoś powodu myślałem, że guava ma taką listę. Ale nie mogę znaleźć tego w ich Javadoc.

Jeślipo prostu Chcesz mieć kolekcje obiektów i scalać je w czasie O(1) i nie masz nic przeciwko implementacji własnej struktury danych, najprostszym sposobem na to jest użycie niezrównoważonego drzewa binarnego: każdy węzeł jest albo liściem (przechowującym wartość), albo kombinacją dwóch drzew i możesz zaimplementować je jako dwie klasy z abstrakcyjną klasą nadrzędną lub interfejsem. Do ekstrakcji pierwiastków można użyć trawersu o pierwszej głębokości.

Jest to zasadniczo to samo, co ColinD sugestia konkatenacji iteratora, ale więcej gołych kości.

haczyk polega na tym, że iteracja nad tą kolekcją będzie , a nie być O(n)! Będzie O (n + m) Gdzie m jest liczbą wykonanych połączeń (ponieważ każdy z nich jest węzłem do przejścia). Jest to prawda zarówno mojego rozwiązania, jak i Colinda. Nie wiem, czy to prawda dla wszystkich możliwych rozwiązań tego problemu.

Mniejsza o powyższe. W ramach tego programu każdy merge dodaje co najmniej jeden element, więc m n i tak koszt iteracji jest nadal O (n). (Jeśli używasz konkatenacji iteratora, upewnij się, że często nie łączysz pustych iteratorów, ponieważ zwiększyłoby to koszt.)

Scalanie połączonych list jest rzeczywiście O(1) i można traktować listy oparte na tablicach w ten sam sposób, tzn. mając wiele obiektów połączonych między sobą.

Istnieją implementacje powyższego, jest to szybsze niż ArrayList podczas usuwania / wstawiania od środka / startu. I iteracja jest praktycznie taka sama. Losowy dostęp może być jednak nieco wolniejszy.

Chciałem zasugerować klasę CompositeCollection z apache.commons, ale patrząc na kod źródłowy to działa również w O (n). Jeśli potrzebujesz tylko iterować nad elementami i nie chcesz korzystać z kolekcji Google zgodnie z sugestią Colinda, możesz łatwo utworzyć własny iterator kompozytowy, np.

public class CompositeCollectionIterator<T> implements Iterator<T>{

  private Iterator<T>[] iterators;
  private int currentIteratorIndex = 0;
  public CompositeCollectionIterator( Collection<T>... aCollections ) {
    iterators = new Iterator[ aCollections.length];
    for ( int i = 0, aCollectionsLength = aCollections.length; i < aCollectionsLength; i++ ) {
      Collection<T> collection = aCollections[ i ];
      iterators[i] = collection.iterator();
    }
  }

  public boolean hasNext() {
    if ( iterators[currentIteratorIndex].hasNext() ) return true;
    else if ( currentIteratorIndex < iterators.length - 1 ){
      currentIteratorIndex++;
      return hasNext();
    }
    return false;
  }

  public T next() {
    return iterators[currentIteratorIndex].next();
  }

  public void remove() {
    iterators[currentIteratorIndex].remove();
  }
}

Używając dwóch połączonych list jako kolekcji i przechowując wskaźniki do pierwszego i ostatniego elementu każdej listy(oba wskaźniki potencjalnie wymagają aktualizacji podczas dodawania/usuwania elementów), możesz połączyć obie listy W O (1) - po prostu podłącz ostatni element pierwszej listy do pierwszego elementu drugiej listy i odpowiednio dostosuj pierwszy/ostatni wskaźnik.

Obawiam się, że będziesz musiał zwijać własną implementację linkowanych list w Javie, ponieważ nie masz bezpośredni dostęp do bazowych węzłów LinkedList, dlatego nie można połączyć ostatniego elementu pierwszej listy z pierwszym elementem drugiej listy.

Na szczęście łatwo jest znaleźć implementacje linked list w Javie, ponieważ jest to bardzo popularny temat w kursach struktury danych. Na przykład tutaj jest jeden - wiem, nazwy są w języku hiszpańskim, ale kod w ListaEncadenada ("LinkedList") i NodoLista ("ListNode") jest dość prosty i powinien być oczywisty, a co najważniejsze - implementacja zawiera wskaźniki do pierwszego i ostatniego elementu listy i może być łatwo modyfikowana do własnych potrzeb.