.NET / C#

Linq: round-robin ordering based on segments

Avatar of author Kees C. Bakker To profile Kees C. Bakker Written by Kees C. Bakker, written on , 3 minute read.

Linq is a wonderful way to work with lists in C#. This article focuses on how you can create a round-robin ordering for segments of your list. It will distribute items of each segment evenly over the list.

A round robin is an arrangement of choosing all elements in a group equally in some rational order (...) A simple way to think of round robin is that it is about "taking turns." Used as an adjective, round robin becomes "round-robin.

Source: definition by What Is

The problem

Let's say we have a list of download URLs and we need to create a program that downloads a file from each URL. The list might look a little bit like this:

var urls = new string[] {
  "https://a.com?download=1.mp3",     "https://a.com?download=2.mp3", 
  "https://a.com?download=3.mp3",     "https://a.com?download=4.mp3", 
  "https://b.nl?download=alpha.mp3",  "https://b.nl?download=beta.mp3", 
  "https://b.nl?download=gamma.mp3",  "https://b.nl?download=delta.mp3", 
  "https://c.es?download=i.mp3",      "https://c.es?download=ii.mp3", 
  "https://c.es?download=iii.mp3",    "https://c.es?download=iv.mp3"
};

Question: How can we process this list in such a way that we put the least pressure on the hosts?
Answer: Order the list in such a way that the program will download: file 1 from a.com first, next file 1 from b.nl, next file 1 from c.es before continuing with file 2 form a.com until all the files are downloaded.

But how?

The basic idea is as follows:

  1. Segment the list into groups (based on the host name)
  2. Join all the items back together and remembering their index in the group list (index) and the index of the group (groupIndex)
  3. Sort the items by index, groupIndex

Show me some code!

Let's put the idea into code:

var x = urls
			
	//convert the urls to uri's
	.Select(u => new Uri(u))
			
	//create groups of unique hosts
	.GroupBy(u => u.Host)
			
	//select them back together into a single list
	.SelectMany((group, groupIndex) => group.Select((item, index) => new { Index = index, GroupIndex = groupIndex, Value = item }))
			
	//order by the group item index
	.OrderBy(u => u.Index)
			
	//order by the group index
	.ThenBy(u => u.GroupIndex)
			
	//show position (or one could select u.Value.ToString() for just the URL)
	.Select((u, position) => new { Position = position, Index = u.Index, GroupIndex = u.GroupIndex, Value = u.Value });
		
//write it to the console		
x.ToList().ForEach(u => Console.WriteLine(u));

The Select and SelectMany methods provide indexes that we leveraged to do the actual ordering. The console will show the following feedback:

{ Position = 0, Index = 0, GroupIndex = 0, Value = https://a.com/?download=1.mp3 }
{ Position = 1, Index = 0, GroupIndex = 1, Value = https://b.nl/?download=alpha.mp3 }
{ Position = 2, Index = 0, GroupIndex = 2, Value = https://c.es/?download=i.mp3 }
{ Position = 3, Index = 1, GroupIndex = 0, Value = https://a.com/?download=2.mp3 }
{ Position = 4, Index = 1, GroupIndex = 1, Value = https://b.nl/?download=beta.mp3 }
{ Position = 5, Index = 1, GroupIndex = 2, Value = https://c.es/?download=ii.mp3 }
{ Position = 6, Index = 2, GroupIndex = 0, Value = https://a.com/?download=3.mp3 }
{ Position = 7, Index = 2, GroupIndex = 1, Value = https://b.nl/?download=gamma.mp3 }
{ Position = 8, Index = 2, GroupIndex = 2, Value = https://c.es/?download=iii.mp3 }
{ Position = 9, Index = 3, GroupIndex = 0, Value = https://a.com/?download=4.mp3 }
{ Position = 10, Index = 3, GroupIndex = 1, Value = https://b.nl/?download=delta.mp3 }
{ Position = 11, Index = 3, GroupIndex = 2, Value = https://c.es/?download=iv.mp3 }

Source: When the code runs .Net Fiddle

Conclusion

A round-robin ordering based on segments is easy to make in C# Linq. Use GroupBy to create the segments, use SelectMany to create a simple list with indexes and use OrderBy and ThenOrderBy to sort the list on the index and groupIndex.

expand_less