ما هي أسرع طريقة ممكنة لفرز مجموعة من 7 الاعداد الصحيحه ؟
https://stackoverflow.com/questions/1415173
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هذا هو جزء من البرنامج الذي يحلل الصعاب من لعبة البوكر ، على وجه التحديد "تكساس هولدم".لدي برنامج أنا سعيد مع, ولكنه يحتاج إلى بعض التحسينات الصغيرة إلى أن تكون مثالية.
يمكنني استخدام هذا النوع (وغيرها طبعا):
type
T7Cards = array[0..6] of integer;
هناك نوعان من الأشياء حول هذه المجموعة التي قد تكون مهمة عند اتخاذ قرار بشأن كيفية ترتيب:
- كل عنصر هو قيمة من 0 إلى 51.أي قيم أخرى ممكنة.
- لا توجد التكرارات.أبدا.
مع هذه المعلومات, ما هو بالتأكيد أسرع طريقة حل هذه المصفوفة ؟ أنا استخدم دلفي ، لذلك رمز باسكال سيكون أفضل ، ولكن أستطيع أن أقرأ ج الزائفة ، وإن كان أكثر قليلا ببطء :-)
في هذه اللحظة يمكنني استخدام فرز سريع ، ولكن الشيء المضحك هو أن هذا هو تقريبا أي أسرع من bubblesort!ممكن لأن عدد قليل من البنود.الفرز التهم ما يقرب من 50% من إجمالي وقت تشغيل الأسلوب.
تحرير:
ميسون ويلر سئل لماذا من الضروري تحسين.سبب واحد هو أن الطريقة سوف يطلق 2118760 مرات.
الأساسية البوكر المعلومات:جميع اللاعبين يتم التعامل مع اثنين من بطاقات (جيب) ثم خمس بطاقات يتم التعامل الجدول (3 الأولى تسمى بالتخبط القادم هو بدوره والأخير هو النهر.كل لاعب يختار أفضل خمسة بطاقات لتعويض اليد)
إذا كان لدي اثنين من بطاقات جيب P1 و P2, وسوف تستخدم التالية حلقات لتوليد جميع التوليفات الممكنة:
for C1 := 0 to 51-4 do
if (C1<>P1) and (C1<>P2) then
for C2 := C1+1 to 51-3 do
if (C2<>P1) and (C2<>P2) then
for C3 := C2+1 to 51-2 do
if (C3<>P1) and (C3<>P2) then
for C4 := C3+1 to 51-1 do
if (C4<>P1) and (C4<>P2) then
for C5 := C4+1 to 51 do
if (C5<>P1) and (C5<>P2) then
begin
//This code will be executed 2 118 760 times
inc(ComboCounter[GetComboFromCards([P1,P2,C1,C2,C3,C4,C5])]);
end;
وأنا أكتب هذا وأنا لاحظت شيء واحد أكثر من ذلك:آخر خمس عناصر المصفوفة سوف تكون دائما مرتبة ، حتى انها مجرد مسألة وضع أول اثنين من عناصر في الموقف الصحيح في الصفيف.التي يجب تبسيط الأمور قليلا.
لذا ، فإن السؤال الجديد هو:ما هي أسرع طريقة ممكنة لفرز مجموعة من 7 الصحيحه عند آخر 5 عناصر فرز بالفعل.وأعتقد أن هذا يمكن حلها مع بعض (?) إذا و مقايضة :-)
المحلول
أنا لا أعرف الكثير عن تكساس هولدم:لا يهم ما تناسب P1 و P2 هي أم أنه فقط يهم إذا كانت من نفس النوع أو لا ؟ إلا إذا كان دعوى(P1)==بدلة(P2) المسائل, ثم هل يمكن أن تفصل بين حالتين, لديك فقط 13x12/2 الاحتمالات المختلفة P1/P2, و يمكنك بسهولة precalculate طاولة الحالتين.
خلاف ذلك, أود أن أقترح شيئا من هذا القبيل:
(* C1 < C2 < P1 *)
for C1:=0 to P1-2 do
for C2:=C1+1 to P1-1 do
Cards[0] = C1;
Cards[1] = C2;
Cards[2] = P1;
(* generate C3...C7 *)
(* C1 < P1 < C2 *)
for C1:=0 to P1-1 do
for C2:=P1+1 to 51 do
Cards[0] = C1;
Cards[1] = P1;
Cards[2] = C2;
(* generate C3...C7 *)
(* P1 < C1 < C2 *)
for C1:=P1+1 to 51 do
for C2:=C1+1 to 51 do
Cards[0] = P1;
Cards[1] = C1;
Cards[2] = C2;
(* generate C3...C7 *)
(هذا هو مجرد مظاهرة بطاقة واحدة P1, سيكون لديك لتوسيع أن P2, ولكن أعتقد أنها واضحة.على الرغم من أنه سوف يكون هناك الكثير من الكتابة...) بهذه الطريقة الفرز لا تأخذ أي وقت من الأوقات على الإطلاق.ولدت التباديل أمرت بالفعل.
نصائح أخرى
من أجل مجموعة صغيرة جدا, نوع الإدراج وعادة ما يمكن أن تغلب فرز سريع لأنه يحتوي على النفقات العامة منخفضة جدا.
WRT تحرير الخاص بك, إذا كنت بالفعل في الغالب في ترتيب (آخر 5 عناصر هي بالفعل فرز) ، نوع الإدراج هو بالتأكيد الطريق للذهاب.في تقريبا-فرز مجموعة من البيانات سوف تغلب فرز سريع في كل مرة ، حتى بالنسبة مجموعات كبيرة.(خاصة بالنسبة مجموعات كبيرة!هذا هو نوع الإدراج أفضل سيناريو و فرز سريع هو أسوأ الأحوال.)
لا أعرف كيف يتم تنفيذ هذا ولكن ما يمكنك فعله هو مجموعة من 52 بدلا من 7 ، فقط ضع البطاقة في فتحة مباشرة عندما تحصل عليه لأن لا يمكن أبدا أن تكون التكرارات ، وبهذه الطريقة لن تضطر إلى نوع الصفيف.هذا قد يكون أسرع اعتمادا على كيفية استخدامها.
هناك فقط 5040 التباديل من 7 عناصر.يمكنك programmaticaly توليد البرنامج الذي يجد أحد ممثلة المدخلات الخاصة بك في أقل عدد ممكن من المقارنات.وسوف تكون شجرة كبيرة من if-then-else تعليمات كل مقارنة ثابت زوج من العقد ، على سبيل المثال if (a[3]<=a[6]).
الجزء صعبة هو البت فيها 2 من العناصر مقارنة في عقدة الداخلية.لهذا يجب أن تأخذ في الاعتبار نتائج المقارنات في العقد الجد من الجذر إلى عقدة معينة (على سبيل المثال a[0]<=a[1], not a[2]<=a[7], a[2]<=a[5]) و مجموعة من التباديل الممكنة التي ترضي المقارنات.قارن زوج من العناصر التي يقسم المجموعة إلى أجزاء متساوية قدر الإمكان (تقليل حجم أكبر).
مرة واحدة كنت قد التقليب ، فمن تافهة نوعا ما في الحد الأدنى من مجموعة من مقايضة.
منذ آخر 5 بنود هي بالفعل فرز قانون يمكن أن تكون مكتوبة فقط لإعادة الأولى 2 البنود.منذ كنت تستخدم باسكال, لقد كتبت و اختبار خوارزمية الفرز التي يمكن تنفيذ 2,118,760 مرات في حوالي 62 ميلي ثانية.
procedure SortT7Cards(var Cards: T7Cards);
const
CardsLength = Length(Cards);
var
I, J, V: Integer;
V1, V2: Integer;
begin
// Last 5 items will always be sorted, so we want to place the first two into
// the right location.
V1 := Cards[0];
V2 := Cards[1];
if V2 < V1 then
begin
I := V1;
V1 := V2;
V2 := I;
end;
J := 0;
I := 2;
while I < CardsLength do
begin
V := Cards[I];
if V1 < V then
begin
Cards[J] := V1;
Inc(J);
Break;
end;
Cards[J] := V;
Inc(J);
Inc(I);
end;
while I < CardsLength do
begin
V := Cards[I];
if V2 < V then
begin
Cards[J] := V2;
Break;
end;
Cards[J] := V;
Inc(J);
Inc(I);
end;
if J = (CardsLength - 2) then
begin
Cards[J] := V1;
Cards[J + 1] := V2;
end
else if J = (CardsLength - 1) then
begin
Cards[J] := V2;
end;
end;
استخدام مين نوعا ما.البحث عن الحد الأدنى و الأقصى عنصر في وقت واحد و مكان لهم في الناتج الصفيف.كرر ثلاث مرات.(تحرير:لا, لن أحاول قياس سرعة نظريا :_))
var
cards,result: array[0..6] of integer;
i,min,max: integer;
begin
n=0;
while (n<3) do begin
min:=-1;
max:=52;
for i from 0 to 6 do begin
if cards[i]<min then min:=cards[i]
else if cards[i]>max then max:=cards[i]
end
result[n]:=min;
result[6-n]:=max;
inc(n);
end
for i from 0 to 6 do
if (cards[i]<52) and (cards[i]>=0) then begin
result[3] := cards[i];
break;
end
{ Result is sorted here! }
end
هذا هو أسرع طريقة:منذ 5-بطاقة فرز القائمة بالفعل ، فرز اثنين من قائمة بطاقة (قارن & مبادلة) ، ثم دمج القائمتين التي O(k * (5+2).في هذه الحالة (ك) تكون عادة 5:اختبار الحلقة(1) قارن(2) نسخ(3), المدخلات القائمة الزيادة(4) و القائمة إخراج الزيادة(5).هذا هو 35 + 2.5.رمي في حلقة التهيئة و يمكنك الحصول على 41.5 البيانات ، المجموع.
هل يمكن أيضا انبسط الحلقات التي من شأنها أن توفر لك ربما 8 أو بيانات أو التنفيذ ، ولكن جعل كل الروتين حوالي 4-5 مرات أطول مما قد تعبث مع التعليمات الخاصة بك ذاكرة التخزين المؤقت ضرب النسبة.
نظرا P(0 إلى 2), C(0 إلى 5) نسخ إلى ساعة(0 إلى 6) مع ج() بالفعل فرز (ترتيب تصاعدي):
If P(0) > P(1) Then
// Swap:
T = P(0)
P(0) = P(1)
P(1) = T
// 1stmt + (3stmt * 50%) = 2.5stmt
End
P(2), C(5) = 53 \\ Note these are end-of-list flags
k = 0 \\ P() index
J = 0 \\ H() index
i = 0 \\ C() index
// 4 stmt
Do While (j) < 7
If P(k) < C(I) then
H(j) = P(k)
k = k+1
Else
H(j) = C(i)
j = j+1
End if
j = j+1
// 5stmt * 7loops = 35stmt
Loop
و لاحظ أن هذا هو أسرع من خوارزمية أخرى من شأنها أن تكون "أسرع" إذا كان حقا فرز جميع بطاقات 7:استخدام قليلا-قناع(52) إلى الخريطة بت كل مجموعة 7 بطاقات في ذلك مجموعة من 52 ورقة (بت-قناع) ثم مسح بت قناع لكي تبحث عن 7 بت التي تم تعيينها.أن يأخذ 60-120 البيانات في أحسن الأحوال (ولكن لا يزال أسرع من أي دولة أخرى الفرز النهج).
لمدة سبعة أرقام الأكثر كفاءة خوارزمية موجود فيما يتعلق عدد من المقارنات فورد جونسون.في الواقع ، ويكيبيديا المراجع ورقة العثور بسهولة على جوجل, التي تدعي فورد جونسون أفضل لمدة تصل إلى 47 الأرقام.للأسف المراجع فورد جونسون ليست من السهل العثور على خوارزمية يستخدم بعض هياكل البيانات المعقدة.
فإنه يظهر على فن برمجة الكمبيوتر ، المجلد 3 ، دونالد كانوث ، إذا كان لديك الوصول إلى ذلك الكتاب.
هناك ورقة الذي يصف FJ و أكثر كفاءة الذاكرة الإصدار هنا.
على أية حال, لأن الذاكرة النفقات العامة من أن الخوارزمية ، أشك في أنه سيكون من قيمتها في حين الخاص بك على الأعداد الصحيحة ، حيث أن تكلفة مقارنة عددين هي رخيصة نوعا ما بالمقارنة مع تكلفة تخصيص الذاكرة والتلاعب المؤشرات.
الآن أنت ذكرت أن 5 بطاقات فرز بالفعل, و تحتاج فقط إلى إدراج اثنين.يمكنك أن تفعل هذا مع نوع الإدراج أكثر كفاءة مثل هذا:
Order the two cards so that P1 > P2
Insert P1 going from the high end to the low end
(list) Insert P2 going from after P1 to the low end
(array) Insert P2 going from the low end to the high end
كيف يمكنك أن تفعل ذلك سوف تعتمد على بنية البيانات.مع مجموعة سوف تكون مبادلة كل عنصر ، لذلك المكان P1 في 1st, P2 و 7 (أمر عال إلى منخفض), ثم مبادلة P1 و من ثم P2 أسفل.مع قائمة, تحتاج فقط لإصلاح المؤشرات حسب الاقتضاء.
ومع ذلك أكثر من مرة بسبب خصوصية من التعليمات البرمجية الخاصة بك ، هو حقا أفضل إذا كنت تتبع nikie اقتراح فقط تولد عن الحلقات apropriately ل كل الاختلاف التي P1 و P2 يمكن أن تظهر في القائمة.
على سبيل المثال نوع P1 و P2 بحيث P1 < P2.دعونا جعل Po1 و Po2 موقف من 0 إلى 6 من P1 و P2 على القائمة.ثم القيام بذلك:
Loop Po1 from 0 to 5
Loop Po2 from Po1 + 1 to 6
If (Po2 == 1) C1start := P2 + 1; C1end := 51 - 4
If (Po1 == 0 && Po2 == 2) C1start := P1+1; C1end := P2 - 1
If (Po1 == 0 && Po2 > 2) C1start := P1+1; C1end := 51 - 5
If (Po1 > 0) C1start := 0; C1end := 51 - 6
for C1 := C1start to C1end
// Repeat logic to compute C2start and C2end
// C2 can begin at C1+1, P1+1 or P2+1
// C2 can finish at P1-1, P2-1, 51 - 3, 51 - 4 or 51 -5
etc
ثم استدعاء دالة يمر Po1, Po2, P1, P2, C1, C2, C3, C4, C5, و هذه الدالة بإرجاع جميع التباديل الممكنة على أساس Po1 و Po2 (وهذا 36 مجموعات).
شخصيا, أعتقد أن هذا هو أسرع يمكنك الحصول على.يمكنك تجنب تماما الحاجة إلى طلب أي شيء, لأن البيانات التي سيتم طلبها مسبقا.كنت تحمل في بعض المقارنات على أي حال لحساب يبدأ وينتهي ، ولكن تكلفتها التقليل كما معظمهم سوف يكون على الأبعد الحلقات ، حتى لا تتكرر كثيرا.وأنها يمكن أن تكون حتى أكثر الأمثل في تكلفة أكثر رمز الازدواجية.
لمدة 7 عناصر ، هناك فقط عدد قليل من الخيارات.يمكنك بسهولة كتابة المولدات التي تنتج طريقة لفرز جميع التوليفات الممكنة من 7 عناصر.شيء مثل هذا الأسلوب لمدة 3 عناصر:
if a[1] < a[2] {
if a[2] < a[3] {
// nothing to do, a[1] < a[2] < a[3]
} else {
if a[1] < a[3] {
// correct order should be a[1], a[3], a[2]
swap a[2], a[3]
} else {
// correct order should be a[3], a[1], a[2]
swap a[2], a[3]
swap a[1], a[3]
}
}
} else {
// here we know that a[1] >= a[2]
...
}
طبعا طريقة 7 عناصر ستكون أكبر ، ولكن ليس من الصعب أن تولد.
رمز أدناه هي قريبة من المثلى.فإنه يمكن أن يتم بشكل أفضل من خلال تأليف قائمة إلى أن اجتاز حين جعل الشجرة ، ولكن ليس لدي وقت الآن.هتاف!
object Sort7 {
def left(i: Int) = i * 4
def right(i: Int) = i * 4 + 1
def up(i: Int) = i * 4 + 2
def value(i: Int) = i * 4 + 3
val a = new Array[Int](7 * 4)
def reset = {
0 until 7 foreach {
i => {
a(left(i)) = -1
a(right(i)) = -1
a(up(i)) = -1
a(value(i)) = scala.util.Random.nextInt(52)
}
}
}
def sortN(i : Int) {
var index = 0
def getNext = if (a(value(i)) < a(value(index))) left(index) else right(index)
var next = getNext
while(a(next) != -1) {
index = a(next)
next = getNext
}
a(next) = i
a(up(i)) = index
}
def sort = 1 until 7 foreach (sortN(_))
def print {
traverse(0)
def traverse(i: Int): Unit = {
if (i != -1) {
traverse(a(left(i)))
println(a(value(i)))
traverse(a(right(i)))
}
}
}
}
في البرمجية الزائفة:
int64 temp = 0;
int index, bit_position;
for index := 0 to 6 do
temp |= 1 << cards[index];
for index := 0 to 6 do
begin
bit_position = find_first_set(temp);
temp &= ~(1 << bit_position);
cards[index] = bit_position;
end;
إنه طلب من دلو نوع, التي يجب أن تكون أسرع من أي من مقارنة الانواع التي اقترحت.
ملاحظة: الجزء الثاني يمكن أيضا أن تنفذ من قبل بالتكرار على بت في الزمن الخطي ، ولكن في الواقع قد لا يكون أسرع:
index = 0;
for bit_position := 0 to 51 do
begin
if (temp & (1 << bit_position)) > 0 then
begin
cards[index] = bit_position;
index++;
end;
end;
على افتراض أن كنت بحاجة إلى مجموعة من بطاقات في نهاية الأمر.
الخريطة الأصلية بطاقات بت على 64 بت عدد صحيح ( أو أي عدد صحيح مع >= 52 بت ).
إذا خلال المسح الأولي على فرز مجموعة لا تغييره.
التقسيم صحيح في يقضم كل تتوافق مع القيم 0 × 0 0xf.
استخدام يقضم كما المؤشرات المقابلة فرز الفرعية المصفوفات.سوف تحتاج 13 مجموعات من 16 sub-المصفوفات ( أو فقط 16 sub-المصفوفات واستخدامها الثانية المراوغة ، أو بت العمليات بدلا من النظر الجواب ؛ ما هو أسرع سوف تختلف من منصة ).
لسلسلة غير فارغة sub-المصفوفات في الصفيف.
هل يمكن استخدام أكبر من يقضم إذا كنت تريد.بايت من شأنه أن يعطي 7 مجموعات من 256 المصفوفات و تجعل من المرجح أن غير فارغة المصفوفات تتطلب وصل.
هذا يفترض أن الفروع هي مكلفة مؤقتا مجموعة يصل رخيصة.
#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
// for general case of 7 from 52, rather than assuming last 5 sorted
uint32_t card_masks[16][5] = {
{ 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0 },
{ 2, 0, 0, 0, 0 },
{ 1, 2, 0, 0, 0 },
{ 3, 0, 0, 0, 0 },
{ 1, 3, 0, 0, 0 },
{ 2, 3, 0, 0, 0 },
{ 1, 2, 3, 0, 0 },
{ 4, 0, 0, 0, 0 },
{ 1, 4, 0, 0, 0 },
{ 2, 4, 0, 0, 0 },
{ 1, 2, 4, 0, 0 },
{ 3, 4, 0, 0, 0 },
{ 1, 3, 4, 0, 0 },
{ 2, 3, 4, 0, 0 },
{ 1, 2, 3, 4, 0 },
};
void sort7 ( uint32_t* cards) {
uint64_t bitset = ( ( 1LL << cards[ 0 ] ) | ( 1LL << cards[ 1LL ] ) | ( 1LL << cards[ 2 ] ) | ( 1LL << cards[ 3 ] ) | ( 1LL << cards[ 4 ] ) | ( 1LL << cards[ 5 ] ) | ( 1LL << cards[ 6 ] ) ) >> 1;
uint32_t* p = cards;
uint32_t base = 0;
do {
uint32_t* card_mask = card_masks[ bitset & 0xf ];
// you might remove this test somehow, as well as unrolling the outer loop
// having separate arrays for each nibble would save 7 additions and the increment of base
while ( *card_mask )
*(p++) = base + *(card_mask++);
bitset >>= 4;
base += 4;
} while ( bitset );
}
void print_cards ( uint32_t* cards ) {
printf ( "[ %d %d %d %d %d %d %d ]\n", cards[0], cards[1], cards[2], cards[3], cards[4], cards[5], cards[6] );
}
int main ( void ) {
uint32_t cards[7] = { 3, 9, 23, 17, 2, 42, 52 };
print_cards ( cards );
sort7 ( cards );
print_cards ( cards );
return 0;
}
نلقي نظرة على هذا:
http://en.wikipedia.org/wiki/Sorting_algorithm
سوف تحتاج إلى اختيار واحد التي سوف يكون مستقر أسوأ الأحوال تكلفة...
خيار آخر يمكن أن نضع مجموعة فرز طوال الوقت ، لذلك إضافة بطاقة من شأنها أن تبقي مجموعة مرتبة تلقائيا ، يمكنك أن انتقل إلى الفرز...
ما JRL يشير إلى دلو النوع.منذ لديك محدودة منفصلة عن مجموعة من القيم الممكنة, يمكنك أن يعلن 52 الدلاء مجرد قطرة كل عنصر في دلو في س(1) مرة.وبالتالي دلو نوع O(n).دون ضمان من عدد محدود من العناصر المختلفة ، أسرع النظرية نوع O(n log n) التي أشياء مثل دمج النوع سريعة النوع.انها مجرد توازن أفضل وأسوأ السيناريوهات ثم.
ولكن الجواب طويل قصير, استخدام دلو النوع.
إذا كنت تحب المذكورة أعلاه اقتراح للحفاظ على 52 عنصر الصفيف الذي يحتفظ دائما الصفيف الخاص بك مرتبة ، ثم قد تكون أنت يمكن أن تبقى قائمة أخرى من 7 عناصر مرجع 7 عناصر صالحة في 52 عنصر الصفيف.بهذه الطريقة يمكننا حتى تجنب تحليل 52 عنصر الصفيف.
أعتقد هذا أن تكون فعالة حقا ، فإننا بحاجة إلى قائمة مرتبطة نوع الهيكل الذي يدعم العمليات:InsertAtPosition() و DeleteAtPosition() و تكون فعالة في ذلك.
هناك الكثير من الحلقات في الردود.نظرا متطلبات سرعة و حجم صغير من مجموعة البيانات لن تفعل أي حلقات.
لم أحاول ذلك ولكن أظن أفضل إجابة بالكامل بسطه نوع فقاعة.كما ربما تكتسب قدرا كبيرا من الاستفادة من يجري القيام به في الجمعية.
وأتساءل عما إذا كان هذا هو النهج الصحيح ، على الرغم من.كيف أنت ذاهب إلى تحليل 7 بطاقة اليد??أعتقد أنك تسير في نهاية المطاف إلى تحويل ذلك إلى التمثيل التحليل على أي حال.لن 4x13 مجموعة تكون أكثر فائدة التمثيل ؟ (و هذا من شأنه أن يجعل الفرز المسألة خلافية ، على أية حال.)
معتبرا أن الأخير 5 عناصر هي دائما فرز:
for i := 0 to 1 do begin
j := i;
x := array[j];
while (j+1 <= 6) and (array[j+1] < x) do begin
array[j] := array[j+1];
inc(j);
end;
array[j] := X;
end;
فقاعة نوع هو صديقك.أنواع أخرى لديك الكثير من النفقات العامة رموز غير مناسبة عدد صغير من العناصر
هتافات
هنا هو الأساسي الخاص بك O(n) نوع.لست متأكدا كيف يقارن إلى الآخرين.ويستخدم بسطه الحلقات.
char card[7]; // the original table of 7 numbers in range 0..51
char table[52]; // workspace
// clear the workspace
memset(table, 0, sizeof(table));
// set the 7 bits corresponding to the 7 cards
table[card[0]] = 1;
table[card[1]] = 1;
...
table[card[6]] = 1;
// read the cards back out
int j = 0;
if (table[0]) card[j++] = 0;
if (table[1]) card[j++] = 1;
...
if (table[51]) card[j++] = 51;
إذا كنت تبحث عن النفقات العامة منخفضة جدا مثالية نوعا ما ، يجب إنشاء الفرز الشبكة.يمكنك توليد رمز 7 صحيح الشبكة باستخدام بوس-نيلسون الخوارزمية.
هذا من شأنه أن أضمن عدد ثابت من يقارن عدد متساو من مقايضة في أسوأ الأحوال.
الشفرة التي تم إنشاؤها قبيح لكن هو الأمثل.
البيانات الخاصة بك في مجموعة مرتبة و سأفترض انك مبادلة جديدة اثنين إذا كان هناك حاجة لذلك أيضا فرزها حتى أ.إذا كنت ترغب في الاحتفاظ بها في مكان ثم استخدام نموذج من نوع الإدراج;ب.إذا كنت تريد أن يكون ذلك نتيجة في مجموعة أخرى القيام دمج عن طريق نسخ.
مع أعداد صغيرة الثنائية ختم مبالغة ، و الثلاثي ختم المناسب على أي حال:واحد بطاقة جديدة سوف الغالب مثل انقسم الى اثنين و ثلاثة ، بمعنى.2+3 أو 3+2, اثنين من بطاقات في الفردي أزواج, على سبيل المثال2+1+2.
لذلك معظم الوقت في الفضاء كفاءة نهج وضع أصغر بطاقة جديدة مقارنة مع[1] (بمعنى.تخطي[0]) ثم البحث اليسار أو اليمين للعثور على بطاقة يجب أن تحل ، ثم تبادل و نقل الحق (التحول بدلا من السطح) ، مقارنة مع أكبر بطاقة جديدة حتى تجد أين تذهب.بعد هذا عليك أن يتحول إلى الأمام من قبل ثنائي (ورقتين تم إدراج).المتغيرات عقد بطاقات جديدة (و مقايضة) يجب أن تكون السجلات.
ابحث عن النهج سيكون أسرع ولكن استخدام المزيد من الذاكرة.
استخدام الفرز الشبكة, كما هو الحال في C++ code:
template<class T>
inline void sort7(T data) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
//DD = Define Data, create a local copy of the data to aid the optimizer.
#define DD1(a) register auto data##a=*(data+a);
#define DD2(a,b) register auto data##a=*(data+a);register auto data##b=*(data+b);
//CB = Copy Back
#define CB1(a) *(data+a)=data##a;
#define CB2(a,b) *(data+a)=data##a;*(data+b)=data##b;
DD2(1,2) SORT2(1,2)
DD2(3,4) SORT2(3,4)
DD2(5,6) SORT2(5,6)
DD1(0) SORT2(0,2)
SORT2(3,5)
SORT2(4,6)
SORT2(0,1)
SORT2(4,5)
SORT2(2,6) CB1(6)
SORT2(0,4)
SORT2(1,5)
SORT2(0,3) CB1(0)
SORT2(2,5) CB1(5)
SORT2(1,3) CB1(1)
SORT2(2,4) CB1(4)
SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}
استخدام وظيفة أعلاه إذا كنت تريد أن تمر عليه التكرار أو مؤشر واستخدام وظيفة أدناه إذا كنت تريد أن تمر سبعة الحجج واحدة تلو الأخرى.راجع للشغل, باستخدام قوالب يسمح القائمون على توليد حقا رمز الأمثل حتى لا تحصل على ركوب template<> إلا إذا كنت تريد كود C (أو بعض اللغات الأخرى رمز).
template<class T>
inline void sort7(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5, T& e6) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a) register auto data##a=e##a;
#define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b;
#define CB1(a) e##a=data##a;
#define CB2(a,b) e##a=data##a;e##b=data##b;
DD2(1,2) SORT2(1,2)
DD2(3,4) SORT2(3,4)
DD2(5,6) SORT2(5,6)
DD1(0) SORT2(0,2)
SORT2(3,5)
SORT2(4,6)
SORT2(0,1)
SORT2(4,5)
SORT2(2,6) CB1(6)
SORT2(0,4)
SORT2(1,5)
SORT2(0,3) CB1(0)
SORT2(2,5) CB1(5)
SORT2(1,3) CB1(1)
SORT2(2,4) CB1(4)
SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}
