Что такое AccessTime для словаря <Dictionary <char, int>, List <string>>, это все еще O (1)? - PullRequest
Новая
       27

Что такое AccessTime для словаря <Dictionary <char, int>, List <string>>, это все еще O (1)?

1 голос
/ 15 января 2012

Я хотел реализовать алгоритм с Dictionary<Dictionary<char,int>, List<string>>, чтобы найти слова анаграммы в словаре.

Поскольку мне нужно реализовать свой пользовательский EqualityComparer для этого словаря, остается ли время доступа O (1), то есть большим O (1)?

Второй вопрос, как часть EqualityComparer Мне также нужно реализовать GetHashCode().Каков эффективный способ определения GetHashCode() для Dictionary<Dictionary<char,int>, List<string>>?

Я только что придумал этот метод, есть ли лучшая альтернатива? 

public int GetHashCode(Dictionary<char, int> obj)
    {
        unchecked
        {
            int hashCode = 17;
            foreach (var item in obj)
            {
                hashCode += 23 * item.Key.GetHashCode();
            }
            return hashCode;
        }
    }

Любое слово совета приветствуется.Спасибо!

Ответы [ 3 ]

2 голосов
/ 15 января 2012

Время доступа Dictionary<TKey, TValue> приближается к O (1), но не совсем так.В идеальных сценариях (хорошее распределение / мало коллизий) вы можете думать об этом как о (1).В ситуациях, когда существует много коллизий из-за низкой дисперсии значений GetHashCode, время доступа ухудшается и может приближаться к O (N).

2 голосов
/ 15 января 2012

Как насчет преобразования слова "need" в строку "d1e2n1" вместо использования словаря в качестве ключа? Чтобы построить эту строку, вы можете использовать двоичное дерево. Символ будет использоваться в качестве ключа и количество символов в качестве значения. Двоичное дерево автоматически сортируется по ключу, что не относится к словарю.

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

public override int GetHashCode()
{
    // Combine hashcode of a and b
    return a.GetHashCode() ^ b.GetHashCode();
}

Поиск записи в несортированном списке является операцией O (n). Поиск записи в отсортированном списке является операцией O (log (n)), если используется двоичный поиск.

Поиск слова в списке в словаре - это операция O (1 + n), которая аналогична операции O (n) или операции O (1 + log (n)), которая является такой же, как операция O (log (n)).

EDIT:

Вот возможная реализация: 

var anagrams = new Dictionary<string, List<string>>();
foreach (string word in words) {
    string key = GetFrequency(word);
    List<string> list;
    if (anagrams.TryGetValue(key, out list)) {
        list.Add(word);
    } else {
        list = new List<string> { word };
        anagrams.Add(key, list);
    }
}

Он использует этот метод для получения ключа: 

private string GetFrequency(string word)
{
    var dict = new SortedDictionary<char, int>(); // Implemented as binary tree
    foreach (char c in word.ToLower()) {
        int count;
        if (dict.TryGetValue(c, out count)) {
            dict[c] += 1;
        } else {
            dict[c] = 1;
        }
    }
    return dict.Aggregate(new StringBuilder(), (sb, item) => sb.Append(item.Key).Append(item.Value), sb => sb.ToString());
}

Используя это определение для слов ... 

var words = new List<string> { "need", "eden", "team", "meat", "meta", "Nat", "tan" };

Этот тест ... 

foreach (var item in anagrams.OrderBy(x => x.Key)) {
    Console.WriteLine();
    Console.WriteLine(item.Key + ":");
    foreach (string word in item.Value.OrderBy(w => w)) {
        Console.WriteLine("    " + word);
    }
}

... производит этот вывод 

a1e1m1t1:
    meat
    meta
    team

a1n1t1:
    Nat
    tan

d1e2n1:
    eden
    need

РЕДАКТИРОВАНИЕ № 2:

Вот расчет частоты, предложенный Беном Фойгтом 

private string GetFrequencyByBenVoigt(string word)
{
    char[] chars = word.ToLower().ToCharArray();
    Array.Sort(chars);
    return new string(chars);
}

Результат теста будет 

aemt:
    meat
    meta
    team

ant:
    Nat
    tan

deen:
    eden
    need
1 голос
/ 15 января 2012

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

...