Just a guy with a love for tech

A faster way of combining and sorting large lists.

Adam L September 17, 2016

A few months ago I stumbled upon an issue whilst adding lists of names for staff members to Game Dev Manager.

The issue was that the game started to take a very long time initialising.

After a bit of code profiling we located two lines of code that were killing performance. List<string>.Contains() and List<string>.Sort()

The Contains() method was called several thousand times which was taking somewhere in the region of about 5-10 seconds per list.

And since we have three lists, one for male, female and surnames, the time taken to initialise the game became unbearable.

We were loading the names from mods into a List<string> object, then use the List.Contains() method to check if the name being added to the list was already present.

After the lists were combined we then used the List.Sort() method, again called three times, once for each list

<pre class="tab-convert:true tab-size:1 lang:c# decode:true" title="Bad Example">List<string> nameLists = GDMCore.Resources.JSON.Loader.GetResourcesByType<NameList>();
foreach (string uuid in nameLists)
{
  List<string> listToAppend;
  NameList nameList = JsonConvert.DeserializeObject<NameList>(GDMCore.Resources.JSON.Loader.GetResourceContent(uuid));
  nameList.Names.Sort();
  if (nameList.Type == Framework.Enumerations.NameType.First)
  {
    if (nameList.Sex == Enumerations.Sex.Female)
    {
      listToAppend = this._femaleNames;
    }
    else
    {
      listToAppend = this._maleNames;
    }
    
    nameList.Names.Sort();
    foreach (string nameEntry in nameList.Names)
    {
      // Don't add duplicate names.
      if (!listToAppend.Contains(nameEntry))
      {
        listToAppend.Add(nameEntry);
      }
    }
  }
  else
  {
    foreach (string nameEntry in nameList.Names)
    {
      // Don't add duplicate names.
      if (!this._lastNames.Contains(nameEntry))
      {
        this._lastNames.Add(nameEntry);
      }
    }
  }
}

this._femaleNames.Sort();
this._maleNames.Sort();
this._lastNames.Sort();

Big O ComplexityAfter a bit of thinking, I decided that the best solution for the problem would be to use a HashSet<string> in conjunction with a List. My reasoning was this:

HashSet is a collection that contains no duplicate elements, and whose elements are in no particular order and is designed to perform lookups in O(1) time.

O(1) means that, no matter how much data, it will execute in constant time. The amount of time to execute one operation (illustrated).

Whereas List<string>.Contains() is an O(n) operation. This means that for large enough input sizes the running time increases linearly with the size of the input.

By using the HashSet to check if a name had already been added, I could add it to the main list if it was not found, decreasing times dramatically.

However, I could still not avoid calling List<string>.Sort() for each list, however by changing to HashSets reduced initialisation time to just a few milliseconds instead of 30 seconds. A massive reduction, I’m sure you’ll agree.

<pre class="tab-convert:true tab-size:2 lang:c# decode:true" title="Better Example">Dictionary<string, ResourceDescriptor> nameLists = Game.Instance.ResourceManager.GetResourcesByType<NameList>();
HashSet<string> nameHash;

foreach (string uuid in nameLists.Keys)
{
  List<string> listToAppend;
  NameList nameList = Game.Instance.ResourceManager.CreateInstanceOfResource<NameList>(uuid);
  
  listToAppend = this._nameLists[nameList.Type][nameList.Sex];
  
  nameHash = new HashSet<string>(listToAppend);
  
  foreach (string nameEntry in nameList.Names)
  {
    // Don't add duplicate names.
    if (!nameHash.Contains(nameEntry))
    {
      listToAppend.Add(nameEntry);
      nameHash.Add(nameEntry);
    }
  }
  
  this._nameLists[nameList.Type][nameList.Sex] = listToAppend;
}

foreach (int typeAttribute in Enum.GetValues(typeof(NameType)))
{
  foreach (int sexAttribute in Enum.GetValues(typeof(Sex)))
  {
    this._nameLists[(NameType)typeAttribute][(Sex)sexAttribute].Sort();
    System.Diagnostics.Debug.WriteLine(
    "Loaded {0} {1} {2} names)",
    this._nameLists[(NameType)typeAttribute][(Sex)sexAttribute].Count(),
    (NameType)typeAttribute,
    (Sex)sexAttribute);
  }
}

Back to top