С++: Уменьшение памяти в 8 раз

[pika]

Всем добрый вечер!

Возникла следующая проблема, нужно написать программу - Решето Эратосфена (сколько простых чисел меньших данного) с некоторыми ограничениями.

Вводится число 2<=N<=200000000
Лимит памяти 30mb
Cобственно данная программа занимает ~190-200mb, при N=200000000;
нужно уменьшить размер массива в 8 раз, я понимаю, что нужно обращаться к битам, но не могу реализовать.
На форуме пишу первый раз, поэтому сильно не ругайте.
Спасибо!

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;

int main()
{
int n;
cin>>n;
char* S;
S=(char*)malloc(n* sizeof(bool));
int count;
int i,j;
float sqrt_n = sqrt(n)+1;
memset(S,false,n);
for(i = 2 ; i < sqrt_n ; ++i)
  if(S[i] == 0)
    for(j = i*i ; j < n ; j+=i)
      S[j]=1;
    count=0;
  for(i = 2 ; i < n ; ++i)
    if(S[i] == 0)
      count++;
    if(count > 0) cout<<count; else cout<<'1';
  free(S);
  return 0;
  
}

[Alexu007]

Работать с битами несложно. Для этого достаточно операторов "и" и "или", в си это "&" и "|", если не ошибаюсь. Тип char восьмибитовый, следовательно в нём можно хранить 8 единиц или нулей, и соответственно сократить используемую память в 8 раз.

Чтобы включить произвольный бит, допустим 4-й, нужна операция "или": Х | bx00010000, после этого в четвёром бите будет 1 независимо от того, что там было до того, ноль или единица. Другие биты не изменяются.

Чтобы выключить произвольный бит, допустим 4-й, нужна операция "и": Х & bx11101111, после этого в четвёром бите будет 0 независимо от того, что там было до того, ноль или единица. Другие биты не изменяются.

Чтобы прочитать значение произвольного (в нашем примере - четвёртого) бита, нужно (при необходимости) скопировать значение в другую переменную, т.к. мы его изменим, обнулить "ненужные" биты с помощью оператора "и": Х & bx00010000, теперь если в переменной Х ноль - следовательно 4 бит был равен 0, если число больше 0 - единице.

Чтобы работать допустим с 30-м битом, нужно вычислить смещение - число первых восьмибайтовых чисел: 30 / 8 = 3, и остаток от деления 30 % 8 = 6, это позиция где нужно включить (выключить, проверить) соответствующий бит. Следовательно первые 3 числа X[0], X[1] и X[2] пропускаем, в четвёртом X[3] проделываем нужные нам логические операции с 6-м битом.

[nestoklon]

pika в сообщении #540319 писал(а):

я понимаю, что нужно обращаться к битам, но не могу реализовать

Всё уже реализовано. http://www.cplusplus.com/reference/stl/bitset/

Хотя, внимательно прочитал документацию сам. Совсем халявы не будет. Размер надо задавать во время компиляции. Так что надо или разбивать на куски разумного размера (завести битсет на пару килобайт и потом использовать массив из таких) или пользоваться http://www.boost.org/doc/libs/1_42_0/li ... itset.html

Ну и тут http://stackoverflow.com/questions/2633 ... -bit-array приведена заготовка низкоуровневого решения, когда всё делается самостоятельно ручками.

[venco]

nestoklon в сообщении #540367 писал(а):

pika в сообщении #540319 писал(а):

я понимаю, что нужно обращаться к битам, но не могу реализовать

Всё уже реализовано. http://www.cplusplus.com/reference/stl/bitset/

Хотя, внимательно прочитал документацию сам. Совсем халявы не будет.

Будет. std::vector<bool> хранит элементы в битах, и с ним можно работать как с обычным вектором.

[nestoklon]

venco в сообщении #540368 писал(а):

std::vector<bool> хранит элементы в битах

Точно. Я помнил о нём, но смутно. Вместо него сходу нашёл bitset и решил, что меня подвела память.

[pika]

Всем спасибо, разобрался.

[Alexu007]

Я тоже разобрался. И без использования векторов, а напрямую работая с битами.

Решил тремя способами: с массивами int, char и char/8. Кстати при попытке создания массива char[2 000 000] вылетает ошибка "переполнение стека" (для int - ещё раньше) и задача решается только с битами - результат 148933 простых числа - интересно, правильно? А при 20 000 000 не помогают уже и биты. Массив char[20 000 000 / 8] не создается. Интересно, как выкручивался автор темы с максимальным заявленным размером в 200 000 000?

.....

Sorry, с динамическими массивами дело пошло получше, int *X = new int [20 000 000] работает, но 200 000 000 и динимическое выделение не переваривает. а прога с битами подсчитала - получилось 11 078 937.

[pika]

Если кому-то интересно, то наткнулся на хорошую статью, по решету.

http://e-maxx.ru/algo/eratosthenes_sieve

[nestoklon]

Alexu007 в сообщении #540860 писал(а):

Интересно, как выкручивался автор темы с максимальным заявленным размером в 200 000 000?

Динамически-то небось поболе создать можно -- там пока вся память не закончится можно выделять (под виндой правда до трёх гигов только на приложение). Главное чтоб не слишком большими кусками -- несколькими кусками можно больше выделить чем одним.

[Joker_vD]

nestoklon
Все равно, при неудачном раскладе нужно два массива — если стек посреди памяти валяется.

[Alexu007]

Используется синтаксис C++

void __fastcall TForm1::Button1Click(TObject *Sender)
{
//алгоритм "решето Эратосфена"
//третий способ


char Mov[8] = {0x01, 0x02, 0x04, 0x08,
               0x10, 0x20, 0x40, 0x80};

const int N = 999999999;
const int N1 = N / 8 + 1;

int Cx;

char *BIT = new char[N1];
char X;


//обнуляем вновь созданный массив
for(int i = 0; i < N1; i++) {BIT[i] = 0;}

//принудительно делаем "непростыми" 0 и 1
BIT[0] = BIT[0] | Mov[0];
BIT[0] = BIT[0] | Mov[1];

//собственно алгоритм
for(int i = 0; i < N; i++)
  {
  X = BIT[i / 8] & Mov[i % 8];
  if (X == 0)
    {
     for(int j = i * 2; j < N; j += i)
      {
      BIT[j / 8] = BIT[j / 8] | Mov[j % 8];
      }
    }
  }


//последнее простое число
int Y = 0;
//счётчик простых чисел
Cx = 0;

//считаем результат
for(int i = 0; i < N; i++)
  {
  X = BIT[i / 8] & Mov[i % 8];

  if (X == 0) {Cx++; if(i > (N-100)) Y = i;}
  }

//вывод на экран
Label2->Caption = Y;
Label3->Caption = Cx;

delete BIT;
return;
}
//---------------------------------------------------------------------------

Алгоритм "с битами" ненамного сложнее алгоритма с "char", но требует в 8 раз меньше памяти. Быстродействие приблизительно одинаковое, возможно из-за того, что при "char" перелопачивается больший объём памяти. Работает при N = 999 999 999, дальше не пробовал. Найденное ближайшее к N простое число - 999 999 761.

nestoklon в сообщении #541380 писал(а):

Alexu007 в сообщении #540860 писал(а):

Интересно, как выкручивался автор темы с максимальным заявленным размером в 200 000 000?

Динамически-то небось поболе создать можно -- там пока вся память не закончится можно выделять (под виндой правда до трёх гигов только на приложение). Главное чтоб не слишком большими кусками -- несколькими кусками можно больше выделить чем одним.

C++ builder отказывается создавать динамический массив int размером 200 млн. Табличка с ошибкой выскакивает при запуске программы. Может ограничение в билдере, может в винде 7.

[nestoklon]

Alexu007 в сообщении #541421 писал(а):

ненамного сложнее алгоритма с "char"

Вообще говоря, насколько мне известно, нет никакой гарантии что char занимает 8 бит. А не те же 32 что и int.

Alexu007 в сообщении #541421 писал(а):

C++ builder отказывается создавать динамический массив int размером 200 млн.

А два массива по 100млн? А четыре по 50?

[Alexu007]

Проверил:

Оказывается, чуток слукавил: динамический массив создаётся до 208 млн. int, на 209-м миллионе выдаёт ошибку при работе программы (не при компиляции). Два динамических массива int создаются с размером 120 млн. каждый, при 2х130 возникает та же ошибка, точнее не искал. То есть общий размер больше, но не в 2 раза.

sizeof(char) = 1, sizeof(int) = 4. Следовательно char всё-таки занимает в 4 раза меньше места, чем int.

С массивами полное соответствие: 832 млн. char работает, 836 - нет. Можно найти простое число до 8х832 млн. = 6 656 млн., далее вступают в силу системные ограничения.

[nestoklon]

Да, и правда char 1 байт.

У меня malloc ом выделяет без проблем до трёх гигов. При том что в ноуте их всего три. Правда, при попытке их использовать начинает судорожно перекидывать память и в процессе сливания системы в свап виснет. Ну, может не совсем виснет, но я не дождался. Windows7-x64, последний интеловский компилятор.

[Zealint]

На самом деле в случае с char может получиться ерунда. Вообще-то он однобайтовый. Но он на то и символьный, что может однажды стать двухбайтовым, как int из 2 байт однажды стал 4. Поэтому лучше выделять память для битового поля такими кусками, которые заведомо будут одного и того же размера (едва ли когда-нибудь long с языке C станет больше 4 байт). Или явно использовать sizeof во всей программе с любым типом, выделять памяти нужно

(N+sizeof(тип)*8-1) / sizeof(тип) / 8

А потом делением на sizeof(тип)*8 и взятием остатка вырезать нужный битик.

А ещё для решения указанной задачи можно забить на решето и решать по-другому.