[C++] szybkie wypisanie pewnych elementów tablicy

[freeszpak]

Dostajemy na wejściu liczbe całkowitą (liczbe elementów tablicy), następnie elementy tej tablicy. Później kolejną liczbę całkowitą, która mówi ile razy chcemy wypisać pewne elementy tablicy i na końcu dostajemy liczby, które mówią, które elementy tej pierwszej tablicy chcemy wypisać.

Na przykład dane wejściowe to:

Kod: Zaznacz cały

6
2  4  6  333 7 0
4
6 4 1 6

Na wyjściu ma być:

Kod: Zaznacz cały

0
333
2
0

Napisałem już kod, tylko problem w jego szybkości. Automat sprawdzający nie chce uznać odpowiedzi bo obliczenia przekraczają limit czasu.

Kod: Zaznacz cały

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int *tablica;
    tablica = new int[n];
    int *wskaznik=tablica;
    for(int i=0; i!=n; i++)
    {
        cin>>*wskaznik;
        wskaznik++;
    }

    int q;
    cin>>q;
    int *tablicaq;
    tablicaq = new int[q];
    int *wskaznik2=tablicaq;
    int *wskaznik3=wskaznik2;
    for(int i=0; i!=q; i++)
    {
        cin>>*wskaznik2;
        wskaznik2++;
    }

    for(int i=0; i!=q; i++)
    {
        cout<<tablica[*wskaznik3-1]<<endl;
        wskaznik3++;
    }
    delete [] tablica;
    delete [] tablicaq;
    return 0;
}

Dopiero zaczałem cos tymi wskaźnikami robić i nie wiem czy oen mi coś tu w ogóle przyśpieszają, czy je poprawnie używam. Program działa, ale za wolno.
Domyślam się, że trzeba coś zrobić w tej ostatniej pętli, która wypisuje. Tylko jak skorzystać ze wskaźnika do tablicy o nazwie tablica kiedy jej argumentem juz jest wskaźnik do innej tablicy?

[kalwi]

Ojoj, ale miszmasz. Po co tak to komplikujesz? Ten program jest skrajnie mało czytelny

Kod: Zaznacz cały

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int *tablica = new int[n];
    for(int i = 0; i < n; ++i)
     	cin >> tablica[i];

    int q;
    cin >> q;
    int *tablicaq = new int[q];
    for(int i = 0; i < q; ++i)
		cin >> tablicaq[i];

    for(int i = 0; i < q; ++i)
        cout << tablica[tablicaq[i] - 1] << endl;

    delete [] tablica;
    delete [] tablicaq;
    return 0;
}

[freeszpak]

Na początku wyglądał podobnie jak Twój, jednak w trakcie zabawy wskaźnikami tak się popsuł ;P Troche pokombinowałem i uznałem, że trzeba jakoś zrobić wskaźniki, które będą wskazywały na wskaźniki z tej pierwszej tablicy. Tylko jak to zrobić? Czytam o wskaźnikach do wskaźników i cięgle nie moge tego zastosowac w tym przypadku...

[kalwi]

Tutaj nigdzie nie zrobiłeś wskaźnika na wskaźnik. To by było coś w stylu

Kod: Zaznacz cały

int **wsk

Poza tym nawet nie wiem co chcesz w ten sposób osiągnąć. No i tablica sama w sobie to przecież wskaźnik.

Kod: Zaznacz cały

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int *tablica = new int[n];
    for(int i = 0; i < n; ++i)
        cin >> tablica[i];

    int q;
    cin >> q;
    int *tablicaq = new int[q];
    for(int i = 0; i < q; ++i)
      cin >> tablicaq[i];

    for(int i = 0; i < q; ++i)
        cout << *(tablica + *(tablicaq + i) - 1) << endl;

    delete [] tablica;
    delete [] tablicaq;
    return 0;
}

[freeszpak]

Nie wiem, niby powinno działac, no i w sumie działa, ale ciągle za wolno Nie wiem jak to się da zrobić szybciej, bez sensu

[kalwi]

Spróbuj ewentualnie tak:

Kod: Zaznacz cały

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector <int>tablica(n);
    for(int i = 0; i < n; ++i)
        cin >> tablica[i];

    int q;
    cin >> q;

    vector <int>tablicaq(q);
    for(int i = 0; i < q; ++i)
      cin >> tablicaq[i];

    for(int i = 0; i < q; ++i)
        cout << tablica[tablicaq[i] - 1] << endl;
    return 0;
}

-- 15 lis 2016, o 23:10 --Lub też spróbuj:

Kod: Zaznacz cały

https://pl.wikibooks.org/wiki/C%2B%2B/Listy

[freeszpak]

Nie wchodzi, dzięki za pomoc. Poddaję się juz na dzisiaj z tym zadaniem ;/

[kalwi]

To problemem raczej nie jest czas wykonywania się programu, a jest jakiś problem z wczytywaniem danych/wyświetlaniem. Tu naprawdę ciężko o optymalizację tego kodu

[Afish]

Strumienie są wolniejsze od scanf, niepotrzebnie zapamiętujecie drugą tablicę, niepotrzebnie alokujecie dynamicznie tablicę na stercie zamiast użyć prealokowanej. A jak to nie wystarczy, to można napisać własną obsługę wejścia/wyjścia.

[freeszpak]

Dzisiaj na laboratorium dowiedziałem się, że gdyby przy wypisywaniu tablicy użyć
zamiast endl, to program by przeszedł

[Dasio11]

A tak, endle potrafią jeść czas. Warto też napisać

std::ios_base::sync_with_stdio( false );

jeśli jednocześnie ze strumieniami nie używa się funkcji wejścia/wyjścia z C - potrafi przyspieszyć program kilkukrotnie.