# Pagination algorithm based on scores

I need to divide scoreResult into pages (which is already ordered by score column from highest to lowest), and each page cannot contain too many records (e.g. 12 is a limitation in my example), and each page cannot contain duplicate id1, and each page needs to be ordered by score from highest to lowest.

Here is my working code; I am seeking advice, especially of smarter and more efficient solutions.

scoreResult = [
#id1,id2,score",
"1,28,300.1",
"4,5,209.1",
"20,7,208.1",
"23,8,207.1",
"16,10,206.1",
"1,16,205.1",
"1,31,204.6",
"6,29,204.1",
"7,20,203.1",
"8,21,202.1",
"2,18,201.1",
"2,30,200.1",
"15,27,109.1",
"10,13,108.1",
"11,26,107.1",
"12,9,106.1",
"13,1,105.1",
"22,17,104.1",
"1,2,103.1",
"28,24,102.1",
"18,14,11.1",
"6,25,10.1",
"19,15,9.1",
"3,19,8.1",
"3,11,7.1",
"27,12,6.1",
"1,3,5.1",
"25,4,4.1",
"5,6,3.1",
"29,22,2.1",
"30,23,1.1"
]

PageLimit = 12

def pageResult():

#store final resutls
pages = {}
# store dictionary to see if page exists
# key = host_id+#+page_id, value = item
pageDict = {}
# key: page ID, value: # of items
pageCount = {}
for item in scoreResult:
page= 0
host_id=item.split(',')[0]

while pageDict.has_key(str(host_id)+'#'+str(page)) or (pageCount.has_key(page) and pageCount[page] >= PageLimit):
#print page
page += 1
pageDict[str(host_id)+'#'+str(page)] = True
if pages.has_key(page):
pages[page].append(item)
else:
pages[page]=[]
pages[page].append(item)

if pageCount.has_key(page):
pageCount[page] += 1
else:
pageCount[page] = 1

for k,v in pages.items():
print k
print v

if __name__=="__main__":
pageResult()


If you look at your code you have a lot of if pageCount.has_key(page): else:. This can be replaced with a defaultdict. pages defaults to a list, as if pages[page] does not exist you manually default it to a list. And page_count defaults to zero.

As a simple example the following is how you could use default-dicts:

from collections import defaultdict

pages = defaultdict(list)
pages[0].append('Page 1')


I think changing page_dict to a set would be better, as they index the same way, but using a set will use less memory.

I would use a tuple as page_dict's key, rather than a string. This is as (a, b) is easier to read than str(a) + "#" + str(b).

Python also has a style guide called PEP8, which basically means that your variables should be snake_case, and PageLimit should be UPPER_SNAKE_CASE as it's a constant.

Using the above should get you:

def page_result(score_result):
pages = defaultdict(list)
page_dict = set()
page_count = defaultdict(int)
for item in score_result:
page = 0
host_id = item.split(',')[0]

while (host_id, page) in page_dict or page_count[page] >= PAGE_LIMIT:
page += 1

pages[page].append(item)
page_count[page] += 1

for k, v in pages.items():
print k
print v


You could make another default-dict to store the latest page for a host_id.

This limits the amount of times the while loop runs. This dramatically reduces the amount of time it takes on larger data-sets. But has little diffrence on small data sets, and can perform slower!

I use the same data as given in the question, but timesed by 100. scoreResult *= 100.

This gave me the following times, over 1000 tries:

• Original: 225.99s
• My original: 53.14s
• My updatet: 2.97s
• Mathias': 58.83s

This shows that there may be little speed-up from using a dictionary rather than len.
I also removed the prints.

def page_result(score_result):
pages = defaultdict(list)
page_dict = set()
page_count = defaultdict(int)
host_page = defaultdict(int)
for item in score_result:
host_id = item.split(',')[0]
page = host_page[host_id]

while page_count[page] >= PAGE_LIMIT:
page += 1

pages[page].append(item)
page_count[page] += 1
host_page[host_id] = page + 1

for k, v in pages.items():
print k
print v


I would also recommend:

1. Moving the print part of the function into it's own function.
2. Read the data from a file. Saving it as a JSON file and using Python's JSON library is a simple way to do this.
• Thanks Joe, very cool comments. Wondering if you have ideas to improve the algorithm efficiency? I think I only did a straightforward implementation and there might be smarter ways for pagination with unique ID on each page? Thanks. – Lin Ma Jan 15 '16 at 17:38
• @LinMa I can think of a way... But I think it's a premature optimisation... But here I go, to see if it is plausible – Peilonrayz Jan 15 '16 at 17:49
• @LinMa I updated the answer with it. I'm still shocked at how much of a change it makes... – Peilonrayz Jan 15 '16 at 18:41
• @LinMa Yes from that to "I would also recommend:" If you are having a hard time telling, you may want to press the "edited x minutes ago", the removals will be in red, where the additions will be in green. – Peilonrayz Jan 15 '16 at 18:59
• – Peilonrayz Jan 16 '16 at 1:51

# A function has parameters

It allows for more flexibility and reusability. There is absolutely no need to declare scoreResult as a global variable, it forces you to use that variable name each time you want to use this function. Instead declare it as a parameter of the function.

Same goes for PageLimit; except for this one you can use a default value to avoid specifying it each time. Something along the lines of:

def pageResult(data, PageLimit=12):


# A function can return data

Especially a function altering input data such as yours. Functions should essentially perform one task and let other tasks to the rest of the program. Your function performs the pagination. Period. Let the pretty printing to someone else.

If you return pages at the end of your function, you can have your "main" par looks like:

if __name__=="__main__":
scoreResult = [
#id1,id2,score",
"1,28,300.1",
"4,5,209.1",
# snip
"30,23,1.1"
]

pages = pageResult(scoreResult)
for k, v in pages.items():
print k
print v


This let you change the way you print (or even use) your result without modifying the behaviour of your function.

# Checking for keys in dictionaries

some_dict.has_key(something) is deprecated: use something in some_dict instead.

You also use pageDict only to check the existence of specific keys in it, never using the associated values. The whole purpose of pageDict[str(host_id) + '#' + str(page)] = True is only to create the key, not to store a value: use a set instead. You can use it pretty similarly:

while str(host_id) + '#' + str(page) in pageDict ...:
page += 1


# Getting values out of dictionaries

Checking if a key exist in a dictionary and, if it does, retrieve its value is so common in Python that you have three ways of doing it:

• using some kind of if ... else such as in your while loop;
• accessing the value directly with the key and catching the KeyError if it didn't exist (preferred when failures are expected to be low);
• using the get method which does the latter in one line.

get even allows to retrieve a default value if the key doesn't exist. Which you can use to simplify your while:

while str(host_id) + '#' + str(page) in pageDict or pageCount.get(page, 0) >= PageLimit:


In the same vein, creating a default value for a key or retrieving the existing value has been implemented in the setdefault method:

pages.setdefault(page, []).append(item)
count = pageCount.setdefault(page, 0)
pageCount[page] = count + 1


# Use proper data-structures

Converting data to a string for comparison purposes is not the way to go. You are both loosing meaning and time for comparisons. You'd better of use tuples instead.

And speaking of meaning, why not convert your ids into integers first:

page = 0
host_id = int(item.split(',')[0])
while (host_id, page) in pageDict or pageCount.get(page, 0) >= PageLimit:
page += 1
# We add a tuple here, hence the double parenthesis


Additionally, the number of items stored for a single page can be found using the length of the list of items of this specific page. Thus, you don't need pageCount at all:

while (host_id, page) in pageDict or len(pages.get(page, [])) >= PageLimit:
page += 1
# We add a tuple here, hence the double parenthesis
pages.setdefault(page, []).append(item)


Lastly, you can simplify the use of get and setdefault on pages by turning this dictionary into a collections.defaultdict. It lets you specify a constructor for default values when building the dictionary. Each access to a key that has not been defined before will create the associated values using this constructor, thus no need to specify each time using either get or setdefault. Example:

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> d['test']
[]
>>> d['again'].append(1)
>>> d
defaultdict(<type 'list'>, {'test': [], 'again': [1]})


# A note on style

The official Python style guide is PEP8. Out of it, note:

• the use of snake_case instead of camelCase or TitleCase for variables or functions naming;
• the use of a space before and after the = in an assignment (except for specifying default values of parameters);
• the use of a space after comas.

You should also try to come with better, more explicit, names instead of pageXXX.

# Proposed improvement

from collections import defaultdict

def paginate(data, page_limit=12):
pages = defaultdict(list)
ids_in_page = set()

for item in data:
page = 0
host_id = int(item.split(',')[0])

# Find the page where the id is not already in that page
# and which still has room in it.
while (host_id, page) in ids_in_page or len(pages[page]) >= page_limit:
page += 1

# We add a tuple here, hence the double parenthesis

pages[page].append(item)

return pages

if __name__=="__main__":
score_result = [
#id1,id2,score",
"1,28,300.1",
"4,5,209.1",
"20,7,208.1",
"23,8,207.1",
"16,10,206.1",
"1,16,205.1",
"1,31,204.6",
"6,29,204.1",
"7,20,203.1",
"8,21,202.1",
"2,18,201.1",
"2,30,200.1",
"15,27,109.1",
"10,13,108.1",
"11,26,107.1",
"12,9,106.1",
"13,1,105.1",
"22,17,104.1",
"1,2,103.1",
"28,24,102.1",
"18,14,11.1",
"6,25,10.1",
"19,15,9.1",
"3,19,8.1",
"3,11,7.1",
"27,12,6.1",
"1,3,5.1",
"25,4,4.1",
"5,6,3.1",
"29,22,2.1",
"30,23,1.1",
]

pages = paginate(score_result)
for k, v in pages.items():
print(k)
print(v)


# A quick note on input data

I already stated that using string to store data remove the meaning associated to them. I don't know where you get your input from, neither what you plan to do with your output, but I have the feeling that you'll spend some time converting back-and-forth between strings and numerical values.

You'd better of using tuples of number if you can do so:

score_result = [
#id1, id2, score
(1, 28, 300.1),
(4, 5, 209.1),
(20, 7, 208.1),
(23, 8, 207.1),
(16, 10, 206.1),
(1, 16, 205.1),
(1, 31, 204.6),
(6, 29, 204.1),
(7, 20, 203.1),
(8, 21, 202.1),
(2, 18, 201.1),
(2, 30, 200.1),
(15, 27, 109.1),
(10, 13, 108.1),
(11, 26, 107.1),
(12, 9, 106.1),
(13, 1, 105.1),
(22, 17, 104.1),
(1, 2, 103.1),
(28, 24, 102.1),
(18, 14, 11.1),
(6, 25, 10.1),
(19, 15, 9.1),
(3, 19, 8.1),
(3, 11, 7.1),
(27, 12, 6.1),
(1, 3, 5.1),
(25, 4, 4.1),
(5, 6, 3.1),
(29, 22, 2.1),
(30, 23, 1.1),
]


This lets you retrieve the host id using host_id = item[0] instead of int(item.split(',')[0]).

• You could try grouping by ID before dispatching on pages to try to balance them. I may update the answer if I come with something when I have more time. – 301_Moved_Permanently Jan 15 '16 at 17:45
• "# We add a tuple here, hence the double parenthesis' -- tuples should always have a comma at the end: ids_in_page.add((host_id, page,)) – rbp Jan 15 '16 at 19:37
• @rbp Why for? It is required for 1-sized tuples so the parser doesn't treat it as a single value, but for the rest it is not mandatory at all. It is visually better when written on multiple line such as score_result` but otherwise I don't get the reasonning. – 301_Moved_Permanently Jan 15 '16 at 19:43
• stackoverflow.com/questions/7992559/… – rbp Jan 15 '16 at 19:44
• @rbp So what's more that what I said? It's better for multiline tuples/list and only required for 1-element tuples. – 301_Moved_Permanently Jan 15 '16 at 19:52