HybridSort of QuickSort和MergeSort

Question

我将尝试在Osječki Matematički List中发表一篇关于我制作的编程语言(č，简称AEC)的文章，为了演示它对于实现算法的可用性，我尝试在其中实现一种快速排序算法。

我的算法的基本思想是，当数组被随机洗牌时，QuickSort工作得更好，而当数组已经接近排序时，MergeSort工作得更好。下面是：

Syntax GAS ;Neka ArithmeticExpressionCompiler ispisuje asemblerski kod kompatibilan s GNU Assemblerom, da bude kompatibilan s GCC-om. Po defaultu ispisuje kod kompatibilan s FlatAssemblerom (a FlatAssembler na Linuxu ne radi bas najbolje).
verboseMode ON ;Neka ArithmeticExpressionCompiler ispisuje vise komentara u asemblerski kod koji ispisuje (da bude laksi za citanje i debuggiranje).
AsmStart ;Neka GNU Assembler obavijesti linkera da je "hybrid_sort" naziv potprograma...
    .global hybrid_sort
    hybrid_sort:
AsmEnd
If gornja_granica-donja_granica<2 ;Ako je niz duljine manje od 2 (0 ili 1), znaci da je vec poredan, pa prekidamo izvodenje ovog potprograma.
    AsmStart ;Kako radimo izvan sekcija, mozemo jednostavno prekinuti izvodenje potprograma asemblerskom naredbom "ret" (inace bismo, da radimo u sekcijama, morali znati vrti li se program na 32-bitnom ili 64-bitnom Linuxu).
        ret
    AsmEnd 
EndIf
razvrstanost:=0
i:=donja_granica
While i < gornja_granica - 1
    razvrstanost:=razvrstanost+(originalni_niz[i]

我的编译器生成的程序集代码可以看到这里。它可以使用GNU汇编程序进行组装，但是，您将无法从它获得可执行程序。这只是一个期望从外部程序调用的例程。这类方案的一个例子是：

/*
 * Dakle, ovo ce biti omotac oko "hybrid_sort.aec" napisan u C++-u.
 * "hybrid_sort.aec" sam po sebi nije program koji se moze pokrenuti,
 * i zato cemo od C++ compilera (u ovom slucaju, GCC-a) traziti da
 * napravi program unutar kojeg ce se "hybrid_sort.aec" moze pokrenuti,
 * i, po mogucnosti, koji ce olaksati da ga testiramo. Drugim rijecima,
 * ovo je program s kojim se "hybrid_sort.aec" moze staticki linkirati.
 * */
#include 
#include 
#include 
#include 
#include 

namespace AEC { // Da se razlikuju AEC-ove varijable od C++-ovih.
extern "C" {    // Za GNU Linker (koji se dobije uz Linux i koristi ga GCC), AEC
// jezik je dijalekt C-a, a moj compiler je C compiler.
float result, originalni_niz[1 << 16], kopija_originalnog_niza[1 << 16],
    pomocni_niz[1 << 16], i, gdje_smo_u_prvom_nizu, gdje_smo_u_drugom_nizu,
    gornja_granica, donja_granica, sredina_niza,
    stog_sa_sredinama_niza[1 << 10], stog_s_donjim_granicama[1 << 10],
    stog_s_gornjim_granicama[1 << 10], vrh_stoga, pomocna_varijabla_za_zamijenu,
    gdje_je_pivot, j, pivot, koliko_usporedbi_ocekujemo_od_QuickSorta,
    koliko_usporedbi_ocekujemo_od_MergeSorta, razvrstanost,
    Eulerov_broj_na_koju_potenciju, polinom_pod_apsolutnom,
    razvrstanost_na_potenciju[8],
    broj_vec_poredanih_podniza = 0, broj_obrnuto_poredanih_podniza = 0,
    broj_pokretanja_MergeSorta = 0,
    broj_pokretanja_QuickSorta =
        0; // GNU Linker omogucuje da se varijable ne deklariraju ne samo u
           // razlicitim datotekama, nego i u razlicitim jezicima. Znaci, ne
           // moram traziti kako se, recimo, na 64-bitnom Linuxu deklariraju
           // globalne varijable na asemblerskom jeziku, jer GCC to vec zna.
void hybrid_sort(); //".global hybrid_sort" iz "hybrid_sort.aec". U C++-u ga
// morate deklarirati da biste ga mogli koristiti. C++ nije
// kao JavaScript ili AEC u tom pogledu, C++ pokusava pronaci
// krivo natipkana imena varijabli i funkcija vec za vrijeme
// compiliranja.
}
} // namespace AEC
const int n = 1 << 16;

int main() {
  std::cout << "sortedness\tsorted_array\treverse\tMergeSort\tQuickSort\n";
  for (int i = 0; i < n; i++)
    AEC::originalni_niz[i] = i;
  for (int i = 0; i <= n; i += 1 << 9) {
    std::sort(&AEC::originalni_niz[0], &AEC::originalni_niz[n]);
    if (i < (n / 2))
      std::reverse(&AEC::originalni_niz[0], &AEC::originalni_niz[n]);
    int broj_ispremjestanja = abs(i - (n / 2)) * 1.5;
    for (int j = 0; j < broj_ispremjestanja; j++)
      std::iter_swap(&AEC::originalni_niz[std::rand() % n],
                     &AEC::originalni_niz[std::rand() % n]);
    if (!(rand() % 100))
      std::random_shuffle(
          &AEC::originalni_niz[0],
          &AEC::originalni_niz[n]); // Ponekad namjesti da poredanost bude nula.
    if (!(rand() % 100))
      std::sort(&AEC::originalni_niz[0], &AEC::originalni_niz[n],
                [](float a, float b) -> bool {
                  return a > b;
                }); // Ponekad namjesti da poredanost bude 1. Za to sam koristio
                    // C++-ove lambda funkcije. Njih GCC podrzava jos od 2007, a
                    // komercijalni compileri jos od ranije. Nadam se da netko
                    // nece pokusati ukucati ovo u neki arhaican compiler.
    float razvrstanost = 0;
    for (int j = 0; j < n - 1; j++)
      razvrstanost += AEC::originalni_niz[j] < AEC::originalni_niz[j - 1];
    razvrstanost = razvrstanost / ((n - 1) / 2) - 1;
    std::copy_n(&AEC::originalni_niz[0], n, &AEC::kopija_originalnog_niza[0]);
    AEC::broj_vec_poredanih_podniza = 0;
    AEC::broj_obrnuto_poredanih_podniza = 0;
    AEC::broj_pokretanja_MergeSorta = 0;
    AEC::broj_pokretanja_QuickSorta = 0;
    AEC::gornja_granica = n;
    AEC::donja_granica = 0;
    AEC::vrh_stoga = -1;
    AEC::hybrid_sort();
    std::sort(&AEC::kopija_originalnog_niza[0],
              &AEC::kopija_originalnog_niza[n]);
    if (!std::equal(&AEC::originalni_niz[0], &AEC::originalni_niz[n],
                    &AEC::kopija_originalnog_niza[0])) {
      std::cerr << "C++-ov std::sort nije dobio isti rezultat za i=" << i << '!'
                << std::endl;
      return 1; // Javi operativnom sustavu da je doslo do pogreske.
    }
    std::cout << razvrstanost << '\t'
              << std::log(1 + AEC::broj_vec_poredanih_podniza)
              << '\t' // Broj vec poredanih podniza moze biti i nula (ako je,
                      // recimo, razvrstanost jednaka -1), a, kako logaritam od
                      // nula ne postoji, dodat cu jedinicu da se program ne rusi
                      // na nekim compilerima.
              << std::log(1 + AEC::broj_obrnuto_poredanih_podniza) << '\t'
              << std::log(1 + AEC::broj_pokretanja_MergeSorta) << '\t'
              << std::log(1 + AEC::broj_pokretanja_QuickSorta) << '\n';
  }
  std::flush(std::cout); // Obrisi meduspremnik prije no sto zavrsis program.
  return 0; // Javi operativnom sustavu da je program uspjesno zavrsen.
}

我对如何使它变得更好感兴趣。我注意到它比C++ std::sort快得多。

以下是我所做的一些测量：

我还试图通过测量每个算法用于特定排序数组的频率来诊断性能问题：

但我仍然不知道到底是什么使它慢下来，比C++ std::sort慢100倍以上。你能弄明白吗？或者你能以其他方式使我的代码更好吗？

Answer 1

生成的程序集代码效率很低！

第一个示例.

莱伊看了看最上面这个小部分：

若gornja_granica-donja_granica<2 AsmStart ret AsmEnd EndIf

这是其可读形式的程序集代码：

    finit
    fld dword ptr [gornja_granica]
    fld dword ptr [donja_granica]
    fsubp
    mov dword ptr [result],0x40000000 #IEEE754 hex of 2
    fld dword ptr [result]
    fcomip
    fstp dword ptr [result]
    jna secondOperandOfTheComparisonIsSmallerOrEqualLabel914728
    fld1
    jmp endOfTheLessThanComparisonLabel862181
secondOperandOfTheComparisonIsSmallerOrEqualLabel914728:
    fldz   ; 2 LT (a-b)
endOfTheLessThanComparisonLabel862181:

#Comparing the just-calculated expression with 0...
    fistp dword ptr [result]
    mov eax, dword ptr [result]
    test eax,eax
#Branching based on whether the expression is 0...
    jz ElseLabel529946
    ret
    finit
ElseLabel529946:
EndIfLabel210662:

基本上，这段代码想要到达ElseLabel529946 if gornja_granica-donja_granica<2。对于分支，您真正需要的唯一信息来自fcomip指令。它定义了EFLAGS中的CF和ZF (和PF)，您可以立即跳转。

• 而不加载0.0或1.0
• 而不存储在内存变量中
• 而不测试该内存变量
• 没有额外的跳跃

这是一个改进的代码：

    finit
    fld     dword ptr [gornja_granica]
    fld     dword ptr [donja_granica]
    fsubp
    mov     dword ptr [result], 0x40000000     ; IEEE754 hex of 2
    fld     dword ptr [result]
    fcomip
    fstp    st(0)                              ; Clears FPU stack
    jna     ElseLabel529946
    ret
    finit
ElseLabel529946:

请注意，要丢弃st(0)，不需要移动到内存中。将st(0)复制到自身，并弹出FPU堆栈。

这一情况进一步改善。内存访问更少，代码更短！

    finit
    fld     dword ptr [gornja_granica]
    fsub    dword ptr [donja_granica]
    fld1
    fadd    st(0), st(0)                       ; st(0) == 1 + 1
    fcomip
    fstp                                       ; Clears FPU stack
    jna      ElseLabel529946
    ret
ElseLabel529946:

第二个示例.

而i<7 = i=7

这应该写成While i<=7

我已经查看了它的组装代码，并且看到了与上面一样的低效。但是由于|算子的存在，它们的负面影响更大。

第三个示例.

sredina_niza:=sredina_niza-mod(sredina_niza,1)

mod()函数的汇编代码使用了大量的指令。您所需要的是一个int()函数，您只需使用frndint (圆形到整数)指令即可。这是：

sredina_niza:=int(sredina_niza)

就会快得多。

知道了前面提到的情况，我毫不怀疑MergeSort或QuickSort的效率会更低。

Answer 2