Оптимизация редкого скалярного произведения в C#

Я думаю, что вы не можете больше оптимизировать вашу функцию dot_product. Вы должны пробежаться по одному словарю и проверить, содержит ли второй словарь какие-либо из этих идентификаторов. Возможно, вы могли бы реализовать проверку того, какой словарь меньше по размеру, и выполнить foreach на этом словаре. Это может дать дополнительную производительность, если размер обоих словарей может варьироваться в больших числах (например, arr1 = 500000 и arr2 = 1000).

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

Чтобы получить хороший ответ на ваш вопрос (от себя), вы должны проверить не только ваш алгоритм (который кажется мне довольно быстрым), но и то, сколько времени требуется для создания и поддержки необходимой инфраструктуры для этой функции и насколько высоки затраты на них?

Обновление

Прочитав ваш комментарий, я не могу понять, почему этот метод такой медленный (без использования профайлера ;-)). Обычно TryGetValue должен работать где-то на уровне O(1), само вычисление тоже не так уж сложно. Так что единственное, что можно было бы сделать, это оптимизировать выполнение foreach. Но из-за того, что кто-то должен перебрать все элементы, вы можете сделать это только немного короче, выбрав для этого шага самый короткий из двух (как уже упоминалось).

Кроме этого, я не вижу больше ничего, что можно сделать.

Я рекомендую использовать SortedList вместо Словаря. Вместо многократного запуска TryGetValue теперь вы можете создать два отдельных перечислителя и просматривать каждый список параллельно. Всегда двигайтесь вперед с тем списком, который «отстает» в перечислении, и каждый раз, когда вы видите, что два перечисленных элемента равны, вы нашли совпадение. На данный момент у меня нет под рукой моей IDE, но псевдокод выглядит следующим образом:

Get enumerator for vector A
Get enumerator for vector B
while neither enumerator is at the end
   if index(A) == index(B) then
     this element is included in dot product
     move forward in A and B
   else if index(A) < index(B) then
     move forward in A
   else # index(A) > index(B)
     move forward in B
continue while loop

Вы можете попробовать следующее, что довольно быстро. Определите struct типа:

public struct MyDoubles
{
    public Double Val1 { get; set; }
    public Double Val2 { get; set; }
    public Double Product()
    {
        return Val1 * Val2;
    }
}

И определите массив длиной с самый большой id.

MyDoubles[] values = new MyDoubles[1000000];

Затем заполните Val1 значениями из массива1 и Val2 значениями из массива2, используя id в качестве позиции индекса.

Затем выполните цикл и вычислите:

public double DotProduct2(MyDoubles[] values)
{
    double res = 0;
    for (int i = 0; i < values.Length; i++)
    {
        res += values[i].Product();
    }
    return res;
}

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

Мои временные затраты на вычисления в версии со словарем и в предложенной мной версии с массивом/структурой дают такие цифры:

Dict: 5.38s
Array: 1.87s

[Обновление с релизной сборкой]

Dict: 4.70s
Array: 0.38s