Точка компромисса между словарем (хэш-таблицей) и списком находок

Question

Короткий вопрос: Сколько элементов может быть в списке, чтобы сделать линейный поиск, такой как List O (n), быстрее, чем Dictionary, который является O (1)?

Кажется, я помню, что в колледже (и в старшей школе) при сравнении методов поиска (бинарный и линейный) всегда была точка, где линейный был быстрее. это было O (n) против O (log)

Я не могу нарисовать график здесь. но должны быть некоторые накладные расходы для постоянной производительности. Так что вопрос в том, есть ли у меня 10 элементов, List.Find имеет больше смысла, чем

if (Dictionary.Contains(x))
    value = Directiory[x]

Или Hashtable, где значение = Hashtable [x] не потерпит неудачу, но потребует бокса

Answer 1

Я задал себе тот же вопрос и провел тест, чтобы выяснить это. Я обнаружил, что скорость словаря уже превосходит список при поиске около 3-4 элементов.

Мне показалось, что это далеко не все, исходя из накладных расходов на словарь, поэтому я проверил, нашел ли кто-либо другой такой же результат, и, похоже, это результаты, найденные другими. http://dotnetperls.com/dictionary-time

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

Answer 2

Так что после выполнения моего собственного теста, похоже, Hash-Dictionary всегда побеждает. Это объект Dictionary с HashCode, int32, в качестве ключа

10 items    500,000 itterations             
Test Name                                           First   Last    Not Found   Average 
FindInList                                          104.26  255.29  254.63      204.73
FindInArray                                         51.28   192.23  182.91      142.14
FindInHashDict                                      56.3    54.38   51.16       53.95
FindInDict                                          105.75  101.38  52.02       86.38

100 items   500,000 itterations             
Test Name                                           First   Last    Not Found   Average 
FindInList                                          102.83  1873.45 1820.85     1265.71
FindInArray                                         56.21   1313.61 1310.65     893.49
FindInHashDict                                      91.01   53.31   60.46       68.26
FindInDict                                          119.01  101.65  100.11      106.92

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

    private SearchResult FindInDict()
    {
        SearchResult result = new SearchResult();
        result.SeachType = "FindInDict";
        result.itterations = 1;

        Stopwatch timer = new Stopwatch();

        timer.Start();
        if (dictStrBoundryTask.ContainsKey(NameOfFirst))
        {
            TaskBase t = dictStrBoundryTask[NameOfFirst];
        }

        timer.Stop();

        result.firstItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        if (dictStrBoundryTask.ContainsKey(NameOfLast))
        {
            TaskBase t = dictStrBoundryTask[NameOfLast];
        }

        timer.Stop();

        result.lastItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        if (dictStrBoundryTask.ContainsKey(NameOfNotFound))
        {
            TaskBase t = dictStrBoundryTask[NameOfNotFound];
        }

        timer.Stop();

        result.notFoundItem = timer.Elapsed.TotalMilliseconds;

        return result;

    }

    private SearchResult FindInHashDict()
    {
        SearchResult result = new SearchResult();
        result.SeachType = "FindInHashDict";
        result.itterations = 1;

        Stopwatch timer = new Stopwatch();

        timer.Start();
        if (dictIntBoundryTask.ContainsKey(NameOfFirst.GetHashCode()))
        {
            TaskBase t = dictIntBoundryTask[NameOfFirst.GetHashCode()];
        }

        timer.Stop();

        result.firstItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        if (dictIntBoundryTask.ContainsKey(NameOfLast.GetHashCode()))
        {
            TaskBase t = dictIntBoundryTask[NameOfLast.GetHashCode()];
        }

        timer.Stop();

        result.lastItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        if (dictIntBoundryTask.ContainsKey(NameOfNotFound.GetHashCode()))
        {
            TaskBase t = dictIntBoundryTask[NameOfNotFound.GetHashCode()];
        }

        timer.Stop();

        result.notFoundItem = timer.Elapsed.TotalMilliseconds;

        return result;
    }

    private SearchResult FindInArray()
    {
        SearchResult result = new SearchResult();
        result.SeachType = "FindInArray";
        result.itterations = 1;

        Stopwatch timer = new Stopwatch();

        timer.Start();
        foreach (TaskBase t in arrayBoundaryTask)
        {
            if (t.Name == NameOfFirst)
            {
                break;
            }
        }

        timer.Stop();

        result.firstItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        foreach (TaskBase t in arrayBoundaryTask)
        {
            if (t.Name == NameOfLast)
            {
                break;
            }
        }
        timer.Stop();

        result.lastItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        foreach (TaskBase t in arrayBoundaryTask)
        {
            if (t.Name == NameOfNotFound)
            {
                break;
            }
        }

        timer.Stop();

        result.notFoundItem = timer.Elapsed.TotalMilliseconds;

        return result;
    }

    private SearchResult FindInList()
    {
        SearchResult result = new SearchResult();
        result.SeachType = "FindInList";
        result.itterations = 1;

        Stopwatch timer = new Stopwatch();

        timer.Start();
        TaskBase t = listBoundaryTask.Find(x => x.Name == NameOfFirst);

        if (t!=null)
        {

        }

        timer.Stop();

        result.firstItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        t = listBoundaryTask.Find(x => x.Name == NameOfLast);

        if (t != null)
        {

        }
        timer.Stop();

        result.lastItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        t = listBoundaryTask.Find(x => x.Name == NameOfNotFound);

        if (t != null)
        {

        }

        timer.Stop();

        result.notFoundItem = timer.Elapsed.TotalMilliseconds;

        return result;
    }

Answer 3

Проверьте оба метода с вашими данными и принять решение.

Если в вашей коллекции всего 10 элементов, вероятно, постоянная стоимость хеширования перевесит стоимость просмотра каждого элемента в вашем списке (наихудший случай). Мы не можем сказать наверняка, хотя. Проверьте это и узнайте.

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

Answer 4

Я не думаю, что есть жесткое и быстрое правило, которое вы могли бы применить, чтобы придумать пуленепробиваемую метрику.Вы всегда можете представить себе вырожденный случай Hashtable, в котором вы заканчиваете O (n) поисками из-за столкновений, однако с реалистичными данными шансы этого ничтожны.

В общем случае, если быстрый поиск важен для вашегоПриложение, то конструкция типа Hashtable всегда ваш лучший выбор.

(Хеш-таблицы имеют свой собственный набор недостатков - они не волшебная палочка. В Википедии есть хорошее объяснение случаев, когда вы не захотите выбирать Хеш-таблицу: ссылка .)

Answer 5

Поиск по словарю всегда быстрее, чем линейный поиск.