Как на JS быстро найти угол между векторами? (22-мерные вектора, поиск по условию минимального/максимального угла из 5 000 записей)?

Question

[Всеволод Родионов]

Собственно, в заголовке весь вопрос.
Есть клиентское приложение на JS, внутри него необходимо (в рамках рекомендательного алгоритма) из приблизительно 5к записей выбрать определенные, наиболее подходящие по критерию. Оптимизации выборки уже есть, хотелось бы оптимизировать.

Сейчас расчитываю по стандартной формуле cos α = a·b / |a|·|b|.
Код выглядит примерно так:

function getScaledAngleForVectors(vec1, vec2) { //cos α = a·b / |a|·|b|
    var length = Math.max(vec1.length, vec2.length);
    var scalarMulti = 0;
    for (var i = 0; i < length; i++)
        scalarMulti += vec1[i] * vec2[i] || 0;
    var cosAlpha = scalarMulti / (getLength(vec1) * getLength(vec2));
    var alpha = Math.acos(cosAlpha);
    return 1 - cosAlpha;
}
function getLength(vec) {
    var n = vec.length;
    var length = 0;
    for (var i = 0; i < n; i++)
        length += Math.pow(vec[i] || 0, 2);
    return Math.pow(length, .5);
}

Перспективные направления - использование целочисленных значений и работа с Uint16Array, либо приведение векторов к единичным - в таком случае шаг "cos α = a·b / |a|·|b|" можно свести до "cos α = a·b".
Возможно, кто-то подскажет что-то еще?

Answer 1

[Армянское Радио]

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

Answer 2

[Alexander Sydorenko]

Вот в этом коде, у Вас где-то логическая ошибка

...
    var cosAlpha = scalarMulti / (getLength(vec1) * getLength(vec2));
    var alpha = Math.acos(cosAlpha);
    return 1 - cosAlpha;
}

Зачем считать alpha если на результат это не влияет? Поэтому думаю все таки, что возврат не верный.. а надо что то типа return alpha;

Comments

[Всеволод Родионов]

Возврат верный, но операция и вправду лишняя, спасибо)
Дело в том, что мне нужно не точное число, а ранжирование векторов относительно друг друга, и в таких условиях (любой из параметров вектора больше или равен нулю) это допустимо - все результаты лежат между 0 и 90 градусами, а косинусы - в интервале между 0 и 1, использовать 1-cos дает 0 в случае точного совпадения, 1 в случае максимально возможного угла между векторами.

Answer 3

[Алексей]

Мой вариант

"use strict";
// Функция для вычисления угла между 2 векторами
var angleBetweenTwoVectors = function(vector1, vector2) {
    // скалярное произведение векторов
    var scalMultVectors = vector1.reduce(function(sum, current, i) {
        return sum + (current * vector2[i])
    }, 0);
    // модуль вектора равен квадратному корню из суммы квадратов его координат
    var moduleVector = function(v) {
        // Находим квадраты слагаемых
        var step1 = v.map(function(currentValue) {
            return Math.pow(currentValue, 2)
        });
        // Складываем их
        var step2 = step1.reduce(function(sum, current) {
            return sum + current
        });
        // Вычисляем квадратный корень
        return Math.sqrt(step2, 2)
    };
    // Вычисляем косинус угла между векторами
    var cosA = scalMultVectors / (moduleVector(vector1) * moduleVector(vector2));
    console.log("cos(" + cosA + ")");
    return Math.acos(cosA);

}
// test
var v1 = [4, 3, 4];
var v2 = [4, 4, 4];
console.log(angleBetweenTwoVectors(v1, v2) + " радиан");

Comments

[Алексей]

Из готовых решений для работы с 3d векторами для себя отметил:
evanw.github.io/lightgl.js/docs/vector.html
https://github.com/evanw/lightgl.js/blob/master/sr...