Share
Satsen är en samlingstyp som implementerar de grundläggande algebraiska uppsättningalgoritmerna, inklusive fackföreningen, korsningen, skillnaden och symmetrisk skillnad. Var och en av dessa algoritmer kommer att förklaras i detalj i respektive sektion.
Konceptuellt är uppsättningar samlingar av objekt som ofta har viss gemensamhet. Till exempel kan vi ha en uppsättning som innehåller positiva jämn heltal:
[2, 4, 6, 8, 10, ...]
Och en uppsättning som innehåller positiva udda heltal:
[1, 3, 5, 7, 9, ...]
Dessa två uppsättningar har inga gemensamma värden. Tänk nu på en tredje uppsättning som är alla faktorer i nummer 100:
[1, 2, 4, 5, 10, 20, 25, 50, 100]
Med tanke på dessa uppsättningar kan vi nu svara på frågan "Vilka faktorer på 100 är udda?" Genom att titta på uppsättningen odda heltal och uppsättningen faktorer med 100 och se vilka värden som finns i båda uppsättningarna. Men vi kan också svara på frågor som "Vilka udda tal är inte faktorer på 100?" Eller "Vilka positiva tal, jämnt eller udda, är inte faktorer på 100?"
Det här kanske inte verkar vara mycket användbart, men det beror på att exemplet är något konstruerat. Tänk om uppsättningarna var varje anställd hos ett företag och varje anställd som hade fullgjort den obligatoriska årliga träningen.
Vi kunde enkelt svara på frågan "Vilka anställda har inte slutfört obligatorisk utbildning?"
Vi kan fortsätta att lägga till ytterligare uppsättningar och börja svara på mycket komplexa frågor som, "Vilka heltidsanställda på säljteamet som har utfärdat ett företags kreditkort har inte deltagit i obligatorisk utbildning på den nya kostnadsrapporteringsprocessen?"
De Uppsättning klassen implementerar IEnumerable gränssnitt och accepterar ett generiskt argument som borde vara ett IComparable typ (testning för jämlikhet är nödvändig för att de inställda algoritmerna ska fungera).
Medlemmarna av uppsättningen kommer att finnas i en .NET Lista klass, men i praktiken finns uppsättningar ofta i trädstrukturer som ett binärt sökträd. Detta val av underliggande behållare påverkar komplexiteten hos de olika algoritmerna. Till exempel använder du Lista, innehåller har en komplexitet av O (n), medan användning av ett träd skulle resultera i O (log n) i genomsnitt.
Förutom de metoder som vi kommer att genomföra, Uppsättning innehåller en standardkonstruktor och en som accepterar en IEnumerable av objekt att fylla i med.
public class Set: IEnumerable där T: IComparable privat readonly List _items = new List (); public Set () public Set (IEnumerable items) AddRange (items); public void Add (T-post); public void AddRange (IEnumerable items); offentlig bool Ta bort (T-post); offentliga bool Innehåller (T-punkt); offentlig inträkning get; public Set Union (Ange andra); public Set Intersection (Ange andra); allmän inställd skillnad (set annan); Offentlig uppsättning symmetrisk skillnad (Ange andra); offentlig IEnumerator GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ();
| Beteende | Lägger till föremålet i uppsättningen. Om objektet redan finns i uppsättningen kastas en InvalidOperationException. |
| Prestanda | På) |
Vid genomförandet av Lägg till algoritm måste ett beslut fattas: kommer uppsättningen att tillåta dubbla objekt eller inte? Till exempel, med tanke på följande uppsättning:
[1, 2, 3, 4]
Om den som ringer försöker lägga till värdet tre, blir satsen:
[1, 2, 3, 3, 4]
Även om detta kan vara acceptabelt i vissa sammanhang är det inte det beteende vi ska genomföra. Föreställ dig en uppsättning som innehåller alla elever på en lokal högskola. Det skulle inte vara logiskt att låta samma student läggas till uppsättningen två gånger. Att försöka göra det är faktiskt ett fel (och kommer att behandlas som sådant i denna implementering).
Notera: Lägg till använder innehåller Metod
Accentsconagua
public void Lägg till (T item) if (Innehåller (objekt)) släng nytt InvalidOperationException ("Föremålet finns redan i Set"); _items.Add (item); | Beteende | Lägger till flera objekt i uppsättningen. Om någon medlem av ingångsräkaren finns i uppsättningen eller om det finns dubbla objekt i inmatningsräknaren, kommer en InvalidOperationException att kastas. |
| Prestanda | O (mn), där m är antalet poster i ingångsräkningen och n är antalet objekt som för närvarande finns i uppsättningen. |
public void AddRange (IEnumerable items) foreach (T-post i objekt) Lägg till (objekt);
| Beteende | Tar bort det angivna värdet från uppsättningen om det hittades, och returnerar sant. Om uppsättningen inte innehåller det angivna värdet returneras false. |
| Prestanda | På) |
public bool Ta bort (T-punkt) return _items.Remove (item);
| Beteende | Returnerar sant om uppsättningen innehåller det angivna värdet. Annars returneras det falskt. |
| Prestanda | På) |
public bool Innehåller (T item) return _items.Contains (item);
| Beteende | Returnerar antalet objekt i uppsättningen eller 0 om uppsättningen är tom. |
| Prestanda | O (1) |
public int Count get return _items.Count;
| Beteende | Returnerar en räknare för alla objekt i uppsättningen. |
| Prestanda | O (1) för att returnera uppräknaren. Att räkna upp alla objekt har en komplexitet på O (n). |
offentlig IEnumerator GetEnumerator () return _items.GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () return _items.GetEnumerator ();
| Beteende | Returnerar en ny uppsättning som är resultatet av fackföreningen för nuvarande och ingångssatsen. |
| Prestanda | O (mn), där m och n är antalet artiklar i respektive och aktuella uppsättningar. |
Sammansättningen av två uppsättningar är en uppsättning som innehåller alla de distinkta föremålen som finns i båda uppsättningarna.
Till exempel ges två uppsättningar (vardera representerade i rött):
Två ingångssatser före fackföreningen När unionsoperationen utförs innehåller utgångssatsen alla objekt i båda uppsättningarna. Om det finns några föremål som finns i båda uppsättningarna, läggs bara en enda kopia av varje objekt till utgångssatsen.
Utgångsinställningen efter fackföreningen (återställda objekt är gula) Ett mer konkret exempel kan ses när vi förenar flera uppsättningar av heltal:
[1, 2, 3, 4] union [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
public Set Union (Ange andra) Ange resultat = nytt Set (_items); foreach (T-post i other._items) if (! Contains (item)) result.Add (item); returresultat;
| Beteende | Returnerar en ny uppsättning som är resultatet av skärningsläget för nuvarande och ingångssatserna. |
| Prestanda | O (mn), där m och n är antalet artiklar i respektive och aktuella uppsättningar. |
Korsning är den punkt där två uppsättningar "skär", till exempel deras gemensamma medlemmar. Med hjälp av Venn-diagrammet från fackföreningen visas skärningen av de två uppsättningarna här:
Korsningen mellan de två ingångssatserna visas i gult Eller, med hjälp av uppsättningar av heltal:
[1, 2, 3, 4] korsas [3, 4, 5, 6] = [3, 4]
public Set Intersection (Ange andra) Ange resultat = ny Set (); foreach (T item i _items) if (other._items.Contains (item)) result.Add (item); returresultat;
| Beteende | Returnerar en ny uppsättning som är resultatet av skillnadsoperationen för nuvarande och ingångssatserna. |
| Prestanda | O (mn), där m och n är antalet artiklar i respektive och aktuella uppsättningar. |
Skillnaden eller inställd skillnad mellan två uppsättningar är de objekt som finns i den första uppsättningen (den uppsättning vars Skillnad metod kallas), men existerar inte i den andra uppsättningen (metodens parameter). Venn-diagrammet för denna metod visas här med den returnerade uppsättningen i gul:
Den inställda skillnaden mellan två uppsättningar Eller, med hjälp av uppsättningar av heltal:
[1, 2, 3, 4] skillnad [3, 4, 5, 6] = [1, 2]
Offentlig inställd skillnad (Ange andra) Ange resultat = Ny uppsättning (_items); foreach (T-post i other._items) result.Remove (item); returresultat
| Beteende | Returnerar en ny uppsättning som är resultatet av den symmetriska skillnadsoperationen för nuvarande och ingångssatserna. |
| Prestanda | O (mn), där m och n är antalet artiklar i respektive och aktuella uppsättningar. |
Den symmetriska skillnaden mellan två uppsättningar är en uppsättning vars medlemmar är de objekt som existerar i endast en eller den andra uppsättningen. Venn-diagrammet för den här metoden visas här med den returnerade uppsättningen i gul
Den symmetriska skillnaden mellan två uppsättningar Eller med hjälp av heltalssatser:
[1, 2, 3, 4] symmetrisk skillnad [3, 4, 5, 6] = [1, 2, 5, 6]
Du kanske har märkt att detta är det exakta motsatsen till korsningen. Med detta i åtanke, låt oss se vad det skulle ta för att hitta den symmetriska skillnaden med endast de uppsatta algoritmer som vi redan har tittat på.
Låt oss gå igenom vad vi vill ha.
Vi vill ha en uppsättning som innehåller alla objekt från båda uppsättningarna förutom de som finns i båda. Eller sagt ett annat sätt, vi vill ha föreningen av båda uppsättningarna utom skärningspunkten för båda uppsättningarna. Vi vill ha den inställda skillnaden mellan facket och skärningen mellan båda uppsättningarna.
Steg för steg ser det ut så här:
[1, 2, 3, 4] union [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
[1, 2, 3, 4] genomskärning [3, 4, 5, 6] = [3, 4]
[1, 2, 3, 4, 5, 6] set skillnad [3, 4] = [1, 2, 5, 6]
Vilket ger den resulterande uppsättningen vi ville ha: ([1, 2, 5, 6]).
public Set SymmetricDifference (Ange andra) Set union = Union (andra); Ange skärningspunkt = Korsning (andra); returnera union.Förskjutning (korsning);
Du kanske undrar varför jag inte tillade en IsSubset metod. Denna typ av metod används vanligtvis för att bestämma om en uppsättning helt är innehållen i en annan uppsättning. Vi kanske till exempel vill veta om:
[1,2,3] är delmängd [O, 1, 2, 3, 4, 5] = Sann
av följande skäl:
[1,2,3] är delmängd [0, 1, 2] = falsk
Anledningen till att jag inte har detaljerat en IsSubset Metoden är att den kan utföras med hjälp av befintliga medel. Till exempel:
[1,2,3] skillnad [O, 1, 2, 3, 4, 5] = []
En tom resultatuppsättning visar att hela första uppsättningen var inne i den andra uppsättningen, så vi vet att den första uppsättningen är en komplett delmängd av den andra. Ett annat exempel, med hjälp av korsningen:
[1,2,3] genomskärning [O, 1, 2, 3, 4, 5] = [1,2,3]
Om utgångssatsen har samma antal element som ingångssatsen, vet vi att ingångssatsen är en delmängd av den andra uppsättningen.
I ett allmänt ändamål Ange klass, med en IsSubset Metoden kan vara användbar (och kan implementeras mer optimalt); Jag ville emellertid göra gällande att detta inte nödvändigtvis är ett nytt beteende, utan snarare bara ett annat sätt att tänka på befintlig verksamhet.
