Sjednocení množin v C++

C++, C#, Visual Basic, Delphi, Perl a ostatní

Moderátor: Moderátoři Živě.cz

Odeslat příspěvekod nahodnakolemjdouci 20. 4. 2010 16:33

Mám dva txt soubory, každý obsahuje milion čísel neuspořádaných, může obsahovat duplicity. Mám za úkol provést sjednocení do jednoho txt vzestupně a zároveň odstranit duplicity. Můžete mi někdo poradit jak na to?
Nejdříve si asi budu muset seřadit obě množiny vzestupně? To ale netuším jak.
A pak je asi nejlepší použít mergesort, který už pak asi ty duplicity odstraní, nebo ne?

Případně mě ještě napadl quickshort, ale ten merge bude lepší, hm?

Jinak v programování jsem úplný začátečník.
nahodnakolemjdouci
Kolemjdoucí

Odeslat příspěvekod Wikan 20. 4. 2010 16:58

Nejdřív obě množiny spojíš, pak je seřadíš algoritmem dle výběru (quick, merge, heap...). A pak vytvořenou množinu procházíš prvek po prvku, pokud se nějaký prvek shoduje s předchozím, tak ho nezapíšeš, jinak ano.
Wikan
Moderátor
Uživatelský avatar

Odeslat příspěvekod nahodnakolemjdouci 20. 4. 2010 17:15

No ale jak to spojit? Akorát jsem našla merge, ale to spojuje seřazené soubory. Jak spojit neseřazené?
nahodnakolemjdouci
Kolemjdoucí

Odeslat příspěvekod martin_o5 20. 4. 2010 17:23

Nejprve načti obě množiny - např. do polí, poté je spoj - jakkoli, seřaď, odstraň duplicity a nakonec ulož zpět do výstupního txt.
"Štěstí je jako malé dítě. Musíte ho neustále podpírat a pomáhat mu"
martin_o5
Mírně pokročilý
Uživatelský avatar

Odeslat příspěvekod Nargon 20. 4. 2010 17:47

Ja bych se te zeptal na jednu vec. Chces se naucit programovat (tj hlavne algoritmizovat) a nebo chces splnit zadani a odevzdat tenhle ukol?
Pokud ti staci jen ta druha cast, tak bych ti doporucil pouzit STL knihovnu a z ni tridu "set". S tim to zvladnes na nekolika radcich. Standartni datove typy ti to automaticky seradi a pri vlozeni duplicitniho cisla to nevadi, bude tam jen jednou.

viz tento kod:
Kód: Vybrat vše
#include <iostream>
#include <set>

#define length(a) ( sizeof ( a ) / sizeof ( *a ) )

using namespace std;

int main() //Vstupní bod programu
{
   int soubor1[] = {8,3,3,4,8,5,2,6,4,2,1,8,1,3,8,6,4}; //pro jednoduchost mam ty data ulozene v polich, ty je samozrejme budes mit v souboru.
   int soubor2[] = {3,8,6,1,2,3,5,9,8,7,4,2,2,5,6,8,1,3,4,9,6,3,2,1,5,4,7,8,5,2,3,6,9,1,2,4,5,8,7,9};


   set<int> mnozina; //vytvorim set typu int

   for (int i = 0; i<length(soubor1);i++) mnozina.insert(soubor1[i]); //vsechny cisla vlozim do mnoziny pomoci metody insert
   for (int i = 0; i<length(soubor2);i++) mnozina.insert(soubor2[i]); //a nacpu tam i cisla z druheho souboru

   set<int>::const_iterator iter; //vyrobim si iterator
   for(iter=mnozina.begin(); iter!=mnozina.end(); iter++) cout << *iter << " "; //a pomoci iteratoru projdu celou mnozinu a vypisu
   cout<<endl;
   //1 2 3 4 5 6 7 8 9

   getchar();
   return 0;
}


Ale jak jsem rekl, zalezi jestli se chces naucit algoritmicky myslet a vymyslet spravny postup reseni a to pak nejak naprogramovat. Pokud to chces, tak ten kod hodne rychle zapomen. A nebo chces mit tenhle ukol hotovej aniz by ses neco naucil. Pak ho klidne pouzij. Teda jestli nemate zakazano pouzivat STL knihovnu.
Desktop: Ryzen 7 1800X (3.95GHz, 1.35V), Asus Crosshair VI Hero, 16GB DDR4 Ram (3200MHz), 128GB SSD + 3TB HDD, Nvidia GTX 1080
Notebook: Asus UL50VT 15.6" (SU7300@1.7GHz, 4GB ram, 500GB HDD, Intel GMA 4500MHD + nVidia G210M, dlouha vydrz cca 7+ hod)
Nargon
Moderátor

Odeslat příspěvekod nahodnakolemjdouci 20. 4. 2010 18:02

No jasně, že se chci naučit programovat, ale nemá mi to kdo vysvětlit. Proto se tu ptám, nemám se od čeho odrazit.

Nicméně ještě mě zajímá, když načtu oba soubory do polí a ty spojím, budu mít pole se dvěmi miliony prvků, není to problém?
nahodnakolemjdouci
Kolemjdoucí

Odeslat příspěvekod Nargon 20. 4. 2010 18:13

milion prvku je 1 000 000, pokud to budou prvky typu "int" tak kazdy zabere 4B pameti. takze celkem 4 000 000 B pameti coz je cca 3.8MB pameti. Teda jeste krat dve, kdyz mas ty dve pole to je cca 7.6MB. Takze pokud to nedelas na nejakem obstaroznim PC ktery ma malou ramku, tak to neni problem.
Desktop: Ryzen 7 1800X (3.95GHz, 1.35V), Asus Crosshair VI Hero, 16GB DDR4 Ram (3200MHz), 128GB SSD + 3TB HDD, Nvidia GTX 1080
Notebook: Asus UL50VT 15.6" (SU7300@1.7GHz, 4GB ram, 500GB HDD, Intel GMA 4500MHD + nVidia G210M, dlouha vydrz cca 7+ hod)
Nargon
Moderátor

Odeslat příspěvekod MiliNess 20. 4. 2010 19:45

Nargon píše:milion prvku je 1 000 000, pokud to budou prvky typu "int" tak kazdy zabere 4B pameti. takze celkem 4 000 000 B pameti coz je cca 3.8MB pameti. Teda jeste krat dve, kdyz mas ty dve pole to je cca 7.6MB. Takze pokud to nedelas na nejakem obstaroznim PC ktery ma malou ramku, tak to neni problem.


Problém to bude, pokud těch 7,6 MB budeš alokovat na zásobníku (tedy budeš uvnitř funkce vytvářet statické pole) a neřekneš linkeru, aby se použil větší zásobník. (v mnoha případech se používá zásobník, který může růst max. do 1MB, kvůli chybám v rekurzivním volání)
Hardwarová nezávislost znamená, že to neběží na žádném počítači.
MiliNess
Pokročilý

Odeslat příspěvekod Nargon 20. 4. 2010 19:55

Imho pouziti kouzelneho sluvka "new" je v C++ celkem jednoduche. tak nevidim duvod alokovat takhle velke pole na zasobniku. Ale je pravda ze zacatecnik by to nemusel vedet.
Desktop: Ryzen 7 1800X (3.95GHz, 1.35V), Asus Crosshair VI Hero, 16GB DDR4 Ram (3200MHz), 128GB SSD + 3TB HDD, Nvidia GTX 1080
Notebook: Asus UL50VT 15.6" (SU7300@1.7GHz, 4GB ram, 500GB HDD, Intel GMA 4500MHD + nVidia G210M, dlouha vydrz cca 7+ hod)
Nargon
Moderátor

Odeslat příspěvekod sejnt 21. 4. 2010 09:29

Ja uz len cakam kedy sa tu objavi aj tretie zadanie ,ktore tam bolo "Rozdil mnozin" :-D .
Lekvár je produkt šialenej myšlienky ako neurobiť zo všetkých sliviek slivovicu.[CZ] Povidla jsou produkt šílený myšlenky jak neudelat ze všech švestek slivovici.
sejnt
Junior
Uživatelský avatar

Odeslat příspěvekod pucmeloudek 21. 4. 2010 09:35

a kartezsky soucin :)
jinak osobne, pokud bych dostal zadani obsahujici formulaci, ze mam z MNOZINY odstranit DUPLICITY, tak bych to okamzite zadavajicimu omlatil o hlavu. takova uloha ma asi tak stejny smysl jako chytat ryby v nadobe s cerstve vydestilovanou vodou...
pucmeloudek
Junior

Odeslat příspěvekod sejnt 21. 4. 2010 09:41

Lekvár je produkt šialenej myšlienky ako neurobiť zo všetkých sliviek slivovicu.[CZ] Povidla jsou produkt šílený myšlenky jak neudelat ze všech švestek slivovici.
sejnt
Junior
Uživatelský avatar

Odeslat příspěvekod pucmeloudek 21. 4. 2010 10:01

Vyborne zadani svedcici o duchaplnosti autora. Sice o odstranovani duplicit z mnozin nemluvi, zato si ale v uloze protireci. Nejdriv napise, ze jsou dany mnoziny a pak v poznamkach, ze je treba je nejdriv vytvorit.
To musi byt radost na zaklade takovych zadani neco tvorit.
A navic si plete trideni s razenim...
O booooooze, tihle nedouci.
pucmeloudek
Junior

Odeslat příspěvekod Nargon 21. 4. 2010 11:13

nahodnakolemjdouci píše:No jasně, že se chci naučit programovat, ale nemá mi to kdo vysvětlit. Proto se tu ptám, nemám se od čeho odrazit.


Pak je take vhodne pouzit ten "set" akorat si ho musis implementovat sam. Je tam myslim pouzit samovyvazovaci AVL binarni strom. Velice dobre je jeho implementace vysvetlena tady: http://tjn.fjfi.cvut.cz/~virius/jera/bi ... stromu.htm (sice je to v jazyku Pascal, ale prepsat to do C++ neni tezke)
Diky jeho pouziti mas pak automaticky vyresene serazeni dat a take odstraneni duplicit.

A postup je pak podobny jako u setu. Proste do toho stromu postupne naladujes vsechny cisla z obou vstupnich souboru. A pak ten strom metodou INORDER projdes a vypises vsechny cisla. A mas je hezky serazene a odstranene duplicity. Tohle je asi ten nejlepsi zpusob jak to napsat. Ale nevim jestli neni pro tebe moc slozity.


A nebo muzes udelat to co jsi navrhoval na zacatku pomoci MergeSortu si oba vstupni soubory seradit a pak je jednim Mergem spojit dohromady. A tady bych doporucoval tu "merge" funkci vylepsit o odstranovani duplicit. Staci si pamatovat posledni cislo co jsi vlozil do vysledku a pokud by jsi mel do vysledku vlozit stejne cislo tak ho do vysledku nevkladat a do vysledku vlozit cislo jen v pripade ze je jine nez to co si pamatujes. Tim si sice pridelas praci s ruznou "delkou" dat a budes s tim muset pocitat, ale mas vyresene duplicity a diky jejim odstranenim to bude i o neco rychlejsi.
Desktop: Ryzen 7 1800X (3.95GHz, 1.35V), Asus Crosshair VI Hero, 16GB DDR4 Ram (3200MHz), 128GB SSD + 3TB HDD, Nvidia GTX 1080
Notebook: Asus UL50VT 15.6" (SU7300@1.7GHz, 4GB ram, 500GB HDD, Intel GMA 4500MHD + nVidia G210M, dlouha vydrz cca 7+ hod)
Nargon
Moderátor

Odeslat příspěvekod nahodnakolemjdouci 21. 4. 2010 15:44

To je konec, moc nechápu, co mi tu radíte. Víte, my jsme celý semestr brali vytváření tříd a dědičnosti a podobně a pak nám najednou mrskou takové zadání na zápočet s věcmi, které nebyly na jediné přesnášce.

Nejvíce se mi líbilo použít pole: načíst data do dvou polí, sloučit je a seřadit, ale pak tu MiliNess napíše, že může být problém s velikostí zásobníku. Tak já fakt nevím.

Když budu chtít použít AVL strom, tak přece když bude vyvážený a budou v něm načtená data, už by v něm automaticky neměly být duplicity, ne?
nahodnakolemjdouci
Kolemjdoucí

Další stránka

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 0 návštevníků