optimale Parameter für einen Paging-Mechanismus ermitteln

[mental.dIseASe]

Hallo zusammen,

ich habe hier gerade einen Paging-Mechanismus vor mir, der mir die Ergebnismenge einer Abfrage einschränkt und die resultierenden Zeilen ausspuckt. Er wird konfiguriert über die zwei Parameter PageNumber und PageSize:

Sei eine Abfrage mit 15 Zeilen Ergebnis gegeben, dann liefern folgende Konfigurationen von PageNumber und PageSize die angegebenen Zeilen zurück:

Beispiel:

PageNumber == 1, PageSize == 1 -> Zeile 1
PageNumber == 1, PageSize == 5 -> Zeilen 1 bis 5
PageNumber == 2, PageSize == 5 -> Zeilen 6 bis 10
PageNumber == 2, PageSize == 10 -> Zeilen 11 bis 15
PageNumber == 2, PageSize == 15 -> (leer)

Ein Offset ist NICHT konfigurierbar.

Angenommen, ich möchte eine bestimmte Anzahl hintereinander stehender Zeilen haben und kenne deren Indizes. Gibt es dann eine Möglichkeit, aus diesen Indizes PageNumber und PageSize so zu berechnen, dass

a) alle Zeilen in einer Page (also in einem Rutsch) ausgelesen werden
und
b) möglichst wenige Zeilen auf der Ergebnis-Page sind, die nicht zum Ergebnis gehören

Angenommen, ich wollte also die Zeilen 12 bis 15 haben, 4 Zeilen, dann wäre das optimale Parameterpaar zum Auslesen wohl (PageNumber == 3, PageSize == 5). Dies würde die Zeilen 11-15 ausspucken, mit Zeile 11 also nur eine Zeile Ausschuss. Unoptimal im Sinne der Fragestellung wäre zum Beispiel das Parameterpaar (PageNumber == 2, PageSize == 8), weil es zwar alle gesuchten Zeilen ausliest, aber mit 4 unnötigen Zeilen auch unnötig viel Auschuss produziert.

Da meine Mathe-Vorlesung schon ein paar Jahre her ist und mein Gehirn gerade Matsch ist, wende ich mich mit dieser Frage an euch. Vielleicht reicht auch schon ein kraftvoller Schubser in die richtige, mathematische Ecke. Programmatischer Hintergrund ist, dass ich für eine Auswahlliste bestimmte Elemente nachladen will, ohne die Liste komplett neuzuladen.

 

[hroessler]

Handelt es sich bei dem Quellsystem um eine Datenbank? Bei manche Datenbanken kannst du schon eine Handeln von Pages in die Query einbauen. Dann musst du Programmseitig nicht mehr viel tun ausser die nächste / vorherige Seite anfordern.

Greetz
​hroessler

 

[mental.dIseASe]

Sagen wir mal, der Paging-Mechanismus ist vorgegeben(legacy und unumstößlich) und ich will ihn nur optimal im Sinne der Fragestellung verwenden. Um mal vom Quellsystem zu abstrahieren, würde ich mir eine Liste vorstellen, auf die man ausschließlich mit diesem Mechanismus zugreifen kann.

 

[dcc22]

Bin mir nicht sicher wovon du da redest, aber Paging kenne ich nur von RAM, so werden die Daten dort verwaltet
Scheint ein ähnliches Problem zu sein.

 

[Daaron]

Der gängigere Begriff ist Pagination....

Meine spontane Herangehensweise:
- Wie viele Zeilen stellen das Minimum dar, um die gewünschte Ergebnismenge abzubilden? Das wäre dann wohl PageSize
- Was ist das maximale ganzzahlige Vielfache von PageSize, das kleiner/gleich der Nummer der ersten benötigten Zeile ist? Da hättest du dann die PageNumber.

 

[daemon777]

Der Ansatz wird so wohl noch nciht funktionieren. Wenn man PageSize als (maxValue - minValue) wählt, dann ist noch nicht gesagt, dass minValue auch genau auf der Grenze zu einer neuen Page liegt und somit muss man im allgemeinen Fall 2 Pages auslesen.

Alternativer Vorschlag:
1. Setze PageSize vorläufig auf (maxValue - minValue +1)
2.1. Falls (minValue-1) mod PageSize = 0, dann haben wir bereits eine geeignete PageSize gefunden und fahre fort mit Schritt 3
2.2. Falls nicht, dann setze minValue auf minValue-1 und PageSize auf PageSize+1.
2.3. Wiederhole Schritt 2.2 so lange, bis die Bedingung (minValue-1) mod PageSize = 0 zutrifft.
3. Setze PageNumber auf (minValue-1)/PageSize

Also im Prinzip suche ich hier noch nach der kleinsten PageSize, so dass mein gesuchtes Intervall sich auf genau einer Page befindet. Ob das jetzt tatsächlich das Minimum ist bin ich mir jetzt noch nicht sicher, aber ich glaube das sollte zumindest schonmal funktionieren.

Edit: PageSize ist natürlich minimal (maxValue - minValue +1).

Edit2: Das Ergebnis ist leider immernoch nicht optimal. Es ist nicht immer ausreichend das Intervall nach vorne hin zu erweitern. Ein Beispiel hierfür wäre [23,26]. Hierbei liegt wohl das optimale Ergebnis bei einer PageSize von 7. Die Page 4 hätte also dann die Einträge [22,28]. Mein Algorithmus hätte aber eine PageSize von 13 ermittelt.
Damit wird klar, dass die Findung des Optimums tatsächlich etwas komplexer wird. Statt dass Intervall nur noch vorne um eins zu erweitern müssen alle Möglichkeiten durchgetestet werden. Ist der Unterschied zwischen der optimalen PageSize und der Start-PageSize h, dann werden somit sum(1:h) Tests benötigt und die Laufzeit ist somit quadratisch.

Ergänzung (15. Januar 2015)

Ok ich hab mir jetzt nochmal einen einfachen Algorithmus ausgedacht, bei dem es auch in Linearzeit geht.

Und zwar wollen wir ja herausfinden, welches der kleinste Wert für PageSize ist, bei dem minValue und maxValue auf der gleichen Page landen. Das ist der Fall, falls minValue div PageSize = maxValue div PageSize. Div ist hierbei die Ganzzahldivision.
Also kann man einfach wie folgt vorgehen:
1. PageSize auf Intervallgröße setzen (maxValue - minValue + 1)
2. Solange PageSize um eins erhöhen, bis minValue div PageSize = maxValue div PageSize, wobei dieser Wert automatisch auch der Page-Nr. entspricht.

So das sollte jetzt hinhauen