[2.5.1.1/dictionary] Change sorting order?

[Gilles Ganault]

Hello

I use a dictionary to keep a list of users connected to a web site.

To avoid users from creating login names that start with digits in
order to be listed at the top, I'd like to sort the list differently
every minute so that it'll start with the next letter, eg. display the
list from A...Zdigits the first time, then B...ZAdigits, etc.

That way, users have no incentive to create login names that start
with either a digit or letter A.

I see that dictionaries can be sorted using the... sort() method, but
is it possible to have Python start sorting from a different letter?

Thank you.

 

[Jean-Michel Pichavant]

Hello

I use a dictionary to keep a list of users connected to a web site.

To avoid users from creating login names that start with digits in
order to be listed at the top, I'd like to sort the list differently
every minute so that it'll start with the next letter, eg. display the
list from A...Zdigits the first time, then B...ZAdigits, etc.

That way, users have no incentive to create login names that start
with either a digit or letter A.

I see that dictionaries can be sorted using the... sort() method, but
is it possible to have Python start sorting from a different letter?

Thank you.

Here is one possible solution

l = ['1a', 'a', 'b','c','av','ac'] # you mentioned a dictionary in your
post, if so, l = myDict.keys()
l.sort() # sort your list once and for all
for start in '1abcd':
result = [name for name in l if name[0] >= start] + [name for name
in l if name[0] < start]
print result


['1a', 'a', 'b', 'c', 'av', 'ac']
['a', 'b', 'c', 'av', 'ac', '1a']
['b', 'c', '1a', 'a', 'av', 'ac']
['c', '1a', 'a', 'b', 'av', 'ac']
['1a', 'a', 'b', 'c', 'av', 'ac']


Jean-Michel

 

[Gilles Ganault]

I see that dictionaries can be sorted using the... sort() method, but
is it possible to have Python start sorting from a different letter?

Looks like the solution is to read the list of keys into a list, sort
the list, and then use this to read the dictionary:

http://code.activestate.com/recipes/52306/

But I haven't found whether a list can be sorted by starting from a
given letter instead of "a".

 

[Jean-Michel Pichavant]

Hello

I use a dictionary to keep a list of users connected to a web site.

To avoid users from creating login names that start with digits in
order to be listed at the top, I'd like to sort the list differently
every minute so that it'll start with the next letter, eg. display the
list from A...Zdigits the first time, then B...ZAdigits, etc.

That way, users have no incentive to create login names that start
with either a digit or letter A.

I see that dictionaries can be sorted using the... sort() method, but
is it possible to have Python start sorting from a different letter?

Thank you.

Here is one possible solution

l = ['1a', 'a', 'b','c','av','ac'] # you mentioned a dictionary in
your post, if so, l = myDict.keys()
l.sort() # sort your list once and for all
for start in '1abcd':
result = [name for name in l if name[0] >= start] + [name for name
in l if name[0] < start]
print result


['1a', 'a', 'b', 'c', 'av', 'ac']
['a', 'b', 'c', 'av', 'ac', '1a']
['b', 'c', '1a', 'a', 'av', 'ac']
['c', '1a', 'a', 'b', 'av', 'ac']
['1a', 'a', 'b', 'c', 'av', 'ac']


Jean-Michel

Sorry, the code I provided produce this output:

['1a', 'a', 'ac', 'av', 'b', 'c']
['a', 'ac', 'av', 'b', 'c', '1a']
['b', 'c', '1a', 'a', 'ac', 'av']
['c', '1a', 'a', 'ac', 'av', 'b']
['1a', 'a', 'ac', 'av', 'b', 'c']

which is actually what you are searching for. I just messed up with my
ipython shell history )

JM

 

[Steven D'Aprano]

Hello

I use a dictionary to keep a list of users connected to a web site.

To avoid users from creating login names that start with digits in order
to be listed at the top, I'd like to sort the list differently every
minute so that it'll start with the next letter, eg. display the list
from A...Zdigits the first time, then B...ZAdigits, etc.

That way, users have no incentive to create login names that start with
either a digit or letter A.

If you want to prohibit users from starting their login names with a
digit, prohibit them from creating a login name with a digit.

I see that dictionaries can be sorted using the... sort() method, but is
it possible to have Python start sorting from a different letter?

You can write a customer sort routine by using the key parameter to sort,
which will probably be messy. What I'd do is keep 27 lists of user names,
according to the first letter (26 letters from A to Z, plus one extra):


users = [ # keep separate lists for each starting letter
['aaron', 'avril', 'adam'],
['betty', 'bob'],
['craig', 'cathy'],
['danni', 'da5id', 'donna'],
# ... and so on
['zoe', 'zach'],
['4dam', '1-4m-t00-c001']
]

# add a new user
users[3].append('daniel')


Sort each one individually, and display them in whatever order you like:


def display(start=0):
start = start % 27
all = users[start:] + users[:start]
for l in all:
l.sort()
print l

And in use:
['aaron', 'adam', 'avril']
['betty', 'bob']
['cathy', 'craig']
['da5id', 'daniel', 'danni', 'donna']
['zach', 'zoe']
['1-4m-t00-c001', '4dam']['da5id', 'daniel', 'danni', 'donna']
['zach', 'zoe']
['1-4m-t00-c001', '4dam']
['aaron', 'adam', 'avril']
['betty', 'bob']
['cathy', 'craig']

 

[Steven D'Aprano]

You can write a customer sort routine by using the key parameter to
sort, which will probably be messy. What I'd do is keep 27 lists of user
names, according to the first letter (26 letters from A to Z, plus one
extra):

Replying to myself... the first sign of insanity *wink*

While I'd still stick to that basic strategy, I'd wrap the functionality
in a class so that the whole thing was transparent to the caller. So
instead of the example I gave:

# add a new user
users[3].append('daniel')

I'd write the class so the caller just needed to do:

users.add('daniel')

and the class would calculate which inner list to append it to.

I just thought I'd make that clear in case you thought I expected you to
manually keep track of which inner list each name should go into.

 

[Neil Cerutti]

Hello

I use a dictionary to keep a list of users connected to a web
site.

To avoid users from creating login names that start with digits
in order to be listed at the top, I'd like to sort the list
differently every minute so that it'll start with the next
letter, eg. display the list from A...Zdigits the first time,
then B...ZAdigits, etc.

Resorting is more work than is needed. Just choose a different
starting index each time you display the names, and set up your
lister to wrap-around to your arbitrary starting index.

 

[Gilles Ganault]

Resorting is more work than is needed. Just choose a different
starting index each time you display the names, and set up your
lister to wrap-around to your arbitrary starting index.

Thanks. In this case, it means that in each loop iteration, I must
search the list to find which item starts with the letter I'd like to
begin sorting, eg. "B". Does Python include a search method or do I
have to use a for loop to locate this starting item?

 

[Jon Clements]

Thanks. In this case, it means that in each loop iteration, I must
search the list to find which item starts with the letter I'd like to
begin sorting, eg. "B". Does Python include a search method or do I
have to use a for loop to locate this starting item?

How about a deque of lists... untested

from collections import deque; from itertools import groupby
deq = deque(list(items) for key, items in groupby(sorted(usernames),
lambda L: L[0].upper()))
Then everytime you use deq, rotate it?

hth

Jon.

 

[Gilles Ganault]

Sorry, the code I provided produce this output:

['1a', 'a', 'ac', 'av', 'b', 'c']
['a', 'ac', 'av', 'b', 'c', '1a']
['b', 'c', '1a', 'a', 'ac', 'av']
['c', '1a', 'a', 'ac', 'av', 'b']
['1a', 'a', 'ac', 'av', 'b', 'c']

which is actually what you are searching for. I just messed up with my
ipython shell history )

Thanks for the help. I'm a Python newbie, and have a difficult time
understanding what the [] + [] line does :-/

I'll simplify things by using a list instead of a dictionary:

============
connected = []
connected.append("0test")
connected.append("aa")
connected.append("bb")
connected.append("cc")

for start in '1abcd':
result = [name for name in connected if name[0] >= start] + [name
for name in connected if name[0] < start]
print result
============
C:\>test.py
['aa', 'bb', 'cc', '0test']
['aa', 'bb', 'cc', '0test']
['bb', 'cc', '0test', 'aa']
['cc', '0test', 'aa', 'bb']
['0test', 'aa', 'bb', 'cc']
============

Pretty close to what I need to do but..

1. Why is the first iteration done twice?

2. How can I have just one line, save the character that I used as
starting point, increment it, and save it into a file so it can be
read the next time this program runs? For instance, let's say we used
"b" to start looking for items, I'll save "c" in a file for the next
time.

Thank you.

 

[Jan Kaliszewski]

If you want to prohibit users from starting their login names with a
digit, prohibit them from creating a login name with a digit.

I understand that a real problem is to make all names -- regardless of
characters they are made of -- having "the equal rights" in terms of
visibility.

List, not dictionaries (they have nothing to do with the matter).

You can write a customer sort routine by using the key parameter to sort,
which will probably be messy.

It could be done e.g. in such a way:

# (for Python 2.x)
from collections import deque
import string

CHARS = string.ascii_lowercase + string.digits
def rotated_key(rotated_chars=deque(CHARS)):
rotated_chars.rotate(1)
tr_table = string.maketrans(CHARS, ''.join(rotated_chars))
def key(item):
return item.translate(tr_table)
return key

# generate some names
import random
users = [''.join(random.choice(CHARS) for i in xrange(3))
for j in xrange(50)]

for i in xrange(50):
users.sort(key=rotated_key())
print ','.join(users)
print

But it still doesn't guarantee real "equal rights in visibility" (holders
of names starting with rarely used characters are in better situation).

What I'd do is keep 27 lists of user names,
according to the first letter (26 letters from A to Z, plus one extra):

users = [ # keep separate lists for each starting letter
['aaron', 'avril', 'adam'],
['betty', 'bob'],
['craig', 'cathy'],
['danni', 'da5id', 'donna'],
# ... and so on
['zoe', 'zach'],
['4dam', '1-4m-t00-c001']
]

But here the second letter becomes important for "visibility" and users
still are not equal.

And all this mess in unnecessary, because there is one perfect and simple
solution -- see the Neil Cerutti's post.

Thanks. In this case, it means that in each loop iteration, I must
search the list to find which item starts with the letter I'd like to
begin sorting, eg. "B". Does Python include a search method or do I
have to use a for loop to locate this starting item?

There is e.g. `bisect' module -- you can search as well as insert with
its functions. But IMHO you shouldn't search for the next starting
*letter*, but for the next *name* in the list (basing on name that was
used recently).

If the list were immutable, no searching would be needed (indexes would
be sufficient), but in real life users can be added and deleted in the
meantime (so index of a particular name changes).

Regards,

*j

 

[Dave Angel]

Hello

I use a dictionary to keep a list of users connected to a web site.

To avoid users from creating login names that start with digits in
order to be listed at the top, I'd like to sort the list differently
every minute so that it'll start with the next letter, eg. display the
list from A...Zdigits the first time, then B...ZAdigits, etc.

That way, users have no incentive to create login names that start
with either a digit or letter A.

I see that dictionaries can be sorted using the... sort() method, but
is it possible to have Python start sorting from a different letter?

Thank you.

Seems to me the other solutions I've seen so far are more complex than
needed. I figure you either want an unordered list, in which case you
could use random.shuffle(), or you want a list that's sorted, but starts
somewhere in the middle, at an arbitrary place, goes to the end, and
wraps back to the beginning. So use random.randint() to choose an index
within the list, and concatenate two slices of the list, based on that
index in reverse order.

And don't bother generating it each minute, but simply generate it each
time you need it. I doubt if the cost of generating it is much
different than the cost of checking the time.

I guess there's a third possibility, that you don't want some of the G
names at the beginning, and some at the end. In that case, I'd generate
the random index as above, then increment it till the first character of
the item changes. Use that index as your split point.

If you like any of these, I could elaborate with some code. But each
approach is pretty straightforward.

DaveA

 

[Gilles Ganault]

Seems to me the other solutions I've seen so far are more complex than
needed. I figure you either want an unordered list, in which case you
could use random.shuffle(), or you want a list that's sorted, but starts
somewhere in the middle, at an arbitrary place, goes to the end, and
wraps back to the beginning. So use random.randint() to choose an index
within the list, and concatenate two slices of the list, based on that
index in reverse order.

Yes, this is exactly what I need: Start listing items from a given
index (actually, using a character since the list contains names) all
the way to the end of the list; If the character wasn't the very
first, go back to the first time and display the list until we get to
the current character.

Python is so feature-rich, I'm sure there's a much simpler way to do
this than this crappy code of mine:

=============
connected = []
connected.append("0dummy")
connected.append("aa")
connected.append("bb")
connected.append("cc")

index = 0
for item in connected:
#For testing purposes;
#Final code will read/increment character from file
if item[index] == "b":
break
else:
index = index + 1

#Print items between current character and end of list
tempindex = index
while(tempindex < len(connected)):
print connected[tempindex]
tempindex = tempindex + 1

#if current letter not first character,
#display beginning of list up to current character
if index != 0:
tempindex = 0
while tempindex < index:
print connected[tempindex]
tempindex = tempindex + 1
=============

Thank you for any help

 

[Arnaud Delobelle]

Seems to me the other solutions I've seen so far are more complex than
needed. I figure you either want an unordered list, in which case you
could use random.shuffle(), or you want a list that's sorted, but starts
somewhere in the middle, at an arbitrary place, goes to the end, and
wraps back to the beginning. So use random.randint() to choose an index
within the list, and concatenate two slices of the list, based on that
index in reverse order.

Yes, this is exactly what I need: Start listing items from a given
index (actually, using a character since the list contains names) all
the way to the end of the list; If the character wasn't the very
first, go back to the first time and display the list until we get to
the current character.

Python is so feature-rich, I'm sure there's a much simpler way to do
this than this crappy code of mine:

=============
connected = []
connected.append("0dummy")
connected.append("aa")
connected.append("bb")
connected.append("cc")

index = 0
for item in connected:
#For testing purposes;
#Final code will read/increment character from file
if item[index] == "b":
break
else:
index = index + 1

#Print items between current character and end of list
tempindex = index
while(tempindex < len(connected)):
print connected[tempindex]
tempindex = tempindex + 1

#if current letter not first character,
#display beginning of list up to current character
if index != 0:
tempindex = 0
while tempindex < index:
print connected[tempindex]
tempindex = tempindex + 1
=============

Thank you for any help

Here's a straightforward way to do it, taking advantage of negative
indices (no doubt there are many others):

connected = '0dummy aa bb cc'.split()
connected ['0dummy', 'aa', 'bb', 'cc']
startindex = random.randrange(len(connected))
startindex 2
for i in xrange(startindex - len(connected), startindex):

.... print connected
....
bb
cc
0dummy
aa
connected[-1] is the last element of connected
connected[-2] is the one before last
etc...

I'll let you figure out why the loop works as it does.

HTH

 

[Jan Kaliszewski]

PS.

There is e.g. `bisect' module -- you can search as well as insert with
its functions. But IMHO you shouldn't search for the next starting
*letter*, but for the next *name* in the list (basing on name that was
used recently).

Or simply choose the starting index randomly -- using
random.randrange(len(userlist)) or random.randint(0, len(userlist)-1) --
and use bisect.insort() for inserting to the list keeping it sorted (if
you need to list users sorted+rotated).

Regards,
*j

 

[Steven D'Aprano]

Resorting is more work than is needed. Just choose a different starting
index each time you display the names, and set up your lister to
wrap-around to your arbitrary starting index.

The original poster's requirement is to start at a new *letter* each
time, not whatever name happens to be at index N.

Unless you can predict what index to use for (say) names starting with
"B", then your scheme doesn't work. In order to find that index, you have
to do a linear search of the list after every sort, turning sorting into
O(N**2) instead of O(N*log N).

 

[Neil Cerutti]

The original poster's requirement is to start at a new *letter*
each time, not whatever name happens to be at index N.

Unless you can predict what index to use for (say) names
starting with "B", then your scheme doesn't work. In order to
find that index, you have to do a linear search of the list
after every sort, turning sorting into O(N**2) instead of
O(N*log N).

O(N*Log N) + O(N) == O(N**2)?

Besides, the idea was to avoid sorting altogether.

 

[Jean-Michel Pichavant]

Sorry, the code I provided produce this output:

['1a', 'a', 'ac', 'av', 'b', 'c']
['a', 'ac', 'av', 'b', 'c', '1a']
['b', 'c', '1a', 'a', 'ac', 'av']
['c', '1a', 'a', 'ac', 'av', 'b']
['1a', 'a', 'ac', 'av', 'b', 'c']

which is actually what you are searching for. I just messed up with my
ipython shell history )

Thanks for the help. I'm a Python newbie, and have a difficult time
understanding what the [] + [] line does :-/

I'll simplify things by using a list instead of a dictionary:

============
connected = []
connected.append("0test")
connected.append("aa")
connected.append("bb")
connected.append("cc")

for start in '1abcd':
result = [name for name in connected if name[0] >= start] + [name
for name in connected if name[0] < start]
print result
============
C:\>test.py
['aa', 'bb', 'cc', '0test']
['aa', 'bb', 'cc', '0test']
['bb', 'cc', '0test', 'aa']
['cc', '0test', 'aa', 'bb']
['0test', 'aa', 'bb', 'cc']
============

Pretty close to what I need to do but..

1. Why is the first iteration done twice?

2. How can I have just one line, save the character that I used as
starting point, increment it, and save it into a file so it can be
read the next time this program runs? For instance, let's say we used
"b" to start looking for items, I'll save "c" in a file for the next
time.

Thank you.

1/ [] + [] is using 2 python lists comprehension, Google it for details.
It is quite difficult to read until you become familiar with it. Once
you get it, you can write magical stuff )
Basically, list comrehension allows to map functions to list elements
and / or filter those elements.

So what I'm using is the filter feature of list comprehension:
[list of names for which the first char is greater that 'start'] + [list
of names for which the first char is less than 'start']

2/ Are you sure you want to do that ? looks like you are using a hammer
to smash a fly. As someone has suggested before, maybe you want to
pickup some starting index random.

connected = ['aa', 'bb', 'cc', '0test']

import random

def getNewOrder(myList):
index = random.randint(0,len(myList)-1)
print index
return myList[index:] + myList[:index] # using slicing instead of list comprehension (suggested by DaveA)

print getNewOrder(connected)

JM

 

[Steven D'Aprano]

Seems to me the other solutions I've seen so far are more complex than
needed. I figure you either want an unordered list, in which case you
could use random.shuffle(), or you want a list that's sorted, but starts
somewhere in the middle, at an arbitrary place, goes to the end, and
wraps back to the beginning. So use random.randint() to choose an index
within the list, and concatenate two slices of the list, based on that
index in reverse order.

And don't bother generating it each minute, but simply generate it each
time you need it.

According to the OP's stated requirements, he needs it every minute.

Personally, from a usability perspective, I think a refresh of a
(potentially huge) list of users every minute would be horrible. I think
the whole design needs to be rethought, but that's not my decision.

I doubt if the cost of generating it is much
different than the cost of checking the time.

Checking the time is quite fast -- it's a simple system call. Slicing and
copying a list containing potentially tens or hundreds of thousands of
names is anything but cheap!

from timeit import Timer
t1 = Timer('x = time.time()', 'import time')
t2 = Timer('y = x[:1000] + x[1000:]', 'x = [None]*100000')

t1.timeit(1000) 0.0025529861450195312
t2.timeit(1000)

3.0900199413299561

Slicing is more than 1000 times slower than checking the time. If you
think I'm being unfair, that the OP's application will never have 100,000
names, try it with 1000 names:

t3 = Timer('y = x[:1000] + x[1000:]', 'x = [None]*1000')
t3.timeit(1000)

0.041487932205200195

That's 20 times slower than checking the time.

That's the advantage of my suggestion: the only slicing done is the tiny
master list, which means copying 27 pointers. Easy and fast, and it
doesn't matter whether you have one user or one million, that operation
will take exactly the same amount of time. Your suggestion to keep all
the users in one giant list, and slice it repeatedly, scales terribly.

I guess there's a third possibility, that you don't want some of the G
names at the beginning, and some at the end. In that case, I'd generate
the random index as above, then increment it till the first character of
the item changes. Use that index as your split point.

Another solution that doesn't scale terrible well. (Although not as bad
as the previous one.)

And what's with the random index thing? Why are you throwing away
perfectly good information every time you want to shift letters? Your
solution is something like this:

You have a book opened at the start of Chapter 11, and you now want to
jump to the start of Chapter 12.

(1) Open the book at a random page.
(2) Is it the start of Chapter 12?
If yes, you're done.
If no, turn to the next page. If you reach the end of
the book, start again at the beginning.
(3) Go to step 2.

There are search techniques that start with a random index, but they
don't advance one position at a time! (E.g. binary search, or hunt-and-
bisect search, or similar.) But why search each time when you can keep an
index to the start of each chapter and jump straight there in constant
time?

 

[Jean-Michel Pichavant]

Sorry, the code I provided produce this output:

['1a', 'a', 'ac', 'av', 'b', 'c']
['a', 'ac', 'av', 'b', 'c', '1a']
['b', 'c', '1a', 'a', 'ac', 'av']
['c', '1a', 'a', 'ac', 'av', 'b']
['1a', 'a', 'ac', 'av', 'b', 'c']

which is actually what you are searching for. I just messed up with
my ipython shell history )

Thanks for the help. I'm a Python newbie, and have a difficult time
understanding what the [] + [] line does :-/

I'll simplify things by using a list instead of a dictionary:

============
connected = []
connected.append("0test")
connected.append("aa")
connected.append("bb")
connected.append("cc")

for start in '1abcd':
result = [name for name in connected if name[0] >= start] + [name
for name in connected if name[0] < start]
print result
============
C:\>test.py
['aa', 'bb', 'cc', '0test']
['aa', 'bb', 'cc', '0test']
['bb', 'cc', '0test', 'aa']
['cc', '0test', 'aa', 'bb']
['0test', 'aa', 'bb', 'cc']
============

Pretty close to what I need to do but..

1. Why is the first iteration done twice?

2. How can I have just one line, save the character that I used as
starting point, increment it, and save it into a file so it can be
read the next time this program runs? For instance, let's say we used
"b" to start looking for items, I'll save "c" in a file for the next
time.

Thank you.

1/ [] + [] is using 2 python lists comprehension, Google it for
details. It is quite difficult to read until you become familiar with
it. Once you get it, you can write magical stuff )
Basically, list comrehension allows to map functions to list elements
and / or filter those elements.

So what I'm using is the filter feature of list comprehension:
[list of names for which the first char is greater that 'start'] +
[list of names for which the first char is less than 'start']

2/ Are you sure you want to do that ? looks like you are using a
hammer to smash a fly. As someone has suggested before, maybe you want
to pickup some starting index random.

connected = ['aa', 'bb', 'cc', '0test']

import random

def getNewOrder(myList):
index = random.randint(0,len(myList)-1)
print index
return myList[index:] + myList[:index] # using slicing instead of
list comprehension (suggested by DaveA)

print getNewOrder(connected)

JM

Ok I realized that picking up a random index prevent from grouping names
starting with the same letter (to ease visual lookup).
Then go for the random char, and use char comparison (my first example).

JM