Arrayer
↑Snabböversikt
Section titled “Snabböversikt”En array lagrar ett fast antal element av samma typ i en indexerad följd. I C# innehåller int[] heltal och values[0] läser första elementet. Indexering är O(1) eftersom positionen kan beräknas direkt.
| Operation | Typisk kostnad | Varför |
|---|---|---|
| Läs eller ersätt via index | O(1) |
Direkt indexering |
| Sök i osorterad array | O(n) |
Alla värden kan behöva granskas |
| Sätt in i mitten | O(n) |
Värden behöver flyttas eller kopieras |
| Gå igenom samtliga värden | O(n) |
Alla element behandlas |
Undersök index
Section titled “Undersök index”Prova själv
Index börjar på 0.
Index ger direkt åtkomst till ett värde utan att behöva leta från början.
Steg för steg
Section titled “Steg för steg”- Skapa arrayen.
new int[4]ger plats för fyra heltal, som börjar med värdet noll. - Spara ett värde.
values[2] = 9ersätter det tredje elementet. - Läs ett värde.
values[2]ger nu9på konstant tid. - Iterera. En loop går igenom värdena när alla måste behandlas.
int[] values = { 4, 8, 12, 16 };Console.WriteLine(values[2]); // 12values[1] = 10;foreach (int value in values) Console.WriteLine(value);#include <array>#include <iostream>std::array<int, 4> values{4, 8, 12, 16};std::cout << values[2] << '\n'; // 12values[1] = 10;for (int value : values) std::cout << value << '\n';Array eller dynamisk lista?
Section titled “Array eller dynamisk lista?”En array har en fast Length. List<int> kan växa men kan ibland behöva skapa en större underliggande array och kopiera värdena. Att lägga till sist tar vanligen amorterat O(1), men en enskild operation kan kräva mer arbete.
När passar en array?
Section titled “När passar en array?”Välj en array när storleken är känd, du vill ha snabb indexering eller ska arbeta med numeriska värden i en algoritm. Välj en lista när längden ofta förändras.
Array och dynamisk lista
Section titled “Array och dynamisk lista”En vanlig array har en bestämd längd. En dynamisk lista som C# List<T> använder normalt en intern array som ibland behöver växa. Det gör upprepade tillägg effektiva i genomsnitt, men att lägga in ett objekt längst fram kräver ofta att många andra värden flyttas.
Index är inte samma sak som sökning
Section titled “Index är inte samma sak som sökning”Om du känner till indexet är direkt åtkomst vanligen O(1). Att leta efter ett okänt värde kan kräva O(n) arbete. I en sorterad array kan du använda binärsökning, men insättning mitt i arrayen kostar fortfarande ofta O(n).
Välj efter behov
Section titled “Välj efter behov”Använd arrayer när storleken är känd och stabil. Använd en dynamisk lista när antalet objekt ändras. Mät allokeringar i prestandakritisk kod och tänk på hur samlingarna använder minnet.