Eric Mahurin
6/13/2008 2:36:00 PM
[Note: parts of this message were removed to make it a legal post.]
On 6/12/08, Matthew Moss <matthew.moss@gmail.com> wrote:
> Solution Time Score
> Andrea Fazzi 0.159 438
> Dustin Barker 0.020 589
> Eric Ivancich 4.671 311
> Steven Hahn -DNF-
> Eric Mahurin 0.211 311
> Matthew Moss 0.022 589
> Thomas ML 0.114 311
Did anybody try to analyze the complexity of the final solution from Thomas?
The problem with analyzing his solution is this line:
break unless weight1 * (names.size / 2).floor < maxweight
This causes some dependency on the data for run-time. It seems like this
line should only be needed for improving runtime, but commenting it out
gives non-optimal results. Don't get it. If you ignore this line, the
analysis is easier. There are O(n**2) pairs and each recursive call
decrements n by 2. When you get to a single pair, it is O(1). So,
O(n**2*(n-2)**2*(n-4)**2*...*2**2*1) or O(n!**2). It is probably more, but
most of this is hidden in the C code (for these size inputs, we can assume
every C method call is O(1)).
My solution is easy to analyze because it doesn't have any data dependent
variation. It should need to fill a O(2**n) memoization cache which takes
O(n) for each entry - so O(n*2**n).
From the random runs I've done, the ThomML algorithm doesn't look like
O(n!**2) at all. The randomized complexity looks similar to my O(n*2**n)
algorithm based on random input experiments.
I was wondering if a worst case scenario could make his algorithm behave
more like O(n!**2). I tried two extreme scenarios: a) love-hate: the more
one player loves another, the more the second player hates the first, b)
popularity: each player has a popularity ranking and every player will
prefer in the popularity order.
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!).
My algorithm doesn't have these extreme variations. For all cases, 24
players: 3.8s, 26 players: 10s, 28 players: 30s.
The script I used to generate input for these cases in below. The first arg
is the # players. Here's what you can use for the second arg:
nothing/default/-2: the popularity case, -1: love-hate case, 0: random w/o
seeding, >0: random w/ seeding.
Eric
#!/usr/bin/env ruby
NAMES = %w(Adam Anna Bob Betty Chuck David Daria Evan Ellen Fred Faye
Greg Gail Hank Helen Irene John Janet Laura Matt Maria Nadine Oleg
Olivia Peter Pamela Rick Rosa Steve Susan Theo Tracy Vicki Walter)
def sample(n, seed)
srand(seed) if seed>0
names = NAMES.clone
i = 1
while names.size<n
i += 1
NAMES.each { |name| names << "#{name}#{i}" }
end
names = names[0, n].sort!
prefs = Hash.new { |h,k| h[k] = [] }
names.each { |name1|
i = 0
names2 = (seed>=0) ? names.sort_by { rand } : names
names2.each { |name2|
next if name2==name1
next if prefs[name1].include?(name2)
while prefs[name1][i]
i += 1
end
prefs[name1][i] = name2
if seed==-1
!prefs[name2][names.size-2-i] or raise("#{name2} #{i}
#{prefs.inspect}")
prefs[name2][names.size-2-i] = name1
end
}
}
names.each { |name|
puts("#{name}: #{prefs[name].join(' ')}")
}
end
sample(Integer(ARGV[0] || 10), Integer(ARGV[1]||-2))