Paralelní pole - Parallel array
V oblasti výpočetní techniky je skupina paralelních polí (také známá jako struktura polí nebo SoA) formou implicitní datové struktury, která používá více polí k reprezentaci singulárního pole záznamů . Uchovává samostatné, homogenní datové pole pro každé pole záznamu, přičemž každé má stejný počet prvků. Potom objekty umístěné na stejném indexu v každém poli jsou implicitně pole jednoho záznamu. Ukazatele z jednoho objektu na druhý jsou nahrazeny indexy pole. To kontrastuje s běžným přístupem ukládání všech polí každého záznamu společně do paměti (také známé jako pole struktur nebo AoS). Například je možné deklarovat pole se 100 názvy, z nichž každý je řetězec, a 100 věkových skupin, z nichž každé je celé číslo, přičemž každé jméno je přiřazeno k věku, který má stejný index.
Příklady
Příklad v C pomocí paralelních polí:
int ages[] = {0, 17, 2, 52, 25};
char *names[] = {"None", "Mike", "Billy", "Tom", "Stan"};
int parent[] = {0 /*None*/, 3 /*Tom*/, 1 /*Mike*/, 0 /*None*/, 3 /*Tom*/};
for (i = 1; i <= 4; i++) {
printf("Name: %s, Age: %d, Parent: %s \n",
names[i], ages[i], names[parent[i]]);
}
v Perlu (pomocí hash polí pro uchovávání odkazů na každé pole):
my %data = (
first_name => ['Joe', 'Bob', 'Frank', 'Hans' ],
last_name => ['Smith','Seger','Sinatra','Schultze'],
height_in_cm => [169, 158, 201, 199 ]);
for $i (0..$#{$data{first_name}}) {
printf "Name: %s %s\n", $data{first_name}[$i], $data{last_name}[$i];
printf "Height in CM: %i\n", $data{height_in_cm}[$i];
}
Nebo v Pythonu :
first_names = ["Joe", "Bob", "Frank", "Hans" ]
last_names = ["Smith","Seger","Sinatra","Schultze"]
heights_in_cm = [169, 158, 201, 199 ]
for i in range(len(first_names)):
print("Name: %s %s" % (first_names[i], last_names[i]))
print("Height in cm: %s" % heights_in_cm[i])
# Using zip:
for first_name, last_name, height_in_cm in zip(first_names, last_names, heights_in_cm):
print(f"Name: {first_name} {last_name}")
print(f"Height in cm: {height_in_cm}")
Výhody a nevýhody
Paralelní pole mají oproti běžnému přístupu řadu praktických výhod:
- V některých případech mohou ušetřit značné množství místa tím, že se vyhnou problémům se zarovnáním. Některé architektury například fungují nejlépe, pokud jsou vždy uložena 4bytová celá čísla začínající na paměťových místech, která jsou násobkem 4. Pokud bylo předchozí pole jeden bajt, mohou být zbytečné 3 bajty. Mnoho moderních kompilátorů se může automaticky vyhnout takovým problémům, ačkoli v minulosti někteří programátoři explicitně deklarovali pole v pořadí snižujících se omezení zarovnání.
- Pokud je počet položek malý, mohou indexy polí zabírat podstatně méně místa než plné ukazatele, zejména u některých architektur.
- Sekvenční zkoumání jednoho pole každého záznamu v poli je na moderních počítačích velmi rychlé, protože to představuje lineární procházení jednoho pole, které ukazuje ideální lokalitu chování referencí a mezipaměti.
- Mohou umožnit efektivní zpracování s instrukcemi SIMD v určitých architekturách sady instrukcí
Některé z těchto výhod silně závisí na konkrétním programovacím jazyce a používané implementaci.
Paralelní pole však mají také několik silných nevýhod, které slouží k vysvětlení, proč nejsou obecně upřednostňovány:
- Mají výrazně horší referenční polohu při nonsekvenční návštěvě záznamů a zkoumání více polí každého záznamu, protože různá pole mohou být uložena libovolně daleko od sebe.
- Zatemňují vztah mezi poli jednoho záznamu (např. Index mezi nimi neobsahuje informace o typu, index může být použit chybně).
- Mají malou přímou jazykovou podporu (jazyk a jeho syntaxe obvykle nevyjadřují žádný vztah mezi poli v paralelním poli a nemohou zachytit chyby).
- Protože svazek polí není „věc“, jeho předávání je únavné a náchylné k chybám. Například místo volání funkce, která má dělat něco s jedním záznamem (nebo strukturou nebo objektem), musí funkce brát pole jako samostatné argumenty. Když je přidáno nebo změněno nové pole, musí se změnit mnoho seznamů parametrů, kde by předávání objektů jako celku těmto změnám zcela zabránilo.
- Jejich růst nebo zmenšení je drahé, protože každé z několika polí musí být znovu přiděleno. Víceúrovňová pole mohou tento problém zlepšit, ale ovlivňují výkon díky dodatečnému přesměrování potřebnému k nalezení požadovaných prvků.
- Možná nejhorší ze všeho je, že výrazně zvyšují možnost chyb. Jakékoli vkládání, mazání nebo přesouvání musí být vždy důsledně aplikováno na všechna pole, jinak již nebudou pole mezi sebou synchronizována, což povede k bizarním výsledkům.
Špatnou referenční lokalitu lze v některých případech zmírnit: pokud lze strukturu rozdělit do skupin polí, ke kterým se obecně přistupuje společně, lze pro každou skupinu sestavit pole a jejími prvky jsou záznamy obsahující pouze tyto podmnožiny větších struktur pole. (viz design orientovaný na data ). Toto je cenný způsob, jak urychlit přístup k velmi velkým strukturám s mnoha členy, a přitom ponechat části struktury svázané dohromady. Alternativou k jejich spojování pomocí indexů polí je použití odkazů ke spojení částí dohromady, ale to může být méně efektivní v čase a prostoru.
Další alternativou je použití jednoho pole, kde každý záznam je struktura záznamu. Mnoho jazyků poskytuje způsob deklarace skutečných záznamů a jejich polí. V jiných jazycích může být možné to simulovat deklarací pole o velikosti n*m, kde m je velikost všech polí dohromady, sbalení polí do toho, co je ve skutečnosti záznamem, přestože konkrétní jazyk postrádá přímou podporu pro evidence. Některé optimalizace kompilátoru , zejména pro vektorové procesory , jsou schopny tuto transformaci provést automaticky, když jsou v programu vytvořena pole struktur.
Viz také
Reference
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest a Clifford Stein . Úvod do algoritmů , druhé vydání. MIT Press a McGraw-Hill, 2001. ISBN 0-262-03293-7 . Strana 209 části 10.3: Implementace ukazatelů a objektů.
- Skeet, Jon (3. června 2014). „Anti-pattern: paralelní kolekce“ . Citováno 28. října 2014 .