Свободный словарь, нужен совет

Question

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

Если в словаре есть запись под ключом "Джонсон", я хочу найти значение заданы входные строки "Джон", "Джо". Также я хочу иметь возможность извлечь несколько значений, которые соответствуют входная строка по заданному условию. Например, если есть записи "Джон А" и "Джон Б", я хочу чтобы иметь такую ​​функциональность, как FindFirst, которая возвращала бы итератор к первому найденному значению.

В идеале я бы предпочел использовать существующие System.Collections.Generic.Dictionary возможно получение нового класса и переопределение некоторых методов

Answer 1

Я подозреваю, что SortedList<TKey, TValue> будет вашей лучшей ставкой здесь, это словарь, основанный на бинарном дереве поиска. Его свойство Keys возвращает IList<TKey> с временем доступа O (1).

Вы должны получить свойство Keys и выполнить двоичный поиск, чтобы найти ключ, который начинается с вашего ключа поиска. Затем посмотрите вверх и вниз от этого образца ключа, чтобы найти диапазон ключей, которые на самом деле совпадают. Это даст производительность O (log n), а не производительность O (n), которую вы получите, просмотрев все ключи.

Я бы не извлек бы из этого, хотя - я бы написал тип, который имеет a SortedList<,> внутри.

Answer 2

Хотя я сомневаюсь, что словарь подходит для чего-то подобного, вы можете использовать:

dictionary[dictionary.Keys.First(d=>d.StartsWith("Jo"))]

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

Мне понадобится +1 Джон, чтобы указать SortedList<TKey,TValue>

Answer 3

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

То, что вы, например, имеете структуру btree +, состоящую из простых ключей, в которой вы находите первую совпадающую запись, затем вы следуете перечислителю btree +, пока не найдете соответствие.

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

Ваши примеры "Jo" и "John" в "Johnson" являются примерами "StartsWith ()", где сортировка ключей принесет вам пользу. Если вы также ожидаете искать простую подстроку, а не только начальный сегмент, вам нужно взглянуть на другие алгоритмы хранения и поиска ключа.

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

Answer 4

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

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

Answer 5

Вы можете использовать пользовательские сравнения на равенство со словарем, предоставив реализацию IEqualityComparer . Однако Dictionary - это хэш-карта, для которой требуется сопоставление каждого ключа с одним и тем же целочисленным хешем, что делает его менее полезным в вашем случае. Вы можете использовать SortedDictionary (который также является IDictionary), предоставляя настраиваемое IComparer и время поиска O (log (n)) (вместо O (1), которое в идеале может предоставить Dictionary ).