Sort with extra variables

[Thomas Dybdahl Ahle]

I have a sort function in a python chess program.
Currently it looks like this:

def sortMoves (board, table, ply, moves):
f = lambda move: getMoveValue (board, table, ply, move)
moves.sort(key= f, reverse=True)
return moves

However I'd really like not to use the lambda, as it slows down the code.

I've thought about saving the extra variables in the global space, but it
really feals ugly.

Do you have any ideas how I can sort these moves the fastest?

[Diez B. Roggisch]

Re: Sort with extra variables

Thomas Dybdahl Ahle schrieb:

I have a sort function in a python chess program.
Currently it looks like this:
>
def sortMoves (board, table, ply, moves):
f = lambda move: getMoveValue (board, table, ply, move)
moves.sort(key= f, reverse=True)
return moves
>
However I'd really like not to use the lambda, as it slows down the code.
>
I've thought about saving the extra variables in the global space, but it
really feals ugly.
>
Do you have any ideas how I can sort these moves the fastest?

First of all, in your case it is somewhat strange to use

f = lambda ...

because then you could as well use

def f(move):
....

But that is just a general remark. Regarding the question: I don't see
how that could possibly become faster without much more insight into
what you are doing in getMoveValue. As it seems, it is dependend of a
lot of factors that change often, so caching it isn't a real option. And
I hope you are aware that the key-method is invoked only _once_ per
list-item!

Thus it is pretty efficient.

Diez

[Paul Rubin]

Re: Sort with extra variables

Thomas Dybdahl Ahle <lobais@gmail.c omwrites:

Do you have any ideas how I can sort these moves the fastest?

One idea: if you're using alpha-beta pruning, maybe you can use
something like heapq instead of sorting, since a lot of the time you
only have to look at the first few moves (ordered best-first).

[Bjoern Schliessmann]

Re: Sort with extra variables

Thomas Dybdahl Ahle wrote:

However I'd really like not to use the lambda, as it slows down
the code.

Did you check how much the slowdown is?

Regards,


Björn

--
BOFH excuse #65:

system needs to be rebooted

[Thomas Dybdahl Ahle]

Re: Sort with extra variables

Den Fri, 02 Mar 2007 21:13:02 +0100 skrev Bjoern Schliessmann:

Thomas Dybdahl Ahle wrote:
>

>However I'd really like not to use the lambda, as it slows down the
>code.

>
Did you check how much the slowdown is?

Yes, the lambda adds 50%

[Thomas Dybdahl Ahle]

Re: Sort with extra variables

Den Fri, 02 Mar 2007 11:44:27 -0800 skrev Paul Rubin:

Thomas Dybdahl Ahle <lobais@gmail.c omwrites:

>Do you have any ideas how I can sort these moves the fastest?

>
One idea: if you're using alpha-beta pruning, maybe you can use
something like heapq instead of sorting, since a lot of the time you
only have to look at the first few moves (ordered best-first).

Do you mean that I add my moves something like this?

from heapq import heappush, heappop
heap = []
for move in genAll():
heappush(heap, (-getMoveValue (board, table, ply, move), move))

And then use heappop(heap) in the alphabeta loop?
I don't know much of heap queues, but it actually looks very smart.

[Thomas Dybdahl Ahle]

Re: Sort with extra variables

Den Fri, 02 Mar 2007 20:33:45 +0100 skrev Diez B. Roggisch:

Thomas Dybdahl Ahle schrieb:

>I have a sort function in a python chess program. Currently it looks
>like this:
>>
>def sortMoves (board, table, ply, moves):
> f = lambda move: getMoveValue (board, table, ply, move)
> moves.sort(key= f, reverse=True)
> return moves
>>
>However I'd really like not to use the lambda, as it slows down the
>code.
>>
>I've thought about saving the extra variables in the global space, but
>it really feals ugly.
>>
>Do you have any ideas how I can sort these moves the fastest?

>
First of all, in your case it is somewhat strange to use
f = lambda ...
because then you could as well use
def f(move):
....

Wouldn't that be just as slow?

But that is just a general remark. Regarding the question: I don't see
how that could possibly become faster without much more insight into
what you are doing in getMoveValue. As it seems, it is dependend of a
lot of factors that change often, so caching it isn't a real option. And
I hope you are aware that the key-method is invoked only _once_ per
list-item!

Yeah, key is a nice thing. My only problem is that I need these other
objects to generate the value, and I don't want to create a new function
each time..

In my profiling the functions with the lambda line says 860 cumtime and
getMoveValue says 580.

[MonkeeSage]

Re: Sort with extra variables

On Mar 2, 5:11 pm, Thomas Dybdahl Ahle <lob...@gmail.c omwrote:

Wouldn't that be just as slow?

Well, I'm not sure about speed, but with the lambda you're creating a
new callable for f every time you call sortMoves. Intuitively, that
seems like it would be more of a hit than just doing a lookup for a
predefined function. Mabye not though...you could time it and see.

Regards,
Jordan

[Thomas Dybdahl Ahle]

Re: Sort with extra variables

Den Fri, 02 Mar 2007 15:20:33 -0800 skrev MonkeeSage:

On Mar 2, 5:11 pm, Thomas Dybdahl Ahle <lob...@gmail.c omwrote:

>Wouldn't that be just as slow?

>
Well, I'm not sure about speed, but with the lambda you're creating a
new callable for f every time you call sortMoves. Intuitively, that
seems like it would be more of a hit than just doing a lookup for a
predefined function. Mabye not though...you could time it and see.

I guess the thing is that I'd have to create a new callable no matter
how, as it is the only way to bring the extra variables into the getValue
function when called by sort.

[MonkeeSage]

Re: Sort with extra variables

On Mar 2, 5:51 pm, Thomas Dybdahl Ahle <lob...@gmail.c omwrote:

I guess the thing is that I'd have to create a new callable no matter
how, as it is the only way to bring the extra variables into the getValue
function when called by sort.

Yes, but you don't have to create it every time you call sortMoves...

def sortKey(move):
return getMoveValue(bo ard, table, ply, move)

def sortMoves(board , table, ply, moves):
moves.sort(key= sortKey, reverse=True)
return moves

Regards,
Jordan

[Paul Rubin]

Re: Sort with extra variables

Thomas Dybdahl Ahle <lobais@gmail.c omwrites:

Do you mean that I add my moves something like this?
>
from heapq import heappush, heappop
heap = []
for move in genAll():
heappush(heap, (-getMoveValue (board, table, ply, move), move))
>
And then use heappop(heap) in the alphabeta loop?

Yes, something like that. If you want to get, say, the five smallest
values in a list, heapq lets you do that without having to sort the
whole list.

[Thomas Dybdahl Ahle]

Re: Sort with extra variables

Den Fri, 02 Mar 2007 16:27:47 -0800 skrev MonkeeSage:

On Mar 2, 5:51 pm, Thomas Dybdahl Ahle <lob...@gmail.c omwrote:

>I guess the thing is that I'd have to create a new callable no matter
>how, as it is the only way to bring the extra variables into the
>getValue function when called by sort.

>
Yes, but you don't have to create it every time you call sortMoves...
>
def sortKey(move):
return getMoveValue(bo ard, table, ply, move)
>
def sortMoves(board , table, ply, moves):
moves.sort(key= sortKey, reverse=True) return moves

Well, you'd have to define the function inside the sortMoves function, as
it is where the variables exists.

def sortMoves(board , table, ply, moves):
def sortKey(move):
return getMoveValue(bo ard, table, ply, move)
moves.sort(key= sortKey, reverse=True) return moves

Wouldn't that make it create the callable at each call?

[Thomas Dybdahl Ahle]

Re: Sort with extra variables

Den Fri, 02 Mar 2007 16:46:05 -0800 skrev Paul Rubin:

Thomas Dybdahl Ahle <lobais@gmail.c omwrites:

>Do you mean that I add my moves something like this?
>>
>from heapq import heappush, heappop
>heap = []
>for move in genAll():
> heappush(heap, (-getMoveValue (board, table, ply, move), move))
>>
>And then use heappop(heap) in the alphabeta loop?

>
Yes, something like that. If you want to get, say, the five smallest
values in a list, heapq lets you do that without having to sort the
whole list.

Yeah, I use this now. The only think I don't really like, is the need of
creating a ton of tupples, but it doesn't show me too much it seams.

[MonkeeSage]

Re: Sort with extra variables

On Mar 2, 7:34 pm, Thomas Dybdahl Ahle <lob...@gmail.c omwrote:

Well, you'd have to define the function inside the sortMoves function, as
it is where the variables exists.

Oh, sorry, I wasn't thinking there!

Regards,
Jordan

[Alex Martelli]

Re: Sort with extra variables

Thomas Dybdahl Ahle <lobais@gmail.c omwrote:

I have a sort function in a python chess program.
Currently it looks like this:
>
def sortMoves (board, table, ply, moves):
f = lambda move: getMoveValue (board, table, ply, move)
moves.sort(key= f, reverse=True)
return moves
>
However I'd really like not to use the lambda, as it slows down the code.
>
I've thought about saving the extra variables in the global space, but it
really feals ugly.
>
Do you have any ideas how I can sort these moves the fastest?

Maybe

moves.sort(key= functool.partia l(board, table, ply), reverse=True)

might be a bit faster? Not sure, but maybe worth trying.

If not, a bit faster (nothing major) might be

def f(move, board=board, table=table, ply=ply):
return getMoveValue(bo ard, table, ply, move)

the small advantage here would be to use the lexically scoped variable
lookup just once (at nested-def time) with the three names being then
looked up as locals in the len(moves) call to f...


Alex