Új hozzászólás Aktív témák
-
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: 14295Lá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.[ Szerkesztve ]
http://www.bferi.hu/download.php ; http://bferi.hu/egyeb.php
Új hozzászólás Aktív témák
● ha kódot szúrsz be, használd a PROGRAMKÓD formázási funkciót!
- D1Rect: Nagy "hülyétkapokazapróktól" topik
- Napelem
- Kompakt vízhűtés
- Samsung Galaxy Watch (Tizen és Wear OS) ingyenes számlapok, kupon kódok
- A Gigabyte is visszaveszi alaplapjainak alapértelmezett tuningját
- Villanyszerelés
- Politika
- NVIDIA GeForce RTX 4060 / 4070 S/Ti/TiS (AD104/103)
- A Honor és a Huawei uralja a kínai mobilpiacot
- Ezek a OnePlus 12 és 12R európai árai
- További aktív témák...