High Runtime для Dictionary.Add для большого количества элементов

Question

У меня есть C # -приложение, которое хранит данные из TextFile в объекте Dictionary. Объем хранимых данных может быть довольно большим, поэтому вставка записей занимает много времени. Со многими элементами в Словаре становится еще хуже из-за изменения размера внутреннего массива, в котором хранятся данные для Словаря. Поэтому я инициализировал Словарь с количеством добавляемых элементов, но это не влияет на скорость.

Вот моя функция:

private Dictionary<IdPair, Edge> AddEdgesToExistingNodes(HashSet<NodeConnection> connections)
{
  Dictionary<IdPair, Edge> resultSet = new Dictionary<IdPair, Edge>(connections.Count);

  foreach (NodeConnection con in connections)
  {
    ...
    resultSet.Add(nodeIdPair, newEdge);
  }

  return resultSet;
}

В моих тестах я вставляю ~ 300 тыс. Предметов. Я проверил время выполнения с помощью ANTS Performance Profiler и обнаружил, что среднее время для resultSet.Add (...) не изменяется, когда я инициализирую Словарь с необходимым размером. Это то же самое, что когда я инициализирую словарь новым Dictionary (); (в среднем около 0,256 мс для каждого добавления). Это определенно вызвано количеством данных в словаре (хотя я инициализировал его с нужным размером). Для первых 20 тыс. Элементов среднее время добавления составляет 0,03 мс для каждого элемента.

Есть идеи, как сделать надстройку быстрее?

Спасибо заранее, Frank

Вот мой IdPair-Struct:

public struct IdPair
{
  public int id1;
  public int id2;

  public IdPair(int oneId, int anotherId)
  {
    if (oneId > anotherId)
    {
      id1 = anotherId;
      id2 = oneId;
    }
    else if (anotherId > oneId)
    {
      id1 = oneId;
      id2 = anotherId;
    }
    else
      throw new ArgumentException("The two Ids of the IdPair can't have the same value.");
  }
}

Answer 1

Поскольку у вас есть структура, вы получаете реализацию Equals () и GetHashCode () по умолчанию. Как уже отмечали другие, это не очень эффективно, так как использует отражение, но я не думаю, что отражение - это проблема.

Я предполагаю, что ваши хэш-коды распределяются неравномерно по умолчанию GetHashCode (), что может произойти, например, если реализация по умолчанию возвращает простой XOR всех членов (в этом случае хэш (a, b) == хэш (б, а)). Я не могу найти документацию о том, как реализован ValueType.GetHashCode (), но попробуйте добавить

public override int GetHashCode() {
    return oneId << 16 | (anotherId & 0xffff);
}

что может быть лучше.

Answer 2

IdPair - это struct, и вы не изменили Equals или GetHashCode. Это означает, что будет использоваться реализация этих методов по умолчанию.

Для типов значений реализация по умолчанию Equals и GetHashCode использует отражение, что может привести к снижению производительности. Попробуйте предоставить собственную реализацию методов и посмотрите, поможет ли это.

Моя предложенная реализация, это может быть не совсем то, что вам нужно / нужно:

public struct IdPair : IEquatable<IdPair>
{
    // ...

    public override bool Equals(object obj)
    {
        if (obj is IdPair)
            return Equals((IdPair)obj);

        return false;
    }

    public bool Equals(IdPair other)
    {
        return id1.Equals(other.id1)
            && id2.Equals(other.id2);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            int hash = 269;
            hash = (hash * 19) + id1.GetHashCode();
            hash = (hash * 19) + id2.GetHashCode();
            return hash;
        }
    }
}