HashSet & Список для хранения строк

Спокойной ночи,HashSet & Список для хранения строк

Я пытался эталон производительности HashSet и список типов данных в C#, чтобы проверить какой из них лучше, когда много вставок/удаление должно быть сделано. Код, который я использую, примерно следующий.

public static Func<String, HashSet<String>> ListaPossiveisCorreccoes = StrPalavra => { 

     (...) 
     HashSet<String> ListaCorreccoes = new HashSet<String>(); 
     (...) 

     (Lots of .Add operations) 

     return ListaCorreccoes; 

    }; 


    public static Func<String, IEnumerable<String>> ListaCorreccoes = (StrPalavra) => 
    { 


     HashSet<String> ConjuntoCorreccoes = new HashSet<String> (); 

     foreach (String StrTmp in ListaPossiveisCorreccoes(StrPalavra)) 
      foreach (String StrTmp2 in ListaPossiveisCorreccoes(StrTmp)) 
       ConjuntoCorreccoes.Add(StrTmp2); 

     return ConjuntoCorreccoes/*.Distinct()*/.Where(PalavraConhecida)*/; 

    };

Когда я бег sequentaly две функции, описанной выше, она занимает около 250-285ms завершить (я использую запоминание). Однако, если я заменяю HashSet<String> на List<String> всюду и раскомментирую прокомментированную часть последней строки (таким образом, выбирая дубликаты из списка), для завершения требуется всего 140-145 мс. Это противоречит тому, что я читал о HashSets, в котором говорится, что их производительность намного лучше, чем в списках операций добавления/удаления. Может кто-нибудь, пожалуйста, скажите мне, нормально ли это? 250 мс, конечно, не много, но это почти в два раза больше времени, чем в списках, и это важно, поскольку эти функции призваны вызываться повторно.

спасибо.

источник

2010-10-19 Miguel

От вопроса

Это противоречит тому, что я читал о HashSets, который говорит, что их производительность гораздо лучше, чем списков в дополнение/удаление операции

Я не уверен, где вы читаете, что HashSet<T> имеет более высокую производительность по сравнению с Lis<T> относительно добавления. Это просто неправильно.

List<T>.Add в частности будет превзойти HashSet<T>.Add. В большинстве случаев Add on List<T> - это просто назначение в индекс массива и приращение индекса. Это намного сложнее для HashSet<T>.

Удалить сложнее и зависит от того, удаляются ли элементы с начала, конца или середины коллекции.

источник

2010-10-19 20:59:34 JaredPar

Здесь я взял эту идею из ... http://www.codethinked.com/post/2010/02/22/An-Overview-Of-System_Collections_Generic.aspx – Miguel

Вы правы, это, вероятно, будет медленнее, чем список, но, говоря в терминах нотации заказа, операции добавления списка и HashSet в большинстве случаев эквивалентны [O (1)]. MSDN говорит (как для List, так и для HashSet): Если граф уже равен емкости объекта HashSet , емкость автоматически настраивается для размещения нового элемента. Если граф меньше емкости внутреннего массива, этот метод является операцией O (1). Если объект HashSet должен быть изменен, этот метод становится операцией O (n), где n является Count. http://msdn.microsoft.com/en-us/library/bb353005.aspx –

Это не мое, но у меня есть интересная информация.

http://www.phase9studios.com/post/2008/01/08/DictionaryVSHashTable.aspx

Я всегда думал, что Хеш был больше для поиска значений. Вы получаете повышение производительности в поиске, а не вставке.

источник

2010-10-19 21:00:05 Justin

Большое спасибо за эту интересную информацию, но на самом деле словарь не подходит для той задачи, которую мне нужно сделать здесь. ,Во всяком случае, я очень ценю вашу помощь. – Miguel

HashSet & Список для хранения строк

ответ

Смежные вопросы