API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Dec 14th, 2019
141
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.96 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <string>
  3. #include <time.h>
  4. #include <stdlib.h>
  5. #include <random>
  6.  
  7. std::string random_string() //generator losowych napisow 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ
  8. {
  9. std::string str("abcdefghijklmnopqrstuvwxyz");
  10.  
  11. std::random_device rd;
  12. std::mt19937 generator(rd());
  13.  
  14. std::shuffle(str.begin(), str.end(), generator);
  15.  
  16. return str.substr(0, 2);
  17. }
  18.  
  19. template<typename T>
  20. class Node
  21. {
  22. public:
  23. std::string name;
  24. T data;
  25.  
  26. std::string to_string()
  27. {
  28. return name + " " + std::to_string(data);
  29. }
  30.  
  31. Node()
  32. {
  33. name = random_string();
  34. data = rand() % 100;
  35. }
  36. Node(std::string str, T data)
  37. {
  38. this->name = str;
  39. this->data = data;
  40. }
  41.  
  42. bool operator==(Node* data)
  43. {
  44. if (this->data == data.data && this->name == data.name)
  45. return true;
  46. else
  47. return false;
  48. }
  49.  
  50. bool operator==(std::string data)
  51. {
  52. if (this->name == data)
  53. return true;
  54. else
  55. return false;
  56. }
  57. };
  58.  
  59. template<typename T>
  60. class List_Node
  61. {
  62. public:
  63. T data;
  64. List_Node* next;
  65. List_Node* prev;
  66.  
  67. List_Node()
  68. {
  69. data = next = prev = NULL;
  70. }
  71.  
  72. List_Node(T data)
  73. {
  74. this->data = data;
  75. next = prev = NULL;
  76. }
  77.  
  78. ~List_Node()
  79. {
  80. }
  81. };
  82.  
  83. template<typename T>
  84. class Lista
  85. {
  86. private:
  87. List_Node<T>* head;
  88. List_Node<T>* tail;
  89. public:
  90.  
  91. int counter;
  92. Lista()
  93. {
  94. this->head = this->tail = NULL;
  95. this->counter = 0;
  96. }
  97.  
  98. ~Lista()
  99. {
  100. List_Node<T>* node;
  101. while (this->head)
  102. {
  103. node = this->head->next;
  104. delete this->head;
  105. this->head = node;
  106. }
  107. }
  108.  
  109. //Dodaje element <T> na poczatek listy
  110. void add_Front(T data)
  111. {
  112. List_Node<T>* node = new List_Node<T>(data);
  113. if (this->head)
  114. {
  115. node->next = this->head;
  116. node->prev = NULL;
  117. this->head->prev = node;
  118. this->head = node;
  119. }
  120. else
  121. this->head = this->tail = node;
  122. this->counter++;
  123. }
  124.  
  125. //Dodaje element <T> na koniec listy
  126. List_Node<T>* add_Back(T data)
  127. {
  128. List_Node<T>* node = new List_Node<T>(data);
  129. if (this->head)
  130. {
  131. node->prev = this->tail;
  132. node->next = NULL;
  133. this->tail->next = node;
  134. this->tail = node;
  135. }
  136. else
  137. this->head = this->tail = node;
  138. this->counter++;
  139. return node;
  140. }
  141.  
  142. //Dodaje elementy z zachowaniem kolajnosci
  143. List_Node<T>* add_Order(T dane)
  144. {
  145. List_Node<T>* new_node = new List_Node<T>(dane);
  146. if (this->head)
  147. {
  148. List_Node<T>* tmp;
  149. tmp = this->head;
  150. T* tmp_data = tmp->data;
  151.  
  152. if (*tmp_data == dane == 0)//sprawdzam czy klucze sa takie same
  153. {
  154. std::cout << "Takie same indeksy" << std::endl;
  155. return NULL;
  156. }
  157. else if ((*tmp_data == dane) > 0)
  158. return this->add_Front(dane);
  159. tmp = this->head->next; //przechodze do nastepnego elementu
  160. if (tmp)
  161. tmp_data = tmp->data;
  162.  
  163. while (tmp)
  164. {
  165. if ((*tmp_data == dane) == 0)
  166. {
  167. std::cout << "Takie same indeksy" << std::endl;
  168. return NULL;
  169. }
  170. else if ((*tmp_data == dane) > 0) //wstawianie przed
  171. {
  172. new_node->prev = tmp->prev;
  173. tmp->prev->next = new_node;
  174. new_node->next = tmp;
  175. tmp->prev = new_node;
  176. this->counter++;
  177. return new_node;
  178. }
  179. tmp = tmp->next;
  180. if (tmp)
  181. tmp_data = tmp->data;
  182. }
  183. return this->add_Back(dane);
  184. }
  185. else
  186. return this->add_Front(dane);
  187. }
  188.  
  189. //Usuwa z listy pierwszy element z listy nie usuwajac <T> i zwraca wskaznk na dane
  190. T del_Front()
  191. {
  192. if (this->head)
  193. {
  194. List_Node<T>* node = this->head;
  195. T node_data = node->data;
  196.  
  197. this->head = this->head->next;
  198. node->next = NULL;
  199. node->data = NULL;
  200. delete node;
  201.  
  202. if (this->head)
  203. this->head->prev = NULL;
  204. else
  205. this->tail = NULL;
  206. this->counter--;
  207.  
  208. return node_data;
  209. }
  210. else return NULL;
  211. }
  212.  
  213. //Usuwa z ostatni pierwszy element z listy nie usuwajac <T> i zwraca wskaznk na dane
  214. T del_Back()
  215. {
  216. if (this->head)
  217. {
  218. List_Node<T>* node = this->tail;
  219. T node_data = node->data;
  220.  
  221. this->tail = this->tail->prev;
  222. node->prev = NULL;
  223. node->data = NULL;
  224. delete node;
  225. if (this->tail)
  226. this->tail->next = NULL;
  227. else
  228. this->head = NULL;
  229. this->counter--;
  230. return node_data;
  231. }
  232. else return NULL;
  233. }
  234.  
  235. //Usuwa cala liste (true usuwa tez wartosci z <T>, false czysci liste)
  236. void delete_(bool a)
  237. {
  238. if (a)
  239. {
  240. while (this->head)
  241. delete this->del_Front();
  242. }
  243. else
  244. {
  245. while (this->head)
  246. this->del_Front();
  247. }
  248. }
  249.  
  250. //Usuwa element po wskazniku List_Node<T>
  251. T del(List_Node<T>* node)
  252. {
  253. if (node == this->head)
  254. return this->del_Front();
  255. else if (node == this->tail)
  256. return this->del_Back();
  257. else if (node == NULL)
  258. return NULL;
  259. else
  260. {
  261. node->next->prev = node->prev;
  262. node->prev->next = node->next;
  263. node->next = node->prev = NULL;
  264. T node_data = node->data;
  265. delete node;
  266. this->counter--;
  267. return node_data;
  268. }
  269. }
  270.  
  271. //Usuwa element po indeksie
  272. T* del(int number)
  273. {
  274. return this->del(this->get_Index(number));
  275. }
  276.  
  277. //Zwraca wskaznik na dane z head
  278. T* ret_Head()
  279. {
  280. if (this->head)
  281. return this->head->data;
  282. else
  283. return NULL;
  284. }
  285.  
  286. //Zwraca wskaznik na dane z tail
  287. T* ret_Tail()
  288. {
  289. if (this->head)
  290. return this->tail->dane;
  291. else
  292. return NULL;
  293. }
  294.  
  295. //Zwraca wskaznik na list_node<T> po nr in indeksu
  296. List_Node<T>* get_Index(const int in)
  297. {
  298. if (in >= this->counter)
  299. {
  300. //cout << "Blad odczytu liczba poza zakresem\n";
  301. return NULL;
  302. }
  303. else
  304. {
  305. List_Node<T>* node;
  306. node = this->head;
  307. for (int i = 1; i <= in; i++)
  308. node = node->next;
  309. return node;
  310. }
  311. }
  312.  
  313. //Zwraca ilosc elementow w liscie
  314. int get_Size()
  315. {
  316. return this->counter;
  317. }
  318.  
  319. //Zwraca napis jednego elementu
  320. std::string to_string(List_Node<T>* node)
  321. {
  322. if (node == NULL)
  323. return "Blad odczytu \n";
  324. std::string str;
  325. str = node->data->to_string();
  326. return str;
  327. }
  328.  
  329. //Zwraca napis jednego elementu po indeksie
  330. std::string to_string(const int number)
  331. {
  332. return this->to_string(this->get_Index(number));
  333. }
  334.  
  335. //Zwraca cala liste do napisu
  336. std::string to_string()
  337. {
  338. if (this->head)
  339. {
  340. List_Node<T>* node;
  341. std::string kek;
  342. node = this->head;
  343. int i = 0;
  344. while (node)
  345. {
  346. i++;
  347. kek = kek + this->to_string(node) + " -> ";
  348. if (i > 5)
  349. break;
  350. node = node->next;
  351. }
  352. return kek;
  353. }
  354. else
  355. return "Lista pusta";
  356. }
  357.  
  358. //Ustawia nowe dane na wskazanym miejscu
  359. void set(int index, T* dane)
  360. {
  361. List_Node<T>* node;
  362. node = this->get_Index(index);
  363. if (node == NULL)
  364. {
  365. std::cout << "Bledne dane wejsciowe \n\n";
  366. }
  367. else if (node->data != NULL)
  368. {
  369. node->data = dane;
  370. }
  371. else
  372. std::cout << "Bledne dane wejsciowe \n\n";
  373. }
  374.  
  375. //Przeszukuje tablice i zwraca wskaznik na List_Node<T>
  376. T search(T number)
  377. {
  378. if (this->head)
  379. {
  380. List_Node<T>* node;
  381. node = this->head;
  382. T node_data = node->data;
  383. while (node)
  384. {
  385. //if (node_data == number)
  386. if (cmp(node_data,number))
  387. {
  388. //cout << "Znaleziono rekord\n\n";
  389. return node->data;
  390. }
  391. node = node->next;
  392. if (node)
  393. node_data = node->data;
  394. }
  395. //cout << "Nie znaleziono rekordu\n\n";
  396. return NULL;
  397. }
  398. else
  399. return NULL;
  400. }
  401.  
  402. bool cmp(T data,T data1)
  403. {
  404. if (data1->name==data->name)
  405. return true;
  406. else
  407. return false;
  408. }
  409.  
  410. T search(std::string number)
  411. {
  412. if (this->head)
  413. {
  414. List_Node<T>* node;
  415. node = this->head;
  416. T node_data = node->data;
  417. while (node)
  418. {
  419. if (*node_data == number)
  420. {
  421. //cout << "Znaleziono rekord\n\n";
  422. return node->data;
  423. }
  424. node = node->next;
  425. if (node)
  426. node_data = node->data;
  427. }
  428. //cout << "Nie znaleziono rekordu\n\n";
  429. return NULL;
  430. }
  431. else
  432. return NULL;
  433. }
  434.  
  435. //Przeszukuje tablice i zwraca wskaznik na List_Node<T>
  436. //Wyswietla kilka wartosci i pozwala wybrac rekord
  437. List_Node<T>* searchd(T number)
  438. {
  439. if (this->head)
  440. {
  441. List_Node<T>* node;
  442. node = this->head;
  443. T node_data = node->data;
  444. while (node)
  445. {
  446. if (node_data == number)
  447. {
  448. //cout << "Znaleziono rekord\n\n";
  449. return node;
  450. }
  451. node = node->next;
  452. if (node)
  453. node_data = node->data;
  454. }
  455. //cout << "Nie znaleziono rekordu\n\n";
  456. return NULL;
  457. }
  458. else
  459. return NULL;
  460. }
  461.  
  462. //Usuwa po liczbie
  463. T search_and_destroy(T number)
  464. {
  465. //cout << "Usuwanie po peselu " << number << endl;
  466. return del(searchd(number));
  467. }
  468.  
  469. //Usuwa po stringu
  470. T search_and_destroy(std::string tx)
  471. {
  472. std::cout << "Usuwanie po nazwie" << std::endl;
  473. return del(search(tx));
  474. }
  475. };
  476.  
  477. template<typename T>
  478. class Hasz
  479. {
  480. private:
  481.  
  482. int Max_cap;
  483. int Act_cap;
  484.  
  485. void rehash()
  486. {
  487. int newmax = Max_cap * 2;
  488. Lista<T>** newtab = new Lista<T> * [newmax];
  489. for (int i = 0; i < newmax; i++)
  490. {
  491. newtab[i] = new Lista<T>;
  492. }
  493.  
  494. for (int i = 0; i < this->Act_cap; i++)
  495. {
  496. const int tmp = table[i]->counter;
  497. for (int j = 0; j < tmp; j++)
  498. {
  499. T tmp = table[i]->del_Front();
  500.  
  501. std::string nazwa = tmp->name;
  502. int lenght = nazwa.length();
  503. int suma = 0;
  504.  
  505. for (int i = 0; i < lenght; i++)
  506. {
  507. int x = lenght - i - 1;
  508. suma = suma + nazwa[i] * pow(31, x);
  509. }
  510. suma = suma % newmax;
  511. newtab[abs(suma)]->add_Front(tmp);
  512. }
  513. }
  514.  
  515. for (int i = 0; i < Max_cap; i++)
  516. {
  517. table[i]->delete_(true);
  518. delete table[i];
  519. }
  520.  
  521. delete[] table;
  522. Max_cap = newmax;
  523. table = newtab;
  524. }
  525.  
  526.  
  527.  
  528. public:
  529.  
  530. int getHash(std::string data)
  531. {
  532. int lenght = data.length();
  533. int suma = 0;
  534.  
  535. for (int i = 0; i < lenght; i++)
  536. {
  537. int x = lenght - i - 1;
  538. suma = suma + data[i] * pow(31, x);
  539. }
  540. suma = suma % Max_cap;
  541. return abs(suma);
  542. }
  543.  
  544. Lista<T>** table;
  545. Hasz()
  546. {
  547. Max_cap = 2;
  548. Act_cap = 0;
  549. table = new Lista<T> * [Max_cap];
  550. for (int i = 0; i < Max_cap; i++)
  551. {
  552. table[i] = new Lista<T>;
  553. }
  554. }
  555.  
  556. void add(T data)
  557. {
  558. if (Act_cap >= (float)Max_cap * 0.75)
  559. this->rehash();
  560.  
  561. std::string nazwa = data->name;
  562. int lenght = nazwa.length();
  563. int suma = 0;
  564. for (int i = 0; i < lenght; i++)
  565. {
  566. int x = lenght - i - 1;
  567. suma = suma + nazwa[i] * pow(31, x);
  568. }
  569. suma = suma % Max_cap;
  570. T tmp = table[abs(suma)]->search(data->name);
  571. if (tmp)
  572. {
  573. bool t;
  574. }
  575. table[abs(suma)]->add_Front(data);
  576. Act_cap++;
  577. }
  578.  
  579. std::string to_string()
  580. {
  581. std::string str = "Ilosc elementow " + std::to_string(this->Act_cap) + " Max elementow " + std::to_string(this->Max_cap) + "\n";
  582. int j = 0;
  583. for (int i = 0; i < Max_cap; i++)
  584. {
  585. if (table[i]->counter == 0)
  586. {
  587.  
  588. }
  589. else
  590. {
  591. str = str + table[i]->to_string() + "\n";
  592. j++;
  593. if (j >= 10)
  594. break;
  595. }
  596. }
  597. return str;
  598. }
  599.  
  600. T findHash(T data)
  601. {
  602. int hasz = getHash(data->name);
  603.  
  604. return table[hasz]->search(data);
  605. }
  606.  
  607. bool deleteHash(T data)
  608. {
  609. int hasz = getHash(data->name);
  610. return (bool)table[hasz]->search_and_destroy(data);
  611. }
  612.  
  613. void reset(bool t)
  614. {
  615. for (int i = 0; i < Max_cap; i++)
  616. {
  617. table[i]->delete_(t);
  618. delete table[i];
  619. }
  620. delete[] table;
  621. }
  622.  
  623. std::string stats()
  624. {
  625. std::string str;
  626. int min = 7;
  627. int max = 0;
  628. int nulltables = 0;
  629. int sum = 0;
  630. for (int i = 0; i < Max_cap; i++)
  631. {
  632. if (max < table[i]->counter)
  633. max = table[i]->counter;
  634.  
  635. if (table[i]->counter == 0)
  636. nulltables++;
  637. else
  638. {
  639. if (min > table[i]->counter)
  640. min = table[i]->counter;
  641. sum = sum + table[i]->counter;
  642. }
  643. }
  644.  
  645. float avg = (float)sum / (Max_cap - nulltables);
  646. str = str + "Minimum = " + std::to_string(min);
  647. str = str + "\nMaximum = " + std::to_string(max);
  648. str = str + "\nSrednia = " + std::to_string(avg);
  649. str = str + "\nPuste listy = " + std::to_string(nulltables);
  650. return str;
  651. }
  652. };
  653. //int main()
  654. //{
  655. // Node<int> data("string", 6);
  656. // Node<int> data1("kusi", 1);
  657. // Node<int> data2("kek", 2);
  658. // Node<int> data3("XD", 69);
  659. // Node<int> nowy("nowy", 10);
  660. //
  661. // Hasz<Node<int>*>* hasz = new Hasz<Node<int>*>;
  662. //
  663. // hasz->add(&data);
  664. // std::cout << hasz->to_string() << std::endl << std::endl;
  665. // hasz->add(&data1);
  666. // std::cout << hasz->to_string() << std::endl << std::endl;
  667. // hasz->add(&data2);
  668. // std::cout << hasz->to_string() << std::endl << std::endl;
  669. // hasz->add(&data3);
  670. // std::cout << hasz->to_string() << std::endl << std::endl;
  671. // Node<int>*t = hasz->findHash(&data3);
  672. // *t = nowy;
  673. // if (t)
  674. // std::cout << t;
  675. //
  676. // std::cout << hasz->to_string() << std::endl << std::endl;
  677. // //hasz->delall();
  678. //}
  679.  
  680. int main()
  681. {
  682. srand(time(NULL));
  683. const int MAX_ORDER = 6;
  684. for (int o = 5; o <= MAX_ORDER; o++)
  685. {
  686. Hasz<Node<int>*>* ht = new Hasz<Node<int>*>();
  687. const int n = pow(10, o);
  688.  
  689. clock_t t1 = clock();
  690. for (int i = 0; i < n; i++)
  691. {
  692. Node<int>* data = new Node<int>();
  693. ht->add(data);
  694. }
  695.  
  696. Node<int>* da = new Node<int>();
  697. Node<int>* dd = new Node<int>();
  698. da->data = 10;
  699. da->name = "aa";
  700.  
  701. dd->data = 10;
  702. dd->name = "aa";
  703. ht->add(da);
  704. std::cout<<ht->getHash("aa");
  705. std::cout<<ht->findHash(dd);
  706. clock_t t2 = clock();
  707. double time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
  708.  
  709. std::cout << "Przebieg: " << o << " Czas ogolny: " << time1 * 1000 << " milisekund. " << "Czas na element: " << (time1 / n) * 1000000 << " mikrosekund. " << std::endl;
  710. std::cout << ht->to_string() << std::endl;
  711. std::cout << ht->stats() << std::endl;
  712. const int m = pow(10, 4);
  713.  
  714. int hits = 0;
  715.  
  716. t1 = clock();
  717.  
  718. for (int i = 0; i < m; i++)
  719. {
  720. Node<int>* dataf = new Node<int>();
  721. Node<int>* entry = ht->findHash(dataf); // wyszukiwanie wg losowego klucza
  722. if (entry)
  723. hits++;
  724. delete dataf;
  725. delete entry;
  726. }
  727. t2 = clock();
  728.  
  729. double time2 = (t2 - t1) / (double)CLOCKS_PER_SEC;
  730. std::cout << "Szukanie: Trafien " << hits << " Czas ogolny: " << time2 * 1000 << " milisekund. " << "Czas na element: " << (time2 / n) * 1000000 << " mikrosekund. " << std::endl << std::endl;
  731. ht->reset(true);
  732. delete ht;
  733. }
  734. return 0;
  735. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!