Minifeladatok III.

Az előző két minifeladat (Minifeladatok I és Minifeladatok II) az érték típusok tulajdonságairól szólt. Most az érték típusok talán legismertebb tulajdonságát vizsgáljuk meg közelebbről egy példán, mégpedig azt, hogy az érték típus reprezentációja érték szerint másolódik egyik változóról a másikra, míg a referencia típus esetében a reprezentációra egy hivatkozást tárolnak a változók, és csak a hivatkozások másolódnak.

Ennek következményeképpen az érték típusú változók másolgatása (paraméter átadás, visszatérési érték, egyszerű értékadás) drágább, hiszen egy referencia 4 (64 bitnél 8) byte, az érték típus reprezentációja viszont ennél több lehet.

A mai feladatott már több helyen ellőttem, remélem azért van, akinek új. A feladat megjósolni egy algoritmus futásideje közötti különbséget, attól függően, hogy érték típust vagy referencia típust használ.

Tegyük fel, hogy van egy típus:

public struct Item : IComparable<Item>
{
    public double P { get; set; }
    public double R { get; set; }
    public double N { get; set; }

    public int CompareTo(Item other)
    {
        return (this.P * this.R * this.N).CompareTo(other.P * other.R * other.N);
    } // CompareTo()
} // struct Item

Ez a típus 24 byte-ot foglal a reprezentációhoz. Az algoritmus, amit használni fogunk, egy rendező algoritmus, emiatt implementálja az Item az IComparable interfészt. Bár a Minifeladatok II esetében láttuk, hogy veszélyes lehet interfészen keresztül használni egy érték típust, a mi esetünkben ez a veszély nem áll fenn.

Az algoritmus, amit használni fogunk, nem más, mint a gyorsrendezés, az Array.Sort<T> által implementálva. Mivel generikus megvalósításról van szó, egy Item típusra testreszabott implementáció fog működni. Ennek köszönhetően a CompareTo nem interfész metódusként hívódik meg, hanem az Item sajátjaként, ami annyit jelent, hogy nincs szükség boxing műveletre.

Ahogy a gyorsrendezés algoritmusa fut, az Item-eket folyamatosan mozgatja egyik helytről a másikba a memóriában. Ez 24 byte mozdítását jelenti lépésenként. (két elem cseréje egy ideiglenes változón keresztül már 3 * 24 byte)

Ha az Item-et class-ként implementáljuk, akkor a 4 (8 byte)-os referenciák mozognak. Emiatt elvileg gyorsabban fut a rendezés.

A feladat

A gyorsrendezés (QuickSort) működésének ismeretében ki kell számolni, hogy a példa program által rendezett húszmillió Item átlagosan mekkora memóriamozgatással jár a referencia típusú Item és az érték típusú Item esetében.

Az átmozgatott adat mennyiségének ismeretében meg kell becsülni a két implementáció futásidejének arányát.

A példaprogram érték típusra:

namespace Rendezes
{
    using System;
    using System.Collections.Generic;
    using System.Diagnostics;

    public struct Item : IComparable<Item>
    {
        public double P { get; set; }
        public double R { get; set; }
        public double N { get; set; }

        public int CompareTo(Item other)
        {
            return (this.P * this.R * this.N).CompareTo(other.P * other.R * other.N);
        } // CompareTo()
    } // struct Item

    class Program
    {
        // Ez a metódus nem lényeges, csak véletlen értékkel
        // tölt fel egy Items tömböt
        static Item[] GenerateData(int count)
        {
            var generator = new Random();

            var result = new Item[count];

            // Bonusz kérdés, miért jobb a 'result.Length', mint a 'count'?
            for (var i = 0; i < result.Length; i++)
            {
                result[i] =
                    new Item
                    {
                        P = generator.NextDouble(),
                        R = generator.NextDouble(),
                        N = generator.NextDouble()
                    };
            } // for i

            return result;
        } // GenerateData()

        static void Main(string[] args)
        {
            var toBeSorted = GenerateData(20000000);

            var sw = Stopwatch.StartNew();

            Array.Sort(toBeSorted);

            Console.WriteLine("Rendezési idő: {0:s\\.fff}", sw.Elapsed);
        } // Main()
    } // class Program
} // namespace Rendezes

Referencia típushoz értelemszerűen csak a struct-ot kell class-ra átírni az Item definíciójában.

A kérdések tehát:

  • Mekkora adatmennyiség mozdul érték típus illetve referencia típus esetén?
  • A memória mozgatás alapján melyik esetben gyorsabb a rendezés?
  • Mi a valós eredmény?
  • Mi az eredmény oka?
  1. #1 by blaces on 2012. March 17. - 14:49

    Tetszenek a Minifeladatok, csak így tovább! Igaz még nem tudom őket megfejteni, egyetemi oktatás és öntanulás mellett is tanulhatok tőled sokat.
    A megoldások kifejtése nagyon tetszik, nagyon alapos, részletes. (Bár néha sok az új infó, és előfordul, hogy többször átolvasok egy bekezdést de simán megéri és megértem :))

    • #2 by Tóth Viktor on 2012. March 19. - 09:32

      Köszönöm, és örülök, ha tanulságosak a feladatok.

  1. Megoldás – Minifeladatok III. - pro C# tology - devPortal

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: