Diskuze: Porovnání rychlosti bubblesortu

krysta24

Člen

krysta24:16.4.2019 19:23

O obecné rady, co by šlo, jak napsat elegantněji. Jsem si vědom, že to zdaleka není ideální. Kód slouží jen pro demonstraci. - Je to trochu frankenstein nakopírovaný z mojich jiných programů ve volné hodině.

Zkusil jsem: Přemýšlet.

Chci docílit: Zjistit, proč je vylepšené řešení mého bubblesortu stále tak pomalé. Očekával bych několikanásobné zrychlení, ale dostavuje se jen zrychlení v řádu %. Pomůžete mi vysvětlit v čem je problém? Případně, jak ho opravit? Když přesunuju jen každý 4. prvek, tak bych očekával zhruba 4násobné zrychlení. Pokud tam vložím jen jeden "neseřazený", tak je čas prakticky 0 (stopwatch nic nezměří ani na poli v řádu desetitisíců).

static int[] bubbleSort(int[] pole)
        {
            for (int k = 0; k < pole.Length - 1; k++)
            {
                for (int i = 0; i < pole.Length - k - 1; i++)
                {
                    if (pole[i] > pole[i + 1])
                    {
                        vymen(ref pole[i], ref pole[i + 1]);
                    }
                }
            }
            return pole;
        }
        static int[] vylepsenyBubbleSort(int[] pole)
        {
            int k=0;
            bool prehozene = true;
            while (prehozene == true)
            {
                prehozene = false;
                for (int i = 0; i < pole.Length - k - 1; i++)
                {
                    if (pole[i] > pole[i + 1])
                    {
                        vymen(ref pole[i], ref pole[i + 1]);
                        prehozene = true;
                    }
                }
                k++;

            }
            return pole;
        }

Celý program

using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Porovnani_ryhlosti_bubblesort_na_serazenem_poli
{
    class Program
    {
        static void vymen(ref int a, ref int b)
        {
            int pom = b;
            b = a;
            a = pom;
        }
        static int[] bubbleSort(int[] pole)
        {
            for (int k = 0; k < pole.Length - 1; k++)
            {
                for (int i = 0; i < pole.Length - k - 1; i++)
                {
                    if (pole[i] > pole[i + 1])
                    {
                        vymen(ref pole[i], ref pole[i + 1]);
                    }
                }
            }
            return pole;
        }
        static int[] vylepsenyBubbleSort(int[] pole)
        {
            int k=0;
            bool prehozene = true;
            while (prehozene == true)
            {
                prehozene = false;
                for (int i = 0; i < pole.Length - k - 1; i++)
                {
                    if (pole[i] > pole[i + 1])
                    {
                        vymen(ref pole[i], ref pole[i + 1]);
                        prehozene = true;
                    }
                }
                k++;

            }
            return pole;
        }
        static int[] serazenePole(int velikostPole)
        {
            int[] pole = new int[velikostPole];
            Random nahodne = new Random();
            for (int i = 0; i < velikostPole; i++)
            {
                if (i % 4 == 0) // kazdy ctvrty prvke bude nahodny
                {
                    pole[i] = nahodne.Next(0, velikostPole*10);
                }
                else
                {
                    pole[i] = i;
                }
            }
            return pole;
        }
        static void vypisPole(int[] pole)
        {
            for (int i = 0; i < pole.Length; i++)
            {
                Console.Write(pole[i] + " ");
            }
            Console.WriteLine();
        }
        static void Main(string[] args)
        {

            Console.Write("Zadejte delku pole: ");
            int delka = int.Parse(Console.ReadLine());
            int[] razenePole = serazenePole(delka);
            vypisPole(razenePole);

            int[] pole2 = razenePole.Clone() as int[];
            //vypisPole(pole2);
            Stopwatch stopWatch2 = new Stopwatch();
            stopWatch2.Start();
            pole2 = bubbleSort(pole2);
            stopWatch2.Stop();
            //vypisPole(pole2);
            TimeSpan ts2 = stopWatch2.Elapsed;

            // Format and display the TimeSpan value.
            string elapsedTime2 = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
                ts2.Hours, ts2.Minutes, ts2.Seconds,
                ts2.Milliseconds / 10);
            Console.WriteLine("RunTime " + elapsedTime2);

            int[] pole3 = razenePole.Clone() as int[];
            //vypisPole(pole3);
            Stopwatch stopWatch3 = new Stopwatch();
            stopWatch3.Start();
            pole3 = vylepsenyBubbleSort(pole3);
            stopWatch3.Stop();
            //vypisPole(pole3);
            TimeSpan ts3 = stopWatch3.Elapsed;

            // Format and display the TimeSpan value.
            string elapsedTime3 = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
                ts3.Hours, ts3.Minutes, ts3.Seconds,
                ts3.Milliseconds / 10);
            Console.WriteLine("RunTime " + elapsedTime3);
            Console.ReadKey();
        }
    }
}

Editováno 16.4.2019 19:24

Odpovědět

16.4.2019 19:23

David Hartinger

Vlastník

David Hartinger:16.4.2019 19:43

Pokud ti to nejde lineárně zrychlit, tak časová složitost není lineární. Ono by to i dávalo smysl, protože BS ji má kvadratickou v nejhorším případě (čísla jdou pozpátku a vše se musí prohodit) a lineární v tom nejlepším (je to již setříděné). Ty máš něco mezi, takže to nebude tak, že to 4x zlepšíš a on se 4x zrychlí Nejlepší budeš mít, když si vypíšeš pod sebe jednotlivé kroky (obsahy pole po projetí vnějšího cyklu) a uvidíš, kolik jich to musí udělat oproti úplně náhodnému poli.

Úvod do časové složitosti zde na síti jsi předpokládám četl - https://www.itnetwork.cz/…st-stabilita

Editováno 16.4.2019 19:44

Nahoru Odpovědět

16.4.2019 19:43

New kid back on the block with a R.I.P

krysta24

Člen

krysta24:16.4.2019 20:13

Díky, toho, že obtížnost neroste lineárně jsem si vědom.

Nicméně uvažoval jsem takto, že z většiny seřazené pole na tom bude daleko lépe než "náhodné" (přes Random).

Výsledky, které jsem teď porovnal mezi náhodným (první čísla patří k normálnímu, 2. k vylepšenému)

Pocet kroku je 199990000
RunTime 00:00:02.26
Pocet kroku je 199860205
RunTime 00:00:02.32

a 3/4 uspořádaným

Pocet kroku je 199990000
RunTime 00:00:01.07
Pocet kroku je 199702339
RunTime 00:00:01.07

Oba s 20000 prvky, čísla od 1 do 20000.

Očekával bych, že metoda vylepsenyBubbleSort bude v 2. případě znatelně lepší v porovnání s 1. Ve skutečnosti je tomu spíše naopak.

Je to podle tebe v pořádku?

Editováno 16.4.2019 20:14

Nahoru Odpovědět

16.4.2019 20:13

David Hartinger

Vlastník

David Hartinger:16.4.2019 20:24

Může to být správně. Nejsem matematik, ale kvadratická složitost je sviňa. Když si představíš, že seřazené pole o 10 prvcích to udělá za 10 porovnání (lineární složitost), ale náhodné za 100 prohození. Tak u 20000 prvků je ten rozdíl |20000 - 400000000|. Počítám krok jinak než ty, ale naskáče to tam slušně. To vylepšení to prostě o tolik nespraví a vzhledem k tomu, že jsou tam nějaké instrukce navíc (další proměnná a práce s ní), může to být ve finále i pomalejší. Můžeš to ještě zkusit s menším počtem prvků.

Ty ten algoritmus nezlepšuješ na úrovni složitosti, tak je stále stejná, takže pro dostatečně velká n to bude stejné, což +/- je.

Editováno 16.4.2019 20:25

Akceptované řešení
+20 Zkušeností
+2,50 Kč

Nahoru Odpovědět

16.4.2019 20:24

New kid back on the block with a R.I.P

krysta24

Člen

krysta24:16.4.2019 21:18

Asi to tak vypadá. Moje původní představa o projití toho seřazeného pole byla, že by se z toho "vytahaly" ty čísla navíc (většinou jsou řádově větší než ty okolo) na konec a zbyly by ty víceméně seřazené.

Trochu jsem si s tím ještě hrál (intervaly vložení nahodných čísel a velikost pole), a zdá se mi, že u menších polí, jsou ty rozdíly skutečně nejvýraznější.

Nahoru Odpovědět

16.4.2019 21:18

Peter Mlich

Člen

Peter Mlich:18.4.2019 8:29

Zkus si napsat insert sort s tim, ze neporovnavas pole od 0, 1, 2, 3... ale odprostredka, pulku, pulku...

Bubble sort funguje takto:
ooooooo1
oooooo1
ooooo1
oooo1
ooo1
oo1
o1
1
Coz je velike mnozstvi porovnavacich operaci (suma(o)+suma(1)).
suma = 8+7+6+5+4+3+2+1 = 15 + 11 + 10 = 36

Insert to middle v nejhorsim pripade
1.
o1.
xo1.
xoo1.
xxoo1.
xxoxo1.
xxxoxo1.
xxxoxoo1
Opet, suma o a 1. x je hodnota, ktera se neporovnava.
suma = 1 + 2 + 2 + 3 +3 + 3 + 3 + 4 = 10 + 5 + 6 = 21
Pocty porovnani podle delky pole by sly napsat i takto:
x
00
01
000
001
010
011
0000
0001
0010
0011
0100
...

Zpet k tve otazce...
Tvuj algoritmus se snazi napodobovat quick sort, ale ne tak uplne. Ktery samozrejme v nejhorsim pripade ma stejne skore jako bubble sort. Nejhorsi pripad pro nej nastava u serazeni pole opacne, 9,8,7,6,5,4,3,2,1.
V podstate dela totez co bubble sort. Jedina zmena je v tom, ze muze skoncit o neco drive.

Ja jsem si delal takove slozitejsi testy, kdy jsem sledoval cas, za jak dlouho seradi algoritmus pole. Pole, bud vygenerujes 1000 nahodnych cisel nebo od 0 do 999 a pak to zamichas.
krok1: zkopiruje 0-10 z pole, zapni cas, serad pomoci alg1, zapis cas[0] a suma_cas[0].
krok2: zkopiruje 0-10 z pole, zapni cas, serad pomoci alg2, zapis cas[1] a suma_cas[1].
if (suma_cas[0]<x) potom zastav krok1 pro pole 0-100
if (suma_cas[0]<x) potom zastav krok2 pro pole 0-100
...
Cim dele algoritmus vydrzi, tim je rychlejsi.
https://mlich.zam.slu.cz/…sorting3.htm
[+ effective], start effective
Neprijemne je, ze moderni cpu a prohlizece maji optimalizace, takze si pamatuji vysledky z prechozich kroku, pokud byla pouzita stejna data a stejne algoritmy. Takze, treba ve Firefox naskakuji ty casy divne
Ten druhy test, tam mam asi zrovna nastavene nejake neodladene veci, ktere se zacykluji Ten zac pocita pocet operaci.
Ano, pocet operaci porovnani ma vliv na rychlost. Ale take dalsi operace. Jako napriklad presun prvku. Ten rozdil vidis u klasickeho insert sortu a upraveneho.

A jeste mma jeden zajimavy test. Serazeni 4 cisel.
https://mlich.zam.slu.cz/…-sort-x2.htm
Cim mensi cislo Avg, tim lepe.
Zajimavy je prvni sloupec. to je naticni alg. prohlizece. Zkus Explorer, Edge, Operu, Chrome, Firefox (co mas). Kazdy pouziva neco jineho.

Editováno 18.4.2019 8:32

Nahoru Odpovědět

18.4.2019 8:29