Interpretacja polecenia - zmierz czas operacji wstawiania/usuwania dla tablicy posortowanej i nie.

Question

Witam, mam zadanko na poziomie, zakładam, drugiego roku studiów. Treść zadania to w przybliżeniu "zmierz czas operacji wstawiania, usuwania, oraz szukania losowego elementu dla tablicy posortowanej i nieposortowanej". Hmm, z jednej strony można bez problemu dodawać elementy do tablicy:

#define TEST_SIZE 1000000  

algorithmInitialTime= clock();

    for (int i =1; i<TEST_SIZE; ++i)
    {
      size_t newArrSize = TEST_SIZE +i;
      int* newArr = new int[newArrSize];

      memcpy( newArr, testArray, (TEST_SIZE+i-1) * sizeof(int) );
      delete [] testArray;
      testArray = newArr;

      testArray[TEST_SIZE] = 0
    }

  algorithTime = clock() - algorithmInitialTime;
  double algorithTime_seconds = static_cast<double>(algorithTime)/CLOCKS_PER_SEC;
   std::cout<<"Unsorted Array - inserting time in sec:  "<< algorithTime_seconds<<std::endl;

(nie próbowałem tego kompilować, przepraszam za drobne błędy jeżeli są),

Analogicznie można usuwać, tylko że za każdym razem ucinać ostatni element tablicy. Przeszukanie przy pomocy bibliotek algorithm... Ale czy ja dobrze w ogóle rozumiem zadanie? Nie wiem, siedzę nad tym pół dnia i albo ostatnio podniósł się poziom na studiach, albo ja utknąłem gdzieś w zeszłej dekadzie i nie znam sposobu na rozwiązanie go bardziej po ludzku. Co o tym sądzicie? To jest dobrze, czy może pan profesor napisał "tablica", a miał na ten przykład na myśli jakiś kontener STL?

Comments

U nas często przez czas mają na myśli liczbę operacji porównania i przypisania lub podobne rzeczy, które nie są mierzone przez faktyczny czas operacji, a właśnie taką symulacje.

---

A próbowałeś zapytać pana profesora o wyjaśnienie?

---

 Treść zadania to w przybliżeniu "zmierz czas operacji wstawiania, usuwania, oraz szukania losowego elementu dla tablicy posortowanej i nieposortowanej". 

To jest bardzo nieprecyzyjne wyjaśnienie, można to na wiele sposobów zinterpretować. Nie wiadomo o jaki kontener chodzi, ani co to znaczy mierzyć czas(może chodzić o złożoność obliczeniową). Zadanie jest zbyt ogólne jak dla mnie. Na pewno zadanie nie jest jakoś bardziej dokładnie sformułowane ?

---

@vector: Nie, ono nie jest bardziej precyzyjne. Z resztą, nie bawiąc się, dokładnie brzmi tak: "Porównaj ze sobą czasy wykonania wstawiana, usuwania, znajdowania minimalnego elementu oraz losowego elementu w:" i pod spodem między innymi "posortowanej i nieposortowanej tablicy". Nie jest to jedyne takie zadanie, zdarza mu się napisać "algorytm z wykładów", jakby ciężko było napisać po ludzku nazwę, a potem weź się człowieku domyślaj i zgaduj :P.

@Arkadiusz Sikorski, załóżmy przestrzeń hipotetyczną w której pana profesora nigdy nie widziałem, ani nie zobaczę.

@Mitelak meh, mi się wydaje że najlepiej na chama czas mierzyć. Tylko jak sobie zrobiłem testy z takim koślawym dodawaniem do tablicy, to zasadniczo nie dość że nie ma różnicy pomiędzy posortowaną i nie (bo niby z jakiej racji miała by być), to jeszcze zajmuje to ogromne ilości czasu. Więc podejrzewam że to w tym co rozumiemy jako "tablica" lezy problem.

---

zmierz czas operacji wstawiania, usuwania, oraz szukania losowego elementu dla tablicy posortowanej i nieposortowanej.

Posortowana:

wstawianie: dłużej od nieposortowanej, gdyż musi wstawić w odpowiednie miejsce aby było posortowane

szukanie: szukanie szybciej od nieposortowanej, gdyż nie musi sprawdzać wszystkich elementów tabeli

usuwanie: też usunie się szybciej dany element gdyż szybciej się go znajdzie po wartości

Nieposortowana: odwrotnie od posortowanej

 

Musisz chyba zaimplementować klasę PosortowanaTablica i NieposortowanaTablica oraz dać im 3 metody add, search, delete.

---

Ogólnie całość laborki odwołuje się do drzewa BST, a te tablice chyba mają być tylko takim porównaniem. Wątpię żeby chodziło o napisanie własnej implementacji tablicy, bo przecież było by o tym jakieś napomknięcie.... zrobiłem rozwiązanie równie upośledzone co zadanie, więc wychodzi że czasy dla posortowanej i nieposortowanej są zawsze takie same, nie pomyślałem że posortowana tablica traci swoją posortowatość gdy się coś jej doda na końcu...

---

widocznie coś źle zaimplementowałeś jak wyszły Ci takie same czasy, z pewnością posortowane drzewo/tablica, będzie wyszukiwać daną wartość szybciej, szybciej też ją usunie i z pewnością będzie dłużej trwało wstawianie do niej wartości, oczywiście jeżeli zrobi się to tak jak trzeba.

Możliwe też że za małe dane im wrzuciłeś, walnij tak aby liczyło kilkanaście sekund.

---

Nie, wszystko jest dobrze. Chodzi o to że std::min_element czy std::find nie zwracają uwagi na to że tablica jest posortowana, zawzse działają tak samo. Ja nie implementuje od zera tej tablicy, korzystam ze zwykłej tablicy w stylu c, bo teoretycznie te bajeranckie tablice, chociaż mogą mieć mylące nazwy (np. std::array), tablicami nie są. Usuwanie elementów jest niezależne od posortowania, a dodawanie - racja, zapomniałem żeby tablica pozostała posortowana :P.

---

Po pierwsze chyba nie masz robić swojej struktury ze zwykłej tablicy tylko na zasadzie drzewa binarnego.

Po drugie usuwanie jest szybsze bo wystarczy zmienić 2 wskaźniki a nie trzeba przenosić wszystkich elementów tablicy o jeden do tyłu jak to jest w przypadku dynamicznych tablic.

Po 3 szukanie jest szybsze jeżeli je dobrze zaimplementujesz zgodnie z drzewem binarnym, w pierwszym porównaniu już porównałeś połowę elementów.