0

I am making a drawing program in python with pygame right now. The interface is supposed to be vimesque, allowing the user to control most things with key presses and entering commands. I want to allow live binding of the buttons; the user should be able to change which keycode corresponds to which function. In my current structure, all bindings are stored in a dictionary of functions to keycodes, 'bindingsDict.' Whenever the main loop receives a KEY_DOWN event, I execute: bindingDictkeyCode Where keyCode is stored as an integer. This works, but it seems to be taking a lot of time and I am having trouble thinking of ways I could optimize.
Does anyone know the big O run time of dict look ups? I assumed because it hashed it would run in ln(n) but there's a huge difference in performance between this solution and just writing a list of if statements in the mainloop (which does not allow for dynamic binding).

hedgehogrider
  • 1,168
  • 2
  • 14
  • 22
  • 1
    Why do you think it takes a lot of time? Did you profile? Don't optimize blindly. – kindall Sep 24 '12 at 00:51
  • 2
    http://wiki.python.org/moin/TimeComplexity O(1) ... so I doubt thats your problem – Joran Beasley Sep 24 '12 at 00:51
  • You're right. I started throwing down timers everywhere, seems like the problem is with my mapped functions. I had different versions of the function running on my two test cases. – hedgehogrider Sep 24 '12 at 01:06
  • @JoranBeasley Link says that the average case scenario is O(1), amortized worst case is O(n). I thought big O notation was always the worst case.... O well... – hedgehogrider Sep 24 '12 at 01:08
  • average case is O(1) ... not sure it may be classed O(n) from worst case... – Joran Beasley Sep 24 '12 at 01:09
  • Incase you are using manual timers, here's an intro to profiling: http://stackoverflow.com/questions/582336/how-can-you-profile-a-python-script/582337#582337 – ninMonkey Sep 24 '12 at 01:37

1 Answers1

0

It is rather unlikely that dictionary search for response to a user event would cause any noticeable delay on the program. There is something going wrong in your code.

Btw, dict and set search in Python is O(log(1)) - but for 105 keys, or even, if you count modifiers applied, about 1000 different keybindngs could be searched in linearly (that is, if the search was O(N) ) without a noticeable delay, even on a 5 year old (desktop) CPU.

So, just post some of your code if you want a solution for your problem. (reading the comments I've noticed you found something else that seems to be responsible already)

jsbueno
  • 99,910
  • 10
  • 151
  • 209