[C#] Copy and Clone, List<> and KeyedCollection<>

[liquid_ice]

Ik heb 2 afzonderlijke lijsten (een List<> en een KeyedCollection<>).
Deze 2 lijsten zitten samen in een classe TMeeting (jaja, sommige weten al waar het voor is)

Nou moet ik meerdere objecten van TMeeting maken, maar als ik dat doe en ik verander iets in 1 van deze objecten...
dan is het in alle objecten veranderd...
Hoe moet ik deze lijsten goed copieren?

versimpelde weergave van TMeeting

code:

class TMeeting
    {
        private TMemberList Members;
        private List<THous> Houses;
        private int max_nr_houses;
        private int max_nr_invalid_houses;

        public TMeeting(int max_houses, int max_invalid)
        {
            
            this.max_nr_houses = max_houses;
            this.max_nr_invalid_houses = max_invalid;
            Houses = new List<THous>();
            Members = new TMemberList();
        }

        public void CopyMeeting(ref TMeeting NewMeeting)
        {
            THous[] temp_hous = new THous[this.Houses.Count];
            TMember[] temp_member = new TMember[this.Members.Count];
            this.Houses.CopyTo(temp_hous);
            this.Members.CopyTo(temp_member,0);
            foreach(THous hous in temp_hous)
            {
                NewMeeting.AddHous(hous);
            }
            foreach(TMember member in temp_member)
            {
                NewMeeting.Members.Add(member);
            }
        }

    }

De TMemberList:

code:

class TMemberList: KeyedCollection<string, TMember>
    {
        public TMemberList() : base() { }

        protected override string GetKeyForItem(TMember item)
        {
            // In this example, the key is the part number.
            return item.memberNaam;
        }
    }

[Verwijderd]

code:

List<Object> copy = list.Clone();

zoiets toch? Lijkt me iig makkelijk te vinden met behulp van MSDN.

[ Voor 29% gewijzigd door Verwijderd op 03-07-2007 15:18 ]

[Woy]

Dat cloned de objecten volgens mij niet. Het is alleen een kopie van je lijst. Je zou het volgende kunnen doen.

C#:

public List<TMeeting> CloneList(List<TMeeting> list)
{
    List<TMeeting> result = new List<TMeeting>(list.Count);
    foreach(TMeeting meeting in list)
    {
           TMeeting clone = meeting.Clone();
           result.Add(clone);
    }
    return result;
}

Je zult dan alleen een clone moeten implementeren. Maar zo te zien heb je dat al soortement gedaan met CopyMeeting

[Alex Picard]

Interessante linkjes:
shallow versus deep copying
Should we Obsolete ICloneable

[liquid_ice]

Met betrekking tot de deep en shallow.

De ene lijst bestaat uit THous objecten, welke een lijst van bedden is.
zie:

code:

class THous:List<TBed>

een TBed heeft weer een lijst met mensen in dat betreffende bed.

code:

private List<TMember> kamergenootjes;

De andere lijst is een MemberList, welke erft van de Keyed Collection

code:

class TMemberList: KeyedCollection<string, TMember>

De class TMember zelf bestaat gewoon uit wat int's strings, string-array's en een enkele enum.

[liquid_ice]

@rwb: ik snap het nut niet helemaal van beide lijsten.
De functie zit in een classe, dus 1 van de lijsten is toch gewoon

code:

this.

public List<TMeeting> CloneList(List<TMeeting> list)

De inplementatie van Clone heb ik al, maar die lijkt dus niet te werken...

[Hydra]

liquid_ice schreef op dinsdag 03 juli 2007 @ 16:48:
De inplementatie van Clone heb ik al, maar die lijkt dus niet te werken...

Een clone van een lijst bevat referenties naar de originele objecten, dat is een shallow clone. Als je een deepclone with doen (dus dat je objecten in de lijst ook gecloned worden) dan zul je daar zelf een functie voor moeten schrijven. Check anders die eerder gegeven links even.

[whoami]

Wat je kan doen, is je object / collection serializen, en dan weer deserializen. Heb je meteen een deep-clone.

[Hydra]

whoami schreef op dinsdag 03 juli 2007 @ 17:41:
Wat je kan doen, is je object / collection serializen, en dan weer deserializen. Heb je meteen een deep-clone.

Lijkt me nogal inefficient...En uh...lui.

[liquid_ice]

Ik weet niet wat je bedoelt met serializen en deserializen.
kan je dat aub ff toelichten?

[whoami]

liquid_ice schreef op dinsdag 03 juli 2007 @ 17:51:
Ik weet niet wat je bedoelt met serializen en deserializen.
kan je dat aub ff toelichten?

Kan je dat ff opzoeken in de MSDN ? Gewoon de keyworden Serialize / Deserialize of Serializen / Deserializen zullen wel genoeg zijn lijkt me.
Het komt erop neer dat je je object 'persist' naar een MemoryStream bv, en deze dan opnieuw 'unpersist'.

Hydra schreef op dinsdag 03 juli 2007 @ 17:50:
[...]


Lijkt me nogal inefficient...En uh...lui.

Innefficiënt ? Mwah, dat zal er vanaf hangen, ik denk dat het nogal meevalt.
Lui ? Tja .... zowiezo is het dan niet nodig om je Clone() functie aan te passen als je je classes aanpast (field erbij, field verwijderen,...), dus dat is fijn.

[ Voor 30% gewijzigd door whoami op 03-07-2007 18:35 ]

[riezebosch]

whoami schreef op dinsdag 03 juli 2007 @ 17:41:
Wat je kan doen, is je object / collection serializen, en dan weer deserializen. Heb je meteen een deep-clone.

Toen ik je antwoord las dacht ik gelijk dat ik het al een keer eerder had gelezen, en moest zelfs even controleren of het niet het oude topic was wat weer omhoog gekomen was. En toen ik even ging zoeken bleek zelfs dat jij het zelf was die ook al in een eerder topic eenzelfde antwoord gegeven had

[Woy]

liquid_ice schreef op dinsdag 03 juli 2007 @ 16:48:
@rwb: ik snap het nut niet helemaal van beide lijsten.
De functie zit in een classe, dus 1 van de lijsten is toch gewoon

code:

this.

public List<TMeeting> CloneList(List<TMeeting> list)

De inplementatie van Clone heb ik al, maar die lijkt dus niet te werken...

Als de functie die ik gaf een member van List<T> zou zijn zou je idd gewoon this. kunnen gebruiken. Ik was er echter vanuit gegaan dat je de standaard List<T> implementatie gebruikt en je er dus geen functies aan toe voegt.

De functie die ik gaf neemt een List<TMeeting> en stopt een clone van alle ellementen in een nieuwe lijst. Je zult deze functie ( eventueel static aangezien hij geen state bij houdt ) ergens in een logische class moeten stoppen

[Hydra]

whoami schreef op dinsdag 03 juli 2007 @ 18:34:
Innefficiënt ? Mwah, dat zal er vanaf hangen, ik denk dat het nogal meevalt.
Lui ? Tja .... zowiezo is het dan niet nodig om je Clone() functie aan te passen als je je classes aanpast (field erbij, field verwijderen,...), dus dat is fijn.

Tja. Je misbruikt eigenlijk een bepaalde functionaliteit voor een ander doel. Ik vind het niet netjes. Helemaal gezien het feit dat de TS nogal 'nieuw' is, lijkt het me een goed idee hem gewoon te vertellen hoe het 'hoort'.

[whoami]

Ik zeg nergens dat dit 'de enige manier' is.
Maar, als jij een betere, snellere, nettere oplossing weet, post ze gerust.

[Niemand_Anders]

Volgens is de oplossing vrij simpel. Gewoon ICloneable implementeren voor THous(e) en TMember.
CopyMeeting wordt dan als volgt:

code:

public void CopyMeeting(ref TMeeting newMeeting)
{
      foreach(THous hous in this.Houses)
          newMeeting.AddHous((THouse)  hous.Clone());
      foreach(TMember member in this.Members)
          newMeeting.Members.Add((TMember)  member.Clone());
}

Ofwel, THouse en TMember retouneren een kopie van zichzelf. THous krijgt een protected/private constructor waarmee alle properties kunnen worden gezet:

code:

public object Clone()
{
        return new THouse(this.beds, this.rooms, this.xx);        //aanroep van private/protected constructor
}

Verder nog een opmerking over je naming conventie. Die is namelijk nogal rommelig. Op basis van de class benaming denk ik dat je langere tijd in Delphi hebt geprogrammeerd. Als je de MSDN styling aanhoud is in principe alles Pascal Cased (elke eerst letter van een woord een hoofdletter - BackColor). Een uitzondering hierop zijn variabelen (non-public fields en argumenten). Deze zijn Camel cased (naam begint met kleine letter, andere eerste letters van een woord weer met hoofdletters - backColor).

[whoami]

In jouw clone method geef je dus gewoon de referentie door naar die Beds, en rooms, waardoor jouw 'geclonede' object gewoon nog steeds naar dezelfde instanties van Beds & Rooms wijst.

[Niemand_Anders]

Je hebt gelijk, Maar het ICloneable verhaal zal ook moeten worden doorgevoerd voor alle objecten die moeten waarvan een kopie moet worden gemaakt.

Object instances worden daarnaast standard als reference doorgegeven. Misschien is explicit boxing een oplossing. Ik weet niet of het werkt, maar misschien is het een gok waard:

code:

class THouse
{
    protected THouse([in] TBeds[] beds, [in] TRooms rooms, in type name..) { ... }
    public object Clone()
    {
         return new THouse(this.beds, this.rooms);
    }
}

Theoretisch zou dat het probleem moeten verhelpen. Want zou je binnen Clone() this.beds veranderen dan zou dat buiten de functie geen effect mogen hebben. Ik weet alleen niet hoe diep de boxing door werkt bij het 'in' keyword.

[EfBe]

Was het idee van een competitie niet dat je zelf op eigen kracht moet zien te winnen?

[Kwistnix]

riezebosch schreef op dinsdag 03 juli 2007 @ 19:18:
[...]

Toen ik je antwoord las dacht ik gelijk dat ik het al een keer eerder had gelezen, en moest zelfs even controleren of het niet het oude topic was wat weer omhoog gekomen was. En toen ik even ging zoeken bleek zelfs dat jij het zelf was die ook al in een eerder topic eenzelfde antwoord gegeven had

Ik ook, maar dan naar aanleiding van een artikel op Javaworld

http://www.javaworld.com/.../jw-javatip76.html?page=1

Op zich wel een aardige tip, maar niet altijd bruikbaar.

[Verwijderd]

Misschien niet geheel van toepassing in dit specifieke geval, maar zeker om even in je achterhoofd te houden: je gebruikt nu reference types waarbij er per definitie verschil is tussen deep clone en shallow copy (reference copy). Het kan zijn dat in jouw geval het gebruik van value types ipv reference types een oplossing biedt. Dit zijn in C# dus structures ipv classes (in Delphi: records ipv classes). Dit neemt bovendien wat overhead weg. In de meeste gevallen is deze overhead te verwaarlozen, maar als jij performance kritieke applicaties maakt en een enorme hoeveelheid kopieën maakt voor je algoritme kan deze overhead voelbaar worden.

Nogmaals weet ik niet of dit van toepassing is in dit specifieke geval, aangezien je kopieën maakt van lijsten waarbij de items weer lijsten bevatten. Deze lijsten zijn weer reference types en ben je weer terug bij af: deep clones. Uiteraard kan je dit omzeilen, wederom met verlaging van de overhead, middels arrays. Dit hangt allemaal erg van de betreffende applicatie af, maar misschien heb je er wat aan.

[whoami]

Verwijderd schreef op donderdag 05 juli 2007 @ 01:42:
Misschien niet geheel van toepassing in dit specifieke geval, maar zeker om even in je achterhoofd te houden: je gebruikt nu reference types waarbij er per definitie verschil is tussen deep clone en shallow copy (reference copy). Het kan zijn dat in jouw geval het gebruik van value types ipv reference types een oplossing biedt. Dit zijn in C# dus structures ipv classes (in Delphi: records ipv classes). Dit neemt bovendien wat overhead weg. In de meeste gevallen is deze overhead te verwaarlozen, maar als jij performance kritieke applicaties maakt en een enorme hoeveelheid kopieën maakt voor je algoritme kan deze overhead voelbaar worden.

Zeg jij nu dat je met een struct een betere performance kunt halen, dan met een class ?

[Kwistnix]

whoami schreef op donderdag 05 juli 2007 @ 10:00:
[...]
Zeg jij nu dat je met een struct een betere performance kunt halen, dan met een class ?

Stack allocatie is toch ook sneller?

[Woy]

FallenAngel666 schreef op donderdag 05 juli 2007 @ 12:11:
[...]
Stack allocatie is toch ook sneller?

Ja maar het onnodig kopieren van data niet. Dus als je een grote struct hebt die veel heen en weer gegeven wordt dan moet die telkens gekopieerd worden. Dat is dan natuurlijk niet zo efficient.

[EfBe]

een struct die groter is dan 16bytes is in principe niet efficienter dan een object allocated op de heap. Aldus MS in hun guidelines.

Overigens, is er al aan bod gekomen waarom er uberhaupt gecloned moet worden? Meestal heb je dat nl. niet nodig en is het algoritme gewoon brak.

[Woy]

EfBe schreef op donderdag 05 juli 2007 @ 12:58:
Overigens, is er al aan bod gekomen waarom er uberhaupt gecloned moet worden? Meestal heb je dat nl. niet nodig en is het algoritme gewoon brak.

Mmm.. zou je dat toe kunnen lichten?

[Verwijderd]

whoami schreef op donderdag 05 juli 2007 @ 10:00:
[...]
Zeg jij nu dat je met een struct een betere performance kunt halen, dan met een class ?

Ja, ik zeg dat het kan. En ik zal er nog wat aan toevoegen: classes kunnen ook sneller zijn dan structs. Ik zeg niet dat het altijd zo is, want het hangt, zoals hierboven ook gezegd, van de omvang van de struct af en de manier waarop je hem gebruikt. Ik verwacht in dit geval, waar bijvoorbeeld Bed een struct is, wel performance winst. Maargoed, dat moet TS zelf maar uitzoeken - het is een optie.

Ik denk trouwens dat de vraag van TS in dit topic voldoende beantwoord is. Of het algoritme wel of niet deugt moet TS zelf maar uitzoeken lijkt me.

[ Voor 19% gewijzigd door Verwijderd op 05-07-2007 13:38 ]

[liquid_ice]

Ik heb elke class een CopyTo gegeven...
De classes met een lijst doorlopen hun lijst gewoon en roepen steeds per element weer de CopyTo aan.

Wat betreft het algoritme, er zal heus nog wel genoeg te verbeteren zijn

[Woy]

Waarom een CopyTo methode? is het niet handiger om een soort van Copy Constructor te maken? Dan doe je het ongeveer zo bijvoorbeeld

C#:

class Test
{
    int aap;
    
    public Test(){/*Default Constructor*/}
    
    public Test( Test test )
    {
        aap = test.aap;
    }
}

Test a = new Test();
Test copy = new Test(a);

[Verwijderd]

Mij lijkt een vorm van compositie toch handiger:
Maak een een interface: bv DeepClonable met een methode 'object DeepClone()'
Elementen uit een lijst kun je vervolgens testen op op die interface en excepties gooien waar de interface niet geimplementeerd wordt. Weet je direct wat je nog aan moet passen.

Deze methode werkt alleen niet zo prettig met third-party libs. Dan is de optie van whoami een prima oplossing. Sowieso is het de meest pragmatische oplossing.

De vraag of je sowieso deep cloning nodig hebt lijkt me een hele goede. In de meeste gevallen kun je zonder.

[EfBe]

rwb schreef op donderdag 05 juli 2007 @ 13:05:
[clone vaak niet nodig]
Mmm.. zou je dat toe kunnen lichten?

Nou, semantisch is een clone een raar iets: want het stelt hetzelfde object voor, nl. de data vormt het object anders heb je alleen code en die is voor alle instances gelijk.

Het punt is dan dus: waarom wil je een clone? Als je een clone wilt als 'temporary' object voor een edit scherm bv, waarbij de gebruiker na 2 uur pielen met de data toch op cancel kan klikken, dan is daar op zich nog wel in te komen, maar dan is serializatie genoeg.

Wil je een clone voor andere zaken, omdat je in de knoei komt met wijzigingen op tijdstip T die je niet wilt zien op tijdstip T+t, dan is je algoritme verkeerd, immers: wijzigingen die je doorvoert op tijdstip T voer je door op een object en DUS is die wijziging valide, wil je daar later op T+t weer vanaf, dan moet je je afvragen waarom die wijziging op T uberhaupt hebt doorgevoerd.

[Woy]

EfBe schreef op donderdag 05 juli 2007 @ 16:47:
[...]

Nou, semantisch is een clone een raar iets: want het stelt hetzelfde object voor, nl. de data vormt het object anders heb je alleen code en die is voor alle instances gelijk.

Het punt is dan dus: waarom wil je een clone? Als je een clone wilt als 'temporary' object voor een edit scherm bv, waarbij de gebruiker na 2 uur pielen met de data toch op cancel kan klikken, dan is daar op zich nog wel in te komen, maar dan is serializatie genoeg.

Wil je een clone voor andere zaken, omdat je in de knoei komt met wijzigingen op tijdstip T die je niet wilt zien op tijdstip T+t, dan is je algoritme verkeerd, immers: wijzigingen die je doorvoert op tijdstip T voer je door op een object en DUS is die wijziging valide, wil je daar later op T+t weer vanaf, dan moet je je afvragen waarom die wijziging op T uberhaupt hebt doorgevoerd.

Ok op zich logisch. Maar stel je wilt iets brute forcen en je hebt een object T en daar kan je verschillende bewerkingen op doen zodat je bijvoorbeeld T+t1 en T+t2 kunt krijgen. Dan zou je toch graag eerst een kopie van T willen maken lijkt me, aangezien je het resultaat bijvoorbeeld weer wilt vergelijken

[Alex Picard]

Efbe, rwb: Het gaat hier dus om een algoritme dat gebruik maakt van Backtracking. Zoals rwb al opmerkt, is dit een brute force algoritme, waarbij je stapjes in een bepaalde richting neemt en deze op een later moment soms ongedaan wil maken om ergens in de reeks een alternatieve stap te maken.

Omdat brute force algoritmen in de regel nogal veel stappen kosten bij iets ingewikkeldere problemen, is het herhaaldelijk kopiëren van objecten erg ongunstig voor de performance. Door structs te gebruiken, zoals Negerzoen voorstelt, kun je enige performance winnen.

Als je enigszins efficiënter te werk wil gaan, kun je bijvoorbeeld Dynamisch programmeren toepassen.

Ik wens iedereen die meedoet aan de wedstrijd veel succes!

[EfBe]

Alex Picard schreef op donderdag 05 juli 2007 @ 18:03:
Efbe, rwb: Het gaat hier dus om een algoritme dat gebruik maakt van Backtracking. Zoals rwb al opmerkt, is dit een brute force algoritme, waarbij je stapjes in een bepaalde richting neemt en deze op een later moment soms ongedaan wil maken om ergens in de reeks een alternatieve stap te maken.

Backtracking is het fenomeen dat gebruik maakt van stackframes en als je dan aan komt zetten met een object graph dan gaat dat inderdaad niet lukken.

Omdat brute force algoritmen in de regel nogal veel stappen kosten bij iets ingewikkeldere problemen, is het herhaaldelijk kopiëren van objecten erg ongunstig voor de performance. Door structs te gebruiken, zoals Negerzoen voorstelt, kun je enige performance winnen.

Lijkt me onzin, de structs worden dan voor je gecopieerd, dus veel zal het niet opleveren.

Ik heb me niet zoveel in het probleem van de wedstrijd verdiept, maar wat ik ervan begreep is het kiezen van een brute force benadering nu juist niet de weg die je moet kiezen: je hebt nl. regels om het op te lossen. Ik weet niet of prolog mag maar dat zou ideaal zijn om dit op te lossen, het is nl. een logikwiz achtig probleem en dat wil prima in prolog.

Dus aan de topicstarter: think outside the box. Een brute force benadering is zelden tot nooit een goede oplossing tenzij er geen andere oplossing is (bv encryptie).

[Woy]

EfBe schreef op donderdag 05 juli 2007 @ 20:56:
[...]
Ik heb me niet zoveel in het probleem van de wedstrijd verdiept, maar wat ik ervan begreep is het kiezen van een brute force benadering nu juist niet de weg die je moet kiezen: je hebt nl. regels om het op te lossen. Ik weet niet of prolog mag maar dat zou ideaal zijn om dit op te lossen, het is nl. een logikwiz achtig probleem en dat wil prima in prolog.

Dus aan de topicstarter: think outside the box. Een brute force benadering is zelden tot nooit een goede oplossing tenzij er geen andere oplossing is (bv encryptie).

Ik heb de opdracht ook niet helemaal goed gelezen, maar ook als je gebruik van een heuristiek om te zoeken wil je toch een soort boom opbouwen lijkt me? Volgens mij hoeft er voor de opdracht niet perse 1 beste oplossing te zijn. Het is best mogenlijk dat er verschillende manieren zijn om een optimale indeling te maken.

[MrBucket]

-edit-
Eh, laat maar

[ Voor 95% gewijzigd door MrBucket op 06-07-2007 10:08 ]