[C++] Wskazówki odnośnie pisania alogorytmów na SPOJ

[Quentin]

Witam!

Zaczynam powoli moją zabawę ze SPOJ i mam kilka pytań odnośnie pisania algorytmów - programów.

1 sprawa:

Chciałbym się zapytać czy znacie jakieś sprawy, o których większość początkujących wcale nie wie. Nie chodzi mi tu o takie problemy, że trzeba pamiętać, aby nie przekroczyć zakresu tablicy itp. Mam na myśli takie wskazówki jak tutaj:

http://pl.spoj.pl/forum/viewtopic.php?f ... 4c314890b8

1. Nie wypisuj niczego poza tym o co Ciebie proszą np. "podaj liczbę testów", "wejście", ponieważ programy sprawdza bezduszna maszyna.
2. Nie musisz sprawdzać poprawności wczytanych danych.
3. Po każdym przypadku testowym wypisuj znak nowej linii.

Innymi słowy: o czym jeszcze trzeba pamiętać, jeżeli program sprawdza maszyna No chyba, że to już tyle rzeczy

2 sprawa:

Lepiej używać zaawansowanych kontenerów STL czy np. takiej klasy string czy lepsze są może poczciwe tablice i tablice znaków Chodzi mi o szybkość działania i ilość zajętej pamięci.

Przeglądając zadania z OIG (z I etapu) napotkałem na kody, których autorzy wyglądało na to nie mają pojęcia, że istnieje klasa string - zamiast tego trudzili się z funkcjami z <cstring>. No chyba, że tak jest szybciej.

Rozwiązuję teraz zadanie:

https://pl.spoj.pl/problems/RNO_DOD/

I napisałem dwa rozwiązania, które wykonują się tak samo szybko i zajmują tyle samo pamięci - 2812 KB. Ale to przez to, że jest to program mały - przy większych pewnie na 99% będą różnice. (Testuję te algorytmy narzędziem Ideone).

Użycie wektora:

Kod: Zaznacz wszystko

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int main()
{
  unsigned short ile_testow;
  cin >> ile_testow;
  
  for( ; ile_testow ; ile_testow--)
  {
      unsigned int n;
      int suma = 0;
      cin >> n;
      
      vector<int> wekt(n);
      for( ; n ; n--)
      { 
          cin >> wekt[n-1]; 
          suma += wekt[n-1];
      }
      
      cout << suma << '\n';
  }

  return EXIT_SUCCESS;
} 

Użycie tablicy alokowanej dynamicznie:

Kod: Zaznacz wszystko

#include <iostream>
#include <cstdlib>
using namespace std;

int main()
{
  unsigned short ile_testow;
  cin >> ile_testow;
  
  for( ; ile_testow ; ile_testow--)
  {
      unsigned int n;
      int suma = 0;
      cin >> n;
      
      int* tabl = new int[n];
      for( ; n ; n--)
      { 
          cin >> tabl[n-1]; 
          suma += tabl[n-1];
      }
      delete [] tabl;
      
      cout << suma << '\n';
  }

  return EXIT_SUCCESS;
} 

I nie oszukujmy się - klasa string czy takie wektory na pewno korzystają z typów pochodnych wbudowanych w C++ - np. z różnorakich tablic. Jak mniemam, lepiej będzie jeżeli w tego typu programach będę stosował rozwiązania takie jak 2-gie

[Pockey]

ad 1. z tego co pamietam nie powinno sie uzywac 'zatrzymywaczy', typu getch(), czy system("pause")
ad 2. jesli to ma byc pisane w C++ to nie widze zadnych argumentow przeciw uzywaniu vectora czy stringa (czy czegokolwiek z STL) - to jest w standardzie C++ i powinno byc ok. muszisz sprawdzic regulamin, ale watpie zeby byl zakaz uzywania STL jak nie bedziesz na 100% pewien to zastosowanie zwyklego char* czy dynamicznej tablicy nie bedzie stanowila wiekszego problemu osobie zorientowanej w C++

[Quentin]

ad 2. jesli to ma byc pisane w C++ to nie widze zadnych argumentow przeciw uzywaniu vectora czy stringa (czy czegokolwiek z STL) - to jest w standardzie C++ i powinno byc ok. muszisz sprawdzic regulamin, ale watpie zeby byl zakaz uzywania STL jak nie bedziesz na 100% pewien to zastosowanie zwyklego char* czy dynamicznej tablicy nie bedzie stanowila wiekszego problemu osobie zorientowanej w C++

Stosować można na 100%. Mi chodzi o to co jest lepsze pod względem szybkości i zajmowanego miejsca w pamięci. Tutaj wygrywają poczciwe tablice, prawda Czyli wysyłać takie rozwiązania jak mój 2-gi kod

Zorientowany jestem w tym bardzo dobrze, więc mi to obojętne Przy tablicach będę się musiał troszkę pomęczyć, ale da to też trochę szybszy program, który dodatkowo zajmuje mniej pamięci - tak sądzę.

Czekam na Waszą odpowiedź

[Pockey]

duzo zalezy tez od kompilatora. z moich doswiadczen wynika ze stl jest bardzo szybki i dobrze optymalizowany przez kompilator. mysle ze w prostych zastosowaniach mozna 'strzelic' zwykla tablice, a jak zadanie bardziej skomplikowane to szybciej i latwiej uzyc stl. stl moze byc troche wolniejszy, ale to sa baaaardzo male roznice (zadne?) przy prostszych programach. jedyny problem to (re)alokacja pamieci. w zwyklej tablicy alokujesz raz i raz zwalniasz. w wektorze niekoniecznie, trzeba umiec uzyc: np. w miare mozliwosci uzywac reserve czy tak jak masz w tym przykladzie z vector (tu: vector<int> wekt(n);). twoje 2 wersje programow podejrzewam beda identycznie szybko dzialac, wiec pisz jak ci wygodniej - nie ma sie co zastanawiac to samo string vs. char* - string moze byc nawet o wiele szybszy.

[Quentin]

mysle ze w prostych zastosowaniach mozna 'strzelic' zwykla tablice, a jak zadanie bardziej skomplikowane to szybciej i latwiej uzyc stl.

No i tego będę się trzymał

Dzięki.

[pejs]

Generalnie w spoju chodzi bardziej o studium przypadku i warunków granicznych/szczególnych niż wyborze kontenera do reprezentacji (nie mówię tu o strukturach typu fibonacci heap i innych), a to czy użyć wektora czy listy zależy od tego jakich operacji będziemy używać - warto zrobić sobie bencha i zobaczyć jaki kontener lepiej zachowuje się przy jakich insertach/selectach/deletach i rozpatrzyć studium przypadku problemu.

[Quentin]

a to czy użyć wektora czy listy zależy od tego jakich operacji będziemy używać

Wiem, wiem

warto zrobić sobie bencha i zobaczyć jaki kontener lepiej zachowuje się przy jakich insertach/selectach/deletach

W Code::Blocks, kiedy program się zakończy, wyświetla się jego czas trwania w ms. Problem w tym, że najczęściej w programie mam wczytywanie z klawiatury czegoś, więc musiałbym umieszczać za każdym razem te dane, które bym wczytał, ręcznie w programie, żeby konsola (czy to co się zajmuje mierzeniem czasu działania programu) nie liczyła czasu potrzebnego na wczytywanie. Po drugie, za każdym razem ten czas różni się nawet o kilkadziesiąt ms, więc nie jest to rozwiązanie dokładne.

Próbowałem też używać funkcji GetTickCount() - ale i tak są duże wahania przy każdym nowym uruchomieniu tego samego kodu...

Więc co polecasz lepszego Są takie narzędzia, które "znają się na rzeczy" i wyświetlają zawsze takie same czasy przy tym samym programie Bardzo by mi to pomogło...

[pejs]

Wykorzystanie tej metody z WinAPI jest w porządku - zapuść wczytywanie strumieniowe z zapisywaniem czasu do pliku - zapuść operacje 1000 razy i podziel na 1000 - będzie dobre uśrednienie. A swoją droga - mocno przyspieszają wstawki asemblerowe, tudzież pisanie w samym asmie jeśli jest to możliwe w danym zadaniu.