Best data structure for storing Employee objects?

Question

I want to create a GUI that allows a user to create new employee objects and access their respective attributes. So far my program only allows for one object's information to be printed at a time:

import sys
from PyQt4 import QtGui

class Employee:

  def __init__(self, id, salary):
    self.id = id
    self.salary = salary

  def info(self):
    return "Employee ID: {}\nFull name:{}\nSalary:{}".format(self.id, self.full_name, self.salary)

class Window(QtGui.QMainWindow, Employee):

  def __init__(self):
    super(Window, self).__init__()  #Returns the parent object or the QMainWindow object
    self.setGeometry(50, 50, 500, 300)
    self.setWindowTitle("Employee builder")

    extractAction = QtGui.QAction("&Add Employee", self)
    extractAction.triggered.connect(self.create_employee)

    mainMenu = self.menuBar()
    fileMenu = mainMenu.addMenu('&File')
    fileMenu.addAction(extractAction)

    self.home()

  def home(self):
    self.show()

  def create_employee(self):
    ID, ok = QtGui.QInputDialog.getInt(self, "integer input dualog", "Enter employees id number:")
    pay, ok = QtGui.QInputDialog.getInt(self, "integer input dualog", "Enter employees salary:")

    emp1 = Employee(ID, pay)
    QtGui.QMessageBox.information(None, "Employee information:", emp1.info)

def run():
  app = QtGui.QApplication(sys.argv)
  GUI = Window()
  sys.exit(app.exec_())

run()

The next logic step as I see it would be to call a method which stores each newly created employee object so that a user can access the objects information based on the objects ID. In Python, would it pay to create a more advanced data structure like a hash table to store the objects? Or should I just be using a dictionary or a list (is a dictionary a hash table)? I am only doing this to learn Python and PyQt4 GUI's so I do not expect to be saving mega bytes of employee information or anything like that.

Answer 1

A hash table is a great data structure if you need to look things up efficiently (amortized constant time) and conveniently by key.

And a Python dict uses a hash table, so it does exactly what you want out of the box. (Of course if you want to build your own hash table as a learning experience, it’s not that hard. But you’re unlikely to get performance as good as the built-in one, especially if you’re using the default CPython interpreter.)

---

Using a dict makes your code a lot simpler to write and read. If you make employees a list of Employee objects, to find one by ID you'd have to do this:

for employee in employees:
    if employee.id == searchid:
        do_stuff(employee)
        break

But if you make if a dict, each each employee value keyed by its employee.id, you can just do this:

employee = employees[searchid]

(Of course in real-life code, both versions need a bit more to handle the case where an ID isn't found.)

And it's also a lot more efficient. The loop is obviously visiting every employee (well, thanks to the break, we're only visiting half of them on average, but still all in the worst case), but the dict version is just hashing searchid and looking it up in a hash table. So, if you make your table 10000x as big, the list version takes 10000x as long, but the dict version is still effectively instantaneous.

---

However, if you want to do things like find all employees with id<=20, a hash table won’t help for that. Instead, you’d want a sorted collection that you can bisect in logarithmic time.

For static data, where you do all your inserts at the start and then only do queries after that, you can just use a list, sort(key=operator.attrgetter('id')) it, then use the bisect module for searching.

If you need to frequently add (or delete) entries throughout the lifetime of the system, you want a tree-like data structure—a red-black tree or other balanced binary search tree, or one of the b-tree variants, or a skip list, etc. Python doesn’t come with any of these, but there are nice implementations all over PyPI (or it might be worth building one yourself as an exercise).

There are also some clever hybrid structures that basically act like a rope/deque at small scales but like a b-tree or a wide skip-list at large scales, which can be even better. And these are also available on PyPI.

Answer 2

This sounds exactly like time for using a dictionary. Dictionaries in Python use hash tables and are very efficient for searching something with a specific key (ID in your case)