Pagination Algorithm
The Implementation
I have recently implemented the pagination to my blog index. That was my first to write to code of pagination by myself. I usually use one that comes with the framework like WordPress or Laravel. Before undertaking, I googled “pagination algorithm”, and found simple-pagination.js on Gist.
I could use his code without any modification. But something prevented me from doing so. “It seems there are lots of unnecessaries,” I thought. So I decided to make my own.
It is a good practice of programming to create pagination. It has an actual use, if you build your application from scratch, and it would be customizable for your needs. I’ve already posted my pagination code at here on the thread of the Gist page shown above.
In this post I’d like to show you the detail of my pagination.
Logic
When I say “pagination”, I mean one that looks like this:
Typically one pagination:
- shows the first and last page.
- shows prev/next buttons.
- shows only a few pages on each side of the current page if there are too many pages between the current page and the first or last page, so replaces those pages with ellipsis(…).
- emphasizes the current page.
That sounds like really simple but when you put it into a computer program, things get complicated. Paginations can be many forms: there could be only one page; there are only a few pages to omit pages between; you are on the page last so no need of showing a next button.
I discerned a pagination from left to right, and reached to the next logic—the literal of the algorithm:
- It does not have the prev if it is on the page “1”, and the next if on the last page.
- It must have at least the page “1”.
- If the current page is greater than 4, it must have “…” after the page “1”.
-
The r is the number of pages to be shown on each side of the current page. The r1 is the current page minus r, and r2 is the current page plus r.
- Add page numbers iterating from that is bigger between 2 and r1, to that is smaller between the last page and r2.
- If the last page is bigger than r2 by 2, it must have “…” on the right side.
- If the last page is bigger than r2, add the last page.
JavaScript
The implementation in JavaScript is:
function paginate({current, max}) {
if (!current || !max) return null
let prev = current === 1 ? null : current - 1,
next = current === max ? null : current + 1,
items = [1]
if (current === 1 && max === 1) return {current, prev, next, items}
if (current > 4) items.push('…')
let r = 2, r1 = current - r, r2 = current + r
for (let i = r1 > 2 ? r1 : 2; i <= Math.min(max, r2); i++) items.push(i)
if (r2 + 1 < max) items.push('…')
if (r2 < max) items.push(max)
return {current, prev, next, items}
}I name the function “paginate” not “pagination” since I think what the function does is a verb.
I wrote the following test code and got the result like:
for (let max = 1; max < 10; max+=2) {
console.log(`max: ${max}`)
for (let current = 1; current <= max; current++) {
let pagination = paginate({current, max})
console.log(` c:${current}`, pagination.items)
}
}
/*
Output:
max: 1
c:1 [1]
max: 3
c:1 [1, 2, 3]
c:2 [1, 2, 3]
c:3 [1, 2, 3]
max: 5
c:1 [1, 2, 3, '…', 5]
c:2 [1, 2, 3, 4, 5]
c:3 [1, 2, 3, 4, 5]
c:4 [1, 2, 3, 4, 5]
c:5 [1, '…', 3, 4, 5]
max: 7
c:1 [1, 2, 3, '…', 7]
c:2 [1, 2, 3, 4, '…', 7]
c:3 [1, 2, 3, 4, 5, '…', 7]
c:4 [1, 2, 3, 4, 5, 6, 7]
c:5 [1, '…', 3, 4, 5, 6, 7]
c:6 [1, '…', 4, 5, 6, 7]
c:7 [1, '…', 5, 6, 7]
max: 9
c:1 [1, 2, 3, '…', 9]
c:2 [1, 2, 3, 4, '…', 9]
c:3 [1, 2, 3, 4, 5, '…', 9]
c:4 [1, 2, 3, 4, 5, 6, '…', 9]
c:5 [1, '…', 3, 4, 5, 6, 7, '…', 9]
c:6 [1, '…', 4, 5, 6, 7, 8, 9]
c:7 [1, '…', 5, 6, 7, 8, 9]
c:8 [1, '…', 6, 7, 8, 9]
c:9 [1, '…', 7, 8, 9]
*/PHP
The implementation in PHP is:
<?php
function paginate(array $params) {
extract($params);
if (!isset($current) || !isset($max)) return null;
$prev = $current === 1 ? null : $current - 1;
$next = $current === $max ? null : $current + 1;
$items = [1];
if ($current === 1 && $max === 1) return [
"current" => $current,
"prev" => $prev,
"next" => $next,
"items" => $items,
];
if ($current > 4) array_push($items, "…");
$r = 2;
$r1 = $current - $r;
$r2 = $current + $r;
for ($i = $r1 > 2 ? $r1 : 2; $i <= min($max, $r2); $i++) array_push($items, $i);
if ($r2 + 1 < $max) array_push($items, "…");
if ($r2 < $max) array_push($items, $max);
return [
"current" => $current,
"prev" => $prev,
"next" => $next,
"items" => $items,
];
}You can test the implementation with the code:
for ($max = 1; $max < 10; $max+=2) {
echo "max: $max\n";
for ($c = 1; $c <= $max; $c++) {
$pagination = paginate(["current" => $c, "max" => $max]);
echo "c:$c\n";
print_r($pagination["items"]);
}
echo "\n";
}The output would be similar to one in JavaScript.
Compare
Is my pagination really better than kottenator’s? There is only one way to find out: test.
Environments
I undertook the performance test in the following environments:
- MacBook Air (M1, 2020), macOS Monterey
- Wifi turned off
- Bluetooth turned off
- Terminal is the only active app besides Finder; no Finer window opened
Test Codes
Since our implementations are bit different, I made two test codes for both functions. They are almost identical. Those two test codes are:
test1.js
const paginate = require('./paginate')
const MAX = 100
console.log('Starting test…')
console.time('paginating')
for (let max = 1; max < MAX; max+=2) {
for (let current = 1; current <= max; current++) {
let __pages = paginate({current, max})
}
}
console.timeEnd('paginating')test2.js
const pagination = require('./simple-pagination')
const MAX = 100
console.log('Starting test…')
console.time('paginating')
for (let max = 1; max < MAX; max+=2) {
for (let current = 1; current <= max; current++) {
let __pages = pagination(current, max)
}
}
console.timeEnd('paginating')I added module.exports to the each end of our pagination files so that that can be loaded in CommonJS.
Results
Here is the record of tests. I run the test program ten times sequentially for each functions—ten times for me, then ten times for kottenator. All the tests were done within three minutes.
| Mine | kottenat.’s | |
|---|---|---|
| 2.388 ms | 4.863 ms | |
| 2.454 | 5.109 | |
| 2.275 | 4.702 | |
| 2.285 | 5.014 | |
| 2.155 | 4.890 | |
| 2.484 | 4.784 | |
| 2.340 | 4.813 | |
| 2.421 | 5.098 | |
| 2.089 | 5.033 | |
| 2.174 | 4.718 | |
| Min | 2.089 | 4.702 |
| Max | 2.484 | 5.109 |
| Avg. | 2.303 | 4.903 |
Taking the average, my pagination is 212.9% faster than kottenator’s.
212.9 = (1 / (2.303/4.903)) * 100
Conclusion
My pagination is better than kottenator’s.
Why
The reason is simple. My pagination iterates way much less than kottenator’s. The problem of his pagination lies in these two lines:
for (let i = 1; i <= last; i++)
// and
for (let i of range)It iterates from the first page to last page, TWICE!
Meanwhile my pagination only iterates five times at maximum, whether the last page is 100, 1000, or 10000, if the pagination shows two pages between ellipsis and the current page. That is the essence of:
for (let i = r1 > 2 ? r1 : 2; i <= Math.min(max, r2); i++)The statement seems complicated to humans but it is simpler and kind to computers.
Lesson
Having taken over the projects from the other developers, I have seen a lot of mess in codebase. Just getting what you want is not enough in programming. There are bunch of approaches to one problem. Your “how” counts.
When we learned for-loop for the first time, we all thought that that was boring, and useless. It’s not. Most of computation involve iteration. That means if we could improve the code inside the for-loop, the computers allocate its resources for other computation, or reduce energy consumption. Maybe we could reduce the money spent on running server, hence.
We are taking for granted of the modern computing power. They are really fast, and getting faster. But we programmer are making them slower with carelessness or short-time thinking. Ironic
I hope that my pagination could be an opportunity for programmers to take a closer look at their program once again and polish them—and slow down the global warming just a little bit.