Форум программистов, компьютерный форум CyberForum.ru

Динамический массив с большим количеством элементов - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.81
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 00:15     Динамический массив с большим количеством элементов #1
Нужно создать динамический массив (каждый элемент целое положительное число до 10^9), который по введенным данным создавал N элементов массива, где N может быть до 10^5.

unsigned long int *arr = new unsigned long int[num];

Я сделал так, но если количество элементов больше 45920, то выводит ошибку
"terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
This application has requested the Runtime to terminate it in unuasual way.
Please contact the application's support team for more information."
IDE Qt Creator.
Статические массивы типа int array[1000000]; сразу выводят ошибку, причем в обоих случая изменение типа элементов массива ничего не меняет.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.03.2013, 00:15     Динамический массив с большим количеством элементов
Посмотрите здесь:

динамический массив из элементов структурного типа C++
Массив: определить индекс столбца с максимальным количеством нулевых элементов C++
Задан массив с количеством элементов n C++
Массив с неизвестным заранее количеством элементов C++
C++ Алгоритм быстрой сортировки не работает с большим количеством чисел
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 03:07     Динамический массив с большим количеством элементов #21
Цитата Сообщение от Avazart Посмотреть сообщение
А если есть фрагментация ... + малое количество оперативки ...+ куча процессов жруших память
А для этого у винды есть VirtualAlloc
да и думать нужно когда пишешь, а не бездумно память выделять удалять
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
13.03.2013, 03:12     Динамический массив с большим количеством элементов #22
Как будто VirualAlloc поможет от фрагментации, которая уже есть.
Avazart
 Аватар для Avazart
6900 / 5140 / 252
Регистрация: 10.12.2010
Сообщений: 22,588
Записей в блоге: 17
13.03.2013, 03:19     Динамический массив с большим количеством элементов #23
Цитата Сообщение от ValeryS Посмотреть сообщение
да и думать нужно когда пишешь, а не бездумно память выделять удалять
Ну вот и я говорю... не известно что там ТС задумал...
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 03:25  [ТС]     Динамический массив с большим количеством элементов #24
Со статическими объявлениями понятно - одномерный массив работает нормально, двумерный даже не создается из-за размера. Динамические не срабатывают. В этой программе кроме этих случаев операций с памятью нету. Оперативки 16 гб. Завтра буду разбираться с битсет и вектором, но я так и не понял, почему может тупить с созданием динамического массива таких размеров.
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 03:25     Динамический массив с большим количеством элементов #25
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
Как будто VirualAlloc поможет от фрагментации, которая уже есть.
конечно
резервируй в начале проги а не когда уже все загадил
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
13.03.2013, 03:27     Динамический массив с большим количеством элементов #26
Не, ну это-то понятно. Я про то, что она ни разу не поможет дефрагментировать кучу.

Выделить себе кусок с самого начала можно и без всяких VirtualAlloc (всё равно malloc() вызывает её при достаточно больших запросах памяти).
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 03:30     Динамический массив с большим количеством элементов #27
Цитата Сообщение от luck Посмотреть сообщение
Динамические не срабатывают. В этой программе кроме этих случаев операций с памятью нету. Оперативки 16 гб.
ты бы код скинул, а то так можно долго гадать

Добавлено через 1 минуту
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
Я про то, что она ни разу не поможет дефрагментировать кучу.
а я даже не знаю кто, в рамках языка, поможет дефрагментировать память
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 03:31  [ТС]     Динамический массив с большим количеством элементов #28
Да я по-моему уже скидывал все части, относящиеся к выделению памяти.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <string.h>
using namespace std;
unsigned long int func(unsigned long int);
//unsigned long int array[100000];
int main()
{
    unsigned long int i,j,num,res = 0;
    cin>>num; //Если num>45920, то ошибка
//    memset(array,0,100000);
    unsigned long int *arr = new unsigned long int[num];
    bool **mass = new bool*[num];
    for (i=0;i<num;i++)
        mass[i]= new bool[num];
    for (i=0;i<num;i++)
        for (j=0;j<num;j++)
            mass[i][j]=0;
    for (i=0;i<num;i++)
      scanf("%d",&arr[i]);
    for (i=0;i<num;i++)
     for (j=0;j<num;j++)
         if ((mass[j][i]==0) and (i!=j) )
                 if (func(arr[i])==func(arr[j]))
         {
                res++;
                mass[i][j]=1;
         }
    printf("%d",res);
    for (i=0;i<num;i++)
        delete[] mass[i];
    delete[] mass;
    delete[] arr;
    return 0;
}
 
unsigned long int func(unsigned long int a)
{
    if (a==0)
        return 0;
    if (a%2==0)
       return func(a/2);
    else
    {
         a=func(a/2)+1;
         return a;
    }
}
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 03:49     Динамический массив с большим количеством элементов #29
у меня на 1000000 нормально отработала
теперь несколько замечаний
Цитата Сообщение от luck Посмотреть сообщение
mass[i][j]=0;
для bool нет нуля есть true и false
следовательно вот это
Цитата Сообщение от luck Посмотреть сообщение
if ((mass[j][i]==0) and (i!=j) )
переписывается так
C++
1
if (!mass[j][i] && (i!=j) )
Цитата Сообщение от luck Посмотреть сообщение
for (i=0;i<num;i++)
* * * scanf("%d",&arr[i]);
Ты всерьез думаешь что пользователь будет с клавиатуры вгонять сто тысяч значений?
даже если по секунде на значения это 30 часов
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 03:52  [ТС]     Динамический массив с большим количеством элементов #30
олимпиадная задача, на том тесте, на котором я застрял из-за перебора памяти, было 56к значений)

На тестах проверки используется GCC 4.7, у меня Qt Creator - и там и там не сработало.
Avazart
 Аватар для Avazart
6900 / 5140 / 252
Регистрация: 10.12.2010
Сообщений: 22,588
Записей в блоге: 17
13.03.2013, 03:55     Динамический массив с большим количеством элементов #31
Цитата Сообщение от ValeryS Посмотреть сообщение
для bool нет нуля есть true и false
чЁ ?
C++
1
if ((mass[j][i]==0) and (i!=j) )
А вот что такое and ?
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
13.03.2013, 03:56     Динамический массив с большим количеством элементов #32
Цитата Сообщение от ValeryS Посмотреть сообщение
для bool нет нуля есть true и false
Ноль приводится к false.

Цитата Сообщение от luck Посмотреть сообщение
олимпиадная задача
Вот с этого надо начинать. Если это олимпиадная задача и она падает на проверочной системе, то 99%, что ваш алгоритм решения — го... не подходит. Целиком.

Цитата Сообщение от Avazart Посмотреть сообщение
А вот что такое and ?
Альтернативный токен. Пункт 2.6 стандарта.
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 04:00  [ТС]     Динамический массив с большим количеством элементов #33
Алгоритм сработал на 10 проверках. На 11 он не сработал, потому что значение num слишком большое, код ошибки - превышение ограничения памяти.
And это видимо моя привычка с паскаля =\
Странно, что на сях сработало.

Добавлено через 1 минуту
Даже если данное решение не пройдет тесты из-за использования массивов (причем я слабо представляю как обойти в отношении массива arr, хотя массив булевых элементов можно и обойти) - все равно он должен работать на моей машине, а это не так.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
13.03.2013, 04:12     Динамический массив с большим количеством элементов #34
Ммм... ОС у вас точно 64-битная?

А то 45920 x 45920 = 2108646400 = чуть меньше 2 гигабайт. Плюс ещё что-то на указатели, библиотеки и т. п. 2 гига — это предел виртуальной памяти на 32-битной Винде (без хитростей). Совпадает же.
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 04:13     Динамический массив с большим количеством элементов #35
Цитата Сообщение от Avazart Посмотреть сообщение
чЁ ?
Те!
на то она и логическая переменная чтобы работать с логическими значениями
а то что 0 равен false, ничего не значит
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
Ноль приводится к false.
я с этим и не спорю
но писать нужно правильно
не пишут ведь
C++
1
 char c=0x41;
а пишут
C++
1
char c='A';
Avazart
 Аватар для Avazart
6900 / 5140 / 252
Регистрация: 10.12.2010
Сообщений: 22,588
Записей в блоге: 17
13.03.2013, 04:18     Динамический массив с большим количеством элементов #36
Цитата Сообщение от ValeryS Посмотреть сообщение
Те!
на то она и логическая переменная чтобы работать с логическими значениями
а то что 0 равен false, ничего не значит
Вы хотите сказать что может быть иначе ?
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 04:19  [ТС]     Динамический массив с большим количеством элементов #37
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
ОС у вас точно 64-битная?
64-битная. Но интересный факт, надо будет иметь в виду)
Avazart
 Аватар для Avazart
6900 / 5140 / 252
Регистрация: 10.12.2010
Сообщений: 22,588
Записей в блоге: 17
13.03.2013, 04:22     Динамический массив с большим количеством элементов #38
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
Ммм... ОС у вас точно 64-битная?
А то 45920 x 45920 = 2108646400 = чуть меньше 2 гигабайт. Плюс ещё что-то на указатели, библиотеки и т. п. 2 гига — это предел виртуальной памяти на 32-битной Винде (без хитростей). Совпадает же.
Ну да гдето так у меня удавалось ужрать 1.7 Г до исключения...
Цитата Сообщение от luck Посмотреть сообщение
64-битная. Но интересный факт, надо будет иметь в виду)
Ну так а компилятор какой стоит ? Может из-за этого ?
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 04:26     Динамический массив с большим количеством элементов #39
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
А то 45920 x 45920 = 2108646400 = чуть меньше 2 гигабайт.
да побольше будет
сначала выделяется память под 45920 указателя а они по 4 байта
Цитата Сообщение от luck Посмотреть сообщение
bool **mass = new bool*[num];
а только потом 45920 блока памяти по 45920 байт
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.03.2013, 04:27     Динамический массив с большим количеством элементов
Еще ссылки по теме:

C++ Динамический массив, удаление и вставка элементов
C++ Применение массивов случайных чисел с большим количеством элементов
Вычислить разность между количеством отрицательных и количеством положительных элементов одномерного массива C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 04:27  [ТС]     Динамический массив с большим количеством элементов #40
Использую IDE Qt Creator, как проверить какой компилятор он использует? Или существует какой то стандартный Qt?
Yandex
Объявления
13.03.2013, 04:27     Динамический массив с большим количеством элементов
Ответ Создать тему
Опции темы

Текущее время: 20:40. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru