Wydajniejsze rozwiązanie problemu zliczania w przedziałach


(matiit) #1

n - maksymalny przedział (0-n)

m - maksymalna liczba przedziałów

Dalej są podawane przedziały.

sito oczywiście znajduje liczby pierwsze

Niestety nie jest to zbyt wydajne, myślę że problemem jest to zliczanie w przedziałach, bo sito jest wydajne.

Przykładowe działanie:

10 5

0 1

1 3

2 7

6 9

8 10

0

2

4

1

0

Kod: http://codepad.org/x8ugiph9

Proszę o jakieś naprowadzenie na wydajniejsze rozwiązanie problemu.


(Marcin 110) #2

Jeśli działanie sita zwracałoby vector/tablicę liczb pierwszych, a nie maskę mógłbyś wyznaczyć ich ilość wyszukiwaniem binarnym, np. za pomocą:

ilosc = distance(upper_bound(b), lower_bound(a));

(matiit) #3

Tzn musiałbym w funkcji sito przekopiować jedynki do tablicy np. takiej? tab[5] = {2,3,5,7,11}?

Czy to nie spowolniłoby bardzo sita?


(Marcin 110) #4

Poprawiłem kod.

Będziesz musiał przejść raz po wszystkich liczbach z sita, ale nie będziesz musiał ich liczyć w każdym przedziale, zatem kod powinien być szybszy. Samo sito też dałoby się zoptymalizować.


(matiit) #5

Jak powinna wyglądać taka tablica?

Trochę nie rozumiem.

Zrobiłem te liczby pierwsze na wektorze:

http://codepad.org/1oDTdZba

Czy to jest ok?


(Marcin 110) #6
#include 

#include 

#include 

#include 


using namespace std;


void sito(int dokad, bool *tab, vector &v)

{

  tab[0] = 0;

  tab[1] = 0;

  for(int i = 2; i * i < dokad; ++i)

      for(int j = 2; j * i < dokad; ++j)

        if(tab[i] == 1) tab[i * j] = 0;

  for (int i = 2; i < dokad; ++i)

    if (tab[i])

      v.push_back(i);

}


int main()

{

  const int MAX = 1000000;

  bool pierwsze[MAX + 1];

  vector vpierwsze;


  for (int i = 0; i < MAX; ++i)

    pierwsze[i] = 1;


  int przedzialy[MAX + 1];

  int n, m;


  scanf("%d %d", &n, &m);

  for(int i = 0; i < 2 * m; ++i)

    scanf("%d", &przedzialy[i]);

  sito(n + 1, pierwsze, vpierwsze);


  int ile_juz = 0;

  for(int i = 0; i < 2 * m; i += 2)

    {

      ile_juz = distance(lower_bound(vpierwsze.begin(), vpierwsze.end(), przedzialy[i]),

                         upper_bound(vpierwsze.begin(), vpierwsze.end(), przedzialy[i + 1])

                         );

      // for(int j = przedzialy[i]; j <= przedzialy[i + 1]; ++j)

      // if(pierwsze[j] == 1)

      // ++ile_juz;

      printf("%d\n", ile_juz);

    }

}

Chodziło mi o coś takiego. Ilość liczb pierwszych we wszystkich przedziałach wyznaczasz w czasie O(n*log(k)), gdzie n to ilość przedziałów, a k ilość wyznaczonych liczb pierwszych zamiast O(n*k).


(matiit) #7

Dziękuję.

Sprawdziłem w referencjach jak działają *_bound i już wszystko rozumiem. Wielkie dzięki, w ogóle nie znałem tych funkcji.


(Marcin 110) #8
#include 

#include 

#include 

#include 

#include 

#include 


using namespace std;


typedef vector > arr;


const int ile = 6; /* \ */

const int iloczyn = 2* 3* 5* 7* 11* 13 ; /* > zalezne parametry */

const int pt[] = { 2, 3, 5, 7, 11, 13}; /* / nalezy dobrac do rozmiaru */

                                            /* cache'u w procesorze */


void elim (bool v[], const arr::iterator& start, const arr::iterator& end)

{

  int j;

  for (arr::iterator it = start; it != end; ++it)

    {

      if (it->second >= iloczyn)

        it->second -= iloczyn;

      else

        {

          for (j = it->second; j < iloczyn; j += it->first)

            v[j] = false;

          it->second = j - iloczyn;

        }

    }

}


void sito (bool v[], arr& pierwsze, int d)

{

  int j, k;

  for (int i = 1; i < iloczyn; ++i)

    if (v[i])

      {

        k = d + i;

        for (j = i + k; j < iloczyn; j += k)

          v[j] = false;

        pierwsze.push_back(make_pair(k, j - iloczyn));

      }

}


#define przepisz(skad, dokad) memcpy(dokad, skad, iloczyn)

// void przepisz(bool skad[], bool dokad[]) {

// for (int i = 0; i < iloczyn; ++i)

// dokad[i] = skad[i];

// }


int main()

{

  int a = 1, b, sqrtb, t, d = 0, n, l, p;

  arr pierwsze, przedzialy;

  vector wszystkiep;

  bool wzorzec[iloczyn], temp[iloczyn];


  for (int i = 0; i < iloczyn; ++i)

    wzorzec[i] = true;


  cin >> b >> n;

  wszystkiep.reserve(1.25506 * b / log(b)); // gorne ograniczenie funkcji pi(n)

  for (int i = 0; i < n; ++i)

    {

      cin >> l;

      cin >> p;

      przedzialy.push_back(make_pair(l, p));

    }

  for (int i = 0; i < ile; ++i)

    pierwsze.push_back(make_pair(pt[i], 0));


  elim(wzorzec, pierwsze.begin(), pierwsze.end());

  przepisz(wzorzec, temp);

  temp[1] = false;

  sito(temp, pierwsze, 0);

  sqrtb = (int) sqrt((double) b);

  t = sqrtb / iloczyn;

  sqrtb = (t + 1) * iloczyn; // zaokraglenie pierwastka do konca przedzialu


  for (int i = 0; i < t; ++i)

    {

      d += iloczyn;

      przepisz(wzorzec, temp);

      elim(temp, pierwsze.begin() + ile, pierwsze.end());

      sito(temp, pierwsze, d);

    }

  if (a < sqrtb)

    {

      for (arr::const_iterator it = pierwsze.begin(); it != pierwsze.end(); ++it)

        if (it->first <= b && it->first >= a)

          wszystkiep.push_back(it->first); // it->first jest pierwsze

    }


  int ml, ms;

  d = sqrtb;

  while (b > d)

    {

      ms = ml = 0;

      przepisz(wzorzec, temp);

      elim(temp, pierwsze.begin() + ile, pierwsze.end());

      if (a > d || b < d + iloczyn)

        {

          for (int i = 0; i < iloczyn; ++i)

            if (temp[i])

              wszystkiep.push_back(d + i); //d + i jest pierwsze

        }

      else

        {

          for (int i = 0; i < iloczyn; ++i)

            if (temp[i])

              wszystkiep.push_back(d + i); //d + i jest pierwsze

        }

      d += iloczyn;

    }


  for(int i = 0; i < n; ++i)

    cout << distance(lower_bound(wszystkiep.begin(), wszystkiep.end(), przedzialy[i].first),

                     upper_bound(wszystkiep.begin(), wszystkiep.end(), przedzialy[i].second)

                     )

         << endl;

  return 0;

}

Jeśli Cię to jeszcze interesuje, to jest tu działający program z zoptymalizowanym sitem (miałem podobny i przerobiłem). Problemem jest tutaj przechowywanie wszystkich liczb pierwszych w wektorze wszystkiep (szybko braknie pamięci). Można w locie dodawać do przedziałów bez spamiętywania wszystkich liczb pierwszych, ale do tego trzeba jakiejś szybkiej struktury (może jakieś drzewa przedziałowe?).

EDIT:

Poprawka, wziąłem zły logarytm


(matiit) #9

Hm, fajne (;

Co do szybszej struktury to nie mam pojęcia...