Сборник строк в словарь

Question

При условии упорядоченного набора строк:

var strings = new string[] { "abc", "def", "def", "ghi", "ghi", "ghi", "klm" };

Используйте LINQ для создания словаря строк для количества вхождений этой строки в коллекции:

IDictionary<string,int> stringToNumOccurrences = ...;

Желательно сделать это за один проход над коллекцией строк ...

Answer 1

var dico = strings.GroupBy(x => x).ToDictionary(x => x.Key, x => x.Count());

Answer 2

По предложению Тимви / Дарина это будет выполнено за один проход над исходной коллекцией, но создаст несколько буферов для группировок.LINQ на самом деле не очень хорош в подсчете, и такая проблема была моей первоначальной мотивацией для написания Push LINQ.Возможно, вам захочется прочитать мое сообщение в блоге , чтобы узнать, почему LINQ здесь не очень эффективен.

Push LINQ и довольно впечатляющая реализация той же идеи - Reactive Extensions - может справиться с этим более эффективно.

Конечно, если вы не особо заботитесь о дополнительной эффективности, используйте ответ GroupBy :)

РЕДАКТИРОВАТЬ: я не заметил, что ваши строки были заказаны.Это означает, что вы можете быть на намного более эффективным, потому что вы знаете, что как только вы увидите строку x, а затем строку y, если x и y различны, вы никогда больше не увидите x.В LINQ нет ничего, что могло бы сделать это особенно легко, но вы можете сделать это самостоятельно довольно просто:

public static IDictionary<string, int> CountEntries(IEnumerable<string> strings)
{
    var dictionary = new Dictionary<string, int>();

    using (var iterator = strings.GetEnumerator())
    {
        if (!iterator.MoveNext())
        {
            // No entries
            return dictionary;
        }
        string current = iterator.Current;
        int currentCount = 1;
        while (iterator.MoveNext())
        {
            string next = iterator.Current;
            if (next == current)
            {
                currentCount++;
            }
            else
            {
                dictionary[current] = currentCount;
                current = next;
                currentCount = 1;
            }
        }
        // Write out the trailing result
        dictionary[current] = currentCount;
    }
    return dictionary;
}

Это O (n), с включенными нет поисками в словаре, кроме как при написанииценности.Альтернативная реализация будет использовать foreach и значение current, начинающееся с нуля ... но это в конечном итоге будет довольно странным в нескольких других отношениях.(Я пробовал это :) Когда мне нужно обработать специальный случай для первого значения, я обычно использую вышеуказанный шаблон.

На самом деле вы могли бы сделать это с LINQ, используя Aggregate, но это было бы довольно неприятно.

Answer 3

Стандартный способ LINQ:

stringToNumOccurrences = strings.GroupBy(s => s)
                                .ToDictionary(g => g.Key, g => g.Count());

Answer 4

Это версия foreach , подобная той, о которой Джон упоминает, что он находит в своем ответе "довольно неприглядную".Я помещаю это здесь, так что есть что-то конкретное, чтобы поговорить.

Я должен признать, что нахожу это проще, чем версия Джона, и не могу понять, что в этом плохого.Джон?Кто-нибудь?

static Dictionary<string, int> CountOrderedSequence(IEnumerable<string> source)
{
    var result = new Dictionary<string, int>();
    string prev = null;
    int count = 0;
    foreach (var s in source)
    {
        if (prev != s && count > 0)
        {
            result.Add(prev, count);
            count = 0;
        }
        prev = s;
        ++count;
    }
    if (count > 0)
    { 
        result.Add(prev, count);
    }
    return result;
}

Обновлено , чтобы добавить необходимую проверку на пустой источник - я все еще думаю, что это проще, чем у Джона: -)

Answer 5

Если вы ищете особенно эффективное (быстрое) решение, то GroupBy, вероятно, слишком медленное для вас.Вы можете использовать цикл:

var strings = new string[] { "abc", "def", "def", "ghi", "ghi", "ghi", "klm" };
var stringToNumOccurrences = new Dictionary<string, int>();
foreach (var str in strings)
{
    if (stringToNumOccurrences.ContainsKey(str))
        stringToNumOccurrences[str]++;
    else
        stringToNumOccurrences[str] = 1;
}
return stringToNumOccurrences;

Answer 6

Если это фактический производственный код, я бы пошел с ответом Тимви .

Если это действительно домашняя работа, и вы должны написать свою собственную реализацию, она не должнабыть слишком жесткимВот лишь несколько советов, указывающих вам правильное направление:

1. Dictionary<TKey, TValue> имеет метод ContainsKey.
2. Свойство this[TKey] интерфейса IDictionary<TKey, TValue> интерфейса имеет видустанавливаемое;то есть, вы можете сделать dictionary[key] = 1 (что означает, что вы также можете сделать dictionary[key] += 1).

Из этих подсказок я думаю, что вы должны быть в состоянии выяснить, как сделать это "вручную".