Какова лучшая структура данных в .NET для поиска по строковому ключу или числовому индексу?

Question

Я ищу наиболее идеальную структуру данных (по производительности и простоте использования), из которой значения можно получить с помощью строкового ключа или индекса.Словарь не работает, потому что вы не можете получить данные по индексу.Есть идеи?

Answer 1

Вы хотите Заказанный словарь сорт.Вам нужно будет включить пространство имен System.Collections.Specialized:

    OrderedDictionary od = new OrderedDictionary(); 
    od.Add("abc", 1); 
    od.Add("def", 2); 
    od.Add("ghi", 3); 
    od.Add("jkl", 4); 

    // Can access via index or key value:      
    Console.WriteLine(od[1]);       
    Console.WriteLine(od["def"]);

Answer 2

Есть System.Collections.ObjectModel.KeyedCollection<строка,TItem>, который является производным от Collection< TItem>. Поиск - O (1).

class IndexableDictionary<TItem> : KeyedCollection<string, TItem>
 { Dictionary<TItem, string> keys = new Dictionary<TItem, string>();

   protected override string GetKeyForItem(TItem item) { return keys[item];}

   public void Add(string key, TItem item) 
    { keys[item] = key;
      this.Add(item);
    }
 }

Answer 3

Одно слово предупреждения.А OrderedDictionary действительно имеет плохие ТТХ для большинства операций, кроме вставки и поиска:Как удаление, так и изменение значения может потребовать линейного поиска по всему списку, что приводит к увеличению времени выполнения. О(н).(Для модификации это зависит от того, осуществлялся ли доступ по индексу или по ключу.)

Для большинства операций с разумными объемами данных это совершенно неприемлемо.Более того, структура данных хранит элементы как в линейном векторе, так и в хеш-таблице, что приводит к некоторым затратам памяти.

Если поиск по индексу происходит не слишком часто, SortedList или SortedDictionary будет иметь гораздо лучшие характеристики производительности (доступ по индексу может быть достигнут через ElementAt метод расширения).

Если, с другой стороны, доступ по индексу является нормой, тогда вообще прекратите использовать словарные структуры данных и просто сохраните свои значения в List<KeyValuePair<TKey, TValue>>.Хотя это означает линейный поиск доступа по ключу, все остальные операции очень дешевы, а общую производительность на практике трудно превзойти.

/РЕДАКТИРОВАТЬ:Конечно, последняя также является словарной структурой данных в теоретическом смысле.Вы могли бы даже инкапсулировать его в классе, реализующем соответствующий интерфейс.

Answer 4

Коллекции на основе хеша (Dictionary, Hashtable, HashSet) отсутствуют, потому что у вас не будет индекса, поскольку вам нужен индекс, я бы использовал вложенный универсальный:

List<KeyValuePair<K,V>>

Конечно, вы теряете поиск ключа O(1), который вы получаете с помощью хэшей.

Answer 5

Словарь может работать с linq.Хотя я не знаю о возможных проблемах с производительностью.Словарь.ЭлементАт(индекс);

Answer 6

Я рекомендую использовать SortedDictionary<string, TValue> или SortedList<string, TValue>.Оба имеют производительность поиска O(log n).

Различия, как указано из библиотека MSDN:

SordedList <(of <(tkey, Tvalue>)>) использует меньше памяти, чем SortedDictionary <(of <(tkey, tvalue>)>).

SortedDictionary <(of <(tkey, Tvalue>)>) имеет более быстрые операции вставки и удаления для несортированных данных:O (log n), в отличие от O (n) для SortedList <(of <(tkey, tvalue>)>).

Если список заполняется сразу из сортированных данных, SortedList <(of <(tKey, TVALUE>)>) быстрее, чем SortedDictionary <(OF <(TKEY, TVALUE>)>).

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

Answer 7

Вы ищете что-то вроде Класс сортированного списка (вот общая версия также).