Parallell array

Vid programmering är en parallell array en datastruktur för att representera en array av poster , som fysiskt består av separata arrayer av samma typ av samma längd för vart och ett av postfälten. Värdena på element med samma serienummer i varje array tillhör logiskt sett samma struktur. Som pekare till strukturen används ett gemensamt index i den parallella arrayen. Detta tillvägagångssätt skiljer sig från det traditionella, där alla fält i strukturen lagras i angränsande minnesområden. Till exempel kan du deklarera en array av strängtyp för 100 namn och en array av heltal för 100 åldrar, och anse att varje namn motsvarar en ålder med samma inmatningsindex.

Ett exempel på implementering av parallella arrayer i C :

char * first_names [] = { "Joe" , "Bob" , "Frank" , "Hans" }; char * last_names [] = { "Smith" , "Seger" , "Sinatra" , "Schultze" }; int * höjder [] = { 169 , 158 , 201 , 199 }; for ( int i = 0 ; i < 4 ; i ++ ) { printf ( "Namn:%s %s, höjd:%d cm \n " , förnamn [ i ], efternamn [ i ], höjder [ i ]); }

Ett exempel på implementering av parallella arrayer i MQL4 (det finns inget strukturstöd på detta språk):

string first_names [] = { "Joe" , "Bob" , "Frank" , "Hans" }; string last_names [] = { "Smith" , "Seger" , "Sinatra" , "Schultze" }; int höjder [] = { 169 , 158 , 201 , 199 }; int i ; för ( i = 0 ; i < 4 ; i ++ ) { Skriv ut ( StringConcatenate ( "Namn: " , förnamn [ i ], " " , efternamn [ i ], ", höjd: " , höjder [ i ], " sm" )); }

Ett exempel på implementering i Perl (med en associativ array för att logiskt gruppera komponenterna i en parallell array):

my %data = ( first_names => [ 'Joe' , 'Bob' , 'Frank' , 'Hans' ], last_names => [ 'Smith' , 'Seger' , 'Sinatra' , 'Schultze' ], höjder => [ 169 , 158 , 201 , 199 ], ); för $i ( 0 .. $# { $data { first_names }}) { printf "Namn:%s %s, höjd:%i cm \n" , $data { first_names }[ $i ], $data { last_names }[ $i ], $data { höjder }[ $i ]; }

Implementeringsexempel i Python :

first_names = [ "Joe" , "Bob" , "Frank" , "Hans" ] last_names = [ "Smith" , "Seger" , "Sinatra" , "Schultze" ] höjder = [ 169 , 158 , 201 , 199 ] för i inom intervallet ( len ( first_names )): print ( "Namn: %s %s , höjd: %d cm" % ( first_names [ i ], efternamn [ i ], höjder [ i ]))

Ett exempel på en alternativ implementering i Python :

first_names = [ "Joe" , "Bob" , "Frank" , "Hans" ] last_names = [ "Smith" , "Seger" , "Sinatra" , "Schultze" ] höjder = [ 169 , 158 , 201 , 199 ] för ( first_name , last_name , height ) in zip ( first_names , last_names , heights ): print ( "Namn: %s %s , höjd: %d cm" % ( first_name , last_name , height ))

Exempelimplementering i bash :

#!/bin/bash declare -a first_names =( 'Joe' 'Bob' 'Frank' 'Hans' ) ; declare -a last_names =( 'Smith' 'Seger' 'Sinatra' 'Schultze' ) ; deklarera -a höjder =( 169 158 201 199 ) ; deklarera -ii ; för (( i = 0 ; i < = ${# förnamn } ; i++ )) ; gör { echo "Namn: ${ first_names [ ${ i } ] } ${ last_names [ ${ i } ] } , höjd: ${ höjder [ ${ i } ] } cm" ; } ; Gjort

Parallella arrayer har ett antal praktiska fördelar jämfört med den klassiska metoden:

  • De kan användas i språk som bara stöder arrayer av primitiva typer, men som inte stöder post arrays, eller inte stöder poster alls.
  • Parallella arrayer är lätta att förstå och använda och används ofta där det är överflödigt att deklarera en ingångsstruktur.
  • De kan spara en betydande mängd minne i vissa fall, eftersom. hantera anpassningsfrågor mer effektivt. Till exempel kan ett av strukturens fält vara en enskild bit - i det vanliga tillvägagångssättet måste oanvända bitar justeras så att en enstaka bit tar hela 8, 16 eller 32 bitar, medan en parallell array tillåter Du kan kombinera 32 eller 64 bitars fält i ett element beroende på processorarkitekturens bitdjup.
  • Om antalet element är litet tar arrayindex upp betydligt mindre utrymme än fullfjädrade pekare, särskilt på arkitekturer med stort bitdjup.
  • Att sekventiellt läsa ett enda fält av varje post i en array är mycket snabbt på moderna datorer eftersom detta motsvarar en linjär passage genom en enda array, vilket ger idealisk lokalitet och cachebeteende.

Trots detta har parallella arrayer flera betydande nackdelar som förklarar varför de inte används i stor utsträckning:

  • De har betydligt sämre lokalitet när de sekventiellt passerar genom poster och läser flera fält, vilket är en typisk uppgift.
  • Förhållandet mellan fält i samma post kan vara subtilt och förvirrande.
  • Ett ganska litet antal språk stöder parallella arrayer som fullfjädrade strukturer - språket och dess syntax indikerar som regel inte förhållandet mellan arrayer i en parallell array.
  • Att ändra storleken på en parallell array är en ganska dyr operation, eftersom du måste omallokera minne för var och en av subarrayerna. Layered arrays är en dellösning på detta problem, men utsätter en prestationsstraff genom att införa ett extra lager av omdirigeringar för att hitta det nödvändiga elementet.
  • När du använder parallella arrayer måste du skriva ut fler bokstäver än när du deklarerar en poststruktur. Detta är ett irrationellt sätt att använda händerna på programmerare.

Dålig lokalitet är en allvarlig nackdel, men följande tillvägagångssätt kan användas för att minska svårighetsgraden av problemet och dess inverkan på prestanda:

  • Om posten har separata uppsättningar av fält som vanligtvis används tillsammans, kan du dela upp strukturen i flera och göra en parallell uppsättning av sådana delposter. Denna metod låter dig avsevärt öka prestandan för att komma åt mycket stora strukturer, samtidigt som deras logiska förening bibehålls. Om det tillåts kan vissa strukturfält dupliceras i olika understrukturer, men då är det upp till programmeraren att hålla reda på ändringar av duplicerade fält och uppdatera alla instanser.
  • Referenser kan användas istället för arrayindex , men den resulterande prestandan är starkt beroende av språket, kompilatorn och processorarkitekturen - en sådan lösning kan vara ineffektiv både när det gäller exekveringstid och minnesfotavtryck.
  • Ett annat alternativ är att kombinera fält av kompatibla typer till en enda endimensionell array så att fält som hör till samma struktur skrivs sekventiellt. Det finns till exempel en parallell array av poster för längd, vikt och ålder - istället för tre separata arrayer kan du skapa en där posterna kommer att se ut så här: [рост1, вес1, возраст1, рост2, вес2, возраст2, ...], alltså för att få det J:te fältet (från M) i den I:e posten (av N) måste du referera till elementet med indexet (M * I + J). Vissa kompilatorer kan automatiskt tillämpa denna typ av optimering för att rulla upp strukturmatriser för anpassning till vektorprocessorer och SIMD- instruktioner.

Se även

  • Ett exempel i en engelsk artikel om en länkad lista
  • En kolumnorienterad DBMS är en ovanlig typ av databas som använder konceptet med parallella arrayer för att organisera data.
  • Associativ array
  • dynamisk array