Czy istnieje limit maksymalnej długości tablicy w C ++?

Czy istnieje maksymalna długość tablicy w C ++?

Czy jest to limit C ++, czy zależy to od mojego komputera? Czy można to zmienić? Czy to zależy od typu, z którego składa się tablica?

Czy mogę jakoś przekroczyć ten limit, czy też muszę szukać lepszego sposobu przechowywania informacji? A jaki powinien być najprostszy sposób?

To, co muszę zrobić, to przechowywać long long int na tablicy, pracuję w środowisku Linux. Moje pytanie brzmi: co mam zrobić, jeśli potrzebuję zapisać tablicę N długich liczb całkowitych z N> 10 cyframi?

Potrzebuję tego, ponieważ piszę jakiś algorytm kryptograficzny (jak na przykład p-Pollard) dla szkoły i trafiam w tę ścianę reprezentacji liczb całkowitych i długości tablic.

Istnieją dwa ograniczenia, oba nie są wymuszane przez C ++, ale raczej przez sprzęt.

Pierwszy limit (nigdy nie powinien zostać osiągnięty) jest ustalany przez ograniczenia typu rozmiaru używanego do opisu indeksu w tablicy (i jego rozmiaru). Podaje się go jako maksymalna wartość, jaką system std::size_tmoże przyjąć. Ten typ danych jest wystarczająco duży, aby zawierać rozmiar w bajtach dowolnego obiektu

Drugi limit to fizyczny limit pamięci. Im większe są twoje obiekty w tablicy, tym szybciej ten limit zostanie osiągnięty, ponieważ pamięć jest pełna. Na przykład, a vector<int>o danym rozmiarze n zwykle zajmuje wielokrotnie więcej pamięci niż tablica typu vector<char>(bez małej stałej wartości), ponieważ intjest zwykle większa niż char. Dlatego a vector<char>może zawierać więcej elementów niż a vector<int>przed zapełnieniem pamięci. To samo dotyczy surowych tablic w stylu C, takich jak int[]i char[].

Dodatkowo, na tę górną granicę może mieć wpływ typ allocatorużytego do skonstruowania, vectorponieważ allocatormoże swobodnie zarządzać pamięcią w dowolny sposób. Bardzo dziwny, ale jednak możliwy do wyobrażenia alokator mógłby łączyć pamięć w taki sposób, że identyczne instancje obiektu współużytkują zasoby. W ten sposób można wstawić wiele identycznych obiektów do kontenera, który w przeciwnym razie zużywałby całą dostępną pamięć.

Poza tym C ++ nie narzuca żadnych ograniczeń.

Nikt nie wspomniał o ograniczeniu rozmiaru ramki stosu .

Istnieją dwa miejsca, w których można przydzielić pamięć:

• Na stercie (pamięć przydzielana dynamicznie).
  Limit rozmiaru jest tutaj połączeniem dostępnego sprzętu i zdolności systemu operacyjnego do symulowania miejsca przy użyciu innych urządzeń do tymczasowego przechowywania nieużywanych danych ( tj. Przenoszenia stron na dysk twardy).
• Na stosie (zmienne zadeklarowane lokalnie).
  Limit rozmiaru jest tutaj zdefiniowany przez kompilator (z możliwymi ograniczeniami sprzętowymi). Jeśli czytasz dokumentację kompilatora, często możesz dostosować ten rozmiar.

Tak więc, jeśli przydzielasz tablicę dynamicznie (limit jest duży i szczegółowo opisany w innych postach.

int* a1 = new int[SIZE];  // SIZE limited only by OS/Hardware

Alternatywnie, jeśli tablica jest alokowana na stosie, jesteś ograniczony przez rozmiar ramki stosu. Uwaga: wektory i inne pojemniki mają niewielką ilość w stosie, ale zwykle większość danych będzie na stercie.

int a2[SIZE]; // SIZE limited by COMPILER to the size of the stack frame

Patrząc na to z praktycznego, a nie teoretycznego punktu widzenia, w 32-bitowym systemie Windows maksymalna całkowita ilość pamięci dostępnej dla pojedynczego procesu wynosi 2 GB. Możesz przekroczyć ten limit, przechodząc do 64-bitowego systemu operacyjnego ze znacznie większą pamięcią fizyczną, ale to, czy to zrobić, czy poszukać alternatyw, zależy w dużej mierze od zamierzonych użytkowników i ich budżetów. Możesz również nieco go rozszerzyć za pomocą PAE .

Typ tablicy jest bardzo ważny, ponieważ domyślne wyrównanie struktury w wielu kompilatorach wynosi 8 bajtów, co jest bardzo marnotrawne, jeśli problemem jest użycie pamięci. Jeśli używasz języka Visual C ++ do kierowania na system Windows, zapoznaj się z dyrektywą #pragma pack, aby rozwiązać ten problem.

Inną rzeczą do zrobienia jest przyjrzenie się, co mogą pomóc w technikach kompresji pamięci, takich jak rzadkie macierze, kompresja w locie itp. Znowu jest to wysoce zależne od aplikacji. Jeśli zmodyfikujesz swój post, aby podać więcej informacji na temat tego, co faktycznie znajduje się w twoich tablicach, możesz uzyskać bardziej przydatne odpowiedzi.

Edycja: biorąc pod uwagę nieco więcej informacji na temat dokładnych wymagań, Twoje potrzeby w zakresie przechowywania wydają się wynosić od 7,6 GB do 76 GB bez kompresji, co wymagałoby raczej drogiego 64-bitowego pudełka do przechowywania jako tablicy w pamięci w C ++. Powstaje pytanie, dlaczego chcesz przechowywać dane w pamięci, w której zakłada się szybkość dostępu i zezwalasz na dostęp losowy. Najlepszy sposób na przechowywanie tych danych poza tablicą zależy w dużej mierze od tego, jak chcesz uzyskać do nich dostęp. Jeśli potrzebujesz losowego dostępu do elementów tablicy, w przypadku większości aplikacji istnieją sposoby grupowania grup danych, które mają tendencję do uzyskiwania dostępu w tym samym czasie. Na przykład w dużych GIS i bazach danych przestrzennych dane często są dzielone według obszaru geograficznego. W terminach programowania C ++ można zastąpić operator tablicy [], aby w razie potrzeby pobrać porcje danych z pamięci zewnętrznej.

Zgodziłbym się z powyższym, jeśli chcesz zainicjować swoją tablicę z

 int myArray[SIZE] 

wtedy ROZMIAR jest ograniczony rozmiarem liczby całkowitej. Ale zawsze możesz malloc kawałek pamięci i mieć do niego wskaźnik, tak duży, jak chcesz, o ile malloc nie zwraca NULL.

Podsumowując odpowiedzi, rozszerz je i odpowiadając bezpośrednio na Twoje pytanie:

Nie, C ++ nie narzuca żadnych ograniczeń co do wymiarów tablicy.

Ale ponieważ tablica musi być przechowywana gdzieś w pamięci, obowiązują ograniczenia związane z pamięcią narzucone przez inne części systemu komputerowego. Zauważ, że te ograniczenia nie odnoszą się bezpośrednio do wymiarów (= liczby elementów) tablicy, ale raczej do jej rozmiaru (= ilości zajętej pamięci). Wymiary ( D ) i rozmiar w pamięci ( S ) tablicy nie są takie same, ponieważ są powiązane z pamięcią pobieraną przez pojedynczy element ( E ): S = D * E . mi zależy od:

Teraz

• rodzaj elementów tablicy (elementy mogą być mniejsze lub większe)
• wyrównanie pamięci (aby zwiększyć wydajność, elementy są umieszczane pod adresami będącymi wielokrotnościami pewnej wartości, co wprowadza
  `` zmarnowaną przestrzeń '' (dopełnienie) między elementami
• wielkość statycznych części obiektów (w programowaniu obiektowym statyczne składowe obiektów tego samego typu są przechowywane tylko raz, niezależnie od liczby obiektów tego samego typu)

Należy również zauważyć, że generalnie uzyskuje się różne ograniczenia związane z pamięcią, przydzielając dane tablicowe na stosie (jako zmienna automatyczna:) int t[N]lub na stercie ( alokacja dynamiczna z malloc()/ newlub przy użyciu mechanizmów STL) lub w statycznej części pamięci procesu (jako zmienna statyczna:) static int t[N]. Nawet w przypadku alokowania na stercie nadal potrzebujesz niewielkiej ilości pamięci na stosie, aby przechowywać odwołania do bloków pamięci przydzielonych na stercie (ale zwykle jest to pomijalne).

Rozmiar size_ttypu nie ma wpływu na programistę (zakładam, że programista używa size_ttypu do indeksowania, ponieważ jest do tego przeznaczony), ponieważ musi to zrobić dostawca kompilatoratypedef to zrobić na typ całkowity wystarczająco duży, aby zaadresować maksymalną ilość pamięci możliwą dla danej platformy architektura.

Źródła ograniczeń rozmiaru pamięci wynikają z

• ilość pamięci dostępnej dla procesu (która jest ograniczona do 2 ^ 32 bajtów dla aplikacji 32-bitowych, nawet na jądrach 64-bitowych systemów operacyjnych),
• podział pamięci procesu (np. ilość pamięci procesu przeznaczonej na stos lub stertę),
• fragmentacja pamięci fizycznej (wiele rozproszonych małych wolnych fragmentów pamięci nie ma zastosowania do przechowywania jednej monolitycznej struktury),
• ilość pamięci fizycznej,
• i ilość pamięci wirtualnej.

Nie można ich modyfikować na poziomie aplikacji, ale możesz użyć innego kompilatora (w celu zmiany limitów rozmiaru stosu), przenieść aplikację na 64-bitowe lub przenieść ją na inny system operacyjny lub zmienić fizyczny / konfiguracja pamięci wirtualnej maszyny (wirtualnej? fizycznej?).

Nie jest niczym niezwykłym (a nawet zalecane) traktowanie wszystkich powyższych czynników jako zewnętrznych zakłóceń, a zatem jako możliwych źródeł błędów w czasie wykonywania, oraz dokładne sprawdzanie i reagowanie na błędy związane z alokacją pamięci w kodzie programu.

W końcu: chociaż C ++ nie narzuca żadnych ograniczeń, nadal musisz sprawdzać niekorzystne warunki związane z pamięcią podczas uruchamiania kodu ... :-)

Jak zauważyło wiele doskonałych odpowiedzi, istnieje wiele ograniczeń, które zależą od wersji kompilatora C ++, systemu operacyjnego i charakterystyki komputera. Sugeruję jednak następujący skrypt w Pythonie, który sprawdza limit na twojej maszynie.

Używa wyszukiwania binarnego i przy każdej iteracji sprawdza, czy średni rozmiar jest możliwy, tworząc kod, który próbuje utworzyć tablicę o tym rozmiarze. Skrypt próbuje go skompilować (przepraszam, ta część działa tylko na Linuksie) i dostosować wyszukiwanie binarne w zależności od sukcesu. Sprawdź to:

import os

cpp_source = 'int a[{}]; int main() {{ return 0; }}'

def check_if_array_size_compiles(size):
        #  Write to file 1.cpp
        f = open(name='1.cpp', mode='w')
        f.write(cpp_source.format(m))
        f.close()
        #  Attempt to compile
        os.system('g++ 1.cpp 2> errors')
        #  Read the errors files
        errors = open('errors', 'r').read()
        #  Return if there is no errors
        return len(errors) == 0

#  Make a binary search. Try to create array with size m and
#  adjust the r and l border depending on wheather we succeeded
#  or not
l = 0
r = 10 ** 50
while r - l > 1:
        m = (r + l) // 2
        if check_if_array_size_compiles(m):
                l = m
        else:
                r = m

answer = l + check_if_array_size_compiles(r)
print '{} is the maximum avaliable length'.format(answer)

Możesz zapisać go na swoim urządzeniu i uruchomić, a wydrukuje w maksymalnym możliwym rozmiarze. W przypadku mojej maszyny jest to 2305843009213693951.

Jedna rzecz, o której nie sądzę, została wspomniana w poprzednich odpowiedziach.

Zawsze wyczuwam „nieprzyjemny zapach” w sensie refaktoryzacji, kiedy ludzie używają takich rzeczy w swoich projektach.

To ogromna tablica i prawdopodobnie nie jest to najlepszy sposób reprezentowania danych zarówno z punktu widzenia wydajności, jak i punktu widzenia wydajności.

Twoje zdrowie,

Obrabować

Jeśli masz do czynienia z tak dużymi danymi, musisz podzielić je na łatwe do zarządzania części. Nie wszystko zmieści się w pamięci dowolnego małego komputera. Prawdopodobnie możesz załadować część danych z dysku (cokolwiek rozsądnie pasuje), wykonać obliczenia i zmiany w nim, zapisać je na dysku, a następnie powtarzać aż do zakończenia.

Choć wszystkie obecne odpowiedzi są irytująco niesprecyzowane, w większości mają rację, ale z wieloma zastrzeżeniami, które nie zawsze są wspomniane. Istota jest taka, że ​​masz dwie górne granice, a tylko jedna z nich jest faktycznie zdefiniowana, więc YMMV :

1. Terminy kompilacji

Zasadniczo na to, na co pozwoli Twój kompilator. W przypadku programu Visual C ++ 2017 na pudełku z systemem Windows 10 x64 jest to mój maksymalny limit w czasie kompilacji przed naliczeniem limitu 2 GB,

unsigned __int64 max_ints[255999996]{0};

Gdybym zamiast tego zrobił to,

unsigned __int64 max_ints[255999997]{0};

Dostałbym:

Error C1126 automatic allocation exceeds 2G

Nie jestem pewien, jak 2G odpowiada 255999996/ 7. Przeszukałem oba numery i jedyną rzeczą, jaką mogłem znaleźć, która była prawdopodobnie powiązana, było pytanie * nix dotyczące problemu z precyzjądc . Tak czy inaczej, nie ma znaczenia, jaki typ tablicy int próbujesz wypełnić, tylko ile elementów można przydzielić.

2. Limity czasu pracy

Twój stack i sterta mają swoje własne ograniczenia. Te limity to zarówno wartości, które zmieniają się w zależności od dostępnych zasobów systemowych, jak i tego, jak „ciężka” jest sama aplikacja. Na przykład przy moich obecnych zasobach systemowych mogę uruchomić to:

int main()
{
    int max_ints[257400]{ 0 };
    return 0;
}

Ale jeśli poprawię to tylko trochę ...

int main()
{
    int max_ints[257500]{ 0 };
    return 0;
}

Bam! Przepełnienie stosu!

Exception thrown at 0x00007FF7DC6B1B38 in memchk.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x000000AA8DE03000). Unhandled exception at 0x00007FF7DC6B1B38 in memchk.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x000000AA8DE03000).

Aby szczegółowo opisać całą wagę punktu aplikacji, dobrze było:

int main()
{
    int maxish_ints[257000]{ 0 };
    int more_ints[400]{ 0 };
    return 0;
}  

Ale to spowodowało przepełnienie stosu:

int main()
{
    int maxish_ints[257000]{ 0 };
    int more_ints[500]{ 0 };
    return 0;
}  

Dziwię się MAX_SIZE () funkcji członka z std :: vector nie zostały tutaj wymienione.

„Zwraca maksymalną liczbę elementów, które kontener może pomieścić ze względu na ograniczenia implementacji systemu lub biblioteki, np. Std :: distance (begin (), end ()) dla największego kontenera.”

Wiemy, że std::vectorjest zaimplementowany jako dynamiczna tablica pod maską, więc max_size()powinna być bardzo zbliżona do maksymalnej długości tablicy dynamicznej na twoim komputerze.

Poniższy program tworzy tabelę przybliżonej maksymalnej długości tablicy dla różnych typów danych.

#include <iostream>
#include <vector>
#include <string>
#include <limits>

template <typename T>
std::string mx(T e) {
    std::vector<T> v;
    return std::to_string(v.max_size());
}

std::size_t maxColWidth(std::vector<std::string> v) {
    std::size_t maxWidth = 0;

    for (const auto &s: v)
        if (s.length() > maxWidth)
            maxWidth = s.length();

    // Add 2 for space on each side
    return maxWidth + 2;
}

constexpr long double maxStdSize_t = std::numeric_limits<std::size_t>::max();

// cs stands for compared to std::size_t
template <typename T>
std::string cs(T e) {
    std::vector<T> v;
    long double maxSize = v.max_size();
    long double quotient = maxStdSize_t / maxSize;
    return std::to_string(quotient);
}

int main() {
    bool v0 = 0;
    char v1 = 0;

    int8_t v2 = 0;
    int16_t v3 = 0;
    int32_t v4 = 0;
    int64_t v5 = 0;

    uint8_t v6 = 0;
    uint16_t v7 = 0;
    uint32_t v8 = 0;
    uint64_t v9 = 0;

    std::size_t v10 = 0;
    double v11 = 0;
    long double v12 = 0;

    std::vector<std::string> types = {"data types", "bool", "char", "int8_t", "int16_t",
                                      "int32_t", "int64_t", "uint8_t", "uint16_t",
                                      "uint32_t", "uint64_t", "size_t", "double",
                                      "long double"};

    std::vector<std::string> sizes = {"approx max array length", mx(v0), mx(v1), mx(v2),
                                      mx(v3), mx(v4), mx(v5), mx(v6), mx(v7), mx(v8),
                                      mx(v9), mx(v10), mx(v11), mx(v12)};

    std::vector<std::string> quotients = {"max std::size_t / max array size", cs(v0),
                                          cs(v1), cs(v2), cs(v3), cs(v4), cs(v5), cs(v6),
                                          cs(v7), cs(v8), cs(v9), cs(v10), cs(v11), cs(v12)};

    std::size_t max1 = maxColWidth(types);
    std::size_t max2 = maxColWidth(sizes);
    std::size_t max3 = maxColWidth(quotients);

    for (std::size_t i = 0; i < types.size(); ++i) {
        while (types[i].length() < (max1 - 1)) {
            types[i] = " " + types[i];
        }

        types[i] += " ";

        for  (int j = 0; sizes[i].length() < max2; ++j)
            sizes[i] = (j % 2 == 0) ? " " + sizes[i] : sizes[i] + " ";

        for  (int j = 0; quotients[i].length() < max3; ++j)
            quotients[i] = (j % 2 == 0) ? " " + quotients[i] : quotients[i] + " ";

        std::cout << "|" << types[i] << "|" << sizes[i] << "|" << quotients[i] << "|\n";
    }

    std::cout << std::endl;

    std::cout << "N.B. max std::size_t is: " <<
        std::numeric_limits<std::size_t>::max() << std::endl;

    return 0;
}

Na moim macOS (wersja Clang 5.0.1) otrzymuję następujące informacje:

|  data types | approx max array length | max std::size_t / max array size |
|        bool |   9223372036854775807   |             2.000000             |
|        char |   9223372036854775807   |             2.000000             |
|      int8_t |   9223372036854775807   |             2.000000             |
|     int16_t |   9223372036854775807   |             2.000000             |
|     int32_t |   4611686018427387903   |             4.000000             |
|     int64_t |   2305843009213693951   |             8.000000             |
|     uint8_t |   9223372036854775807   |             2.000000             |
|    uint16_t |   9223372036854775807   |             2.000000             |
|    uint32_t |   4611686018427387903   |             4.000000             |
|    uint64_t |   2305843009213693951   |             8.000000             |
|      size_t |   2305843009213693951   |             8.000000             |
|      double |   2305843009213693951   |             8.000000             |
| long double |   1152921504606846975   |             16.000000            |

N.B. max std::size_t is: 18446744073709551615

Na ideone gcc 8.3 otrzymuję:

|  data types | approx max array length | max std::size_t / max array size |
|        bool |   9223372036854775744   |             2.000000             |
|        char |   18446744073709551615  |             1.000000             |
|      int8_t |   18446744073709551615  |             1.000000             |
|     int16_t |   9223372036854775807   |             2.000000             |
|     int32_t |   4611686018427387903   |             4.000000             |
|     int64_t |   2305843009213693951   |             8.000000             |
|     uint8_t |   18446744073709551615  |             1.000000             |
|    uint16_t |   9223372036854775807   |             2.000000             |
|    uint32_t |   4611686018427387903   |             4.000000             |
|    uint64_t |   2305843009213693951   |             8.000000             |
|      size_t |   2305843009213693951   |             8.000000             |
|      double |   2305843009213693951   |             8.000000             |
| long double |   1152921504606846975   |             16.000000            |

N.B. max std::size_t is: 18446744073709551615

Należy zauważyć, że jest to teoretyczny limit i na większości komputerów zabraknie pamięci na długo przed osiągnięciem tego limitu. Na przykład widzimy, że dla typu charon gccmaksymalna liczba elementów jest równa maksymalnej std::size_t. Próbując tego , otrzymujemy błąd:

prog.cpp: In function ‘int main()’:
prog.cpp:5:61: error: size of array is too large
  char* a1 = new char[std::numeric_limits<std::size_t>::max()];

Wreszcie, jak wskazuje @MartinYork, w przypadku tablic statycznych maksymalny rozmiar jest ograniczony rozmiarem stosu.

Jak już wspomniano, rozmiar tablicy jest ograniczony przez twój sprzęt i system operacyjny (man ulimit). Twoje oprogramowanie może być jednak ograniczone tylko przez twoją kreatywność. Na przykład, czy możesz przechowywać swoją „macierz” na dysku? Czy naprawdę potrzebujesz długich, długich int? Czy naprawdę potrzebujesz gęstej tablicy? Czy w ogóle potrzebujesz tablicy?

Jednym prostym rozwiązaniem byłoby użycie 64-bitowego Linuksa. Nawet jeśli fizycznie nie masz wystarczającej ilości pamięci RAM dla swojej macierzy, system operacyjny pozwoli ci przydzielić pamięć tak, jak gdybyś to zrobił, ponieważ pamięć wirtualna dostępna dla twojego procesu jest prawdopodobnie znacznie większa niż pamięć fizyczna. Jeśli naprawdę potrzebujesz dostępu do wszystkiego w tablicy, oznacza to przechowywanie go na dysku. W zależności od twoich wzorców dostępu, mogą istnieć bardziej efektywne sposoby zrobienia tego (np. Użycie mmap () lub po prostu przechowywanie danych sekwencyjnie w pliku (w takim przypadku wystarczy 32-bitowy Linux)).

obejdę to, tworząc dynamiczną tablicę 2D:

long long** a = new long long*[x];
for (unsigned i = 0; i < x; i++) a[i] = new long long[y];

więcej na ten temat tutaj https://stackoverflow.com/a/936702/3517001