Ha ennek az algoritmusa nagyon gyors lenne, valamint a a gép is nagyon gyors lenne, akkor ez megoldás lenne az 1D vágás problémára. De sajnos ez nem így van.
Az itt szereplő leggyorsabb algoritmus innen származik.
A fórumon linkelte be "joysefke"(ezúton is köszönöm Neki). Sőt, nem csak belinkelte, hanem Ő is átírta C#-ra(OOP-ban), míg én megmaradtam a C stílusnál. Azt mondja,
hogy a tesztem valamit mér, de nem azt, amit szeretnék. Ezért az itt szereplő kódban "jmax" értékét 1-re állítottam(mindegyik változat csak 1szer fut le).
Viszont a char tömböt kibővítettem. Ezáltal az egyszeri futás is lassabb lett. Kovisoft adta megint a leghatékonyabb megoldást. Íme kovisoft "gyilkos" kódja(is):
using System;
using System.Diagnostics;
using System.Runtime.InteropServices;
namespace TesztConsole
{
class PermIsm
{
[DllImport("kernel32.dll", EntryPoint = "CopyMemory", SetLastError = false)]
public static extern void CopyMemory(int[] dest, int[] src, uint count);
static int intSize = Marshal.SizeOf(typeof(int));
static void Main(string[] args)
{
Console.WriteLine(DateTime.Now);
int jmax = 1;
Stopwatch sw = new Stopwatch();
long t_1 = 0, t_2 = 0, t_3 = 0, t_4 = 0, t_5 = 0, t_6 = 0, t_7 = 0, t_8 = 0, t_9 = 0;
char[] charr = "abcdanananaabcdanan".ToCharArray();
//char[] charr = "ACBC".ToCharArray();
sw.Start();
for (int j = 0; j < jmax; ++j) Teszt_1(charr);
t_1 = sw.ElapsedMilliseconds;
GC.Collect();
t_2 = sw.ElapsedMilliseconds;
for (int j = 0; j < jmax; ++j) Teszt_2(charr);
t_3 = sw.ElapsedMilliseconds;
GC.Collect();
t_4 = sw.ElapsedMilliseconds;
for (int j = 0; j < jmax; ++j) Teszt_3(charr);
t_5 = sw.ElapsedMilliseconds;
GC.Collect();
t_6 = sw.ElapsedMilliseconds;
for (int j = 0; j < jmax; ++j) Teszt_4(charr);
t_7 = sw.ElapsedMilliseconds;
GC.Collect();
t_8 = sw.ElapsedMilliseconds;
for (int j = 0; j < jmax; ++j) Teszt_5(charr);
t_9 = sw.ElapsedMilliseconds;
Console.WriteLine("Permutator: {0}", t_1);
Console.WriteLine("Nem OOP: {0}", t_3 - t_2);
Console.WriteLine("Array.Sort: {0}", t_5 - t_4);
Console.WriteLine("Egyetemi Jegyzet: {0}", t_7 - t_6);
Console.Write("kovisoft: {0}", t_9 - t_8);
}
static void Teszt_1(char[] arr)
{
var p = new Permutator(arr);
do
{
//Console.WriteLine(new string(p.State));
}
while (p.Next());
}
static void Teszt_2(char[] arr)
{
char[] tomb = (char[])arr.Clone();
int size = tomb.Length;
QuickSort(tomb, 0, size - 1);
//Array.Sort(tomb);
bool isFinished = false;
while (!isFinished)
{
int i;
/*for (int k = 0; k < size; ++k) Console.Write("{0} ", tomb[k]);
Console.WriteLine("");*/
for (i = size - 2; i >= 0; --i) if (tomb[i] < tomb[i + 1]) break;
if (i == -1) isFinished = true;
else
{
int ceilIndex = findCeil(tomb, tomb[i], i + 1, size - 1);
char temp = tomb[i];
tomb[i] = tomb[ceilIndex];
tomb[ceilIndex] = temp;
QuickSort(tomb, i + 1, size - 1);
//Array.Sort(tomb, i + 1, size - i - 1);
}
}
}
static void Teszt_3(char[] arr)
{
char[] tomb = (char[])arr.Clone();
int size = tomb.Length;
//QuickSort(tomb, 0, size - 1);
Array.Sort(tomb);
bool isFinished = false;
while (!isFinished)
{
int i;
/*for (int m = 0; m < size; ++m) Console.Write("{0} ", tomb[m]);
Console.WriteLine("");*/
for (i = size - 2; i >= 0; --i) if (tomb[i] < tomb[i + 1]) break;
if (i == -1) isFinished = true;
else
{
int ceilIndex = stfindCeil(tomb, tomb[i], i + 1, size - 1);
char temp = tomb[i];
tomb[i] = tomb[ceilIndex];
tomb[ceilIndex] = temp;
//QuickSort(tomb, i + 1, size - 1);
Array.Sort(tomb, i + 1, size - i - 1);
}
}
}
static void Teszt_4(char[] arr)
{
char[] tomb = (char[])arr.Clone();
int size = tomb.Length;
QuickSort(tomb, 0, size - 1);
//Array.Sort(tomb);
int n = tomb.Length;
int[] tombch = new int[n];
char[] tomb2 = Tomorito(tomb, ref tombch);
/*int smax = tomb2.Length + 1;
Array.Resize(ref tombch, smax);
Array.Resize(ref tomb2, smax);*/
int[] W = new int[n];
IsmPermutacio(tomb2, tombch, n, W, n, 0);
}
static void Teszt_5(char[] arr)
{
char[] arr2 = (char[])arr.Clone();
int size = arr.Length;
QuickSort(arr2, 0, size - 1);
//Array.Sort(arr2);
int n = arr2.Length;
int i, j;
char temp;
//for (i = 0; i < n; ++i) arr2[i] = i + 1;
while (true)
{
// kiirjuk az aktualis permutaciot
/*for (i = 0; i < n; ++i) Console.Write("{0} ", arr2[i]);
Console.WriteLine("");*/
// megkeressuk, hol kezdodik az utolso monoton csokkeno reszsorozat
for (i = n - 2; i >= 0 && arr2[i] >= arr2[i + 1]; --i) ;
// ha a teljes sorozat monoton csokkeno, akkor vegeztunk
if (i < 0) break;
// a csokkeno reszsorozat elotti elemet ki kell cserelnunk a reszsorozatban nagysag szerint rakovetkezovel
for (j = n - 1; arr2[j] <= arr2[i]; --j) ;
temp = arr2[i]; arr2[i] = arr2[j]; arr2[j] = temp;
// tovabbra is monoton csokkeno a reszsorozatunk, forditsuk meg, hogy monoton novekedo legyen
for (j = i + 1; j < n + i - j; ++j)
{
temp = arr2[j]; arr2[j] = arr2[n + i - j]; arr2[n + i - j] = temp;
}
}
}
static void QuickSort(char[] arr2, int p, int r)
{
int Low, High;
char MidValue;
Low = p;
High = r;
MidValue = arr2[(p + r) / 2];
do
{
while (arr2[Low] < MidValue) ++Low;
while (arr2[High] > MidValue) --High;
if (Low <= High)
{
char T = arr2[Low];
arr2[Low] = arr2[High];
arr2[High] = T;
++Low;
--High;
}
} while (Low <= High);
if (p < High) QuickSort(arr2, p, High);
if (Low < r) QuickSort(arr2, Low, r);
}
static int findCeil(char[] str, char first, int l, int h)
{
int ceilIndex = l;
for (int i = l + 1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;
return ceilIndex;
}
static int stfindCeil(char[] str, char first, int l, int h)
{
int ceilIndex = l;
for (int i = l + 1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;
return ceilIndex;
}
static void IsmPermutacio(char[] tomb2, int[] N, int n, int[] W1, int s, int i)
{
int[] V = new int[n];
int[] W = new int[n];
CopyMemory(W, W1, (uint)(n * intSize));
//Array.Copy(W1, W, n);
if (i == 0)
{
for (int l = 0; l < s; ++l) W[l] = -1;
}
if (s != 0)
{
bool ind = true;
do
{
Kombinacio(V, s, N[i], ref ind);
if (!ind)
{
Betesz(N[i], n, V, W, i);
IsmPermutacio(tomb2, N, n, W, s - N[i], i + 1);
Kivesz(W, n, i);
}
} while (!ind);
}
else
{
Betesz(N[i], n, V, W, i);
//*****************************************************
/*for (int q = 0; q < n; ++q) Console.Write(tomb2[W[q]]);
Console.WriteLine("");*/
//*****************************************************
for (int l = 0; l < n; ++l) W[l] = -1;
}
}
static void Kombinacio(int[] V, int n, int k, ref bool ind)
{
if (ind)
{
for (int i = 0; i < k; ++i) V[i] = i;
ind = false;
return;
}
for (int i = k - 1; i > -1; --i)
{
if (V[i] < n - k + i)
{
++V[i];
for (int j = i + 1; j < k; ++j) V[j] = V[j - 1] + 1;
return;
}
}
ind = true;
}
static void Betesz(int ni, int n, int[] V, int[] W, int i)
{
int j = -1, l = 0;
for (int p = 0; p < ni; ++p)
{
while (l < n)
{
if (W[l] == -1) ++j;
if (j == V[p])
{
W[l] = i;
break;
}
++l;
}
}
}
static void Kivesz(int[] W, int n, int i)
{
for (int l = 0; l < n; ++l) if (W[l] == i) W[l] = -1;
}
static char[] Tomorito(char[] arr, ref int[] darabszamok)
{
int ig = arr.Length, tomindex = 0, arrindex = 0;
char[] tom = new char[arr.Length];
darabszamok = new int[arr.Length];
tom[tomindex] = arr[arrindex];
while (arrindex < ig)
{
if (arr[arrindex] == tom[tomindex]) ++darabszamok[tomindex];
else
{
++tomindex;
tom[tomindex] = arr[arrindex];
darabszamok[tomindex] = 1;
}
++arrindex;
}
Array.Resize(ref tom, 2 + tomindex);
Array.Resize(ref darabszamok, 2 + tomindex);
return tom;
}
}
public class Permutator
{
public char[] State { get; }
int _size;
bool isFinished = false;
public Permutator(char[] symbols)
{
if (symbols?.Length > 0)
{
_size = symbols.Length;
State = (char[])symbols.Clone();
QuickSort(State, 0, _size - 1);
//Array.Sort(State);
}
else
throw new ArgumentException("input must be non-empty");
}
public bool Next()
{
if (isFinished)
return false;
isFinished = !AdvanceState();
return !isFinished;
}
bool AdvanceState()
{
int i;
for (i = _size - 2; i >= 0; --i)
if (State[i] < State[i + 1])
break;
if (i == -1)
return false;
int ceilIndex = findCeil(State, State[i], i + 1, _size - 1);
char tmp = State[i];
State[i] = State[ceilIndex];
State[ceilIndex] = tmp;
QuickSort(State, i + 1, _size - 1);
//Array.Sort(State, i + 1, _size - i - 1);
return true;
}
int findCeil(char[] str, char first, int l, int h)
{
int ceilIndex = l;
for (int i = l + 1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;
return ceilIndex;
}
static void QuickSort(char[] arr2, int p, int r)
{//quicksort
int Low, High;
char MidValue;
Low = p;
High = r;
MidValue = arr2[(p + r) / 2];
do
{
while (arr2[Low] < MidValue) ++Low;
while (arr2[High] > MidValue) --High;
if (Low <= High)
{
char T = arr2[Low];
arr2[Low] = arr2[High];
arr2[High] = T;
++Low;
--High;
}
} while (Low <= High);
if (p < High) QuickSort(arr2, p, High);
if (Low < r) QuickSort(arr2, Low, r);
}
}
}
Az eredményből sajnos látszik az OOP hátránya: minél szigorúbban betartjuk az OOP alapelveit, annál lassabban oldjuk meg ugyanazt a feladatot.
Nem véletlenül lehet C-ben gyorsabb kódot írni(a fejlesztési idő hátrányára). A nem OOP Array.Sort esetén is lassú(103 sec.), tehát az Array.Sort helyett QuickSort()-ot használok.
Az egyetemi jegyzet kódját ez alapján készítettem el. Csak optimalizálni akartam.
Ekkor linkelte be "joysefke" az itt látható algoritmust. Azért az figyelemre méltó, hogy egyetemi jegyzetben nem a gyakorlati/hatékony megoldás van,
hanem egy robusztus/lassú kód. Azért 1 egyetemi jegyzetben lévő megoldástól az ember többet várna el(pontosabban én --de sztem nem vagyok egyedül-- ).
Azért gondoljunk bele: Az egyetemi jegyzet kódja kb. 15 percig fut, míg a többi kód 1 percen belül végez ugyanazzal a feladattal.
Közben kovisoft is írt kódot. Természetesen jelentősen gyorsabb még a nem OOP kódnál is, ezért a char tömbhöz hozzá tettem egy 'a' karaktert, és csak kovisoft kódját futtattam le
C-ben és C#-ban is. Az így módosított kód C#-ban 30.6 sec. alatt futott le. A következő C kódban pedig 26.6 sec alatt. Itt "csak" 4 sec. a különbség a C és a C# között a C javára.
Ha még 1 'b' karaktert is hozzá teszek, akkor 3 perc alatt fut le C-ben, és 3.5 perc alatt C#-ban. Tehát a C kód:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/timeb.h>
void QuickSort(char* arr2, int p, int r)
{
int Low, High;
char MidValue;
Low = p;
High = r;
MidValue = arr2[(p + r) / 2];
do
{
while (arr2[Low] < MidValue) ++Low;
while (arr2[High] > MidValue) --High;
if (Low <= High)
{
char T = arr2[Low];
arr2[Low] = arr2[High];
arr2[High] = T;
++Low;
--High;
}
} while (Low <= High);
if (p < High) QuickSort(arr2, p, High);
if (Low < r) QuickSort(arr2, Low, r);
}
void permism(char str_1[])
{
int n = strlen(str_1);
char* str = (char*)malloc(sizeof(char) * (n + 1));
if (str == NULL) {
printf("Memory not allocated.\r\n");
exit(0);
}
strcpy(str, str_1);
QuickSort(str, 0, n - 1);
int i, j;
char temp;
long db = 0;
for (;;)
{
++db;
// kiirjuk az aktualis permutaciot
//printf("%s\n", str);
// megkeressuk, hol kezdodik az utolso monoton csokkeno reszsorozat
for (i = n - 2; i >= 0 && str[i] >= str[i + 1]; i--);
// ha a teljes sorozat monoton csokkeno, akkor vegeztunk
if (i < 0) break;
// a csokkeno reszsorozat elotti elemet ki kell cserelnunk a reszsorozatban nagysag szerint rakovetkezovel
for (j = n - 1; str[j] <= str[i]; j--);
temp = str[i]; str[i] = str[j]; str[j] = temp;
// tovabbra is monoton csokkeno a reszsorozatunk, forditsuk meg, hogy monoton novekedo legyen
for (j = i + 1; j < n + i - j; j++)
{
temp = str[j]; str[j] = str[n + i - j]; str[n + i - j] = temp;
}
}
printf("%ld\r\n", db);
free(str);
}
long timediff(struct timeb* start, struct timeb* end)
{
long seconds;
seconds = (long)(end->time - start->time);
start->millitm = end->millitm - start->millitm;
if (0 > start->millitm) {
start->millitm += 1000;
seconds--;
}
return seconds;
}
void teszt()
{
struct timeb start, end;
long seconds;
int militm;
char str[] = "abcdanananaabcdanana";
//char str[] = "ACBC";
ftime(&start);
permism(str);
ftime(&end);
seconds = timediff(&start, &end);
militm = start.millitm;
printf("elapsed time %ld.%03d seconds\n", seconds, militm);
}
int main()
{
teszt();
return 0;
}