Уважаемые форумчане. Нужна ваша помощь...
Есть следующий код на CLI


где  Info::Types - IDictionary

В среднем получается, что в if заходит порядка 3-4 ТЫСЯЧ раз. Может кто подскажет, как оптимизировать такой поиск?

Это сообщение отредактировал(а) axelprog - 19.3.2008, 17:42

axelprog, когда скорость работы .NET-овых коллекций становится узким местом, стоит задуматься о переходе на native, например, близким аналогом Dictionary будет std::map. Тем более у Вас уже CLI, значит, даже отдельного mixed-проекта создавать не надо. Или так не годится?

Это сообщение отредактировал(а) marcusmae - 19.3.2008, 21:38

Беда в том, что этот dictionary приходит из другой либы, написанной на C#, и поменять его без мощного изменения либы не получится. если только в проекте менять его на map. Только не вижу от этого пользы. В мапе разве можно осуществлять поиск по части ключа? Основные тормоза в том, что надо осуществлять поиск то части ключа, а не по полному ключу (см. if в примере)

Нет. Ну и у Вас это делает функция String::StartsWith(String^), не имеющая отношения к функциям словаря... 

Тогда другой вариант : получите отсортированный массив строковых ключей и создайте из него дерево (деревья) символов. Ну, то есть, чтобы в корнях стояли всевозможные символы, с которых начинаются ключи, ниже - всевозможные символы на второй позиции в строках, ниже - на третьей и т.д. А значениями в узлах дерева положите null или ссылку на соответствующее значения из оригинального словаря. Таким образом Ваш словарь будет проидексирован, как автозаполнение коммандной строки браузера : имея символы части ключа, Вы переместитесь по дереву вниз до некоторого узла, относительно которого нужно будет взять все значения в листьях - они и будут результатом действия if-а. 

Наверно, коряво объясняю?..

Ну может для кого и коряво. А для меня даже черезчур подробно 

Идею я в принципе понял. нужно подумать над возможностью применения

В большинстве случаев доступ к IDictionary происходит за константное время (как в массиве). Проблемы появлятся при возникновении колиизий. Когда разные элементы хранятся в одной ячейке таблицы (про реализацию можно почитать ниже).

При грамотной функции хэширования (GetHashCode()), которая неплохо реализована для string, и достаточно пустых ячеек чтобы предотвратить возникновение коллизий. Рекомендуют заполнять таблицу не более 70-80% (так сказала Вики), 60% (насколько помню я). 
Можно попробовать ресайзить таблицу после 50%.


ИМХО, в данном случае больше тормозит методы ToUpper() (перебрать все элементы и перевести каждый в верхний регистр), чем доступ к таблице.


Поэтому мои рекомендации:
1) impStr->ToUpper() вынести за цикл(ы) for.
2) Если сами ключи не важны, то можно перебирать сразу значения: Info::Types->Values
3) Если важны -- увеличить размер таблицы
4) попробовать отказаться от ToUpper() вообще.


Тут, действительно, лучше реализовать дерево, как советует marcusmae.
Судя по всему FullName логически разделятеся на несколько частей типа: "ParentParentName-ParentName-Name";
И именно по этим ключам формировать дерево.

Но к этому я настоятельно рекомендую прибегнуть только после детальных тестов производительности и после использования всех других (более простых) методов.

P.S. Про хэш таблицу можно почитать здесь.