1D- of 2D-array, wat is sneller?

Ik moet een 2D-veld voorstellen (assen x, y) en ik heb te maken met een probleem: moet ik een 1D-array of een 2D-array gebruiken?

Ik kan me voorstellen dat het herberekenen van indices voor 1D-arrays (y + x * n) langzamer zou kunnen zijn dan het gebruik van 2D-array (x, y), maar ik kon me voorstellen dat 1D in de CPU-cache zou kunnen zijn ..

Ik deed wat googelen, maar vond alleen pagina's met betrekking tot statische array (en stelde dat 1D en 2D in principe hetzelfde zijn). Maar mijn arrays moeten me dynamisch zijn.

Dus wat is

  1. sneller,
  2. kleiner (RAM)

dynamische 1D-arrays of dynamische 2D-arrays?

Bedankt :)

48
Een beknopt advies van een expert voor echte numerieke waarden: fftw.org/doc/… . Het biedt zelfs een oplossing om het beste van beide werelden te hebben.
toegevoegd de auteur alfC, de bron
Er zou geen verschil moeten zijn aangezien uw 2D-array in het geheugen wordt opgeslagen als 1D, dus telkens wanneer u arr [x] [y] intern oproept, wordt nog steeds berekend (& arr [0] [0] ) [x * dim + y]
toegevoegd de auteur Alexandru Barbarosie, de bron
Welke indexmethode u ook gebruikt, zoals arr [n * i + j] of arr [i] [j] , de kosten van indexering worden sterk overschaduwd door eventuele cachevertragingen . Besteed uw inspanningen aan het minimaliseren van cache-vertragingen.
toegevoegd de auteur NovaDenizen, de bron
@KonradRudolph Je hebt gelijk, ik heb het dynamische deel van de vraag volledig gemist.
toegevoegd de auteur juanchopanza, de bron
@KonradRudolph zou dat dan geen 2D-array zijn, zou het :-)
toegevoegd de auteur juanchopanza, de bron
@juan Technisch waar, maar OP spreekt waarschijnlijk van een dynamische array (d.w.z. T ** ), niet een echte array. Als zodanig is het niet meer aangrenzend.
toegevoegd de auteur Konrad Rudolph, de bron
@juanchopanza In algemeen gebruik is het absoluut een 2D-array. In feite, tenzij iemand expliciet spreekt over statische lengtes, neem ik altijd dynamische arrays aan en heb ik bijna altijd gelijk. Bovendien vermeldt OP expliciet dat hij dynamische arrays nodig heeft.
toegevoegd de auteur Konrad Rudolph, de bron
Alleen regel waarvan ik met zekerheid kan zeggen dat dit altijd waar zal zijn, is "Meet de twee benaderingen en zie welke sneller voor u is". Wat is waarschijnlijk om sneller te zijn, is de benadering waarbij je een enkele aaneengesloten toewijzing maakt met de equivalente index berekend uit twee indices.
toegevoegd de auteur Happy Green Kid Naps, de bron
@Paladin - U zou een 2D dynamische array (vector) moeten gebruiken. Niet omdat het sneller is, maar omdat het een beter ontwerp is.
toegevoegd de auteur tfmontague, de bron

7 antwoord

tl; dr: Je zou waarschijnlijk een eendimensionale benadering moeten gebruiken.

Opmerking: Men kan niet in details treden die de prestaties beïnvloeden wanneer dynamische 1d- of dynamische 2d-opslagpatronen worden vergeleken zonder boeken te vullen, omdat de prestatie van code afhankelijk is van een zeer groot aantal parameters. Profiel indien mogelijk.

1. Wat is sneller?

Voor dichte matrices zal de 1D-benadering waarschijnlijk sneller zijn, aangezien deze een betere geheugenlocaliteit en minder toewijzings- en deallocatiekosten biedt.

2. Wat is kleiner?

Dynamic-1D verbruikt minder geheugen dan de 2D-benadering. Dit laatste vereist ook meer toewijzingen.

Opmerkingen

I laid out a pretty long answer beneath with several reasons but I want to make some Opmerkingen on your assumptions first.

Ik kan me voorstellen dat het herberekenen van indices voor 1D-arrays (y + x * n) mogelijk langzamer gaat dan het gebruik van 2D-array (x, y)

Laten we deze twee functies vergelijken:

int get_2d (int **p, int r, int c) { return p[r][c]; }
int get_1d (int *p, int r, int c)  { return p[c + C*r]; }

De (niet-inline) assembly gegenereerd door Visual Studio 2015 RC voor die functies (met optimalisaties ingeschakeld) is:

[email protected]@[email protected] PROC
push    ebp
mov ebp, esp
mov eax, DWORD PTR _c$[ebp]
lea eax, DWORD PTR [eax+edx*4]
mov eax, DWORD PTR [ecx+eax*4]
pop ebp
ret 0

[email protected]@[email protected] PROC
push ebp
mov ebp, esp
mov ecx, DWORD PTR [ecx+edx*4]
mov eax, DWORD PTR _c$[ebp]
mov eax, DWORD PTR [ecx+eax*4]
pop ebp
ret 0

Het verschil is mov (2d) versus lea (1d). De eerste heeft een latentie van 3 cycli en een maximale doorvoersnelheid van 2 per cyclus, terwijl de laatste een latentie heeft van 2 cycli en een maximale verwerkingscapaciteit van 3 per cyclus. (Volgens Instructietabellen - Agner Fog Aangezien de verschillen klein zijn, denk ik dat er geen groot verschil in prestaties zou moeten zijn als gevolg van indexrecalculatie. Ik verwacht dat het zeer onwaarschijnlijk is dat dit verschil zelf de bottleneck is in elk programma.

Dit brengt ons bij het volgende (en meer interessante) punt:

... maar ik kan me voorstellen dat de 1D zich in de cache van de cache zou kunnen bevinden ...

Het is waar, maar 2d kan ook in de cache van de cache zitten. Zie De nadelen: geheugenlocatie voor een verklaring waarom 1d nog steeds beter is.

Het lange antwoord of waarom dynamische tweedimensionale gegevensopslag (aanwijzer naar aanwijzer of vector-van-vector) "slecht" is voor eenvoudige /kleine matrices.

Opmerking: dit gaat over dynamische arrays/toewijzingsschema's [malloc/new/vector etc.]. Een statische 2D-matrix is ​​een aaneengesloten blok geheugen en daarom niet onderhevig aan de nadelen die ik hier ga presenteren.

Het probleem

Om te begrijpen waarom een ​​dynamische array van dynamische arrays of een vectorvector waarschijnlijk niet het gewenste gegevensopslagpatroon is, moet u de geheugenlay-out van dergelijke structuren begrijpen.

Voorbeeldgeval met aanwijzer naar aanwijzingssyntaxis

int main (void)
{
   //allocate memory for 4x4 integers; quick & dirty
    int ** p = new int*[4];
    for (size_t i=0; i<4; ++i) p[i] = new int[4]; 

   //do some stuff here, using p[x][y] 

   //deallocate memory
    for (size_t i=0; i<4; ++i) delete[] p[i];
    delete[] p;
}

De nadelen

Geheugenlocaliteit

Voor deze "matrix" wijst u een blok van vier aanwijzers en vier blokken van vier gehele getallen toe. Alle toewijzingen zijn niet gerelateerd en kunnen daarom resulteren in een willekeurige geheugenpositie.

De volgende afbeelding geeft u een idee van hoe het geheugen er uit kan zien.

Voor de echte 2d-case :

  • Het paarse vierkant is de geheugenpositie die wordt ingenomen door p zelf.
  • De groene vierkantjes verzamelen de geheugenregio p punten naar (4 x int * ).
  • De 4 gebieden met 4 aaneengesloten blauwe vierkanten zijn degene waarnaar wordt verwezen door elke int * van de groene regio

Voor de 2d toegewezen aan 1d case :

  • The green square is the only required pointer int *
  • The blue squares ensemble the memory region for all matrix elements (16 x int).

Real 2d vs mapped 2d memory layout

Dit betekent dat (bij gebruik van de linkerlay-out) u waarschijnlijk slechter presteert dan voor een aaneengesloten opslagpatroon (zoals u aan de rechterkant ziet), bijvoorbeeld door caching.

Laten we zeggen dat een cache-regel "de hoeveelheid gegevens is die tegelijkertijd in de cache wordt overgebracht" en laten we ons een programma voorstellen dat toegang heeft tot de hele matrix, het ene element na het andere.

Als u een goed uitgelijnde 4-maal 4 matrix van 32-bits waarden hebt, kunt u met een processor met een 64 bytes cache-lijn (standaardwaarde) de gegevens "one-shot" (4 * 4 * 4 = 64 bytes) "one-shot". Als u begint met de verwerking en de gegevens zich nog niet in de cache bevinden, wordt u geconfronteerd met een cache-misser en worden de gegevens opgehaald uit het hoofdgeheugen. Deze belasting kan de hele matrix in één keer ophalen, omdat het in een cachelijn past, alleen en of het aaneengesloten wordt opgeslagen (en juist wordt uitgelijnd). Er zullen waarschijnlijk geen missers meer zijn tijdens het verwerken van die gegevens.

In het geval van een dynamisch, "echt tweedimensionaal" systeem met niet-gerelateerde locaties van elke rij/kolom, moet de processor elke geheugenlocatie apart laden. Hoewel slechts 64 bytes vereist zijn, zou het laden van 4 cache-lijnen voor 4 niet-gerelateerde geheugenposities in het ergste geval 256 bytes overbrengen en 75% doorvoerbandbreedte verspillen. Als u de gegevens verwerkt met behulp van het 2d-schema, ziet u opnieuw (als er geen cache in de cache staat) voor het eerste element een cache-misser. Maar nu zal alleen de eerste rij/kolom zich in de cache bevinden na de eerste keer laden uit het hoofdgeheugen, omdat alle andere rijen zich ergens anders in het geheugen bevinden en niet aangrenzend zijn aan de eerste. Zodra u een nieuwe rij/kolom bereikt, zal er opnieuw een cache missen en wordt de volgende belasting van het hoofdgeheugen uitgevoerd.

Lang verhaal kort: het 2d patroon heeft een hogere kans op cachemisks met het 1d schema dat betere mogelijkheden biedt voor prestaties vanwege de plaats van de gegevens.

Frequente toewijzing/deallocatie

  • Zoveel als N + 1 (4 + 1 = 5) toewijzingen (met behulp van nieuwe, malloc, allocator :: allocate of wat dan ook) zijn nodig om de gewenste NxM te maken (4 × 4) matrix.
  • Hetzelfde aantal eigenlijke respectieve deallocatiehandelingen moet ook worden toegepast.

Daarom is het duurder om dergelijke matrices te maken/kopiëren in tegenstelling tot een enkel toewijzingsschema.

Dit wordt nog erger met een groeiend aantal rijen.

Geheugenverbruik overhead

Ik verwacht een grootte van 32 bits voor int en 32 bits voor aanwijzers. (Opmerking: Systeemafhankelijkheid.)

Laten we niet vergeten: we willen een 4 × 4 int-matrix opslaan die 64 bytes betekent.

Voor een NxM-matrix, opgeslagen met het gepresenteerde aanwijzer-naar-aanwijzer schema dat we gebruiken

  • N*M*sizeof(int) [the actual blue data] +
  • N*sizeof(int*) [the green pointers] +
  • sizeof(int**) [the violet variable p] bytes.

That makes 4*4*4 + 4*4 + 4 = 84 bytes in case of the present Voorbeeld and it gets even worse when using std::vector>. It will require N * M * sizeof(int) + N * sizeof(vector) + sizeof(vector>) bytes, that is 4*4*4 + 4*16 + 16 = 144 bytes in total, intead of 64 bytes for 4 x 4 int.

Bovendien - afhankelijk van de gebruikte allocator - kan elke afzonderlijke toewijzing (en waarschijnlijk) nog eens 16 bytes aan geheugenoverhead hebben. (Sommige "Infobytes" die het aantal toegewezen bytes opslaan met het oog op een juiste deallocatie.)

Dit betekent dat het ergste geval is:

N * (16 + M * sizeof (int)) + 16 + N * sizeof (int *) + sizeof (int **)
   = 4 * (16 + 4 * 4) + 16 + 4 * 4 + 4 = 164 bytes! _Overhead: 156% _

Het aandeel van de overheadkosten neemt af naarmate de matrix groter wordt maar nog steeds aanwezig is.

Risico op geheugenlekken

Het aantal toewijzingen vereist een afdoende afhandeling van uitzonderingen om geheugenlekken te voorkomen als een van de toewijzingen mislukt! Je moet de toegewezen geheugenblokken bijhouden en je moet ze niet vergeten bij het vrijgeven van het geheugen.

Als nieuw wordt uitgevoerd met geheugen en de volgende rij niet kan worden toegewezen (met name wanneer de matrix erg groot is), wordt een std :: bad_alloc gegenereerd door nieuw .

Voorbeeld:

In het bovengenoemde nieuwe/verwijdervoorbeeld krijgen we wat meer code te zien als we lekken willen voorkomen in het geval van bad_alloc uitzonderingen.

 //allocate memory for 4x4 integers; quick & dirty
  size_t const N = 4;
 //we don't need try for this allocation
 //if it fails there is no leak
  int ** p = new int*[N];
  size_t allocs(0U);
  try 
  {//try block doing further allocations
    for (size_t i=0; i

Samenvatting

Er zijn gevallen waarin "echte 2d" -geheugenlay-outs passen en logisch zijn (dat wil zeggen als het aantal kolommen per rij niet constant is), maar in de meest eenvoudige en algemene 2D-gegevensopslaggevallen nemen ze gewoon de complexiteit van uw code weg en verminderen de prestaties en geheugenefficiëntie van uw programma.

Alternatief

Gebruik een aaneengesloten blok geheugen en wijs uw rijen toe op dat blok.

De "C ++ manier" om dit te doen is waarschijnlijk om een ​​klasse te schrijven die je geheugen beheert, terwijl je belangrijke dingen als beschouwt

Voorbeeld

To provide an idea of how such a class may look like, here's a simple Voorbeeld with some basic features:

  • 2d-size-constructible
  • 2d-resizable
  • operator(size_t, size_t) for 2d- row major element access
  • at(size_t, size_t) for checked 2d-row major element access
  • Fulfills Concept requirements for Container

Bron:

#include 
#include 
#include 
#include 

namespace matrices
{

  template
  class simple
  {
  public:
   //misc types
    using data_type  = std::vector;
    using value_type = typename std::vector::value_type;
    using size_type  = typename std::vector::size_type;
   //ref
    using reference       = typename std::vector::reference;
    using const_reference = typename std::vector::const_reference;
   //iter
    using iterator       = typename std::vector::iterator;
    using const_iterator = typename std::vector::const_iterator;
   //reverse iter
    using reverse_iterator       = typename std::vector::reverse_iterator;
    using const_reverse_iterator = typename std::vector::const_reverse_iterator;

   //empty construction
    simple() = default;

   //default-insert rows*cols values
    simple(size_type rows, size_type cols)
      : m_rows(rows), m_cols(cols), m_data(rows*cols)
    {}

   //copy initialized matrix rows*cols
    simple(size_type rows, size_type cols, const_reference val)
      : m_rows(rows), m_cols(cols), m_data(rows*cols, val)
    {}

   //1d-iterators

    iterator begin() { return m_data.begin(); }
    iterator end() { return m_data.end(); }
    const_iterator begin() const { return m_data.begin(); }
    const_iterator end() const { return m_data.end(); }
    const_iterator cbegin() const { return m_data.cbegin(); }
    const_iterator cend() const { return m_data.cend(); }
    reverse_iterator rbegin() { return m_data.rbegin(); }
    reverse_iterator rend() { return m_data.rend(); }
    const_reverse_iterator rbegin() const { return m_data.rbegin(); }
    const_reverse_iterator rend() const { return m_data.rend(); }
    const_reverse_iterator crbegin() const { return m_data.crbegin(); }
    const_reverse_iterator crend() const { return m_data.crend(); }

   //element access (row major indexation)
    reference operator() (size_type const row,
      size_type const column)
    {
      return m_data[m_cols*row + column];
    }
    const_reference operator() (size_type const row,
      size_type const column) const
    {
      return m_data[m_cols*row + column];
    }
    reference at() (size_type const row, size_type const column)
    {
      return m_data.at(m_cols*row + column);
    }
    const_reference at() (size_type const row, size_type const column) const
    {
      return m_data.at(m_cols*row + column);
    }

   //resizing
    void resize(size_type new_rows, size_type new_cols)
    {
     //new matrix new_rows times new_cols
      simple tmp(new_rows, new_cols);
     //select smaller row and col size
      auto mc = std::min(m_cols, new_cols);
      auto mr = std::min(m_rows, new_rows);
      for (size_type i(0U); i < mr; ++i)
      {
       //iterators to begin of rows
        auto row = begin() + i*m_cols;
        auto tmp_row = tmp.begin() + i*new_cols;
       //move mc elements to tmp
        std::move(row, row + mc, tmp_row);
      }
     //move assignment to this
      *this = std::move(tmp);
    }

   //size and capacity
    size_type size() const { return m_data.size(); }
    size_type max_size() const { return m_data.max_size(); }
    bool empty() const { return m_data.empty(); }
   //dimensionality
    size_type rows() const { return m_rows; }
    size_type cols() const { return m_cols; }
   //data swapping
    void swap(simple &rhs)
    {
      using std::swap;
      m_data.swap(rhs.m_data);
      swap(m_rows, rhs.m_rows);
      swap(m_cols, rhs.m_cols);
    }
  private:
   //content
    size_type m_rows{ 0u };
    size_type m_cols{ 0u };
    data_type m_data{};
  };
  template
  void swap(simple & lhs, simple & rhs)
  {
    lhs.swap(rhs);
  }
  template
  bool operator== (simple const &a, simple const &b)
  {
    if (a.rows() != b.rows() || a.cols() != b.cols())
    {
      return false;
    }
    return std::equal(a.begin(), a.end(), b.begin(), b.end());
  }
  template
  bool operator!= (simple const &a, simple const &b)
  {
    return !(a == b);
  }

}

Let hier op verschillende dingen:

  • T needs to fulfill the requirements of the used std::vector member functions
  • operator() doesn't do any "of of range" checks
  • No need to manage data on your own
  • No destructor, copy constructor or assignment operators required

U hoeft zich dus niet druk te maken over de juiste verwerking van het geheugen voor elke toepassing, maar slechts één keer voor de klas die u schrijft.

beperkingen

Er kunnen gevallen zijn waarbij een dynamische "echte" tweedimensionale structuur gunstig is. Dit is bijvoorbeeld het geval als

  • de matrix is ​​erg groot en schaars (als een van de rijen niet eens hoeft te worden toegewezen, maar kan worden afgehandeld met een nullptr) of als
  • de rijen hebben niet hetzelfde aantal kolommen (dat wil zeggen als u helemaal geen matrix hebt maar een andere tweedimensionale constructie).
158
toegevoegd
Ik heb 2 hoofdredenen voor het gebruik van het aanwijzervoorbeeld. Allereerst heeft het een voorspelbare geheugenlay-out (de standaard heeft geen garantie hoe de vector zelf eruit ziet) en het tweede punt is dat de meeste van de "naïeve benaderingen" die ik hier op ZO-gebruik-aanwijzers zie.
toegevoegd de auteur Pixelchemist, de bron
Ik heb onlangs een antwoord toegevoegd met betrekking tot de standaard lay-out std: vector en hoe deze in het geheugen is neergelegd. Misschien is dit van belang in relatie tot deze vraag. c ++ Vector, wat gebeurt er wanneer het zich uitbreidt?/reallocate on stack?
toegevoegd de auteur Pixelchemist, de bron
@FrankH Dat is wat ik bedoel met " Het aantal toewijzingen vereist een afdoende afhandeling van uitzonderingen om geheugenlekken te voorkomen als een van de toewijzingen mislukt! " @ ** Risico van geheugenlekken ** maar ik denk dat ik zal een beoordeling hebben om daar iets verder op vooruit te gaan.
toegevoegd de auteur Pixelchemist, de bron
@beesleep: Ja .. dat gebeurt wanneer u operator() kopieert en plakt en halfhartig de naam wijzigt in bij ;)
toegevoegd de auteur Pixelchemist, de bron
Aaneengesloten geheugen stelt de compiler ook in staat om automatisch met SIMD te vector -iseren. deze code heeft bijvoorbeeld een 50x versnelling door een platte array te gebruiken in plaats van pointers-to-pointers . (Het was bijna het slechtste geval: een 3D-matrix van verwijzingen naar aanwijzers naar rijen van slechts 4 dubbel s en een lus in de verkeerde volgorde voor lokaliteit als de dingen meestal aaneengesloten waren toegewezen.) De OP hasn niet gereageerd op de versnelling voor het nieuwe knelpunt , maar het moet aanzienlijk zijn
toegevoegd de auteur Peter Cordes, de bron
Het is een leuk antwoord, maar waarom zou je er op staan ​​om (in het algemeen) onbewerkte verwijzingen in je voorbeeld te gebruiken? Er is geen reden voor, in moderne C ++. Gebruik gewoon std :: vector en wees er klaar mee.
toegevoegd de auteur Konrad Rudolph, de bron
Uw assembly-voorbeeld is misleidend. Het gaat uit van C == 4 , voor grotere of variabele C heeft het een mul of ten minste extra shl nodig . Het verandert waarschijnlijk nog steeds niet het grote plaatje.
toegevoegd de auteur zch, de bron
Fantastisch antwoord; je zou het moeten bloggen :)
toegevoegd de auteur Brennan Vincent, de bron
Er is nog een reden waarom het doen van het "2D-dynamische array" -werk slecht is, maar dat zal je waarschijnlijk alleen bijten op grote formaten: nieuw kan gooien wanneer het op is van geheugen. Sinds de "dynamische toewijzing" vereist deze stijl ten minste twee oproepen naar nieuw (de eerste voor de matrix T * [N] , en de tweede voor de T [N * M] ), dus je moet ook try {} catch {} rond elke kaart plaatsen, anders zou je geheugen lekken als de 1e gelukt is en de tweede gooit. De echte boosdoener is dat C ++/STL nooit last heeft gehad van een standaard matrix -klasse. Als Fortran iets goed heeft gemaakt over C/C ++, dan is dat degene ...
toegevoegd de auteur FrankH., de bron
Is er niet een paar typefouten hier: referentie op() (size_type const rij, size_type const kolom) {return m_data.at (m_cols * row + column); } bij operator() (size_type const rij, size_type const kolom) const {return m_data.at (m_cols * rij + kolom); } ? Moet het niet worden gewijzigd in verwijzing op (size_type const rij, size_type const kolom) en const_reference op (size_type const rij, size_type const kolom) const ?
toegevoegd de auteur beesleep, de bron
Ik weet het ... het gebeurt de hele tijd. Geen overtreding gemaakt :-D. Bedankt voor de code trouwens, een leuk klein en efficiënt stuk werk!
toegevoegd de auteur beesleep, de bron

Unless you are talking about static arrays, 1D is faster.

Here’s the memory layout of a 1D array (std::vector):

+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+

And here’s the same for a dynamic 2D array (std::vector>):

+---+---+---+
| * | * | * |
+-|-+-|-+-|-+
  |   |   V
  |   | +---+---+---+
  |   | |   |   |   |
  |   | +---+---+---+
  |   V
  | +---+---+---+
  | |   |   |   |
  | +---+---+---+
  V
+---+---+---+
|   |   |   |
+---+---+---+

Het is duidelijk dat het 2D-geval de cache-plaats verliest en meer geheugen gebruikt. Het introduceert ook een extra indirectie (en dus een extra aanwijzer om te volgen) maar de eerste array heeft de overhead van het berekenen van de indices, zodat deze meer of minder uitkomen.

15
toegevoegd
Goed antwoord. Ik dacht ook aan cache-missers op dynamische 2d-array
toegevoegd de auteur Alex, de bron

1D- en 2D-statische arrays

  • Grootte: beide hebben dezelfde hoeveelheid geheugen nodig.

  • Snelheid: U kunt ervan uitgaan dat er geen snelheidsverschil is omdat het geheugen voor beide arrays aaneengesloten moet zijn (de hele 2D-array zou als één brok in het geheugen moeten verschijnen in plaats van a bos van brokken verspreid over het geheugen). (Dit zou een compiler kunnen zijn afhankelijk echter.)

1D- en 2D-dynamische arrays

  • Grootte: de 2D-array heeft een klein beetje meer geheugen nodig dan de 1D-array, omdat de pointers die nodig zijn in de 2D-array verwijzen naar de set toegewezen 1D-arrays. (Dit kleine stukje is maar heel klein als we het over hele grote reeksen hebben. Voor kleine reeksen kan het kleine beetje relatief groot zijn.)

  • Snelheid: de 1D-array kan sneller zijn dan de 2D-array omdat het geheugen voor de 2D-array niet aaneengesloten zou zijn, dus cache-missers zouden een probleem worden.


Gebruik wat werkt en het meest logisch lijkt, en als je te maken krijgt met snelheidsproblemen, dan refactor.

8
toegevoegd
Zoals ik al aangaf zal een 4x4 vector > (systeem afhankelijk) 164 bytes vereisen, waarbij 100 bytes boven het hoofd liggen. Ik zou dat niet "een klein beetje" noemen (het is een factor> 2,5), vooral als je er veel van moet behandelen of als je ze heel vaak moet kopiëren. (Het verliest vanzelfsprekend betekenis met een groeiend aantal kolommen.)
toegevoegd de auteur Pixelchemist, de bron
Op snelheid hangt het ook af van hoe je de array gebruikt. Het berekenen van de offset voor willekeurig toegankelijke elementen is hetzelfde, maar als je alle elementen wilt herhalen, is het eenvoudig om met een eendimensionale array alleen lineair itereert en niet lastig te vallen met geneste lussen of met multidimensionale coördinaten in geheugencompensaties.
toegevoegd de auteur Boann, de bron
de dynamische "2D-array" is een array van wijzers die naar andere arrays wijzen. Het vereist dus meer ruimte dan een 1D-array.
toegevoegd de auteur juanchopanza, de bron
@Pixelchemist Dat is waar, en ik heb het niet genoemd omdat ik verwacht dat zijn arrays behoorlijk groot zullen zijn als hij zich zorgen gaat maken over snelheid. : P (denk dat het beter is om dat expliciet te vermelden)
toegevoegd de auteur Mohamad Ali Baydoun, de bron
Oh hey, dat klopt. Bedankt voor het maken van die correctie. @ mr5 Een std: vector gedraagt ​​zich als een dynamische 1D-array omdat hij zo is geprogrammeerd. (Wanneer we statisch zeggen, verwijzen we niet per se naar het statische -zoekwoord)
toegevoegd de auteur Mohamad Ali Baydoun, de bron
"Er is geen snelheidsverschil." Dat hangt er echt van af hoe de compiler offsets berekent voor 2D-arrays.
toegevoegd de auteur SigTerm, de bron
Maar hoe zit het met een statische std :: vector is het een statische of dynamische? Sorry, ik heb niet het vermogen om die te onderscheiden.
toegevoegd de auteur mr5, de bron

De bestaande antwoorden vergelijken alleen 1-D-arrays met arrays van pointers.

In C (maar niet C ++) is er een derde optie; u kunt een aaneengesloten 2-D-array gebruiken die dynamisch is toegewezen en runtime-dimensies heeft:

int (*p)[num_columns] = malloc(num_rows * sizeof *p);

en dit wordt benaderd als p [row_index] [col_index] .

Ik zou verwachten dat dit zeer vergelijkbare prestaties als de 1-D array-case zou hebben, maar het geeft je een mooiere syntax voor toegang tot de cellen.

In C ++ kunt u iets soortgelijks bereiken door een klasse te definiëren die intern een 1-D-array onderhoudt, maar deze kan via de 2-D array-toegangssyntaxis met behulp van overbelaste operators worden blootgesteld. Nogmaals, ik zou verwachten dat dit een vergelijkbare of identieke prestatie zou hebben als de gewone 1-D array.

4
toegevoegd
@Paladin C en C ++ zijn verschillende talen, elk heeft een aantal functies die de andere niet heeft, en sommige van de algemene functies zijn anders geïmplementeerd. Probeer g ++ aan te roepen in de standaardmodus en u krijgt een diagnose, standaard zijn sommige extensies ingeschakeld.
toegevoegd de auteur M.M, de bron
@vsoftco in uw C ++ -code num_cols moet een constante uitdrukking zijn, maar in mijn code kan het tijdens runtime worden bepaald
toegevoegd de auteur M.M, de bron
@ M.M In C (maar niet C ++) is er een derde optie Waarom alleen in C? In C ++ kunt u eenvoudig int (* p) [num_cols] = new int [num_rows] [num_cols]; verwijder [] p; .
toegevoegd de auteur vsoftco, de bron
@ M.M Ohh ik snap het, bedankt! Ja inderdaad, de lhs is een verwijzing naar een VLA in C, goed punt!
toegevoegd de auteur vsoftco, de bron
Dat klinkt vreemd om eerlijk te zijn, ik dacht altijd dat bijna elke geldige C geldig is C ++ .. g ++ 4.8.3 neemt deze code pastebin .com/Te2n1XhZ ...
toegevoegd de auteur Paladin, de bron

Een ander verschil van 1D- en 2D-arrays verschijnt in geheugentoewijzing. We kunnen niet zeker zijn dat leden van de 2D-array sequentieel zijn.

4
toegevoegd
Ja. En dit kan een serieuze impact hebben wanneer de array in kwestie in die 1% prestatiekritieke code zit.
toegevoegd de auteur Arcane Engineer, de bron

Het hangt echt af van hoe uw 2D-array is geïmplementeerd.

int a[200], b[10][20], *c[10], *d[10];
for (ii = 0; ii < 10; ++ii)
{
   c[ii] = &b[ii][0];
   d[ii] = (int*) malloc(20 * sizeof(int));   //The cast for C++ only.
}

Er zijn hier 3 implementaties: b, c en d Er zal niet veel verschil zijn in de toegang tot b [x] [y] of een [x * 20 + y], aangezien je bezig bent met de berekening en de andere de compiler doet voor jou. c [x] [y] en d [x] [y] zijn langzamer omdat de machine het adres waarnaar c [x] verwijst moet vinden en vervolgens vanaf daar toegang heeft tot het y-element. Het is niet één rechte berekening. Op sommige machines (bijv. AS400 met 36 bytes (geen bit) wijzers), is de toegang van de aanwijzer uiterst traag. Het is allemaal afhankelijk van de gebruikte architectuur. Op architecturen van het x86-type zijn a en b dezelfde snelheid, c en d zijn langzamer dan b.

1
toegevoegd

Ik ben dol op het grondige antwoord van Pixelchemist . Een eenvoudigere versie van deze oplossing kan als volgt zijn. Verklaar eerst de afmetingen:

constexpr int M = 16;//rows
constexpr int N = 16;//columns
constexpr int P = 16;//planes

Maak vervolgens een alias en, verkrijg en stel methoden:

template
using Vector = std::vector;

template
inline T& set_elem(vector& m_, size_t i_, size_t j_, size_t k_)
{
   //check indexes here...
    return m_[i_*N*P + j_*P + k_];
}

template
inline const T& get_elem(const vector& m_, size_t i_, size_t j_, size_t k_)
{
   //check indexes here...
    return m_[i_*N*P + j_*P + k_];
}

Ten slotte kan een vector als volgt worden gemaakt en geïndexeerd:

Vector array3d(M*N*P, 0);           //create 3-d array containing M*N*P zero ints
set_elem(array3d, 0, 0, 1) = 5;     //array3d[0][0][1] = 5
auto n = get_elem(array3d, 0, 0, 1);//n = 5

Het definiëren van de vectorgrootte bij initialisatie biedt optimale prestaties . Deze oplossing is gewijzigd van dit antwoord . De functies kunnen overbelast zijn om verschillende dimensies met een enkele vector te ondersteunen. Het nadeel van deze oplossing is dat de parameters M, N, P impliciet worden doorgegeven aan de get en set-functies. Dit kan worden opgelost door de oplossing binnen een klasse te implementeren, zoals gedaan door Pixelchemist .

0
toegevoegd