Так как нет подобного в поставке .NET использовал до этого Wintellect реализацию. Использовал успешно, но наткнулся на потолок ввиде производительности решения. Может подскажете как ускорить или найти уже готовое хорошее решение. Вот мои тесты и реализация внизу:

var wintDict = new MultiDictionary<int, int>();
var myDict = new MultiDictionary2<int, int>();

const int count = 1000000;

var t1 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        wintDict.Add(i, i);
});

var t2 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        myDict.Add(i, i);
});

var t3 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        wintDict.Remove(i, i);
});

var t4 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        myDict.Remove(i, i);
});

wintDict.Clear();
myDict.Clear();

var t5 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        wintDict.Add(RandomGen.GetValue(10), RandomGen.GetValue(10));
});

var t6 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        myDict.Add(RandomGen.GetValue(10), RandomGen.GetValue(10));
});

var t7 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        wintDict.Remove(RandomGen.GetValue(10), RandomGen.GetValue(10));
});

var t8 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        myDict.Remove(RandomGen.GetValue(10), RandomGen.GetValue(10));
});

Результаты:

(послед доступ)
t1 — 00:00:03.1043346
t2 — 00:00:01.1194840
t3 — 00:00:02.2321601
t4 — 00:00:00.2400655

(произвольный доступ)
t5 — 00:00:00.8711732
t6 — 00:00:00.2566774
t7 — 00:00:00.2513308
t8 — > минуты

Собственная реализация сделал Wintellect по всем тестам кроме удаления в произвольном порядке. Причина понятна косвенно (то что в wintellect не все так просто). Но как улучшить и этот показатель не теряя другие?

public class MultiDictionary2<TKey, TValue> : Dictionary<TKey, List<TValue>>
{
    protected readonly IDictionary<TKey, TValue> Inner;

    public void Add(TKey key, TValue value)
    {
        List<TValue> list;
        if (!Inner.TryGetValue(key, out list))
        {
            list = new List<TValue>();
            Inner.Add(key, list);
        }

        list.Add(value);
    }

    public bool Remove(TKey key, TValue value)
    {
        List<TValue> list;
        if (Inner.TryGetValue(key, out list))
        {
            var retVal = list.Remove(value);
            if (list.Count == 0)
                Inner.Remove(key);

            return retVal;
        }

        return false;
    }

    public bool Contains(TKey key, TValue value)
    {
        var list = Inner.TryGetValue(key);
        return (list != null) && list.Contains(value);
    }
}

Может там не прямое удаление идет, а просто пометка как удаленных?

Здравствуйте, Аноним, Вы писали:

А>Так как нет подобного в поставке .NET использовал до этого Wintellect реализацию. Использовал успешно, но наткнулся на потолок ввиде производительности решения. Может подскажете как ускорить или найти уже готовое хорошее решение. Вот мои тесты и реализация внизу:

А>

А>var wintDict = new MultiDictionary<int, int>();
А>var myDict = new MultiDictionary2<int, int>();

А>const int count = 1000000;

А>var t1 = Watch.Do(() =>
А>{
А>    for (var i = 0; i < count; i++)
А>        wintDict.Add(i, i);
А>});
А>

Как вы думаете, сколько перераспределений памяти будет тут происходить?

Здравствуйте, Аноним, Вы писали:


А>Собственная реализация сделал Wintellect по всем тестам кроме удаления в произвольном порядке. Причина понятна косвенно (то что в wintellect не все так просто). Но как улучшить и этот показатель не теряя другие?

public class MultiDictionary2<TKey, TValue> : Dictionary<TKey, List<TValue>>
{
}

Либо заменить на HashSet<TValue>, либо сортировать List<T> при вставке и использовать list.BinarySearch при удалении.

Естественно, производительность просядет.

Здравствуйте, Sinix, Вы писали:

S>Либо заменить на HashSet<TValue>, либо сортировать List<T> при вставке и использовать list.BinarySearch при удалении.

S>Естественно, производительность просядет.

Заменил на HashSet. t2 увеличился в два раза, но t8 стало сопоставимо с t7. Непонятно, почему t2 так сильно отличается от t6.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Sinix, Вы писали:

S>>Либо заменить на HashSet<TValue>, либо сортировать List<T> при вставке и использовать list.BinarySearch при удалении.

S>>Естественно, производительность просядет.

А>Заменил на HashSet. t2 увеличился в два раза, но t8 стало сопоставимо с t7. Непонятно, почему t2 так сильно отличается от t6.

Попробуйте указать параметр capacity в конструкторах ваших словарей.

Здравствуйте, hardcase, Вы писали:

H>Попробуйте указать параметр capacity в конструкторах ваших словарей.

t2 уменьшился до 00:00:01.7138082. Не ахти какой отрыв.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, hardcase, Вы писали:

H>>Попробуйте указать параметр capacity в конструкторах ваших словарей.

А>t2 уменьшился до 00:00:01.7138082. Не ахти какой отрыв.

Скорее всего влияние имеет количество коллизий. Когда у нас значения от 0 до 9, то количество коллизий видимо будет равно нулю, тогда как для 1 000 000 значений их будет много.

Здравствуйте, hardcase, Вы писали:

H>Скорее всего влияние имеет количество коллизий.

Там же число уникальное.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, hardcase, Вы писали:

H>>Скорее всего влияние имеет количество коллизий.

А>Там же число уникальное.

Я имею в виду коллизии хэшей, которыми оперирует словарь.

Здравствуйте, hardcase, Вы писали:

H>Я имею в виду коллизии хэшей, которыми оперирует словарь.

Хеш от числа — это само число.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, hardcase, Вы писали:

H>>Я имею в виду коллизии хэшей, которыми оперирует словарь.

А>Хеш от числа — это само число.

Хэш от числа как правило берется по модулю размера буфера (hash % buffer.Length), в котором находятся значения (списки значений).
Таким образом, при увеличении количества ключей вероятность коллизий при подобном преобразовании хэш-значений повышается.

Здравствуйте, hardcase, Вы писали:

H>Хэш от числа как правило берется по модулю размера буфера (hash % buffer.Length), в котором находятся значения (списки значений).

Это справедливо только для чисел?

H>Таким образом, при увеличении количества ключей вероятность коллизий при подобном преобразовании хэш-значений повышается.

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

Здравствуйте, Аноним, Вы писали:

List при удалении сдвигает все элементы после удаляемого, сохраняя исходный порядок их следования. Делает он это с помощью Array.Copy, но всё-же копирование есть копирование. Возможно, Ваши конкуренты[] используют вместо него массивы, и при удалении просто меняют местами последний элемент с удаляемым. Может быть — linked list, он тоже быстр на удаление.

Здравствуйте, Jolly Roger, Вы писали:

JR>List при удалении сдвигает все элементы после удаляемого, сохраняя исходный порядок их следования. Делает он это с помощью Array.Copy, но всё-же копирование есть копирование. Возможно, Ваши конкуренты[] используют вместо него массивы, и при удалении просто меняют местами последний элемент с удаляемым. Может быть — linked list, он тоже быстр на удаление.

Это уже больше похоже на правду. Надо попробовать. А то мне тут предлагали Capacity менять, что явно занижало стандартный алгоритм ресайза словаря (емнип, увеличение размера в геометрической прогрессии, что довольно быстро достигнет моего count).

Здравствуйте, Jolly Roger, Вы писали:

JR>Здравствуйте, Аноним, Вы писали:

JR>List при удалении сдвигает все элементы после удаляемого, сохраняя исходный порядок их следования. Делает он это с помощью Array.Copy, но всё-же копирование есть копирование. Возможно, Ваши конкуренты[] используют вместо него массивы, и при удалении просто меняют местами последний элемент с удаляемым. Может быть — linked list, он тоже быстр на удаление.

Первоначальное впечатление оказалось ошибочное. Тоже не то. Проблема не в листах. Проблема в словаре. Потому что тормозит тест с последовательным заполнением словаря. В это случае размер листа равен 1, не более. а вот размер словаря увеличивается до миллиона.

Здравствуйте, Аноним, Вы писали:

А>Первоначальное впечатление оказалось ошибочное. Тоже не то. Проблема не в листах. Проблема в словаре. Потому что тормозит тест с последовательным заполнением словаря.

Разве? Видимо, я пропустил упоминание об этом, стартовом-то сообщении было

t8 — > минуты

Собственная реализация сделал Wintellect по всем тестам кроме удаления в произвольном порядке. Причина понятна косвенно (то что в wintellect не все так просто). Но как улучшить и этот показатель не теряя другие?

А t8, если не путаю, это удаление из (max)10-ти словарей, каждый из которых содержит по большому List'у. Причём номенклатура элементов в них небольшая, а это значит, что каждый удаляемый элемнент находится близко к голове.

Впрочем, Вам на месте конечно виднее.

Здравствуйте, Jolly Roger, Вы писали:

JR>Разве? Видимо, я пропустил упоминание об этом, стартовом-то сообщении было

Да, пропустили это http://rsdn.ru/forum/dotnet/3966311.1.aspx

Автор:
Дата: 21.09.10

Здравствуйте, Аноним, Вы писали:

А>Да, пропустили это http://rsdn.ru/forum/dotnet/3966311.1.aspx

Автор:
Дата: 21.09.10

А, это. Ну так ведь бесплатно ничего не бывает. HashSet, во-первых, считает хэш — какие-никакие, а затраты, а во-вторых, перед добавлением проверяет, нет-ли в нём уже такого значения. Отсюда и замедление на вставку. Кроме того, HashSet добавляет только уникальные значения, а у Вас в 8 всего максимум 10 уникальных значений, отсюда и радикальное ускорение при удалении