Код для вычисления "медианы пяти" в C#
Примечание: пожалуйста, не интерпретируйте это как "домашнее задание". Это просто вещь, которую мне интересно знать:)
Медиана пяти иногда используется в качестве упражнения при разработке алгоритма и, как известно, вычисляется с использованием только 6 сравнений.
Каков наилучший способ реализации этой "медианы пяти с использованием 6 сравнений" в C#? Кажется, что все мои попытки приводят к неуклюжему коду:(Мне нужен красивый и читаемый код, но при этом используется всего 6 сравнений.
public double medianOfFive(double a, double b, double c, double d, double e){
//
// return median
//
return c;
}
Примечание: я думаю, что я должен предоставить здесь "алгоритм":
Я обнаружил, что не могу объяснить алгоритм четко, как это сделал Азереаль в своем сообщении на форуме. Поэтому я буду ссылаться на его пост здесь. От http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085
Ну, я был поставлен этой проблемой в одном из моих заданий, и я обратился к этому форуму за помощью, но никакой помощи здесь не было. В конце концов я узнал, как это сделать.
Начните сортировку с четырьмя первыми элементами и упорядочите каждую пару (2 сравнения)
Сравните два нижних из каждой пары и исключите самый низкий из возможных (3 сравнения)
Добавьте в 5-й номер число без пары и сравните их (4 сравнения).
Сравните две младшие из двух новых пар и исключите нижнюю (5 сравнений)
Сравните один и младшую из последней пары, а нижнее число - это медиана.
Возможная медиана в парентезе
(54321)
5: 4 3: 2 2 сравнения
(4 <5 2 <3 1)
4:23 сравнения
2 (4 <5 3 1)
1: 3 4 сравнения
2 (4 <5 1 <3)
4:15 сравнения
1,2 (4 <5 3)
4:36 сравнения
1,2(3)4,5
Три медиана
РЕДАКТИРОВАТЬ: Как ваш запрос и чтобы я не получил больше голосов, это код C++, который я написал, чтобы найти медиану из пяти. Не против, это неловкость
double StageGenerator::MedianOfFive(double n1, double n2, double n3, double n4, double n5){
double *a = &n1, *b = &n2, *c = &n3, *d = &n4, *e = &n5;
double *tmp;
// makes a < b and b < d
if(*b < *a){
tmp = a; a = b; b = tmp;
}
if(*d < *c){
tmp = c; c = d; d = tmp;
}
// eleminate the lowest
if(*c < *a){
tmp = b; b = d; d = tmp;
c = a;
}
// gets e in
a = e;
// makes a < b and b < d
if(*b < *a){
tmp = a; a = b; b = tmp;
}
// eliminate another lowest
// remaing: a,b,d
if(*a < *c){
tmp = b; b = d; d = tmp;
a = c;
}
if(*d < *a)
return *d;
else
return *a;
}
Это должно быть более компактным, не так ли?
РЕДАКТИРОВАТЬ:
Как отметил @pablito в своем ответе. Встроенный List.Sort() не может выполнить это требование, поскольку он использует до 13 сравнений:]
12 ответов
По сути, это просто факт обмена и сортировки кода из вашего примера C++:
private static void Swap(ref double a, ref double b) {
double t = a;
a = b;
b = t;
}
private static void Sort(ref double a, ref double b) {
if (a > b) {
double t = a;
a = b;
b = t;
}
}
private static double MedianOfFive(double a, double b, double c, double d, double e){
// makes a < b and c < d
Sort(ref a, ref b);
Sort(ref c, ref d);
// eleminate the lowest
if (c < a) {
Swap(ref b, ref d);
c = a;
}
// gets e in
a = e;
// makes a < b
Sort(ref a, ref b);
// eliminate another lowest
// remaing: a,b,d
if (a < c) {
Swap(ref b, ref d);
a = c;
}
return Math.Min(d, a);
}
Я нашел этот пост интересным, и в качестве упражнения я создал это, ТОЛЬКО 6 сравнений и НИЧЕГО:
static double MedianOfFive(double a, double b, double c, double d, double e)
{
return b < a ? d < c ? b < d ? a < e ? a < d ? e < d ? e : d
: c < a ? c : a
: e < d ? a < d ? a : d
: c < e ? c : e
: c < e ? b < c ? a < c ? a : c
: e < b ? e : b
: b < e ? a < e ? a : e
: c < b ? c : b
: b < c ? a < e ? a < c ? e < c ? e : c
: d < a ? d : a
: e < c ? a < c ? a : c
: d < e ? d : e
: d < e ? b < d ? a < d ? a : d
: e < b ? e : b
: b < e ? a < e ? a : e
: d < b ? d : b
: d < c ? a < d ? b < e ? b < d ? e < d ? e : d
: c < b ? c : b
: e < d ? b < d ? b : d
: c < e ? c : e
: c < e ? a < c ? b < c ? b : c
: e < a ? e : a
: a < e ? b < e ? b : e
: c < a ? c : a
: a < c ? b < e ? b < c ? e < c ? e : c
: d < b ? d : b
: e < c ? b < c ? b : c
: d < e ? d : e
: d < e ? a < d ? b < d ? b : d
: e < a ? e : a
: a < e ? b < e ? b : e
: d < a ? d : a;
}
Благодарю. Я знаю, что ваши сообщения довольно старые, но это было полезно для моей проблемы.
Мне нужен был способ для вычисления медианы 5 регистров SSE/AVX (4 поплавка / 8 поплавков одновременно или 2 удвоения /4 удвоения одновременно):
без каких-либо условных переходов
только с инструкциями min/max
Если функции min/max запрограммированы для скалярных регистров с условными переходами, мой код не является оптимальным с точки зрения сравнений. Но если функции min/max закодированы с помощью соответствующих инструкций ЦП, мой код очень эффективен, поскольку ЦПУ не выполняет условный переход при выполнении.
template<class V>
inline V median(const V &a, const V &b, const V &c)
{
return max(min(a,b),min(c,max(a,b)));
}
template<class V>
inline V median(const V &a, const V &b, const V &c, const V &d, const V &e)
{
V f=max(min(a,b),min(c,d)); // discards lowest from first 4
V g=min(max(a,b),max(c,d)); // discards biggest from first 4
return median(e,f,g);
}
Это довольно уродливо и может использовать некоторый рефакторинг, но он явно просматривает все сравнения и свопы, чтобы вы могли видеть, что происходит.
public double medianOfFive(double a, double b, double c, double d, double e){
double median;
// sort a and b
if(a > b) // comparison # 1
{
double temp = a;
a = b;
b = temp;
}
// sort c and d
if(c > d) // comparison # 2
{
double temp = c;
c = d;
d = temp;
}
// replace the lower of a and c with e
// because the lowest of the first four cannot be the median
if(a < c) // comparison # 3
{
a = e;
// re-sort a and b
if(a > b) // comparison # 4
{
double temp = a;
a = b;
b = temp;
}
}
else
{
c = e;
// re-sort c and d
if(c > d) // comparison # 4
{
double temp = c;
c = d;
d = temp;
}
}
// eliminate a or c, because the lowest
// of the remaining four can't be the median either
if(a < c) // comparison #5
{
if(b < c) // comparison #6
{
median = c;
}
else
{
median = b;
}
}
else
{
if(d < a) // comparison #6
{
median = a;
}
else
{
median = d;
}
}
return median;
}
Просто чтобы проверить, сколько сравнений:
class MyComparable : IComparable
{
public static int NumberOfComparisons = 0;
public int NumPart { get; set; }
#region IComparable Members
public int CompareTo(object obj)
{
NumberOfComparisons++; //I know, not thread safe but just for the sample
MyComparable mc = obj as MyComparable;
if (mc == null)
return -1;
else
return NumPart.CompareTo(mc.NumPart);
}
#endregion
}
class Program
{
static void Main(string[] args)
{
List<MyComparable> list = new List<MyComparable>();
list.Add(new MyComparable() { NumPart = 5 });
list.Add(new MyComparable() { NumPart = 4 });
list.Add(new MyComparable() { NumPart = 3 });
list.Add(new MyComparable() { NumPart = 2 });
list.Add(new MyComparable() { NumPart = 1 });
list.Sort();
Console.WriteLine(MyComparable.NumberOfComparisons);
}
}
результат 13.
Для полноты, вопрос является частным случаем сортировочной сети, который Кнут (Art of Computer Programming, vol. 3) описывает очень подробно. Классическая статья К.Э. Бэтчера на эту тему краткая и заслуживает прочтения.
Here's a bit of a variant on the other answers, which provides on average from 3.33% to 66.67% improvement over 6 comparisons, and fully partitions the 5 elements around their median as a bonus at no extra cost.
It's possible to find the median of 5 distinct elements in an average of 5.8 comparisons (averaged over all permutations) by using median-of-3 and quickselect, using median-of-3 to select the pivot from a sample of 3 of the 5 elements. Median-of-3 partitions those three elements, which need not be recompared to the pivot when partitioning the remaining 2 elements. So far that's 4-5 comparisons to partition the 5 elements around one of the three middle elements (the median-of-3 cannot be either the minimum or maximum of 5). Up to 3 more comparisons may be necessary to partition the 5 elements around their median (which strictly speaking is more work than merely finding the median), for a total ranging from 4 to 7 comparisons, with (as mentioned) an average of 5.8 over all possible permutations of 5 distinct elements (fewer comparisons if the elements are not distinct). Note that this differs from the usual always-6-comparisons solutions, in that a few cases of distinct inputs may require as many as 7 comparisons, but on the other hand, most permutations of distinct inputs require no more than 6, and often fewer; moreover it is fairly easy to code to save comparisons for non-distinct inputs (only 2 comparisons are required if all inputs are equal; the code to save comparisons when inputs are not distinct using the usual 6-comparison method becomes rather convoluted (try it!), and without that it still takes 6 comparisons even when all inputs are equal).
Order statistics other than the median can be found this way: the 2nd smallest or 2nd largest can be found in on average slightly more (5.81666... comparisons), and of course it's possible to find the minimum or maximum with only 4 comparisons.
Based on that, and by request, here's a heavily commented function to return a pointer to the median of 5 elements, using a variadic comparison function. It's written in C, but it should work just as well in the quadrathorpe-y deviant or in sea ploose ploose. Note that this returns a pointer to the median-valued element only; it does not partition the elements (in fact it doesn't move any elements).
/* a virtual swap, preserving both pointers for later use */
#define VSWAP(ma,mb,mt) mt=ma,ma=mb,mb=mt
/* a virtual swap only preserving the first pointer */
#define VSWAP2(ma,mb,munused) ma=mb
/* virtual rotation to the left; reverse the first 3 args for right rotation */
#define ROTATE(ma,mb,mc,mt) (mt)=(ma),(ma)=(mb),(mb)=(mc),(mc)=(mt)
/* median of 5 elements, no data movement, minimum (average 5.8) comparisons */
/* This implementation minimizes the number of comparisons made (min. 2) when
elements compare equal.
*/
/* As no elements are moved, the elements are of course not partitioned around
the element pointed to by the returned pointer (this differs from selection
of the median via quickselect).
*/
/* Results are biased toward the middle: pc, then pb or pd, last pa or pe. */
/* The implementation is based on a simulation of quickselect using partition3
to select a pivot from the middle three elements, with partitioning by
skipping over the 3 partitioned elements. For distinct inputs, it uses on
average 5.8 comparisons (averaged over all permutations of 5 distinct
elements); fewer for inputs with equal elements. That's an improvement of
about 3% over the usual 6-comparison implementation of median-of-5.
*/
void *fmed5(void *pa, void *pb, void *pc, void *pd, void *pe,
int(*compar)(const void *,const void *))
{
void *t;
int c, d;
/* First compare the 3 middle elements to determine their relative
ordering; pb will point to the minimum, pc to the median, and pd to
the maximum of the three.
*/
/* Ternary median-of-3, biased toward middle element if possible, else
first element. Average 8/3 comparisons for 3 elements (distinct values)
= 0.889 comparisons/element
*/
c=compar(pb,pc); /* 1 */
if (0<c) { /* *pb,*pc out-of-order: *pb>*pc */
/* Before doing anything about pb,pc, compare *pc,*pd. */
d=compar(pc,pd); /* 2a */
if (0>d) { /* *pc<*pd: strictly in order */
/* But *pb might be either larger than or smaller than (or equal
to) *pd, so they may (i.e. unless it's known from the earlier
comparison of original *pc and *pd that *pb is larger than
both) have to be compared, Possibilities:
*pc<*pb<=*pd (virtual swap of pb,pc corrects relationship)
*pc<*pd<*pb (virtual rotation to the left corrects it)
*/
c=compar(pb,pd); /* 3a (if needed) */
if (0<c) { /* *pc < *pd < *pb */
ROTATE(pb,pc,pd,t);
} else { /* *pc < *pb <= *pd */
VSWAP(pb,pc,t);
}
} else { /* *pd==*pc<*pb or reversed ordering: *pd<*pc<*pb */
VSWAP(pb,pd,t); /* one (virtual) swap takes care of it */
} /* *pc:*pd comparisons results if-else */
/* Note that if pc,pd compare equal, pc remains as the chosen
median (biased toward the middle element).
*/
} else if (0==c) { /* *pb,*pc compare equal */
/* Either pb or pc can be taken as the median; bias here is towards
pc, which is already in the middle position. But pd might be
the minimum of the three or the maximum (or it may also be equal
to both pb and pc).
*/
d=compar(pb,pd); /* 2b */
if (0<d) { /* pb,pd are out-of-order */
VSWAP(pb,pd,t);
}
} else { /* *pb,*pc in strict order: *pb < *pc; how about *pc,*pd? */
d=compar(pc,pd); /* 2c */
if (0<d) { /* *pc,*pd are strictly out-of-order: *pd < *pc */
/* But *pb might be either larger than or smaller than (or equal
to) *pd, so they may (i.e. unless it's known from the earlier
comparison of original *pc and *pd that *pb is larger than
both) have to be compared, Possibilities:
*pb<=*pd<*pc (virtual swap of pc,pd corrects relationship)
*pd<*pb<*pc (virtual rotation to the right corrects it)
*/
c=compar(pb,pd); /* 3b (if needed) */
if (0<c) { /* *pd < *pb < *pc */
ROTATE(pd,pc,pb,t);
} else { /* *pc < *pb <= *pd */
VSWAP(pc,pd,t);
}
} /* *pc:*pd comparisons results if-else */
/* Note that if pc,pd compare equal, pc remains as the chosen
median (biased toward the middle element).
*/
} /* *pb:*pc comparisons results if-else chain */
/* Now pb points to the minimum of pb,pc,pd; pc to the median, and pd
to the maximum.
*/
/* Special case: if all three middle elements compare equal (0==c==d),
any one can be returned as the median of 5, as it's impossible for
either of the other two elements to be the median (unless of course
one or both of them also compares equal to pb,pc,pd, in which case
returning any of pb,pc,pd is still correct). Nothing more needs to
be done in that case.
*/
if ((0!=c)||(0!=d)) { /* Not all three of pb,pc,pd compare equal */
int e;
/* Compare pa and pe to pc. */
e=compar(pa,pc); /* 3c or 4a (iff needed) */
/* If three (or more) of the four elements so far compared are
equal, any of those equal-comparing elements can be chhosen as
the median of 5. If all five elements were arranged in order,
one of the three equal-comparing elements would necessarily be
in the middle (at most both of the remaining elements might be
either larger or smaller than the equal elements). So if pa
compares equal to pc and pc also compared equal to pb or to pd,
nothing more need be done; pc can be considered as the median of
five.
*/
if ((0!=e)||(0!=c)||(0!=d)) { /* no three elements compare equal */
int f;
f=compar(pe,pc); /* 4b or 5a (iff needed) */
/* Check again for three equal comparisons to avoid doing any
unnecessary additional work.
*/
if (
(0!=f) /* also not equal; still not three */
||
( /* 0==f && */
((0!=c)&&(0!=d)) /* at most e and f; not three */
||
((0!=c)&&(0!=e)) /* at most d and f; not three */
||
((0!=d)&&(0!=e)) /* at most c and f; not three */
)
) {
/* Possibilites are that:
one of *pa,*pe is less than (or equal to) *pc and one
is greater than (or equal to) *pc; *pc is the median
of five.
*pa and *pe are both less than *pc; the median of five
is then the maximum of *pa,*pb,*pe (*pc and *pd are
at least as large as those three). The ordering of
those 3 elements has not been established, and it
will take two additional comparisons to do so.
*pa and *pe are both greater than *pc; the median of
five is the minimum of *pa,*pd,*pe (neither *pb nor
*pc can be larger than any of those three).
*/
if ((0<e)&&(0<f)) { /* *pa,*pe both > *pc; median of five is
the minimum of *pa,*pe,*pd
*/
/* Bias towards *pd (originally closest of these three
to the middle. Neither *pa nor *pe has yet been
compared to *pd.
*/
e=compar(pa,pe); /* 5b or 6a (iff needed) */
if (0<e) { /* *pe is smaller */
f=compar(pd,pe); /* 6b or 7a (iff needed) */
if (0<f) { /* *pe is smaller */
VSWAP2(pc,pe,t);
} else { /* *pd is smaller or *pd==*pe */
VSWAP2(pc,pd,t);
}
} else { /* *pa==*pe or *pa is smaller */
f=compar(pd,pa); /* 6c or 7b (iff needed) */
if (0<f) { /* *pa is smaller */
VSWAP2(pc,pa,t);
} else { /* *pd is smaller or *pd==*pa */
VSWAP2(pc,pd,t);
}
}
} else if ((0>e)&&(0>f)) { /* *pa,*pe both < *pc; median of
five is the maximum of *pa,*pb,*pe
*/
/* Bias towards *pb (originally closest of these three
to the middle. Neither *pa nor *pe has yet been
compared to *pb.
*/
e=compar(pa,pe); /* 5c or 6d (iff needed) */
if (0<e) { /* *pa is larger */
f=compar(pa,pb); /* 6e or 7c (iff needed) */
if (0<f) { /* *pa is larger */
VSWAP2(pc,pa,t);
} else { /* *pb is larger or *pa==*pb */
VSWAP2(pc,pb,t);
}
} else { /* *pe is larger or *pa==*pe */
f=compar(pe,pb); /* 6f or 7d (iff needed) */
if (0<f) { /* *pe is larger */
VSWAP2(pc,pe,t);
} else { /* *pb is larger or *pe==*pb */
VSWAP2(pc,pb,t);
}
} /* *pa:*pe results if-else */
} /* median of five: minimum or maximum of three if-else */
} /* not three equal elements among five */
} /* not three equal elements among four */
} /* not three equal elements among three */
return pc;
}
Это должно сделать это
private Double medianofFive(double[] input)
{
Double temp;
if (input[0] > input[1])//#1 - sort First and Second
{
temp = input[0];
input[0] = input[1];
input[1] = temp;
}
if (input[2] > input[3])//#2 sort Third and Fourth
{
temp = input[2];
input[2] = input[3];
input[3] = temp;
}
// replace the smaller of first and third with 5th, then sort
int smallerIndex = input[0] < input[2] ? 0 : 2;//#3
input[smallerIndex] = input[4];
//sort the new pair
if(input[smallerIndex]>input[smallerIndex+1])//#4
{
temp = input[smallerIndex];
input[smallerIndex] = input[smallerIndex+1];
input[smallerIndex+1] = temp;
}
//compare the two smaller numbers
// then compare the smaller of the two's partner with larger of the two
// the smaller of THOSE two is the median
if (input[2] > input[0])
//#5
{
temp = input[2] > input[1] ? input[1] : input[2];//#6
}
else
{
temp = input[0] > input[3] ? input[3] : input[0];//#6
}
return temp;
}
Кодирование на самом деле не мое, но вот алгоритм, который я бы использовал, выраженный на естественном языке. Обозначим эти пять чисел через a , b , c , d и e .
Сравните a и b , c и d . WLOG пусть a < b, c < d. (пока 2 сравнения)
Сравните а и в . WLOG пусть a < c. (3)
Сравните б и е . (4) Обратите внимание, что b используется вместо d (и их нельзя поменять местами), потому что b является «двойником» меньшего из a и c .
Случай 1: пусть b < e.
____Сравните b и c — большее значение является медианой. (5)
Случай 2: пусть b > e.
____Сравните a и e . (5)
____Случай 2.1: пусть a < e.
________Сравните c и e — большее значение является медианой. (6)
____Случай 2.2: пусть a > e.
________Сравните b и c — меньшее значение является медианой. (6)
(Форматирование уродливое ik >.<)
-- In Haskell the solution could look like
import Data.Function
median5By pred [a,b,c,d,e] = fst $ merge2 c' d' where
merge2 = merge2By pred
merge2By pred x y = if x `pred` y then (x,y) else (y,x)
((_,b'), de ) = merge2By (pred `on` fst) (merge2 a b) (merge2 d e)
((_,c'),(d',_)) = merge2By (pred `on` fst) (merge2 b' c) de
main = print $ median5By (<) [2,5,4,1,3]
Интересно сколько сравнений в образце MSDN...
public static double Median(this IEnumerable<double> source) {
if (source.Count() == 0) throw new InvalidOperationException("Cannot compute median for an empty set.");
var sortedList = from number in source
orderby number
select number;
int itemIndex = (int)sortedList.Count() / 2;
if (sortedList.Count() % 2 == 0) {
// Even number of items.
return (sortedList.ElementAt(itemIndex) + sortedList.ElementAt(itemIndex - 1)) / 2; } else {
// Odd number of items.
return sortedList.ElementAt(itemIndex); }
}