Уменьшение расстояния: формула расстояния
ПРИМЕЧАНИЕ: Этот ответ был записан, когда.NET 2.0 была текущей версией. Это больше не может относиться к более поздним версиям.
String.Format использование StringBuilder внутренне:
public static string Format(IFormatProvider provider, string format, params object[] args)
{
if ((format == null) || (args == null))
{
throw new ArgumentNullException((format == null) ? "format" : "args");
}
StringBuilder builder = new StringBuilder(format.Length + (args.Length * 8));
builder.AppendFormat(provider, format, args);
return builder.ToString();
}
вышеупомянутый код является отрывком от mscorlib, таким образом, вопрос становится, "StringBuilder.Append() быстрее, чем StringBuilder.AppendFormat()"?
, не сравнивая я, вероятно, сказал бы, что пример кода выше выполнит более быстро использование .Append(). Но это - предположение, попытайтесь сравнить и/или представить два для получения надлежащего сравнения.
Этот парень, Jerry Dixon, сделал некоторое сравнительное тестирование:
http://jdixon.dotnetdevelopersjournal.com/string_concatenation_stringbuilder_and_stringformat.htm
Обновленный:
Печально ссылка выше с тех пор умерла. Однако существует все еще копия на Пути Обратная Машина:
В конце дня это зависит, будет ли Ваше строковое форматирование названным повторяющимся образом, т.е. Вы переделываете некоторую серьезную обработку текста 100's мегабайтов текста, или называют ли это, когда пользователь нажимает кнопку время от времени. Если Вы не делаете некоторое огромное задание пакетной обработки, я придерживался бы Строки. Формат, это помогает удобочитаемости кода. Если Вы подозреваете, что узкое место перфекта тогда прикрепляет профилировщика на Ваш код и видит, где это действительно.
5 ответов
Даже для 2d расстояний неверно, что минимум a ^ 2 + b ^ 2 находится в том же месте, что и минимум а + b . Конечно, это может быть верно для очень специфического ограниченного набора проблем. Если вы пытаетесь найти контрпример, обратите внимание на то, что квадраты чрезмерно перетягивают большие расстояния; если вы построите пример с минимумом, содержащим хотя бы одно большое расстояние, у вас есть хороший шанс, что сумма квадратов будет иметь другой минимум.
Какую проблему вы пытаетесь решить? Конечно, вполне возможно, что для вашей проблемы различие не имеет значения; или что минимум суммы квадратов - более дешевая задача и более простое первое приближение к окончательному решению.
Это может быть очевидно, но если различные расстояния не связаны , то для каждого отдельного расстояния квадрат минимален, когда расстояние равно, и, таким образом, сумма несвязанных расстояний минимальна там, где сумма квадратов равна.
Edit Post update : Вы пытаетесь найти центроид с ограничением, что он лежит на определенной линии. Итак, в общих чертах: у вас только одна степень свободы, и вы можете проводить простую дифференциацию. Однако результат будет иметь сумму дробей со значением sqrt в знаменателе; решить это алгебраически в общем случае невозможно (AFAIK). Я не уверен на 100%, но я думаю, вам повезло в том, что ваша сумма расстояний не имеет локального минимума, кроме глобального; в этом случае метод Ньютона сойдется надежно и быстро.
Итак,
Вы недостаточно проверили. Минимизация D1 + D2 - это не то же самое, что минимизация D1 ^ 2 + D2 ^ 2 в целом, хотя это может быть для некоторых конкретных D1 и D2 .
ИЗМЕНИТЬ после того, как вы напомнили мне, что вас интересуют только расстояния в плоскости:
В случае, когда D1 и D2 - расстояния в геометрическая плоскость, точка на плоскости, которая минимизирует D1 ^ 2 + D2 ^ 2 , также минимизирует D1 + D2 , но
он ломается с тремя точками.
Попробуйте это с тремя точками (0,0), (1,0) и (10, 0):
Минимизация | x | + | x-1 | + | x-10 | - это не то же самое, что минимизация x ^ 2 + (x-1) ^ 2 + (x-10) ^ 2
Вам немного неясно, откуда взялись ваши D1, D2, .. Dn, но я предполагаю, что у вас есть набор точек P1, P2, ..., Pn в плоскости xy, и вы хотите найти точку p0 = (x0, y0), которая минимизирует сумму расстояний между каждой точкой P1 .. Pn и p0.
Итак, ваши D1 .. Dn на самом деле:
D1 = sqrt((x0-x1)^2 + (y0-y1)^2)
D2 = sqrt((x0-x2)^2 + (y0-y2)^2)
..
Dn = sqrt((x0-xn)^2 + (y0-yn)^2)
где x1 .. xn и y1 ... yn известны, а x0, y0 неизвестны. И вы хотите минимизировать D0 :
D0 = D1+D2+......+Dn
Если это верно, вы хотите найти геометрическую медиану . Статья в Википедии должна помочь вам найти решение.
Обновление:
в комментарии вы указываете, что точка P0 должна находиться на заданной строке (пожалуйста, добавьте это в исходную формулировку проблемы). Это означает, что вы можете переписать y0 как функцию x0 :
y0 = a*x0 + b
где указаны a и b. Это снижает сложность ваших функций расстояния и делает вывод серьезной возможностью.
D1 = sqrt((x0-x1)^2 + (ax0+b-y1)^2)
D2 = sqrt((x0-x2)^2 + (ax0+b-y2)^2)
..
Dn = sqrt((x0-xn)^2 + (ax0+b-yn)^2)
Но если количество точек n не слишком велико, я бы просто выполнил поиск * методом перебора в области линия, где x близко к среднему значению x1 .. xn, чтобы найти точку x-, y0, которая минимизирует D0.
Контрпример:
d1 = 1 & d2 = 10 (sum = 11 & sumOfSquares = 101)
d1 = 6 & d2 = 6 (sum = 12 & sumOfSquares = 72)
Сумма увеличилась, но сумма квадратов уменьшилась.
Your problem is the minimization of an objective function given by some norm of your distances. The distances are Euclidean, and as such represent the Euclidean norm between two vectors. In order to understand the difference between minimizing sum(ai) over sum(ai^2) I recommend you read the Wikipedia entry on Norms; bottom line, notice the following:
||x||2 <= ||x||1 <= sqrt(n)||x||2
||x||_\infty <= ||x||2 <= sqrt(n)||x||_\infty
||x||_\infty <= ||x||1 <= n||x||_\infty
Where ||x||2 is the Euclidean norm, ||x||1 is sum(abs(x1)+abs(x2)+...+abs(xn)), and ||x||_\infty is max(abs(x1),abs(x2),...,abs(xn)). In your case all the numbers are positive (you already have the Euclidean norm, so you can seee the difference.
It may also be helpful (though much more difficult to fully grasp) to read the fantastic book by Golub and Van Loan, Matrix Computations.