Форум программистов, компьютерный форум 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++ Алгоритм быстрой сортировки не работает с большим количеством чисел
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Avazart
 Аватар для Avazart
6901 / 5141 / 252
Регистрация: 10.12.2010
Сообщений: 22,601
Записей в блоге: 17
13.03.2013, 04:28     Динамический массив с большим количеством элементов #41
Цитата Сообщение от luck Посмотреть сообщение
Использую IDE Qt Creator, как проверить какой компилятор он использует? Или существует какой то стандартный Qt?
А какой качал ?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 04:35  [ТС]     Динамический массив с большим количеством элементов #42
кажется этот - http://rutracker.org/forum/viewtopic.php?t=4038622

Добавлено через 4 минуты
Без булевого массива все работает (но я не уверен, как себя поведет прога на моем компе при большом количестве элементов - по понятным причинам 60к значений с клавиатуры забить сложно). Но на тестах выходит перебор по времени выполнения на этом же самом тесте из-за вдвое большего количества итераций цикла =\
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 04:57     Динамический массив с большим количеством элементов #43
Цитата Сообщение от Avazart Посмотреть сообщение
Вы хотите сказать что может быть иначе ?
я хочу сказать что в стандарте написано
3.9.1 Fundamental types
..........
6 Values of type bool are either true or false.[Note: there are no signed, unsigned, short, or long bool types or values. —end note ] As described below, bool values behave as integral types. Values of type bool participate in
integral promotions
где написано 0 1

правда дальше читаем
4.5 Integral promotions
...............
An rvalue of type bool can be converted to an rvalue of type int, with false becoming zero and true becoming one
но здесь то речь уже идет о преобразовании
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 05:01  [ТС]     Динамический массив с большим количеством элементов #44
Встретится комбинация [j][i]. Это была попытка уменьшить количества вхождений во внутренности if-a из-за двойного прохождения. Допустим есть удачная комбинация i=2;j=4. Без булева массива цикл войдет в if ещё и при i=4;j=2.
Вообщем вопрос можно оставить для теоретических исследований - алгоритм действительно
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
го... не подходит
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 05:06     Динамический массив с большим количеством элементов #45
Цитата Сообщение от luck Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
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;
             }
если я правильно понял логику
не проще написать так
C++
1
2
3
4
for(int i=0;i<num-1;i++)
  for(int j=i+1;j<num;j++)
          if (func(arr[i])==func(arr[j]))
                res++;
и нафиг никакой массив не нужен
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 05:10  [ТС]     Динамический массив с большим количеством элементов #46
Действительно, так намного лучше, странно, что я не додумался.
Но все равно по времени не прошло, там все намного проще оказалось.
Нужно переформулировать рекурсивное соотношение, оно сводится всего лишь к определнию четности-нечетности, так что подпрограмма не нужна. Но если бы рекурсивная формула была сложнее, то пришлось бы оставить как есть.
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 05:12     Динамический массив с большим количеством элементов #47
Цитата Сообщение от luck Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
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;
      }
}
количество единиц в двоичном представлении числа считает???
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 05:21  [ТС]     Динамический массив с большим количеством элементов #48
Нет. Вот что я пытаюсь решить.
http://codeforces.ru/problemset/problem/272/B

Добавлено через 4 минуты
Кажись я поспешил, не уверен, что эту рекурсию можно так быстро на условия if-a вместо подпрограммы разбить.
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 05:28     Динамический массив с большим количеством элементов #49
Цитата Сообщение от luck Посмотреть сообщение
Нет.
так это и получается количество единиц
вот так
C++
1
2
3
4
5
6
7
8
9
10
int fnc (int n)
{
 int k=0;
  do
  {
    if(n%2) 
       k++;
  }while(n/=2);
return k;
}
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
13.03.2013, 05:31     Динамический массив с большим количеством элементов #50
Куча глобальна в любом случае, а указатель может валяться и в стеке.
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 05:45  [ТС]     Динамический массив с большим количеством элементов #51
Вообщем не представляю что ещё можно придумать.
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
#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <string.h>
using namespace std;
unsigned long int func(unsigned long int);
int main()
{
    unsigned long int i,num,res = 0;
    cin>>num;
    unsigned long int *arr = new unsigned long int[num];
    for (i=0;i<num;i++)
      scanf("%d",&arr[i]);
    for(i=0;i<num-1;i++)
      for(unsigned long int j=i+1;j<num;j++)
          if ((arr[i]==arr[j]) or (func(arr[i])==func(arr[j])))
                    res++;
    printf("%d",res);
    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;
    }
}
Вот что вышло в результате. При 50к+ чисел на входных данных размером в районе 10^9 считает больше 2 секунд, что перебор. А как уменьшить, если уже проще некуда.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
13.03.2013, 05:50     Динамический массив с большим количеством элементов #52
Цитата Сообщение от luck Посмотреть сообщение
Нужно создать динамический массив (каждый элемент целое положительное число до 10^9), который по введенным данным создавал N элементов массива, где N может быть до 10^5.
390 кибибайт - это не много, мне однажды пришлось извращаться с массивом на 17 мебибайт.

Добавлено через 54 секунды
1 771 561 элементов по 10 байт штука.
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 06:03     Динамический массив с большим количеством элементов #53
Цитата Сообщение от luck Посмотреть сообщение
А как уменьшить, если уже проще некуда.
Я же тебе показал реализацию функции никакой рекурсии
можно еще убыстрить
выбрасываем ветвление
C++
1
2
3
4
5
6
7
8
9
unsigned int fnc (unsigned int n)
{
 int k=0;
  do
  {
    k+=%2;
  }while(n/=2);
return k;
}
выбрось long простого int хватит тебе нужно до 1 000 000 000 а int считает до 4 294 967 295
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 06:12  [ТС]     Динамический массив с большим количеством элементов #54
Вроде работает (сайт codeforces упал, на тестах прогнать не могу).
k+=%2; // тут компилятор вывел ошибку, заменил на k+=k%2;
А можно подробней, что означает n/=2 и почему это тот же алгоритм =\
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 06:24     Динамический массив с большим количеством элементов #55
Цитата Сообщение от luck Посмотреть сообщение
что означает n/=2
это тоже самое что n=n/2 (краткая запись)
Цитата Сообщение от luck Посмотреть сообщение
почему это тот же алгоритм =\
по шагам то пройди
если я изменю немного вторую формулу
f(0)=0;
f(2x)=f(x)+0;
f(2x+1)=f(x)+1;
то видно что это алгоритм перевода десятичного числа в двоичное путем деления на двойку
Цитата Сообщение от luck Посмотреть сообщение
k+=%2; // тут компилятор вывел ошибку, заменил на k+=k%2;
это я пропустил буковку
правильно писать
C++
1
k+=n%2;
что равносильно
C++
1
k=k+n%2
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 06:30  [ТС]     Динамический массив с большим количеством элементов #56
В любом случае, опять 25 - 11 тест завален по времени выполнения
Я правда не понял - а зачем в условии while писать выражение? В каком случае будет выход? Когда целочисленное деление n/2 приведет к 0? (то есть при n=1)
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 06:35     Динамический массив с большим количеством элементов #57
вообще то там написано
ограничение по памяти на тест:256 мегабайт
он и по этому параметру непроходит
данные то как вводятся???
файл али что?
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 06:39  [ТС]     Динамический массив с большим количеством элементов #58
Почему не проходит? массив занимает 4 мб, остальное мелочи, по сравнению с ним.
Данные вводятся с клавиатуры (в теории), но у них там какая то система автоматического тестирования, имитирует ввод с клавы.
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
13.03.2013, 08:34     Динамический массив с большим количеством элементов #59
Цитата Сообщение от luck Посмотреть сообщение
массив занимает 4 мб,
пардон умножил неправильно
здесь есть другой путь массив на 32 инта
сейчас обдумаю напишу

Добавлено через 1 час 41 минуту
короче задача решается вообще без выделения памяти
достаточно вспомнить комбинаторику(я целый час вспоминал)
количество комбинаций
n*(n-1);
а количество пар
n*(n-1)/2;

выделяем массив на 32 элемента в него будем заносить количество чисел сумма единиц которых равна номеру элемента массива

потом подсчитаем сумму количество пар в каждом элементе массива
в общем вот код
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
#include <iostream>
 
using namespace std;
unsigned int func(unsigned int);
 
int main()
{
    unsigned long long int res = 0;
    unsigned long long int arr[32]={0};
    unsigned int n,k=0;
    cin>>n;
 
    for (int i=0;i<n;i++)
    {
             cin>>k;
      arr[func(k)]++; 
    
    }
    for (int i=0;i<32;i++)
           res+=(arr[i]*(arr[i]-1))/2;
    cout<<res;
    return 0;
}
 
unsigned int func(unsigned int n1)
{
unsigned int k=0;
  do
  {
    k+=n1%2;
  }while(n1/=2);
return k;
}
проверил до 12 дальше лень
убыстрение
нет выделения памяти
функция вызывается 100000 раз а не 100000*99000
нет ветвлений

Добавлено через 5 минут
проверить не смог, лень регистрироваться
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.03.2013, 09:38     Динамический массив с большим количеством элементов
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
13.03.2013, 09:38     Динамический массив с большим количеством элементов #60
А чаще всего мне было нужно более 2-х гигбибай (289 000 000 элементов по 10 байт штука). Вот это уже должно быть разреженным. Малышь же в 1 771 561 элементов по 10 байт был статическим.
Yandex
Объявления
13.03.2013, 09:38     Динамический массив с большим количеством элементов
Ответ Создать тему
Опции темы

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