From: ThoML <micathom@...>
Date: 2008-06-14T02:19:27+09:00
Subject: Re: Preferable Pairs (#165)

Hi,

> I found some interesting results with these extremes.  The love-hate case
> allowed the ThomML algorithm to go up to hundreds of players (400 players in
> 30seconds).  Probably O(n**2) or O(n**3) for this scenario.  The popularity
> case was quite bad though - 14 players: 19s,  12 players: 1.8s, 10 players:
> 0.2s.  This looks to be O(n!).

Thanks for the script for generating specific types of preferences.
The performance depends on the adequacy of the underlying greedy
algorithm for the data set. In the "love-hate" case, a simple greedy
algorithm already returns optimal pairings. In the "popularity" case,
such an approach doesn't work well.

But the solution submitted is really simple and doesn't use too much
memory. I experimented with memoizing subresults but came to the
conclusion that it isn't worth the trouble for small random data sets
because the cached data is hardly ever used. I assume memoization
could help to avoid those variations you pointed out.

Regards,
Thomas.