基本上我有一个玩家列表,我想把它们配对,这样每个玩家就可以和每个人玩一次。查找此数据的最快方法是什么?
发布于 2011-02-19 02:34:52
假设玩家不会在列表中出现两次,那么双for循环会非常快:
for (int i=0, i <= playerList.Count - 2, i++)
for (int j=i+1, j <= playerList.Count - 1, j++)
//add a new pairing of player i and j发布于 2011-02-19 02:31:22
这种锦标赛日程安排通常被称为round-robin。在维基百科中,也有一个可能的scheduling algorithm的例子。
发布于 2011-02-19 03:02:32
我将两个实现放在一起进行性能比较。非常简单的版本1比版本2慢大约50%,这并不是说没有更快的版本存在。
class Program
{
class Player
{
public string Name { get; set; }
public Player(string name)
{
Name = name;
}
}
class Match
{
public readonly Player Player1;
public readonly Player Player2;
public Match(Player player1, Player player2)
{
Player1 = player1;
Player2 = player2;
}
public override string ToString()
{
return string.Format("{0} vs. {1}", Player1.Name, Player2.Name);
}
}
static readonly List<Player> _players = new List<Player>()
{
new Player("John"),
new Player("Lisa"),
new Player("Matt"),
new Player("Dan"),
new Player("Steve"),
new Player("Sarah"),
new Player("Tim")
};
static void Main(string[] args)
{
const int count = 1000000;
{
var v1 = V1();
var sw = Stopwatch.StartNew();
for (int i = 0; i < count; i++)
{
v1 = V1();
}
Console.WriteLine(v1);
Console.WriteLine(sw.Elapsed);
}
{
var v2 = V2();
var sw = Stopwatch.StartNew();
for (int i = 0; i < count; i++)
{
v2 = V2();
}
Console.WriteLine(v2);
Console.WriteLine(sw.Elapsed);
}
Console.ReadLine();
}
static List<Match> V1()
{
var challengers = new List<Player>(_players);
var matches = new List<Match>();
foreach (var player in _players)
{
challengers.Remove(player);
foreach (var challenger in challengers)
{
matches.Add(new Match(player, challenger));
}
}
return matches;
}
static List<Match> V2()
{
var matches = new List<Match>();
for (int i = 0; i < _players.Count; i++)
{
for (int j = i + 1; j < _players.Count; j++)
{
matches.Add(new Match(_players[i], _players[j]));
}
}
return matches;
}
}https://stackoverflow.com/questions/5045137
复制相似问题