Чтение XML в словарь со временем замедляется

Question

my Приложение C # считывает XML-файл следующей структуры.В файле 150 Мб содержится около 250 000 слов.

<word>
     <name>kick</name>
     <id>485</id>
     <rels>12:4;4256:3;754:3;1452:2;86:2;125:2;</rels>
</word>

Я хочу прочитать XML-файл в словарь .Это некоторые ученики моего класса чтения.

private XmlReader Reader;

public string CurrentWordName;
public int CurrentWordId;
public Dictionary<KeyValuePair<int, int>, int> CurrentRelations;

Вот основной метод моего класса чтения.Он просто читает следующее слово из файла и получает name, id, а отношения сохраняются в Словаре.

CurrentWordId = -1;
CurrentWordName = "";
CurrentRelations = new Dictionary<KeyValuePair<int, int>, int>();

while(Reader.Read())
    if(Reader.NodeType == XmlNodeType.Element & Reader.Name == "word")
    {
        while (Reader.Read())
            if (Reader.NodeType == XmlNodeType.Element & Reader.Name == "name")
            {
                XElement Title = XElement.ReadFrom(Reader) as XElement;
                CurrentWordName = Title.Value;
                break;
            }
        while (Reader.Read())
            if (Reader.NodeType == XmlNodeType.Element & Reader.Name == "id")
            {
                XElement Identifier = XElement.ReadFrom(Reader) as XElement;
                CurrentWordId = Convert.ToInt32(Identifier.Value);
                break;
            }
        while(Reader.Read())
            if (Reader.NodeType == XmlNodeType.Element & Reader.Name == "rels")
            {
                XElement Text = XElement.ReadFrom(Reader) as XElement;
                string[] RelationStrings = Text.Value.Split(';');
                foreach (string RelationString in RelationStrings)
                {
                    string[] RelationsStringSplit = RelationString.Split(':');
                    if (RelationsStringSplit.Length == 2)
                        CurrentRelations.Add(new KeyValuePair<int,int>(CurrentWordId,Convert.ToInt32(RelationsStringSplit[0])), Convert.ToInt32(RelationsStringSplit[1]));
                }
                break;
            }
        break;
    }

if (CurrentRelations.Count < 1 || CurrentWordId == -1 || CurrentWordName == "")
     return false;
else
     return true;

Моя форма Windows имеет backgroundWorker для чтения всехслов.

private void bgReader_DoWork(object sender, DoWorkEventArgs e)
{
    ReadXML Reader = new ReadXML(tBOpenFile.Text);

    Words = new Dictionary<int, string>();
    Dictionary<KeyValuePair<int, int>, int> ReadedRelations = new Dictionary<KeyValuePair<int, int>, int>();

    // reading
    while(Reader.ReadNextWord())
    {
        Words.Add(Reader.CurrentWordId, Reader.CurrentWordName);

        foreach (KeyValuePair<KeyValuePair<int, int>, int> CurrentRelation in Reader.CurrentRelations)
        {
            ReadedRelations.Add(new KeyValuePair<int, int>(CurrentRelation.Key.Key, CurrentRelation.Key.Value), CurrentRelation.Value);
        }
    }

При отладке я заметил, что приложение запускается очень быстро и замедляется со временем .

• 7 секунд для первых 10000 слов
• 30 минут для первых 200 000 слов
• 35 минут для первых 220 000 слов

Я не могу объяснить это поведение!Но я уверен, что слова в XML-файле в среднем имеют одинаковый размер.Может быть, Add() -метод становится медленнее по длине словаря.

Как я могу ускорить мое приложение?

Answer 1

РЕДАКТИРОВАТЬ: Хорошо, теперь, когда я запустил код, я думаю, что это проблема:

foreach (KeyValuePair<KeyValuePair<int, int>, int> CurrentRelation in 
         Reader.CurrentRelations)
{
    ReadedRelations.Add(new KeyValuePair<int, int>(CurrentRelation.Key.Key, 
        CurrentRelation.Key.Value), CurrentRelation.Value);
}

Без этого цикла он работает намного быстрее ... что заставляет меня заподозрить, что тот факт, что вы читаете из XML, фактически является красной сельдью.

Я подозреваю, что проблема в том, что KeyValuePair<,> не переопределяет Equals и GetHashCode. Я считаю, что если вы создадите свой собственный тип значений RelationKey, содержащий два значения int и переопределяющие GetHashCode и Equals (и реализующие IEquatable<RelationKey>), это будет намного быстрее.

В качестве альтернативы, вы всегда можете использовать long для хранения двух int значений - что-то вроде хака, но это будет работать довольно хорошо. Я не могу проверить это сейчас, но я попробую, когда у меня будет больше времени.

Даже просто изменив ваш цикл на:

foreach (var relation in Reader.CurrentRelations)
{
    ReadedRelations.Add(relation.Key, relation.Value);
}

будет проще и немного эффективнее ...

РЕДАКТИРОВАТЬ: Вот пример для RelationKey структуры. Просто замените все вхождения KeyValuePair<int, int> на RelationKey и используйте свойства Source и Target вместо Key и Value:

public struct RelationKey : IEquatable<RelationKey>
{
    private readonly int source;
    private readonly int target;

    public int Source { get { return source; } }
    public int Target { get { return target; } }

    public RelationKey(int source, int target)
    {
        this.source = source;
        this.target = target;
    }

    public override bool Equals(object obj)
    {
        if (!(obj is RelationKey))
        {
            return false;
        }
        return Equals((RelationKey)obj);
    }

    public override int GetHashCode()
    {
        return source * 31 + target;
    }

    public bool Equals(RelationKey other)
    {
        return source == other.source && target == other.target;
    }
}