Is a python dictionary the best data structure to solve this problem?

Question

Hi

I have a number of processes running which are controlled by remote clients. A tcp server controls access to these processes, only one client per process. The processes are given an id number in the range of 0 -> n-1. Were 'n' is the number of processes. I use a dictionary to map this id to the client sockets file descriptor. On startup I populate the dictionary with the ids as keys and socket fd of 'None' for the values, i.e no clients and all pocesses are available

When a client connects, I map the id to the sockets fd. When a client disconnects I set the value for this id to None, i.e. process is available. So everytime a client connects I have to check each entry in the dictionary for a process which has a socket fd entry of None. If there are then the client is allowed to connect.

This solution does not seem very elegant, are there other data structures which would be more suitable for solving this?

Thanks

Answer 1

Why not just use a list? Python lists are arrays behind the scenes, with O(1) access.

sockets = n * [None]

Then once you learn the socket for a given process id:

sockets[id] = socket;

Answer 2

You can keep that idea but add a list or whatever to hold unused socked fd, so that you have no to iterate the dictionary to find the first usable "None". When you pick the first (or last) free process from the "not busy" list, you remove from it. E.g.

# d is the dictionary
# notbusy is a list
d[ notbusy.pop() ] = ... # init the socket

of course you have to check that notbusy is not empty (or try-catch if you prefer); if it is, there are no free usable "slot" and is not possible to connect. When an used slot is "freed", you set to None and add its key to the list notbusy.

Answer 3

"Premature optimization is the root of all evil," as C.A.R. Hoare said.

Rather than ask if this implementation is efficient, perhaps you should ask if this implementation is efficient enough. If it meets your performance requirements and the code is easy to understand, perhaps you should leave it be.

If your code is not giving you the performance you need, I'd suggest Shin's answer. It seems to be the simplest way of getting additional performance.