Oct 092007
 

Einige JSF (Java Server Faces) Komponenten-Frameworks unterstützen Pagination in Tabellen. Dadurch kann der Anwender in den durch die Tabelle dargestellten Datensätzen blättern. Auch das viel geschätzte Richfaces bietet Pagination und unterstützt dabei die Aktualisierung der Tabellenseite über Ajax.

Wird eine Tabelle mit Pagination verwendet, damit der Anwender durch einen hinreichend großen Datenbestand blättern kann, so ist es nachteilig den gesamten Datenbestand aus der Datenbank in den Hauptspeicher zu laden. Da noch nicht bekannt ist, welche Seiten der Tabelle vom Anwender tatsächlich angefordert werden, macht es Sinn nur die Daten für die aktuell angezeigte Tabellenseite zu laden. Die Daten für andere Seiten werden erst geladen, wenn der Anwender die entsprechende Tabellenseite zur Anzeige bringt. Einmal geladene Daten einer Tabellenseite sollten im Speicher gehalten werden, sofern ein bestimmtes Maximum nicht überschritten wird.

Realisiert werden diese Anforderungen mittels Lazy-Loading List. Die Layzy-Loading Liste unterstützt das java.util.List Interface. Erst wenn mittels “List.get(index)” ein Element der Liste gelesen wird, erfolgt das Laden einer Teilmenge von Einträgen in die Liste. Als Basis verwende ich Apache Common Collections für die Realisierung der Lazy-List.


Für das Laden von Listeneinträgen zum Bsp. aus einer Datenbank defineren wir das folgende Interface:

package com.openwishes.util.collection;

import java.util.List;

/**
 * For creating the list element from a query result element
 * when lazily adding to the lazy list.
 * @author MN
 */
public interface IOwLazyListLoader {

  /**
   * Loads the given number of entries starting at the given index (zero based)
   * and returns them in a list.
   *
   * @param pFirstEntryIndex
   * @param pNumEntries
   * @return
   */
  List load(int pFirstEntryIndex, int pNumEntries);

}

Die Implementierung dieser Schnittstelle ist verantwortlich für das Laden eines Blocks von Einträgen. Das Erstellen einer Lazy-List-Instanz erfolgt über folgende (sehr einfache) Factory:

package com.openwishes.util.collection;

import java.util.Collections;
import java.util.List;

/**
 * For having a dynamically growing list when the user performs searches with high number
 * of results and uses pagination.
 * @author Marc Neumann
 */
public final class OwLazyListFactory {

  private OwLazyListFactory() {
  }

  @SuppressWarnings("unchecked")
  public static List createLazyList(IOwLazyListLoader pLoader, int pNumTotal, int pBlockSize) {
    return Collections.unmodifiableList(new OwLazyList(pLoader, pNumTotal, pBlockSize));
  }
}

Die Factory stellt durch “Collections.unmodfiableCollection” sicher, dass die Liste “nur lesend” verwendet wird. Beim Erstellen der Lazy-List muss die Gesamtanzahl der Elemente angegeben werden. Dies wird verwendet, damit die Liste in der Methode “size()” einen fixen Wert zurückgeben kann. Ebenso muss die Blockgröße angegeben werden. Die Blockgröße definiert, in welchen Blöcken Elemente geladen werden. Die Blockgröße entspricht der Anzahl an Tabellenzeilen auf einer Seite bei Pagination.

Die Implementierung der Lazy-List selbst gestaltet sich wie folgt:

package com.openwishes.util.collection;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

import org.apache.commons.collections.list.AbstractLinkedList;

/**
 * This lazy list will load its content partially (in blocks of elements) dynamically.
 * The list is created over a factory and can only be used read only.
 * Some reading methods (indexOf, lastIndexOf, contains, containsAll, toArray) are not supported.
 * The list is only accessed using the list interface,
 * so certain non list interface methods are not explicitely handled.
 *
 * @author Marc Neumann
 */
class OwLazyList extends AbstractLinkedList {

  /**
   * For iterating over the whole lazy list.
   */
  private class OwLazyListIterator extends AbstractLinkedList.LinkedListIterator {

    public OwLazyListIterator(int pFromIndex) {
      super(OwLazyList.this, pFromIndex);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean hasNext() {
      return (nextIndex() < numTotal);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public Object next() {
      return get(nextIndex++);
    }
  }

  /**
   * For iterating over a sub list.
   */
  private class OwLazySubListIterator extends AbstractLinkedList.LinkedSubListIterator {

    public OwLazySubListIterator(AbstractLinkedList.LinkedSubList pSub, int pFromIndex) {
      super(pSub, pFromIndex);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public Object next() {
      return get(nextIndex++);
    }

  }

  private int numTotal;

  private int blockSize;

  private IOwLazyListLoader loader;

  private List[] cachedLists;

  /**
   * Construcor.
   * @param pLoader Used to obtain list elements lazily.
   * @param pNumTotal The total number of elements in the list.
   * @param pBlockSize The elements for dynamic retrieval are queried in blocks of this size.
   */
  public OwLazyList(IOwLazyListLoader pLoader, int pNumTotal, int pBlockSize) {
    numTotal = pNumTotal;
    blockSize = pBlockSize;
    loader = pLoader;

    int numCachedLists = (int) Math.ceil(((float) pNumTotal / (float) pBlockSize));
    cachedLists = new List[numCachedLists];
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public int size() {
    return numTotal;
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public Object get(int pIndex) {
    int indexCachedList = pIndex / blockSize;
    int indexInCachedList = pIndex % blockSize;
    int indexBlockStart = pIndex - indexInCachedList;

    List partialList = cachedLists[indexCachedList];
    if (partialList == null) {
      partialList = loader.load(indexBlockStart, blockSize);
      cachedLists[indexCachedList] = partialList;
    }

    Object resultItem;
    if (indexInCachedList < partialList.size()) {
      resultItem = partialList.get(indexInCachedList);
    }
    else {
      resultItem = null;
    }

    return resultItem;
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public Iterator iterator() {
    return listIterator();
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public ListIterator listIterator() {
    return listIterator(0);
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public ListIterator listIterator(int pFromIndex) {
    return new OwLazyListIterator(pFromIndex);
  }

  /**
   * {@inheritDoc}
   */
  @Override
  protected Iterator createSubListIterator(LinkedSubList pSubList) {
    return new OwLazySubListIterator(pSubList, 0);
  }

  /**
   * {@inheritDoc}
   */
  @Override
  protected ListIterator createSubListListIterator(LinkedSubList pSubList, int pFromIndex) {
    return new OwLazySubListIterator(pSubList, pFromIndex);
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public boolean contains(Object pValue) {
    throw new UnsupportedOperationException();
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public boolean containsAll(Collection pColl) {
    throw new UnsupportedOperationException();
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public int indexOf(Object pValue) {
    throw new UnsupportedOperationException();
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public int lastIndexOf(Object pValue) {
    throw new UnsupportedOperationException();
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public Object[] toArray() {
    throw new UnsupportedOperationException();
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public Object[] toArray(Object[] pArray) {
    throw new UnsupportedOperationException();
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public boolean equals(Object pObj) {
    return (this == pObj);
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public int hashCode() {
    return System.identityHashCode(this);
  }

}

Interessant ist lediglich die Methode “get(int)”: Es wird der Index des Blocks von Elementen ermittelt. Wird ein bestehendes List-Objekt für diesen Block gefunden, so kann aus dieser Teil-Liste das Element ermittelt und zurückgegeben werden. Ist die Teil-Liste noch null, so muss diese mittels des Loader-Objekts geladen werden.

Eine zu beachtende Schwachstelle hat dieser Ansatz: Ändert sich die Anzahl der darzustellenden Elemente nachdem die Lazy-List instanziiert wurde, so hat dies keine Auswirkung mehr auf die fixe Größe der Lazy-List. Ist die tatsächliche Anzahl von Elementen gesunken so wird die Lazy-List “null” bei einem “get(int)” das nicht mehr vorhandene Element liefern – es sei denn die entsprechende Teilliste wurde bereits geladen, bevor die Elementanzahl gesunken ist.

Ebenso kann es zu Problemen kommen, wenn sich die Reihenfolge der Elemente in der Datenquelle ändert.

Es sollte sich also um Daten handeln die sich nicht oder nur wenig dynamisch ändern, während der Anwender in einer Tabelle blättert. Die Vorteile dieses Ansatzes ist die Einfachheit und die erzielte Performance.

Dieser Ansatz wurde bei der Nutzersuche von OpenWishes verwendet und hielt dem Test der Pagination über 100 000 eingetragene Nutzer stand – die Performance war gegenüber einem Test mit 100 eingetragenen Nutzers nahezu identisch.

 Leave a Reply

(required)

(required)

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>