Разница в отсортированном списке

Question

У меня следующая проблема.

У меня есть набор элементов, которые я могу отсортировать по определенному алгоритму А. Сортировка хорошая, но очень дорогая.

Существует также алгоритм B, который может аппроксимировать результат A. Он намного быстрее, но порядок не будет точно таким же.

Принимая вывод A как «золотой стандарт», мне нужно получить значимую оценку погрешности, вызванной использованием B в тех же данных.

Может ли кто-нибудь предложить какой-нибудь ресурс, на который я мог бы посмотреть, чтобы решить мою проблему? Заранее спасибо!

РЕДАКТИРОВАТЬ:

По запросу: добавление примера для иллюстрации случая: если данные являются первыми 10 буквами алфавита,

A выводит: a, b, c, d, e, f, g, h, i, j

B выводит: a, b, d, c, e, g, h, f, j, i

Каковы возможные меры полученной ошибки, которые позволили бы мне настроить внутренние параметры алгоритма B, чтобы получить результат ближе к выходу A?

Answer 1

ро Спирмена

Я думаю, что вы хотите ранг коэффициент корреляции Спирмена . Используя векторы индекса [ранга] для двух сортировок (идеально A и приблизительно B), вы вычисляете корреляцию рангов rho в диапазоне от -1 (совершенно разные) до 1 (абсолютно одинаковые):

где d (i) - разница в рангах для каждого символа между A и B

Вы можете определить свою меру ошибки как расстояние D := (1-rho)/2.

Answer 2

Я бы определил наибольшее правильно упорядоченное подмножество.

                               +-------------> I
                               |   +--------->
                               |   |
A -> B -> D ----->  E  -> G -> H --|--> J
     |             ^ |             |    ^
     |             | |             |    |
     +------> C ---+ +-----------> F ---+

В вашем примере 7 из 10, поэтому алгоритм получает 0,7. Остальные комплекты имеют длину 6. Правильные порядковые оценки 1,0, обратный порядок 1 / n.

Я предполагаю, что это связано с количеством инверсий. x + y указывает x <= y (правильный порядок), а x - y указывает x> y (неправильный порядок).

A + B + D - C + E + G + H - F + J - I

Мы получаем почти такой же результат - 6 из 9 верны, набрав 0,667. Снова исправьте оценки порядка 1,0 и обратного порядка 0,0, и это может быть намного проще для вычисления.

Answer 3

Вы ищете какой-нибудь алгоритм, который вычисляет разницу на основе массива, отсортированного по A, и массива, отсортированного по B в качестве входных данных? Или вы ищете общий метод определения среднего значения массива при сортировке с помощью B?

Если первое, то я предлагаю что-то столь же простое, как расстояние от каждого элемента до того места, где оно должно быть (среднее будет лучше, чем сумма, чтобы удалить длину массива как проблему)

Если второе, то я думаю, мне нужно больше узнать об этих алгоритмах.

Answer 4

Трудно дать хороший общий ответ, потому что правильное решение для вас будет зависеть от вашего приложения.

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

double sortQuality = 1;
if (array.length > 1) {
   int inOrderPairCount = 0;
   for (int i = 1; i < array.length; i++) {
      if (array[i] >= array[i - 1]) ++inOrderPairCount;
   }
   sortQuality = (double) inOrderPairCount / (array.length - 1);
}

Answer 5

Расчет Среднеквадратическая ошибка может быть одним из многих возможных методов. Вот небольшой код Python.

def calc_error(out_A,out_B):
        # in    <= input
        # out_A <= output of algorithm A
        # out_B <= output of algorithm B

        rms_error = 0

        for i in range(len(out_A)):
            # Take square of differences and add
            rms_error +=  (out_A[i]-out_B[i])**2 

        return rms_error**0.5   # Take square root

>>> calc_error([1,2,3,4,5,6],[1,2,3,4,5,6])
0.0
>>> calc_error([1,2,3,4,5,6],[1,2,4,3,5,6]) # 4,3 swapped
1.414
>>> calc_error([1,2,3,4,5,6],[1,2,4,6,3,5]) # 3,4,5,6 randomized
2.44

Примечание: Взятие квадратного корня не обязательно, но взятие квадратов - просто различия могут сводиться к нулю. Я думаю, что функция calc_error выдает приблизительное количество неправильно размещенных пар, но у меня нет удобных инструментов программирования, поэтому:

Взгляните на этот вопрос.

Answer 6

вы можете попробовать что-нибудь, включающее расстояние Хэмминга