Kirjautuminen

Haku

Tehtävät

Koodivinkit: C++: Optimoitu lajittelu

Kirjoittaja: JoinTuanJanohon; viimeksi muokattu 18.07.2006.

Tehokas lajittelu on mielenkiintoinen probleema. Etenkin siihen liittyvä kysymys: montako vertailua n-kokoisen taulukon lajittelu vaatii? Esimerkiksi 256-alkioisen taulukon sortteeraus tarvitsisi vain 256+1 vertailua.

Oheisella apuohjelmalla voi optimoida pieniä inline sort3 - sort6 -funktioita. Ne ovat 3-4 kertaa nopeampia suorittaa, kuin stl:n sort-funktio. Koodi järjestää tiedostoon "xsort.cpp" minimimäärän tarvittavia vertailuja ja vaihtoja.

qsort -algoritmi hajottaa lajittelun nopeasti pieniin osaongelmiin. Jos niihin soveltaa tehokkaita osalajitteluja, koko qsort -algoritmin voi silloin räätälöidä moninkertaiseen nopeuteen. Ohjelmalla ei kannata generoida kovin suuria osalajittelutapauksia, koska silloin koodia generoituu niin paljon, että prosessori hyytyy sellaisen koodimössön kanssa. Esimerkiksi LAJITTELU_KOKO 8:lla koodia generoituu jo muutama satatuhatta riviä. (Valitan työkiireiden vuoksi kommenttien vähyyttä, mutta vastaan koodia koskeviin kysymyksiin kysyttäessä.)

//////////////////////////////////
// Lajittelufunktion generointi //
//         JA 17.7.2006         //
//////////////////////////////////

#include <stdio.h>
#include <memory.h>

#define LAJITTELU_KOKO 4

class Laskuri
{
   public:

   Laskuri(void);
   int* incx(void);
   ~Laskuri(void) {};

   private:

   int x[LAJITTELU_KOKO];
   int y[LAJITTELU_KOKO];

   int* kopio(void);
   void reset(void);
};

Laskuri::Laskuri(void)
{
   reset();
}

void Laskuri::reset(void)
{
   int n=LAJITTELU_KOKO;
   for (int i=0; i<n; i++)
   x[i]=i; x[n-1]-=(int)0x01;
}

int* Laskuri::kopio(void)
{
   int n=LAJITTELU_KOKO;
   memcpy(y, x, sizeof(int)*n);
   return y;
}

int* Laskuri::incx(void)
{
   int n=LAJITTELU_KOKO;
   int i=n-1, j;

   while (i>=0)
   {
      if ((++x[i])==n)
      {
         --i;
      }
      else
      {
         for (j=0; j<i; j++)
         if (x[j]==x[i]) break;

         if (j==i)
         {
            if ((++i)==n)
            return kopio();
            else x[i]=-1;
         }
      }
   }
   return (int*)0;
}

class solmu
{
   public:

   solmu(void);
   ~solmu(void);
   void aja(int*);
   void print(FILE*);

   private:

   solmu *If;
   solmu *Else;
   int LastIf, LastElse;

   void main(int*, int, int);
   void print(FILE*, int*, int, int, int);
};

solmu::~solmu(void)
{
}

solmu::solmu(void)
{
   memset(this, 0, sizeof(solmu));
}

void solmu::aja(int *r)
{
   main(r, 0, 1);
}

void solmu::print(FILE *fi)
{
   int k[LAJITTELU_KOKO];
   int n=(int)LAJITTELU_KOKO;
   for (int i=0; i<n; i++) k[i]=i;

   fprintf(fi, "inline void sort%d(register int *r) {\n", n);
   fprintf(fi, "   register int tmp;\n");
   print(fi, k, 0x00, 0x01, 1);
   fprintf(fi, "}\n\n");
}

void VieritaYlos(int *r, int i, int j)
{
   int tmp=r[j];
   for (; j>i; j--)
   r[j]=r[j-1]; r[i]=tmp;
}

void solmu::main(int *r, int i, int j)
{
   int I=i;
   int J=j;

   if ((++J)==LAJITTELU_KOKO) ++I, J=I+1;

   if (r[j]<r[i])
   {
      VieritaYlos(r, i, j);
      if (J<LAJITTELU_KOKO)
      {
         if (If==(solmu*)0) If=new solmu;
         If->main(r, I, J);
      }
      else LastIf=1;
   }
   else
   {
      if (J<LAJITTELU_KOKO)
      {
         if (Else==(solmu*)0) Else=new solmu;
         Else->main(r, I, J);
      }
      else LastElse=1;
   }
}

void Sisenna(FILE *F, int sisennys)
{
   for (int i=0; i<sisennys; i++)
   for (int j=0; j<3; j++)
   fprintf(F, " ");
}

void TeeVaihdot(FILE *fi, int *b, int t)
{
   int a[LAJITTELU_KOKO], i;
   int n=LAJITTELU_KOKO, j;
   for (i=j=0x00; i<n; i++)
   if ((a[i]=i)!=b[i]) ++j;

   if (j)
   {
      // vaihdot pareittain
      for (i=0; i<n; i++)
      for (j=i+0x01; j<n; j++)
      if (a[i]==b[j]&&a[j]==b[i]&&a[i]!=-1)
      {
         Sisenna(fi, t);
         fprintf(fi, "tmp=r[%d], r[%d]=r[%d], r[%d]=tmp;\n",
         a[i], a[i], b[i], b[i]);
         a[i]=a[j]=b[i]=b[j]=-1;
      }

      // ketjuvaihdot
      do
      {
         for (i=j=0; i<n; i++)
         if (a[i]!=-1&&a[i]!=b[i])
         {a[j]=a[i]; b[j]=b[i]; ++j;}

         if ((n=j)!=0)
         {
            Sisenna(fi, t);
            fprintf(fi, "tmp=r[%d], r[%d]=r[%d], ", a[0], a[0], b[0]);
            for (int etsi=b[0];;)
            {
               for (i=0; i<n; i++)
               if (a[i]==etsi) break;

               if (b[i] == a[0])
               {
                  fprintf(fi, "r[%d]=tmp;\n", a[i]);
                  a[i]=a[0]=-1; --j; break;
               }
               else
               {
                  fprintf(fi, "r[%d]=r[%d], ", a[i], b[i]);
                  etsi=b[i]; a[i]=b[i]=-1; --j;
               }
            }
         }
      }
      while (j>1);
   }
}

void solmu::print(FILE *fi, int *k, int i, int j, int t)
{
   int I=i, J=j;
   int n=sizeof(int);
   int e[LAJITTELU_KOKO];
   memcpy(e, k, n*LAJITTELU_KOKO);
   if ((++J)==LAJITTELU_KOKO) ++I, J=I+1;

   if (If && Else)
   {
      Sisenna(fi, t);
      fprintf(fi, "if (r[%d]<r[%d]) {\n", k[j], k[i]);
      VieritaYlos(k, i, j);
      If->print(fi, k, I, J, t+1);
      Sisenna(fi, t);
      fprintf(fi, "} else {\n");
      Else->print(fi, e, I, J, t+1);
      Sisenna(fi, t);
      fprintf(fi, "}\n");
   }
   else if (If)
   {
      If->print(fi, k, I, J, t);
   }
   else if (Else)
   {
      Else->print(fi, e, I, J, t);
   }
   else
   {
      if (LastIf && LastElse)
      {
         Sisenna(fi, t);
         fprintf(fi, "if (r[%d]<r[%d]) {\n", k[j], k[i]);
         VieritaYlos(k, i, j);
         TeeVaihdot(fi, k, t+1);
         Sisenna(fi, t);
         fprintf(fi, "} else {\n");
         TeeVaihdot(fi, e, t+1);
         Sisenna(fi, t);
         fprintf(fi, "}\n");
      }
      else if (LastIf)
      {
         VieritaYlos(k, i, j);
         TeeVaihdot(fi, k, t);
      }
      else if (LastElse)
      {
         TeeVaihdot(fi, e, t);
      }
   }
}

void GeneroiSolmut(solmu *alku)
{
   int *x;
   Laskuri cou;

   while ((x=cou.incx())!=(int*)0)
   {
      alku->aja(x);
   }
}

void main(void)
{
   FILE *F=fopen("xsort.cpp", "w");
   solmu *alku=new solmu;
   GeneroiSolmut(alku);
   alku->print(F);
   fclose(F);
}
///////////////////////////////
// Ajoesimerkki parametrilla //
// #define LAJITTELU_KOKO 4  //
// Tiedosto: "xsort.cpp"     //
///////////////////////////////

inline void sort4(register int *r) {
   register int tmp;
   if (r[1]<r[0]) {
      if (r[2]<r[1]) {
         if (r[3]<r[2]) {
            tmp=r[0], r[0]=r[3], r[3]=tmp;
            tmp=r[1], r[1]=r[2], r[2]=tmp;
         } else {
            if (r[3]<r[1]) {
               tmp=r[0], r[0]=r[2], r[2]=r[1], r[1]=r[3], r[3]=tmp;
            } else {
               if (r[3]<r[0]) {
                  tmp=r[0], r[0]=r[2], r[2]=r[3], r[3]=tmp;
               } else {
                  tmp=r[0], r[0]=r[2], r[2]=tmp;
               }
            }
         }
      } else {
         if (r[3]<r[1]) {
            if (r[2]<r[0]) {
               tmp=r[0], r[0]=r[3], r[3]=tmp;
            } else {
               tmp=r[0], r[0]=r[3], r[3]=r[2], r[2]=tmp;
            }
         } else {
            if (r[2]<r[0]) {
               if (r[3]<r[2]) {
                  tmp=r[0], r[0]=r[1], r[1]=r[3], r[3]=tmp;
               } else {
                  if (r[3]<r[0]) {
                     tmp=r[0], r[0]=r[1], r[1]=r[2], r[2]=r[3], r[3]=tmp;
                  } else {
                     tmp=r[0], r[0]=r[1], r[1]=r[2], r[2]=tmp;
                  }
               }
            } else {
               if (r[3]<r[0]) {
                  tmp=r[0], r[0]=r[1], r[1]=r[3], r[3]=r[2], r[2]=tmp;
               } else {
                  if (r[3]<r[2]) {
                     tmp=r[0], r[0]=r[1], r[1]=tmp;
                     tmp=r[2], r[2]=r[3], r[3]=tmp;
                  } else {
                     tmp=r[0], r[0]=r[1], r[1]=tmp;
                  }
               }
            }
         }
      }
   } else {
      if (r[2]<r[0]) {
         if (r[3]<r[2]) {
            tmp=r[0], r[0]=r[3], r[3]=r[1], r[1]=r[2], r[2]=tmp;
         } else {
            if (r[3]<r[0]) {
               tmp=r[0], r[0]=r[2], r[2]=tmp;
               tmp=r[1], r[1]=r[3], r[3]=tmp;
            } else {
               if (r[3]<r[1]) {
                  tmp=r[0], r[0]=r[2], r[2]=r[3], r[3]=r[1], r[1]=tmp;
               } else {
                  tmp=r[0], r[0]=r[2], r[2]=r[1], r[1]=tmp;
               }
            }
         }
      } else {
         if (r[3]<r[0]) {
            if (r[2]<r[1]) {
               tmp=r[0], r[0]=r[3], r[3]=r[1], r[1]=tmp;
            } else {
               tmp=r[0], r[0]=r[3], r[3]=r[2], r[2]=r[1], r[1]=tmp;
            }
         } else {
            if (r[2]<r[1]) {
               if (r[3]<r[2]) {
                  tmp=r[1], r[1]=r[3], r[3]=tmp;
               } else {
                  if (r[3]<r[1]) {
                     tmp=r[1], r[1]=r[2], r[2]=r[3], r[3]=tmp;
                  } else {
                     tmp=r[1], r[1]=r[2], r[2]=tmp;
                  }
               }
            } else {
               if (r[3]<r[1]) {
                  tmp=r[1], r[1]=r[3], r[3]=r[2], r[2]=tmp;
               } else {
                  if (r[3]<r[2]) {
                     tmp=r[2], r[2]=r[3], r[3]=tmp;
                  } else {
                  }
               }
            }
         }
      }
   }
}

Kommentit

Metabolix [18.07.2006 23:09:05]

Lainaa #

On varmaankin jokin järkevä syy sille, miksi näin:

if (r[1]<r[0]) {
   if (r[2]<r[1]) {
      if (r[3]<r[2]) {
         if (r[0]<r[1]) {

Eihän tuo viimeinen ehto voi olla tosi, jos ensimmäinen on jo ollut. Näin kuitenkin alkaa tuo jälkimmäinen koodilistauksesi. Vastaavia löytyy tuosta pätkästä useampiakin jo hyvin pikaisella vilkaisulla.

JoinTuanJanohon [23.07.2006 20:15:52]

Lainaa #

Hyvä ja mielenkiintoinen kysymys, johon en osaa vastata. Kuitenkin if- ja else -lohkot suorittavat erilaiset vaihdot. Algoritmin lajittelu käy pöytämallina seuraavasti, jos lajiteltavana ovat esimerkiksi luvut 4, 3, 1, 5, 2;

4, 3, 1, 5, 2
3 < 4 => tosi
3, 4, 1, 5, 2
1 < 3 => tosi
1, 3, 4, 5, 2
...jne.

Lukujen vierittäminen taulukossa yhdellä askeleella tekee aina osan tulevista vertailuista tarpeettomiksi, jolloin vertailun tulos olisi aina tosi tai epätosi. Koodin print –funktiossa:

else if (If)
{
   If->print(fi, k, I, J, t);
}
else if (Else)
{
   Else->print(fi, e, I, J, t);
}

karsii pois ne vertailut, joiden tuloksena on aina ollut joko tosi tai epätosi. Ehkä on olemassa sellainen algoritmi, joka generoisi n-alkiota sisältävälle taulukolle enintään n kappaletta vertailuja - tai vieläkin vähemmän.

Metabolix [21.12.2017 17:54:47]

Lainaa #

Koodivinkin kuvauksessa on vakava virhe. N-kokoista taulukkoa ei voi yleisesti järjestää N+1 vertailulla. Näkeehän sen generoidusta koodistakin: sort6 eli 6-alkioisen taulukon järjestely tekee keskimäärin 11,05 ja enintään 15 vertailua.

Määrän voi myös testata seuraavalla koodilla:

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

struct myint {
	int val;
	myint(int val_ = 0): val(val_) {}
};
int compare_count = 0;
bool operator < (myint a, myint b) {
	compare_count += 1;
	// std::cout << a.val << " < " << b.val << "?\n";
	return a.val < b.val;
}

#include "xsort.cpp"

int main() {
	std::vector<int> a {0, 1, 2, 3, 4, 5};
	std::map<int, int> counts;
	double compare_count_sum = 0, test_count = 0;
	do {
		std::vector<myint> b(a.begin(), a.end());
		compare_count = 0;
		sort6(&b[0]);
		counts[compare_count] += 1;
		test_count += 1;
		compare_count_sum += compare_count;
	} while (std::next_permutation(a.begin(), a.end()));
	for (auto c: counts) {
		std::cout << c.first << " vertailua " << c.second << " tapauksessa.\n";
	}
	std::cout << "Keskiarvo " << compare_count_sum / test_count << "\n";
}

Tässä xsort.cpp sisältää sort6-funktion, jossa register int -tyypin tilalle on vaihdettu myint vertailujen laskemista varten. Ohjelma käy läpi kaikki taulukon järjestykset ja laskee, montako vertailua kunkin järjestämiseen menee.

CutVertex [03.12.2018 01:05:53]

Lainaa #

Sinänsä ihan kiinnostava kyhäelmä mutta jos muistin käyttö on luokkaa O(C*2^n), missä C on tähtitieteellisen suuri vakio, niin käyttökelvotonhan tuo käytännössä on. Toisaalta jos lajittelet muutaman alkion kokoista taulukkoa, niin vertailu qsort-funktioon ei ole kovin kiinnostava - insertion sort -proseduurikin on itseasiassa paljon parempi vaihtoehto kuin quick sort kun järjestettävän taulukon koko liikkuu muutamissa kymmenissä.

Kirjoita kommentti

Muista lukea keskustelun ohjeet.
Tietoa sivustosta