[C++] průnik množin

[OgyDoggy]

Zdravím

potřeboval bych se zeptat zkušených programátorů v C++, co mám použít pro zpracování úkolu na téma průniku číselných množin. Tyto čísla jsou uloženy ve dvou souborech, majících velikost zhruba 10MB) a já bych se chtěl zeptat, jaký je nejlepší způsob pro jejich porovnávání/třídění. Vyděl bych to v načtení souborů, jejich seřazení od nejmenšího po největší, poté odstranění duplicit a následně nějakým způsobem porovnávat hodnoty jedné množiny s druhou a případné hodnoty zapsat do souboru. Není nějaké elegantnější/rychlejší řešení? Nechci aby mi tady někdo psal nějaký kod, chci si to všechno udělat sám, jen žádám o popostrčení.

Děkuji

[zADo]

pokud jde jenom o porovnani mnoziny A proti mnozine B, tak je zbytecne to tridit a odstranovat duplicity, protoze IMHO musis porovnat kazdy clen A s kazdym clenem B a je pritom jedno, jestli budou prvky usporadane, nebo duplicitni.Zalezi na zadani, co s tim delat, ale PHP i .NET maji vestavene funkce pro operace s poli, takze jestli jde o to napsat to same v C++ ?

[OgyDoggy]

porovnavat kazdy s kazdym je nesmysl, to by trvalo moc dlouho a primo v zadani mam, ze se to takhle delat nema

ucim se c++ takže jo, je to třeba psát v c++

[MiliNess]

V STL je už hotová funkce set_intersection().
Popis použití + popis implementace je zde: http://www.cplusplus.com/reference/algo ... ersection/
Takže obsah souborů nacpat do dvou vektorů, použít set_intersection a výsledek nechat uložit třeba do třetího vektoru.
Jako v jiných oblastech platí i v programování "proč vymýšlet něco, co už bylo vymyšleno".
Pak se můžete soustředit na jiné problémy v projektu.

[kohutisko]

ides na to spravne. zaklad je usporiadat si obe mnoziny, co je casova zlozitost O(n.log(n))

spravis si 2 ukazovatele, jeden do jednej mnoziny, druhy do druhej. oba nastavis na zaciatok.

nasledne: ak oba ukazovatele ukazuju na rovnake cislo, tak cislo hodis do vysledku a posunies oba ukazovatele o jedno miesto. ak ukazuju na rozne cisla, tak posunies o 1 ten, ktory ukazuje na mensie cislo. toto ma casovu zlozitost O(n)

tento postup ma (ako to tak teraz v hlave debugujem) vyhodu, ze vo vysledku budu aj tie duplicitne cisla (cize prienik {2,2,3} a {2,2,2} bude {2,2})

ak ich tam nechces, tak si ich hned po utriedeni odstran. opat v case O(n)

cize suma sumarom to cele bezi v O(n.log(n)), ziadne 'kazdy s kazdym' nie je treba.

[IgnorStoupa]

Hmmm, pokud je jasne, ze nejsou duplicity v jednom souboru, tak spojit, radix a duplicity jsou prunik. S duplicitami holt radix na oba dva soubory a srovnavat....

[suk]

Jako v jiných oblastech platí i v programování "proč vymýšlet něco, co už bylo vymyšleno".

A hello world, vsechny sorty, vsechny.... napsal uz nekdo, tak proc rovnou pro zacatek s programovanim nevyrobit vlastni kompilator pro vlastni jazyk, ve kterym si napisu operacni system....
Navic to ma jako domaci ukol takze STL mu sice pomuze ale programovat se tim nenauci - pouze psat kod.
Igor: prej ma odstranit duplicity (jinak velice krasny reseni, ktery by me snad ani nenapadlo )

[OgyDoggy]

děkuji to mi prozatím stačí

[Koblih]

Dalsi moznost je merge sort na prvni pole a pak brat jednotlive polozky z druheho pole a hledat je binarnim vyhledavanim pulenim intervalu v prvnim poli. To taky odstrani duplicity

[OgyDoggy]

zkouším to dělat pomocí toho merge sortu, ale z nějakého důvodu mi to vždycky při seřazování spadne a přestane pracovat zkoušel jsem i quick sort, ale u toho to taky padá napoví mi někdo proč?

Kód: Vybrat vše

#include <iostream>
#include <fstream>


using namespace std;


const unsigned int N = 1000000;
int prvniPole[N];
int druhePole[N];

/* ----------------------------------------------------merge sort---------------------------!
int a[N];
void merge(int,int,int);
void merge_sort(int low,int high)
{
int mid;
if(low<high)
{
  mid=(low+high)/2;
  merge_sort(low,mid);
  merge_sort(mid+1,high);
  merge(low,mid,high);
}
}
void merge(int low,int mid,int high)
{
int h,i,j,b[N],k;
h=low;
i=low;
j=mid+1;

while((h<=mid)&&(j<=high))
{
  if(a[h]<=a[j])
  {
   b[i]=a[h];
   h++;
  }
  else
  {
   b[i]=a[j];
   j++;
  }
  i++;
}
if(h>mid)
{
  for(k=j;k<=high;k++)
  {
   b[i]=a[k];
   i++;
  }
}
else
{
  for(k=h;k<=mid;k++)
  {
   b[i]=a[k];
   i++;
  }
}
for(k=low;k<=high;k++) a[k]=b[k];
}
*/

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

     if (left < j){
            quickSort(arr, left, j);
     }
     if (i < right){
            quickSort(arr, i, right);
     }
}

//------------------------------------maximum-----------------|
int max(int *pole, int pocet_prvku){
   int max, i;

   max=0;
      for(i=0;i<pocet_prvku;i++){
         if(pole[i]>max){
            max=pole[i];
         }
      }

   return(max);
}
//-----------------------------------minimum-----------------!
int min(int *pole, int pocet_prvku){
   int min, i;
   min = N+1;

   for(i=0; i<pocet_prvku; i++){
      if(pole[i]<min){
         min = pole[i];
      }
   }
   return(min);
}

//----------------------------------main----------------------!
int main(int argc, char *argv[]){
   if(argc != 4){
      cerr << "Chyba zadani parametru!" << endl;
      return -1;
   }

   cout << "prvni argument je jmeno programu " << argv[0] << endl << endl;

   ifstream prvni;
      prvni.open(argv[1]);
   ifstream druhy;
      druhy.open(argv[2]);
   ofstream vystup;
      vystup.open(argv[3]);

   cout << "druhy argument: jmeno souboru1 = " << argv[1] << endl << endl;
   cout << "treti argument: jmeno souboru2 = " << argv[2] << endl << endl;
   cout << "ctvrty argument: jmeno vystupniho souboru = " << argv[3] << endl << endl;


   cout << "prvni soubor" << endl;
   for(int i=0; i < N; i++){
      prvni >> prvniPole[i];
   }
   cout << "--------" << endl << endl;
   
   cout << "druhy soubor" << endl;
   for(int j=0; j < N; j++){
      druhy >> druhePole[j];
   }
   cout << "--------" << endl << endl;

   int max_prvek_pole1 = max(prvniPole, N);

   cout << "Maximum pole 1. = " << max_prvek_pole1 << endl << endl;

   int max_prvek_pole2 = max(druhePole, N);

   cout << "Maximum pole 2. = " << max_prvek_pole2 << endl << endl;

   int min_prvek_pole1 = min(prvniPole, N);

   cout << "Minimum pole 1. = " << min_prvek_pole1 << endl << endl;

   int min_prvek_pole2 = min(druhePole, N);

   cout << "Minimum pole 2. = " << min_prvek_pole2 << endl << endl;


   quickSort(prvniPole,min_prvek_pole1,max_prvek_pole1);


   
   //merge_sort(1,max_prvek_pole1);

   prvni.close();
   druhy.close();
   vystup.close();
   
   int konec;
   cin >> konec;
   return 0;
}

tohle je můj prozatimní kod. nejsem si jisty, ale mám dojem, že je to nějak spojené s pamětí

[pucmeloudek]

co se quicksortu tyce, proc davas jako vstupni prvky minimum a maximum toho pole?
tam by preci mel byt index prvniho a posledniho prvku a ne hodnota minima a maxima, ktery tam mas ty:
quickSort(prvniPole,0,N-1);

-- 5. 5. 2010 20:11 --

p.s. kdyby ti nekdo radil, ze chyba je v tom, ze misto

if (i <= j)

tam mas dat

if ((i <= j) == true)

tak mu to nesezer!

[OgyDoggy]

dík to jsem si neuvědomil

ale mám další problém, normálně se mi to setřídí, ale z nějakého důvodu mi to nechce udělat onen průnik. když jsem si dal diagnostický výstup, tak jsem přišel na to, že to bere indexy jenom kolem středu setříděného pole, ale při výstupu hodnot, dává jakés takés hodnoty, které jsou snad dobré. myslel jsem si, že jsem udělal fungující funkci na vyhledání prvku v jednom poli z druhého, je to varianta hledáním půlením intervalu, ale pro hodnoty setříděného pole a nesetříděného pole.

dávám tu onu funkci, třeba někdo na něco přijde

Kód: Vybrat vše

int hledejPrvek(int serazenePole[], int prvni, int posledni, int neserazenePole[]){
   int stred = (prvni + posledni) / 2;
   printf("\njsem v hledani\n\n");
   while(prvni <= posledni){
      printf("\njsem v whilu\n\n");
      for(int i=0; i < posledni; i++){
         if(neserazenePole[i] > serazenePole[stred]){
            prvni = stred + 1;
            printf("\njsem v prave vetvy\n\n");
            cout << i << " " << prvni << " " << posledni << " " << serazenePole[i] << " " << neserazenePole[i];//diagnostika
         } else if (neserazenePole[i] < serazenePole[stred]){
            posledni = stred - 1;
            printf("\njsem v leve vetvy\n\n");
            cout << i << " " << posledni << " " << prvni << " " << serazenePole[i] << " " << neserazenePole[i];//diagnostika
         } else {
            return stred >> vystupniPole[i];
            cout << stred << " ";
         }
         cout << " konec foru " << stred << endl;
      }
      return -(prvni + 1);
   }
}


a ještě celý projekt, kdybych měl náhodou nějakou chybu tam

Kód: Vybrat vše

#include <iostream>
#include <fstream>


using namespace std;


const unsigned int N = 1000000;
int prvniPole[N];
int druhePole[N];
int vystupniPole[N];

void setridPole(int pole[], int vlevo, int vpravo) {
      int i = vlevo, j = vpravo;
      int tmp;
      int stred = pole[(vlevo + vpravo) / 2];

      while (i <= j) {
        while (pole[i] < stred){
                  i++;
        }
        while (pole[j] > stred){
                  j--;
        }
            if (i <= j) {
                  tmp = pole[i];
                  pole[i] = pole[j];
                  pole[j] = tmp;
                  i++;
                  j--;
            }
      };

     if (vlevo < j){
            setridPole(pole, vlevo, j);
     }
     if (i < vpravo){
            setridPole(pole, i, vpravo);
     }
}

//------------------------------------maximum-----------------|
int max(int *pole, int pocet_prvku){
   int max = 0;

      for(int i = 0; i < pocet_prvku; i++){
         if(pole[i] > max){
            max = pole[i];
         }
      }

   return (max);
}
//-----------------------------------minimum-----------------!
int min(int *pole, int pocet_prvku){
   int min = N;

   for(int i = 0; i < pocet_prvku; i++){
      if(pole[i] < min){
         min = pole[i];
      }
   }
   return (min);
}

//----------------------------------------------hledani prvku druheho pole v prvnim------!
int hledejPrvek(int serazenePole[], int prvni, int posledni, int neserazenePole[]){
   int stred = (prvni + posledni) / 2;
   printf("\njsem v hledani\n\n");
   while(prvni <= posledni){
      printf("\njsem v whilu\n\n");
      for(int i=0; i < posledni; i++){
         if(neserazenePole[i] > serazenePole[stred]){
            prvni = stred + 1;
            printf("\njsem v prave vetvy\n\n");
            cout << i << " " << prvni << " " << posledni << " " << serazenePole[i] << " " << neserazenePole[i];//diagnostika
         } else if (neserazenePole[i] < serazenePole[stred]){
            posledni = stred - 1;
            printf("\njsem v leve vetvy\n\n");
            cout << i << " " << posledni << " " << prvni << " " << serazenePole[i] << " " << neserazenePole[i];//diagnostika
         } else {
            return stred >> vystupniPole[i];
            cout << stred << " ";
         }
         cout << " konec foru " << stred << endl;
      }
      return -(prvni + 1);
   }
}
//----------------------------------main----------------------!
int main(int argc, char *argv[]){
   system("cls");

   if(argc != 4){
      cerr << "\nChyba zadani parametru!" << endl;
      return -1;
   }

   cout << "\nprvni argument je jmeno programu " << argv[0] << endl;

   ifstream prvni;
      prvni.open(argv[1]);
   ifstream druhy;
      druhy.open(argv[2]);
   ofstream vystup;
      vystup.open(argv[3]);

   cout << "druhy argument: jmeno souboru1 = " << argv[1] << endl;
   cout << "treti argument: jmeno souboru2 = " << argv[2] << endl;
   cout << "ctvrty argument: jmeno vystupniho souboru = " << argv[3] << endl << endl;

//-------------------------------------------------uložení do paměti-------!
   cout << "prvni soubor" << endl;
   for(int i=0; i < N; i++){
      prvni >> prvniPole[i];
   }
   cout << "--------" << endl << endl;
   cout << "druhy soubor" << endl;
   for(int j=0; j < N; j++){
      druhy >> druhePole[j];
   }
   cout << "--------" << endl << endl;
//--------------------------------------------------maxima-------------!
   int max_prvek_pole1 = max(prvniPole, N);
   cout << "Maximum pole 1. = " << max_prvek_pole1 << endl;
   int max_prvek_pole2 = max(druhePole, N);
   cout << "Maximum pole 2. = " << max_prvek_pole2 << endl;
//--------------------------------------------------minima-------------!
   int min_prvek_pole1 = min(prvniPole, N);
   cout << "Minimum pole 1. = " << min_prvek_pole1 << endl;
   int min_prvek_pole2 = min(druhePole, N);
   cout << "Minimum pole 2. = " << min_prvek_pole2 << endl << endl;
//-------------------------------------------------setrideni prvniho pole----!
   cout << "tridim" << endl;
   setridPole(prvniPole,0,N);
   for(int i=0; i<10; i++){
      cout << prvniPole[i] << " ";
   }
   cout << "\nsetrideno" << endl;
//-------------------------------------------------vyhledavani prvku----!
   cout << "\nhledam prvky" << endl;
   hledejPrvek(prvniPole,0,N,druhePole);
   cout << "\ndokonceno hledani" << endl;
//------------------------------------------------zapis a tisk souboru ---!
   cout << "\nprunik cisel" << endl;
   for(int i=0; i < max(vystupniPole,N); i++){
      cout << vystupniPole[i] << " ";
      vystup << vystupniPole[i];
   }
   cout << "\nfinite" << endl;
   
   prvni.close();
   druhy.close();
   vystup.close();
   
   return 0;
}

štábní kultura kodu je hrozná, ale vyznat se v tom teoreticky dá. zajímalo by mě, proč se nedostanu vůbec do posledního else v té hledací funkci? taky jak zrychlit načítání těch souborů a jakékoliv připomínky ke kodu

[pucmeloudek]

Co takhle zkusit si vzpomenout na pojem dekompozice a aplikovat jej na problem? tj. nejdriv naprogramovat hledani JEDNOHO prvku v serazenem poli a pote teprv dalsi kus kodu, ktery bude toto hledani postupne volat pro jednotlive prvky neserazeneho pole? tohle cos predved je hodne velkej brajgl, kterymu ani za mak nerozumim

[OgyDoggy]

mám to upravené a teď i zjednodušené, funguje to, ale nepřepočítává se mi z nějakého důvodu hodnota proměnné stred, i když ji měním

Kód: Vybrat vše

#include <iostream>
#include <fstream>

using namespace std;

const unsigned int N = 10;
int* prvniPole = new int[N];
int* druhePole = new int[N];
int* vystupniPole = new int[N];

int hledejPrvek(int serazenePole[], int prvni, int posledni, int neserazenePole[]){
   int stred = (prvni + posledni) / 2;

   while(prvni <= posledni){
      for(int i=0; i < N; i++){
         if(serazenePole[i] == neserazenePole[stred]){
            cout << serazenePole[i] << " = " << neserazenePole[stred] << "\n";

         } else if(serazenePole[i] < neserazenePole[stred]) {
            cout << serazenePole[i] << " mensi " << neserazenePole[stred] << "\n";
            posledni = stred - 1;

         } else if(serazenePole[i] > neserazenePole[stred]) {
            cout << serazenePole[i] << " vetsi " << neserazenePole[stred] << "\n";
            prvni = stred + 1;
         }
      }
   }
   return 0;
}

int main(){
   int prvniPole[] = {1,2,33,4,5,6,7087,8,9,10};
   int druhePole[] = {9,3,2,26,5,8,1,10,66,6};

   printf("\nprvni pole\n");
   for(int i = 0; i < N; i++){
      cout << i << " " << prvniPole[i] << "\n";
   }
   printf("\ndruhe pole\n");
   for(int i = 0; i < N; i++){
      cout << i << " " << druhePole[i] << "\n";
   }

   hledejPrvek(prvniPole,0,N,druhePole);

   printf("\n");
   system("pause");
   return 0;
}

[Nargon]

A muzes mi rici kde tu promenou stred menis? jak ja na to koukam, tak ji nikde nemenis.
Funkci hledejPrvek zavolas jen jednou.
V ni hned na zacatku tu promenou stred nejak nastavis, ale v tom cyklu ji uz nikde nemenis.