Алгоритм для оценки монотонности массива (т.е. оценка “sortedness” массива)
Править: Ничего себе, много больших ответов. Да, я использую это в качестве функции фитнеса для оценки в некотором роде качества, выполненного генетическим алгоритмом. Таким образом, стоимость оценки важна (т.е. это должно быть быстро, предпочтительно O(n).)
Как часть приложения AI, с которым я играю, я хотел бы смочь оценить массив кандидата целых чисел на основе его монотонности, иначе его "sortedness". В данный момент я использую эвристику, которая вычисляет самое долгое отсортированное выполнение и затем делит это на длину массива:
public double monotonicity(int[] array) {
if (array.length == 0) return 1d;
int longestRun = longestSortedRun(array);
return (double) longestRun / (double) array.length;
}
public int longestSortedRun(int[] array) {
if (array.length == 0) return 0;
int longestRun = 1;
int currentRun = 1;
for (int i = 1; i < array.length; i++) {
if (array[i] >= array[i - 1]) {
currentRun++;
} else {
currentRun = 1;
}
if (currentRun > longestRun) longestRun = currentRun;
}
return longestRun;
}
Это - хорошее начало, но ему не удается принять во внимание возможность, что могут быть "глыбы" отсортированных подпоследовательностей. Например:
{ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9}
Этот массив делится в три отсортированных подпоследовательности. Мой алгоритм оценит его как отсортированных только 40%, но интуитивно, это должно получить более высокий счет, чем это. Существует ли стандартный алгоритм для этого вида вещи?
9 ответов
Попробуйте выполнить следующие действия: http://zanedp.livejournal.com/201222.html
Вот последовательность, которая преобразует мой файл LaTeX в обычный текст:
$ latex file.tex
$ catdvi -e 1 -U file.dvi | sed -re "s/\[U\+2022\]/*/g" | sed -re "s/([^^[:space:]])\s+/\1 /g" > file.txt
Параметр -e 1 catdvi сообщает ему о выводе ASCII. Если вместо 1 используется 0, будет выведен Юникод. Юникод будет включать все специальные символы, такие как пули, эмдиши и греческие буквы. Он также включает лигатуры для некоторых буквенных комбинаций, таких как «fi» и «fl». Вам это может не понравиться. Поэтому вместо этого используйте -e 1. Используйте параметр -U, чтобы вывести значение Юникода для неизвестных символов, чтобы их можно было легко найти и заменить.
Вторая часть команды находит последовательность [U + 2022], которая используется для обозначения символов маркеров (•) и заменяет их звездочкой (*).
Третья часть съедает все дополнительные пробелы catdvi, брошенные, чтобы сделать текст полностью выровненным, сохраняя места в начале строк (отступы).
После выполнения этих команд следует выполнить поиск последовательности [U + в TXT-файле, чтобы убедиться в отсутствии символов Юникода, которые не могут быть сопоставлены с ASCII, и исправить их.
-121--920956-Вы можете использовать некоторые карты/сокращения реализованы вручную. Также взгляните на swarmiji рамок.
«Распределенная вычислительная система, которая помогает писать и запускать код Clojure параллельно - между ядрами и процессорами»
-121--1364298-Я ожидаю, что выбор функции для использования очень сильно зависит от того, для чего вы намерены использовать ее. Основываясь на вашем вопросе, я думаю, что вы используете генетическую систему для создания программы сортировки, и это будет функция ранжирования. Если это так, то скорость исполнения имеет решающее значение. Исходя из этого, я уверен, что ваш алгоритм с самой длинной сортировкой будет работать довольно хорошо. Это звучит так, как будто это должно определить фитнес довольно хорошо.
Я полагаю, что tcl и Rexx были предназначены для этой цели.
-121--3774788-Чтобы легко протестировать код, необходимо сохранить разделение инициализации объекта.
т.е. в то время как в тестовых случаях у вас нет возможности протестировать некоторые определенные предметы.
как в объекте House, вы не хотите тестировать что-либо, связанное с объектом кухни. и ты хочешь проверить только сад. Таким образом, в то время как вы инициируете класс дома и инициируете объект в некоторых конструкторах или в getters, вы не будете кодировать хорошо, что будет поддерживать тестирование.
-121--1480650- Это кажется хорошим кандидатом на расстояние Левенштейна Дамерау-Левенштейна - количество свопов, необходимых для сортировки массива. Это должно быть пропорционально тому, насколько далеко каждый предмет находится в сортированном массиве.
Вот простой алгоритм рубина, который суммирует квадраты расстояний. Это кажется хорошей мерой сортировки - результат становится все меньше каждый раз, когда два элемента вне порядка меняются местами.
ap = a.sort
sum = 0
a.each_index{|i| j = ap.index(a[i])-i
sum += (j*j)
}
dist = sum/(a.size*a.size)
Что-то вроде этого? http://en.wikipedia.org/wiki/rank_Correlation
Это высоко зависит от того, что вы намереваетесь использовать меру для, но один простой способ сделать это - прокормить массив в стандартный алгоритм сортировки и измерить, сколько операций (свопащих и / или сравнений) необходимо быть сделано для сортировки массива.
Включение GZIP в любом случае будет иметь гораздо больший эффект, чем минимизация HTML.
Минификация во время выполнения может повредить серверы (если не использовать кэширование). Возможно, во время развертывания рекомендуется минимизировать разметку Asp.Net. Таким образом, в репозитории кода по-прежнему имеется неминифицированная версия кода и на сервере. Подумайте о процессе развертывания, когда вы вызываете минификатор HTML (например, этот инструмент Дина Хьюма выглядит многообещающим) для всех файлов .aspx .
Попробуйте:
var img = document.getElementById('widgetField'),
style = img.currentStyle || window.getComputedStyle(img, false),
bi = style.backgroundImage.slice(4, -1);
Некоторые эксперименты с модификатором Ratcliff & Obershelp
>>> from difflib import SequenceMatcher as sm
>>> a = [ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9 ]
>>> c = [ 0, 1, 9, 2, 8, 3, 6, 4, 7, 5 ]
>>> b = [ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9 ]
>>> b.sort()
>>> s = sm(None, a, b)
>>> s.ratio()
0.69999999999999996
>>> s2 = sm(None, c, b)
>>> s2.ratio()
0.29999999999999999
Не слишком уверен, как это доказать.
Вычислить протяженность всех отсортированных подсиполеевых последовательностей, затем квадрат их и добавьте их. Если вы хотите откалибровать, сколько ENPHASIS вы нанесите наибольшее, используйте мощность, отличную от 2.
, я не уверен, что лучший способ нормализовать это по длине, может разделить его на длину в квадрате?
Я бы предложил смотреть на проблему проблему и раскрытие перестановок. Эти алгоритмы часто используются для поиска расстояния между двумя перестановками (личность и неверная строка). Эта мера расстояния должна учитывать больше комков в ценностях порядка, а также развороты (монотонно уменьшающиеся вместо увеличения подпоследовательности). Существуют также аппроксимации, которые являются полиномиальными временем [PDF] .
Это действительно все зависит от того, что число означает, и если эта дистанционная функция имеет смысл в вашем контексте.
Вот один, который я только что составил.
Для каждой пары соседних значений рассчитайте числовую разницу между ними. Если второй больше или равен первой, добавьте, что в отсортировано общее количество , в противном случае добавляйте в unsorted . Когда сделано, возьмите соотношение двух.
То, что вы, вероятно, ищете, это Кендалл Тау . Это однозначная функция расстояния пузырьковой сортировки между двумя массивами.Чтобы проверить, является ли массив «почти отсортированным», вычислите его Тау Кендалла относительно отсортированного массива.