Új hozzászólás Aktív témák

• #9473 pmonitor aktív tag joysefke #9471

  Új Válasz 2021-02-14 10:24:54 #9473

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  pmonitor

  aktív tag

  válasz joysefke #9471 üzenetére

  Készítettem az eredeti OOP kódodra egy kis módosítást. Meg Készítettem 2 nem OOP metódust(az egyik static, a másikhoz példányosítani kell). A nem OOP metódusokban Array.Sort()-ok helyett quicksort-ot használtam. Ezek a kódok hasítanak! A kódokban a kiíratásokat kommenteztem ki(na meg az Array.Sort-ok helyét):
  using System;
using System.Diagnostics;

namespace TesztConsole
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(DateTime.Now);
//int i = 0;
int jmax = 25000;
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;
sw.Start();
for (int j = 0; j < jmax; ++j)
{
var p = new Permutator("abcdananana".ToCharArray());
do
{
/*i++;
Console.WriteLine(new string(p.State));*/
}
while (p.Next());
//Console.WriteLine($"Nr of results: {i}");
}
t_1 = sw.ElapsedMilliseconds;
GC.Collect();
t_2 = sw.ElapsedMilliseconds;
for (int j = 0; j < jmax; ++j) new Program().Teszt_qsort("abcdananana".ToCharArray());
t_3 = sw.ElapsedMilliseconds;
GC.Collect();
t_4 = sw.ElapsedMilliseconds;
for (int j = 0; j < jmax; ++j)
{
var p = new Permutator_modositott("abcdananana".ToCharArray());
do
{
/*i++;
Console.WriteLine(new string(p.State));*/
}
while (p.Next());
//Console.WriteLine($"Nr of results: {i}");
}
t_5 = sw.ElapsedMilliseconds;
GC.Collect();
t_6 = sw.ElapsedMilliseconds;
for (int j = 0; j < jmax; ++j) stTeszt_qsort("abcdananana".ToCharArray());
t_7 = sw.ElapsedMilliseconds;
Console.WriteLine("Eredeti: {0}", t_1);
Console.WriteLine("Módosított: {0}", t_5 - t_4);
Console.WriteLine("Nem OOP: {0}", t_3 - t_2);
Console.WriteLine("Nem OOP static: {0}", t_7 - t_6);
}

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);
}

int findCeilInt(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;
}

void Teszt_qsort(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 = findCeilInt(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 int stfindCeilInt(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 stTeszt_qsort(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 = stfindCeilInt(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);
}
}
}
}
public class Permutator_modositott
{
public char[] State { get; }
int _size;
bool isFinished = false;
public Permutator_modositott(char[] symbols)
{
if (symbols?.Length > 0)
{
_size = symbols.Length;
State = (char[])symbols.Clone();
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, j;
for (i = _size - 2, j = _size - 1; i >= 0; --i, --j)
if (State[i] < State[j])
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;
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;
}
}

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();
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;
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;
}
}
}

  Az eredmény:
  Eredeti: 46213
Módosított: 45772
Nem OOP: 14693
Nem OOP static: 14295

  Látszik, hogy a qsort alkalmazásával kb. harmada idő alatt lefutnak.

  Érdemes lenne a rendezésre is csinálni teszteket.
  De most nincs időm.

• #9472 pmonitor aktív tag joysefke #9471

  Új Válasz 2021-02-13 21:24:23 #9472

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  pmonitor

  aktív tag

  válasz joysefke #9471 üzenetére

  bent maradt a hot pathban a Console.WriteLine()

  Ez nem maradt benn a tesztelős kódban. Ha megnézed a Main-t, akkor láthatod, hogy ez nem a teszt kódja.

Új hozzászólás Aktív témák