Adam Clarridge | 17 May 00:56

Dictionaries or Numpy?

Hi, I'm writing an AI for a board game called Blokus, and I believe
that the quality of the program is going to greatly depend on the
efficiency of the algorithm I use to generate legal moves and rate
them.

I know sort of how I'm going to do this legal move generation, and I
know it is going to require lots of accesses to an array of some kind
which will represent the game board.

I'm fairly new to Python, and I am not sure whether it would be faster
for me to use a Dictionary data type to represent the board
(advantages: indices can be strings or tuples, and the dictionary can
store different types of data as well, so programming would be easier)
or the Numpy array type (don't know much about this, but I have heard
Numpy is faster).

So is Numpy faster for simple array accesses? That would be valuable
and I'd deal with having an integer-indexed integer array if I had to.

Code might look something like this:

for playable_corner in all_playable_corners:
    for piece in all_available_pieces:
        for each_square in piece:
            # if square is not in a legal position, don't add to list
of legal moves

So that if statement would be accessing the board array many many
times. I guess my question is: Is there any way to test Dictionary
access time vs. Numpy array access time?
(Continue reading)

John Fouhy | 17 May 02:08

Re: Dictionaries or Numpy?

On 17/05/2008, Adam Clarridge <adam.clarridge <at> gmail.com> wrote:
>  I'm fairly new to Python, and I am not sure whether it would be faster
>  for me to use a Dictionary data type to represent the board
>  (advantages: indices can be strings or tuples, and the dictionary can
>  store different types of data as well, so programming would be easier)
>  or the Numpy array type (don't know much about this, but I have heard
>  Numpy is faster).

Hi Adam,

I believe a general rule of programming is: don't optimize until you
know you need to.  I would advise using dictionaries for simplicity.
If the program turns out slower than you would like, you can use
profiling tools to figure out where in the code it is spending most of
its time.  If this turns out to involve dictionary lookups, you could
then look at changing to Numpy (hint: you could use the timeit module
to benchmark dictionary access against Numpy arrays).  If your program
design is good, the change should be too hard.

http://en.wikipedia.org/wiki/Optimization_(computer_science)#When_to_optimize

--

-- 
John.
_______________________________________________
Tutor maillist  -  Tutor <at> python.org
http://mail.python.org/mailman/listinfo/tutor

Adam Clarridge | 17 May 18:12

Re: Dictionaries or Numpy?

On 5/16/08, John Fouhy <john <at> fouhy.net> wrote:

On 17/05/2008, Adam Clarridge <adam.clarridge <at> gmail.com> wrote:
>  I'm fairly new to Python, and I am not sure whether it would be faster
>  for me to use a Dictionary data type to represent the board
>  (advantages: indices can be strings or tuples, and the dictionary can
>  store different types of data as well, so programming would be easier)
>  or the Numpy array type (don't know much about this, but I have heard
>  Numpy is faster).


Hi Adam,

I believe a general rule of programming is: don't optimize until you
know you need to.  I would advise using dictionaries for simplicity.
If the program turns out slower than you would like, you can use
profiling tools to figure out where in the code it is spending most of
its time.  If this turns out to involve dictionary lookups, you could
then look at changing to Numpy (hint: you could use the timeit module
to benchmark dictionary access against Numpy arrays).  If your program
design is good, the change should be too hard.

http://en.wikipedia.org/wiki/Optimization_(computer_science)#When_to_optimize

--

John.


Thanks for the insight - I guess I was sort of overlooking that general principle, good to be reminded. The timeit module seems like exactly what I would want later on, too. Thanks again!

Adam


_______________________________________________
Tutor maillist  -  Tutor <at> python.org
http://mail.python.org/mailman/listinfo/tutor

Gmane