Velocity Reviews > Sort with extra variables

# Sort with extra variables

Thomas Dybdahl Ahle
Guest
Posts: n/a

 03-02-2007
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
Guest
Posts: n/a

 03-02-2007
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
Guest
Posts: n/a

 03-02-2007
Thomas Dybdahl Ahle <> writes:
> 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
Guest
Posts: n/a

 03-02-2007
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
Guest
Posts: n/a

 03-02-2007
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?

Thomas Dybdahl Ahle
Guest
Posts: n/a

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

> Thomas Dybdahl Ahle <> writes:
>> 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
Guest
Posts: n/a

 03-02-2007
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
Guest
Posts: n/a

 03-02-2007
On Mar 2, 5:11 pm, Thomas Dybdahl Ahle <lob...@gmail.com> wrote:
> 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
Guest
Posts: n/a

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

> On Mar 2, 5:11 pm, Thomas Dybdahl Ahle <lob...@gmail.com> wrote:
>> 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
Guest
Posts: n/a

 03-03-2007
On Mar 2, 5:51 pm, Thomas Dybdahl Ahle <lob...@gmail.com> wrote:
> 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(board, table, ply, move)

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

Regards,
Jordan