1D немесе 2D массиві, не тезірек?

Маған 2D өрісін ұсынуға тура келеді (ось x, у) және менде проблема туындайды: 1D массивін немесе 2D массивін пайдалану керек пе?

1D массивтерін қайта есептеу индекстерінің (y + x * n) 2D массивінен (x, у) қарағанда, баяу болуы мүмкін деп ойлаймын, бірақ 1D-дің CPU кэшінде болуы мүмкін екенін көрсетуіме болады.

Мен googling жасадым, бірақ тек статикалық массивтерге қатысты беттер тапты (және 1D және 2D - бұл негізінен бірдей). Бірақ менің массивтерімнің динамикасы керек.

Мәселен, не бар?

  1. жылдам,
  2. аз (RAM)

динамикалық 1D массивтері немесе динамикалық 2D массиві?

Спасибо :)

48
Шынайы әлемдік сандарға арналған қысқаша сараптамалық кеңестер:

http://www.fotforum.org/doc/Dynamic-Arrays-in-C_002dThe-Wrong-Way.html#Dynamic-Arrays-in-C_002dThe-Wrong- Way «rel =» nofollow жаңартқыш «> fftw.org/doc/… . Ол тіпті екі әлемнің ең жақсысын табу үшін шұғыл шешім береді.

қосылды автор alfC, көзі
2D массиві 1D ретінде сақталғандықтан, arr [x] [y] деп қоңырау шалған сайын ол (& arr [0] [0] ) [x * dim + y]
қосылды автор Alexandru Barbarosie, көзі
arr [n * i + j] немесе arr [i] [j] сияқты индекстеу әдісін пайдалансаңыз да индекстеудің құны кэш кідірістерінің кез-келгеніне асып түседі . Кэш кідірістерін азайту үшін күш-жігеріңізді жұмсаңыз.
қосылды автор NovaDenizen, көзі
@KonradRudolph Сіз дұрыссыз, мен мәселенің динамикалық бөлігін толығымен жіберіп алдым.
қосылды автор juanchopanza, көзі
@KonradRudolph, ол 2D массив болмаса, онда ол :-)
қосылды автор juanchopanza, көзі
@ juan Техникалық жағынан дұрыс, бірақ ОР - нақты массив емес, динамикалық массив (мысалы, T ** ) туралы айтуы мүмкін. Осылайша, ол бұдан былай жанаспайды.
қосылды автор Konrad Rudolph, көзі
@juanchopanza Жалпы пайдалануда ол мүлдем 2D массиві. Шындығында, егер біреу статикалық ұзындықтар туралы ашық айтпаса, мен үнемі динамикалық массивтерді қабылдаймын және әрдайым дұрыс. Сонымен қатар, анық динамикалық массивтерге қажет екенін ескертеді.
қосылды автор Konrad Rudolph, көзі
Тек қана « ереже , ол әрдайым шындықты ұстанады деп айта аламын:« Екі тәсілді өлшеп, қайсысының жылдамырақ екенін көр ». ықтималдығы деген неғұрлым тезірек дегеніміз - екі көрсеткіштен есептелген эквивалент индексі бар жалғастырушы біріктіру әдісі.
қосылды автор Happy Green Kid Naps, көзі
@Paladin - 2D динамикалық массивін (векторды) қолданыңыз. Бұл тезірек емес, бірақ бұл жақсы дизайн болғандықтан емес.
қосылды автор tfmontague, көзі

7 жауаптар

tl; dr: Сіз бір өлшемді тәсіл қолданған шығарсыз.

Ескерту: Динамикалық 1D немесе динамикалық 2D сақтау үлгілерін кітаптарды толтырусыз салыстыра отырып, өнімділікке әсер ететін егжей-тегжейлі мәліметтерді жасай алмайсыз, себебі кодының орындалуы параметрлердің өте көп санына байланысты. Мүмкіндігінше профиль.

1. Не тезірек?

Тығыз матрицалар үшін 1D тәсілі жылдамырақ болуы мүмкін, себебі бұл жадтың жақсы орналасуын және бөлуді азайтуды және бөлуді азайтады.

2. Қандай аз?

Dynamic-1D 2D тәсіліне қарағанда жадты аз жұмсайды. Соңғысы да көп қаражат бөлуді талап етеді.

Ескертулер

I laid out a pretty long answer beneath with several reasons but I want to make some Ескертулер on your assumptions first.

2D массивіне (x, y) қарағанда 1D массивтерін қайта есептеу индекстері (y + x * n) баяу болуы мүмкін деп ойлаймын.

Мына екі функцияны салыстырайық:

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]; }

Visual Studio 2015 RC осы функцияларға (оңтайландырулар қосулы) арналған генерацияланған (кірістірілген емес) құрастыру:

[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

mov (2d) және lea (1d) арасындағы айырмашылық. Бұрынғы 3 циклдің кідірісі бар және циклдің максималды өткізу қабілеті 2 циклі, ал екіншісі 2 айналымның кешігуіне және цикл үшін максималды өткізу қабілеттілігіне ие. ( Нұсқаулық кестелері бойынша - Agner Fog Арасындағы айырмашылықтар аз болғандықтан, индекстің қайта есептелуінен пайда болатын үлкен айырмашылық болмауы керек деп ойлаймын. Мен бұл айырмашылықты кез-келген бағдарламадағы кедергі деп білемін.

Бұл бізге келесі (және одан да қызықты) тармаққа әкеледі:

... бірақ 1D-дің процессорлық кэште болуы мүмкін екенін көрсетуіме болар еді ...

Рас, бірақ 2d CPU кэшінде де болуы мүмкін. Түсіндіру үшін

Downsides: Memory location бөлімін қараңыз.

Ұзақ жауап немесе динамикалық 2 өлшемді деректерді сақтау (көрсеткіш-көрсеткішін немесе вектор-векторы) қарапайым /кішкентай матрицалар үшін «нашар» болып табылады.

Ескерту: Бұл динамикалық массивтер/бөлу схемалары туралы [malloc/new/vector және т.с.с.]. Статикалық 2D массиві - бұл жадыдағы іргелес блок, осылайша, осында көрсетілетін құлдыраудың болмауы.

Мәселесі

Неліктен динамикалық массивтердің немесе векторлардың векторларының динамикалық массивін таңдау деректерді сақтаудың үлгісі емес екенін түсіну үшін мұндай құрылымдардың жад орналасуын түсіну қажет.

Көрсеткішті көрсеткіш синтаксисіне қолданатын мысал

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;
}

Төмендету

Жадты жері

Бұл «матрица» үшін төрт блоктан бір блок пен төрт бүтін төрт блокты бөліп аласыз. Барлық бөлімдер байланыстырылмаған және сондықтан еркін жады жағдайына әкелуі мүмкін.

Төмендегі сурет сізге жадтың қалай көрінетіні туралы түсінік береді.

real 2d case үшін:

  • Күлгін шаршы - бұл p
  • Жасыл квадрат жад аймағын p тармағына (4 x int * ) аударады.
  • Жасыл аймақтың әрқайсысының int * көрсетілген төрт көгілдір квадраттың 4 аймағы

2d 1d жағдайында көрсетілген үшін:

  • 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

Бұл (сол жақшаны пайдалану кезінде) мысалы, кэширования себебінен көршілес сақтау үлгісіне қарағанда (оң жағынан көрініп тұрғандай), сіз нашар өнімділікті байқайсыз.

Кэш сызығы «кэшке бірден берілетін деректердің сомасы» деп айтайық және бағдарламаның бір элементтен кейінгі матрицаға қол жеткізуін елестетіп көрейік.

Егер сізде 32 бит мәндерінің 4 матрицасы 4 рет дұрыс орналасса, 64 байт кэш желісі (әдеттегі мән) бар процессор деректерді «бір рет» (4 * 4 * 4 = 64 байт) алады. Егер сіз өңдеуді бастасаңыз және деректер кэште болмаса, сізде кэшті жіберіп алуға болады және деректер негізгі жадтан алынады. Бұл жүктеме біртіндеп барлық матрицаны бірден ала алады, себебі ол тек қана сақталады (және дұрыс тураланған) болса, ол кэш сызығына сәйкес келеді. Бұл деректерді өңдей отырып, әлдеқайда көп болмайды.

Әрбір жол/бағанның байланыстырылмаған жерлері бар динамикалық «нақты өлшемді» жүйе болған жағдайда, процессор әрбір жадтың орналасуын бөлек жүктеуі керек. Бұл жағдайда тек 64 байт талап етіледі, 4 кэш желісі 4 бос емес жады жағдайына жүктеледі, ең жаман жағдай сценарийі - шын мәнінде 256 байт ауыстырып, өткізу қабілетін өткізу қабілетін 75% -ға ысырып тастайды. Деректерді 2d-схема арқылы өңдесеңіз, сіз қайтадан (егер кэштелмеген болса) бірінші элементте кэшті жіберіп алмасыңыз. Бірақ қазір басты жолдан бірінші жүктеуден кейін кэште тек бірінші жол/баған ғана болады, себебі барлық басқа жолдар жадта басқа жерде және біріншіге жақын емес. Жаңа жолға/бағанға жеткенде қайтадан кэш жіберіледі және негізгі жадыдағы келесі жүктеме орындалады.

Ұзақ әңгіме қысқаша: 2D үлгісі 1D схемасымен бірге кэштің жетіспеушілігін жоғарылату мүмкіндігіне ие.

Жиі бөлу/деоляция

  • Қалаған NxM (4 × 4) жасау үшін қажет болса, N + 1 (4 + 1 = 5) бөлу (жаңа, malloc, allocator :: allocate немесе басқаларын) матрица.
  • Тиісті, тиісті деаллокарту операцияларын сол санын қолданыңыз.

Сондықтан, мұндай матрицаларды бірыңғай бөлу схемасына қарағанда жасау/көшіру аса қымбат.

Бұл сандар санының артуымен әлдеқайда нашар.

Жад шығыны

Мен int үшін 32 бит пен көрсеткіш үшін 32 бит боламын. (Ескерту: Жүйеге тәуелділік.)

Естеріңізде болсын: біз 64 байтты білдіретін 4 × 4 интер матрицасын сақтауды қалаймыз.

Біз NxM матрицасы үшін ұсынылған көрсеткіш-көрсеткіш схемасымен бірге сақтаймыз

  • 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 Мысал 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.

Бұдан басқа - қолданылған таратушыға байланысты - әр бір бөлу мүмкін (және ең алдымен болады) тағы бір 16 байтты еске түсіруі мүмкін. (Бөлінген байттардың нөмірін тиісті түрде бөлу үшін сақтайтын кейбір «Инфобайты».)

Бұл ең нашар жағдай:

N * (16 + M * sizeof (int)) + 16 + N * мөлшеріof (int *) + sizeof (int **)
   = 4 * (16 + 4 * 4) + 16 + 4 * 4 + 4 = 164 байт! _Overhead: 156% _

Мөлшердің үлесі матрицаның өлшемі өсуде, бірақ әлі де болады, себебі азаяды.

Жадтың ағып кету қаупі бар

Бөлінулердің біреуі сәтсіз болса, қаражаттың жиналуы жадтың ағып кетуіне жол бермеу үшін тиісті ерекшеліктерді өңдеуді қажет етеді! Бөлінген жад блоктарын қадағалауыңыз қажет және оларды жадты бөлу кезінде ұмытып кетпеу керек.

Егер new жады жұмыс істесе және келесі жол бөлінбейді (әсіресе матрица өте үлкен болғанда), std :: bad_alloc new .

Мысалы:

Жоғарыда аталған жаңа/жою мысалында bad_alloc қоспағанда, ағып кетуден аулақ болғымыз келсе, бізде бірнеше код пайда болады.

 //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

Резюме

«Нақты 2д» жад орналасулары сәйкес келеді және мағынасы бар (мысалы, әрбір қатардағы бағандар саны тұрақты емес), бірақ қарапайым және ортақ 2D деректерді сақтау жағдайында олар сіздің кодтың күрделілігін шатастырып, өнімділікті азайтады және сіздің бағдарламаңыздың жады тиімділігі.

Баламалы

Сіз жадты біріктірілген блокпен пайдалануыңыз және жолдарды осы блокқа салыстыруыңыз керек.

«C ++ әдісі», мысалы, маңызды нәрселерді қарастырған кезде, жадты басқаратын сыныпты жазу керек шығар

Мысал

To provide an idea of how such a class may look like, here's a simple Мысал 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

Дерек көзі:

#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);
  }

}

Мұнда бірнеше нәрсеге назар аударыңыз:

  • 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

Сондықтан сіз әрбір бағдарлама үшін дұрыс жадты өңдеу туралы алаңдамайсыз, бірақ сіз жазған сынып үшін бір рет.

Шектеулер

Динамикалық «нақты» екі өлшемді құрылым қолайлы болған жағдайлар болуы мүмкін. Бұл, мысалы, егер болса

  • матрица өте үлкен және сирек (егер кез келген жолды бөлуге болмайды, бірақ nullptr арқылы өңдеуге болады) немесе
  • жолдарда бағандардың саны бірдей болмайды (яғни сізде матрица болмаса да, басқа екі өлшемді құрылым).
158
қосылды
Көрсеткіштің мысалын пайдаланудың 2 негізгі себебі бар. Ең алдымен, ол ескірген еске түсірудің макеті бар (стандартта ол вектордың қалай көрінетініне кепілдік бермейді), ал екінші мәселе - осында қолданылатын көрсеткіштегі «ақылға қонымды тәсілдердің» көпшілігі.
қосылды автор Pixelchemist, көзі
Мен жақында std :: vector және comon layout туралы жауапты жадыда қалай қойдым. Мүмкін, бұл мәселеге қатысты қызығушылық туындауы мүмкін. c ++ векторы, ол кеңейтілсе не болады/стекке қайта бөле аласыз ба?
қосылды автор Pixelchemist, көзі
@FrankH « Бөлінген топтама бөлудің біреуі орындалмаса, еске түсіруді болдырмау үшін сәйкесінше өңдеуді қажет етеді! « @ ** Жадтың ағып кету қаупі **, бірақ менің ойымша, бұл туралы біраз түсіндірілу үшін шолу бар.
қосылды автор Pixelchemist, көзі
@beesleep: Yeah .. бұл кодты operator() қотарып, қотарып жатқанда жүреді және оны at деп жүрекке өзгертеді;)
қосылды автор Pixelchemist, көзі
Қатаң жады да компиляторға SIMD-мен жақсырақ авто-векторизациялауға мүмкіндік береді. Мысалы, Бұл кодта 50x жылдамдық сілтегіштердің орнына жазық массивді пайдалану арқылы . (Бұл іс жүзінде нашар болды: тек 4 қос санын көрсететін көрсеткішке арналған көрсеткіштің 3D матрицасы және нәрселер негізінен бір-бірінен бөлінген болса, дұрыс емес тәртіппен циклда). жаңа таралымға арналған жылдамдықты баяндады, бірақ бұл маңызды болуы керек
қосылды автор Peter Cordes, көзі
Бұл жақсы жауап, бірақ сіз неліктен мысалдағы шикізат көрсеткіштерін пайдалануды (және талқылауды) талап етесіз? Қазіргі C ++-дегі ешқандай себеп жоқ. Тек std :: vector пайдаланыңыз және онымен жасаңыз.
қосылды автор Konrad Rudolph, көзі
Жинау үлгісі дұрыс емес. Үлкен немесе айнымалы C үшін mul немесе кемінде қосымша shl қажет C == 4 . Мүмкін, әлі де үлкен суретті өзгертпейді.
қосылды автор zch, көзі
Фантастикалық жауап; сіз оны блогқа салғаныңыз жөн :)
қосылды автор Brennan Vincent, көзі
«2D динамикалық массиві» деген нәрсені жасаудың тағы бір себебі бар, бірақ ол сізді тек ірі өлшемдерде ғана итеруі мүмкін: new есте сақтау. «Стильді бөлу» бұл стильден кем дегенде new T * [N] массивіне арналған екі қоңырауларын талап етеді және екіншісі T [N * M] ) үшін, сондықтан әрқайсысына try {} catch {} немесе 1-ші сәтті аяқталған жағдайда, 2-ші лақтырылады. Нақты кінәлі деп C ++/STL стандартты matrix сыныбына ешқашан алаңдамайды. Егер Fortran C/C ++-нің үстінен дұрыс нәрсе алса, онда бұл ...
қосылды автор FrankH., көзі
Мұнда бірнеше қателіктер жоқ: сілтемесі() (size_type const жолдары, size_type const бағаны) {return m_data.at (m_cols * row + column); } операторда() (size_type const жолы, size_type const бағаны) const {қайтару m_data.at (m_cols * row + column); } ? Ол сілтемесінде (size_type const жолында, size_type const бағанында) және const_reference (size_type const жолында, size_type const column) const ішінде өзгеруі керек емес пе?
қосылды автор beesleep, көзі
Мен білемін ... Бұл әрқашан. Бірде-бір қылмыс :-D. Айтпақшы, кодексіне рахмет, жақсы және тиімді жұмыс!
қосылды автор beesleep, көзі

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
+---+---+---+
|   |   |   |
+---+---+---+

Әрине, 2D жағдайы кэш жерін жоғалтады және көп жадты пайдаланады. Ол сондай-ақ қосымша инициирует (және, осылайша, қосымша көрсеткіш), бірақ бірінші массив индекстерді есептеу үстінен ие, сондықтан олар тіпті көп немесе аз.

15
қосылды
Жақсы жауап. Сондай-ақ, динамикалық 2D массивіндегі кэшті жіберіп алмады деп ойладым
қосылды автор Alex, көзі

1D және 2D статикалық массивтер

  • Өлшем: Екі бірдей жадты талап етеді.

  • Speed: Сіз жылдамдықтың айырмашылығы болмайтынын болжай аласыз, себебі осы екі массивтердің жадылары бір-біріне жақын болуы керек (The тұтастай 2D массиві бір емес, еске салынған бір жинақ ретінде көрінуі керек жадқа тараған шоқтар). (Бұл компилятор болуы мүмкін тәуелді.)

1D және 2D динамикалық массивтер

  • Өлшемі: 2D массиві 2D массивіндегі қажетті көрсеткіштерге байланысты бөлінген 1D массивтерінің жиынтығын көрсету үшін 1D массивіне қарағанда кішкене көп жадты қажет етеді. (Бұл кішкентай бит тек үлкен массивтер туралы сөйлескен кезде кішкентай болып табылады). Кішігірім массивтер үшін кішкентай бит салыстырмалы түрде сөйлесе алады.)

  • Speed: 1D массиві 2D массивіне қарағанда жылдамырақ болуы мүмкін, себебі 2D массасының жадысы біркелкі болмайды, сондықтан кэшті босатпау мәселе болар еді

    /li>

Не істейтінін және ең логикалық болып көрінгенді қолданыңыз, және жылдамдыққа тап болған жағдайда, рефрактор.

8
қосылды
Мен 4x4 векторы дегенді білдіретін болсақ (жүйеге тәуелді) 164 байт талап етіледі, онда 100 байттың үстіңгі жағы бар. Мен бұл «кішкене» деп атамас едім (бұл фактор> 2.5), әсіресе, егер сіз олардың көпшілігін басқаруға немесе оларды жиі көшіріп алу қажет болса. (Бұл, әрине, бағандардың санының артуымен маңыздылығын жоғалтады.)
қосылды автор Pixelchemist, көзі
Жылдамдығы бойынша, ол массивді қалай пайдаланатыныңызға да байланысты. Кездейсоқ қолжетімді элементтер үшін офсетті есептеу бірдей, бірақ егер сіз барлық элементтерді қайталағыңыз келсе, сызықты түрде итерациялауға және кірістірілген ілмектерге немесе көп өлшемді координаттарды еске сақтауға көбейтуге жол бермеу үшін бір өлшемді массивпен оңай.
қосылды автор Boann, көзі
динамикалық «2D массиві» - басқа массивтерді көрсететін көрсеткіштердің массиві. Сондықтан 1D массивіне қарағанда көбірек орын қажет.
қосылды автор juanchopanza, көзі
@Pixelchemist Бұл шындық, мен оны айтқан жоқпын, себебі оның массивтері жылдамдық туралы алаңдататын болса өте үлкен болады деп күтемін. : P (Дегенмен, дәлірек айтсақ, жақсы болар еді деп ойлаймын)
қосылды автор Mohamad Ali Baydoun, көзі
Иә, бұл дұрыс. Бұл түзету үшін рахмет. @ mr5 std :: vector динамикалық 1D массиві сияқты әрекет етеді, себебі ол сол сияқты бағдарламаланған. ( static деп айтқан кезде, біз static сөзіне сілтеме жасаймыз)
қосылды автор Mohamad Ali Baydoun, көзі
«Жылдам айырмашылық жоқ.» Бұл шын мәнінде компилятор 2D массивтеріне арналған өрістерді есептеуді біледі.
қосылды автор SigTerm, көзі
Бірақ static std :: vector туралы статистикалық немесе динамикалық дегеніміз не? Өкінішке орай, менде олардың арасындағы айырмашылықтар жоқ.
қосылды автор mr5, көзі

Бар жауаптар барлығы 1-D массивтерін көрсеткіштердің массивтерімен салыстырады.

C (бірақ C ++ емес) үшінші нұсқа бар; динамикалық бөлінген және орындалатын уақыт өлшемдеріне ие 2-D масштабты сабақтастығына ие бола аласыз:

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

және бұл p [row_index] [col_index] сияқты қол жетімді.

Мен бұл 1-D массивінің жағдайына ұқсас өнімділікке ие болар еді деп күтемін, бірақ ол сізге жасушаларға кіру үшін жақсы синтаксисті береді.

С ++ жүйесінде сіз 1-D массивін ішкі деңгейде сақтайтын сыныпты анықтау арқылы бірдей нәрсеге қол жеткізе аласыз, бірақ оны шамадан тыс жүктелген операторлар арқылы 2-D массивіне қол жеткізу синтаксисі арқылы ашуға болады. Тағы бірдей 1-D массивіне ұқсас немесе бірдей өнімділікке ие болуды күтемін.

4
қосылды
@Paladin C және C ++ әртүрлі тілдер болып табылады, олардың әрқайсысында кейбір ерекшеліктері бар, ал кейбіреулері әртүрлі түрде орындалады. Стандартты режимде g ++ нұсқасын қолданып көріңіз және сіз диагностикаға ие боласыз, әдепкіде ол кейбір кеңейтімдерді қосады.
қосылды автор M.M, көзі
@vsoftco сіздің C ++ кода num_cols тұрақты өрнек болуы керек, бірақ менің кодымда ол орындалу уақытында анықталуы мүмкін
қосылды автор M.M, көзі
@ M.M C (бірақ C ++ емес) үшінші нұсқа бар Неге тек C? C ++-де оңай жасауға болады int (* p) [num_cols] = new int [num_rows] [num_cols]; жою [] p; .
қосылды автор vsoftco, көзі
@ M.M Ohh Мен көремін, рақмет! Иә, шын мәнінде, lhs C-дегі VLA-нің көрсеткіші.
қосылды автор vsoftco, көзі
Бұл шынымен аңызға айналғандай әсер қалдырады, мен кез-келген C-дың жарамды C ++ .. деп ойладым. G ++ 4.8.3 осы кодты қабылдайды пастаны .com/Te2n1XhZ ...
қосылды автор Paladin, көзі

Жадты бөлу кезінде 1D және 2D массивтерінің тағы бір айырмашылығы пайда болады. 2D массивінің мүшелері дәйекті болып табылатынына сенімді бола алмаймыз.

4
қосылды
Ия. Ал бұл массив өнімділік-сын кодының 1% -ында болғанда елеулі әсер етуі мүмкін.
қосылды автор Arcane Engineer, көзі

Бұл шынымен 2D массивінің қалай іске асырылғанына байланысты.

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.
}

Мұнда 3 іске асыру бар: b, c және d B [x] [y] немесе [x * 20 + y] қатынасына көп айырмашылық болмайды, себебі сіз біреуін есептеп жатырсыз, екіншісі сіз үшін жасайтын компилятор. c [x] [y] және d [x] [y] баяулайды, себебі машина c (x) көрсететін мекенжайды табуы керек, содан кейін ондағылардың элементіне қол жеткізе алады. Бұл тікелей есептеу емес. Кейбір машиналарда (мысалы, 36 байт (бит емес) көрсеткіштері бар AS400) көрсеткіштерге қол жеткізу өте баяу. Бұл қолданыстағы архитектураға байланысты. X86 типті сәулет, a және b бірдей жылдамдық, c және d b қарағанда баяу.

1
қосылды

Мен Pixelchemist ұсынған мұқият жауапты жақсы көремін. Бұл шешімнің қарапайым нұсқасы келесідей болуы мүмкін. Алдымен өлшемдерді жариялаңыз:

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

Содан кейін бүркеншік ат жасаңыз және әдістерді орнатыңыз:

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_];
}

Ақыр соңында, векторды келесі түрде жасауға және индекстеуге болады:

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

Инициализация кезінде вектордың өлшемін анықтау оңтайлы өнімділік . Бұл шешім бұл жауап ішінен өзгертілген. Бір вектормен әртүрлі өлшемдерді қолдау үшін функциялар жүктелуі мүмкін. Бұл шешімнің төмендеуі M, N, P параметрлері жалғану және орнату функцияларына жанама түрде беріледі. Бұл шешімді Pixelchemist арқылы жасалынған сыныпта енгізу арқылы шешуге болады.

0
қосылды