найти и найти индекс болезненно медленный для списка <Object>почему? - PullRequest
1 голос
/ 17 февраля 2012

Я работаю в проекте, который интенсивно использует List, и я пытаюсь найти объект по имени (которое является членом объекта).

Мой код работал без поиска, используя одинСледующий цикл (функция find1), но я обнаружил, что это можно сделать с помощью встроенной команды find, и код работает.Тем не менее, это чувствуется немного медленно.Итак, я сделал проект для проверки скорости:

У меня есть следующий код

    public List<MyObject> varbig = new List<MyObject>();
    public Dictionary<string,string> myDictionary=new Dictionary<string, string>();
    public Form1() {
        InitializeComponent();
    }

    private void button1_Click(object sender, EventArgs e) {
        myDictionary.Clear();
        varbig.Clear();

        for (int i = 0; i < 5000; i++) {
            varbig.Add(new MyObject("name" + i.ToString(),"value"+i.ToString()));
            myDictionary.Add("name" + i.ToString(), i.ToString());
        }
        // first test
        var start1 = Environment.TickCount;
        for (int i = 0; i < 3000; i++) {
            var ss=find1("name499");
        }
        var end1 = Environment.TickCount;
        Console.WriteLine("time  1 :" + (end1 - start1));
        // second test
        var start2 = Environment.TickCount;
        for (int i = 0; i < 3000; i++) {
            var ss=find2("name499");
        }
        var end2 = Environment.TickCount;
        Console.WriteLine("time  2 :" + (end2 - start2));
        // third test
        var start3 = Environment.TickCount;
        for (int i = 0; i < 3000; i++) {
            var ss = find3("name499");
        }
        var end3 = Environment.TickCount;
        Console.WriteLine("time  3 :" + (end3 - start3));

        // first test b
        var start1b = Environment.TickCount;
        for (int i = 0; i < 3000; i++) {
            var ss=find1("name4999");
        }
        var end1b = Environment.TickCount;
        Console.WriteLine("timeb 1 :" + (end1b - start1b));
        // second test
        var start2b = Environment.TickCount;
        for (int i = 0; i < 3000; i++) {
            var ss=find2("name4999");
        }
        var end2b = Environment.TickCount;
        Console.WriteLine("timeb 2 :" + (end2b - start2b));
        // third test
        var start3b = Environment.TickCount;
        for (int i = 0; i < 3000; i++) {
            var ss = find3("name4999");
        }
        var end3b = Environment.TickCount;
        Console.WriteLine("timeb 3 :" + (end3b - start3b));

    }

    public int find1(string name) {
        for (int i = 0; i < varbig.Count; i++) {
            if(varbig[i].Name == name) {
                return i;
            }
        }
        return -1;
    }

    public int find2(string name) {
        int idx = varbig.FindIndex(tmpvar => Name == name);
        return idx;
    }
    public int find3(string name) {
        var ss=myDictionary[name];
        return int.Parse(ss);
    }
}

И я использую следующий объект

public class MyObject {
    private string _name = "";
    private string _value = "";
    public MyObject() {}

    public MyObject(string name, string value) {
        _name = name;
        _value = value;
    }

    public string Name {
        get { return _name; }
        set { _name = value; }
    }

    public string Value {
        get { return _value; }
        set { _value = value; }
    }
}

В основном это сделатьследующее: я создаю массив из 5000 элементов.

время 1 = поиск 499-го объекта (индекса) с помощью простого for-next.

время 2 = поиск 499-го объекта с использованием встроенногоФункция find из List

time 3 = выполняет поиск 499-го элемента с использованием словаря.

Timeb 1, timeb 2 и timeb 3 делают то же самое, но пытаются найти 4999-й элемент вместо499-й элемент.

Я бегал пару раз:

  • время 1: 141
  • время 2: 1248
  • время 3: 0
  • timeb 1: 811
  • timeb 2: 1170
  • timeb 3: 0

  • время 1: 109

  • время 2: 1170
  • время 3: 0
  • timeb 1: 796
  • timeb 2: 1170
  • timeb 3: 0

(маленький, то быстрый)

И, для моего суНа самом деле, встроенная функция findindex абсурдно медленна (в некоторых случаях, почти в 10 раз медленнее).Кроме того, словарный подход почти мгновенно.

Мой вопрос: почему ?.это потому что предикат?

Ответы [ 4 ]

2 голосов
/ 17 февраля 2012

Проблема в этой строке:

int idx = varbig.FindIndex(tmpvar => Name == name);

Name == name неверно, вместо этого следует написать tmpvar.Name == name.

В вашем коде вы сравниваете аргумент name со свойством Name вашей формы; они, очевидно, отличаются, и поэтому метод всегда проверяет весь список, а не останавливается, когда найдено искомое значение. Фактически, как вы можете видеть, просматривая цифры, время, потраченное на find2(), в основном всегда равно.

Что касается словаря, он, очевидно, быстрее других методов, поскольку словари представляют собой структуру памяти, специально созданную для обеспечения быстрого доступа по ключу.

На самом деле они приближаются к O(1) сложности времени, при циклической обработке списка сложность времени равна O(n).

1 голос
/ 17 февраля 2012

В вашем коде есть ошибка - метод find2 использует для сравнения Form.Name вместо имен объектов коллекции. Это должно выглядеть так:

public int find2(string name) {
    return varbig.FindIndex((obj) => obj.Name == name);
}

Результаты без использования Form.Name более последовательны:

time  1 :54
time  2 :50
time  3 :0
timeb  1 :438
timeb  2 :506
timeb  3 :0
1 голос
/ 17 февраля 2012
  • Find1 использует простой метод for (i = 0 to count)
  • Find2 использует встроенный метод Find (который в точности является find1 выше), за исключением того, что вы передали предикат вместе сэто, что, я считаю, замедляет его.
  • Find3 с использованием словаря, я бы предположил, что это самый быстрый без каких-либо таймеров, потому что словарь использует хеш-таблицы под обложками, который имеет поиск 0 (1)время)
0 голосов
/ 13 февраля 2019

Вам не нужно ставить цикл for для поиска в find2 ...

Просто позвоните find2 напрямую, тогда результат будет 0.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...