Можно ли выполнить частичное совпадение строк в ключе строки словаря?

Question

У меня в коде Dictionary<string, List<int>>, который я использую следующим образом:

Key           Values  
2011-07-15    1, 2, 3
2011-07-20    4, 5, 6
2010-02-11    7, 8, 9

Мой код должен иметь возможность запрашивать все значения, соответствующие определенной подстроке в ключе.Например, если бы у меня была подстрока 2011-07, она должна вернуть значения {1, 2, 3, 4, 5, 6}.Подстрока 11 должна возвращать все идентификаторы из 1-9.

Кто-нибудь может порекомендовать краткий способ добиться этого?Или предоставить лучшую структуру данных для получения этой информации?

Answer 1

Я бы сделал метод расширения:

public static class DictionaryExt
{
    public static IEnumerable<T> PartialMatch<T>(this Dictionary<string, T> dictionary, string partialKey)
    {
        // This, or use a RegEx or whatever.
        IEnumerable<string> fullMatchingKeys = 
            dictionary.Keys.Where(currentKey => currentKey.Contains(partialKey));

        List<T> returnedValues = new List<T>();

        foreach (string currentKey in fullMatchingKeys)
        {
            returnedValues.Add(dictionary[currentKey]);
        }

        return returnedValues;
    }
}

«Стоимость» добавления значений в словарь не изменится, но стоимость поиска будет выше, но только тогда, когда вы знаете, что 'мы идем с частичным совпадением.

Кстати, я уверен, что вы можете преобразовать это в одном лямбда-выражении, но концепция остается прежней.В вашем примере этот метод вернул бы 2 списка значений, но вы можете изменить его, чтобы объединить списки.Вот способ расширения, который вы могли бы сделать:

public static IEnumerable<T> PartialMatch<T>(
    this Dictionary<string, IEnumerable<T>> dictionary,
    string partialKey)
{
    // This, or use a RegEx or whatever.
    IEnumerable<string> fullMatchingKeys = 
        dictionary.Keys.Where(currentKey => currentKey.Contains(partialKey));

    List<T> returnedValues = new List<T>();

    foreach (string currentKey in fullMatchingKeys)
    {
        returnedValues.AddRange(dictionary[currentKey]);
    }

    return returnedValues;
}

Edit 2 : Если подумать, вы также можете сделать его более общим.При использовании следующего метода расширения он будет работать с любым словарем, если вы предоставите comparer, который проверяет, что вы подразумеваете под «частичным соответствием»:

public static IEnumerable<TValue> PartialMatch<TKey, TValue>(
    this Dictionary<TKey, IEnumerable<TValue>> dictionary,
    TKey partialKey,
    Func<TKey, TKey, bool> comparer)
{
    // This, or use a RegEx or whatever.
    IEnumerable<TKey> fullMatchingKeys = 
        dictionary.Keys.Where(currentKey => comparer(partialKey, currentKey));

    List<TValue> returnedValues = new List<TValue>();

    foreach (TKey currentKey in fullMatchingKeys)
    {
        returnedValues.AddRange(dictionary[currentKey]);
    }

    return returnedValues;
}

Answer 2

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

myDictionary.Where(kvp => kvp.Key.Contains("11")).SelectMany(kvp => kvp.Value);

Вы все равно должны искать во всех ключах обобщенную подстроку без некоторой довольно крутой магии (не предоставленной .Net), поэтому LINQ не должентебе здесь очень больно.

Answer 3

Если словарь использует внутренние хэши, вам не повезло, так как похожие строки дают разные хэши.Я только что реализовал решение этого требования на выходных в Си, собеседование / домашнее задание.В качестве базовой структуры я использовал отсортированный массив - дорогие вставки, но быстрый поиск (с использованием бинарного поиска).Чтобы найти все записи с ключом, начинающимся с префикса, я бы нашел 1-й, а затем просто перейти к следующему, следующему ... Для общей подстроки, т.е. не только для префикса, мое решение не будет работать.В данный момент я не знаю, что предложить для поиска "общая подстрока".

Answer 4

Вы можете иметь три словаря.Год, месяц, день.

Обратите внимание, что при добавлении элементов в три словаря вы НЕ дублируете элементы.

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

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

Answer 5

Кратким способом будет использование многозначной карты.

Например:

Dictionary<string, Dictionary<string, List<int>>

почему вы не сохраняете 2011-07 в качестве ключа, 15 для внутреннего словарного ключа и 1,2,3 в качестве значений.

map ["2011-07"] ["15"] = {1,2,3};

если вы хотите просто 2011-07, вы можете получить все в другом словаре путем обхода.

map["2011-07"] // вернет вам 1,2,3,4,5,6

и если вы хотите перейти к определенному дню, 2011-07-15, это вернет вам только 1,2,3

foreach(var element in map["2011-07"]){

     var values = element.values; // and you can append them to a list.

}

если вам понадобится год / месяц / день, вам понадобятся многоуровневые словари. или вы также можете использовать Tree .