Софтуерно Инженерство
Loading...
georgi.stef.georgiev avatar georgi.stef.georgiev 916 Точки

Решения и тестове за Judge Assignment 3 (JA3)

Здравейте колеги,

Качени са решенияте и тестовете за Judge Assignment 3 в shared dropbox папката за курса. Има ги и като линкове в системата.

https://www.dropbox.com/sh/wojcivudpltkz8x/AACOqDOwEJhLh0rnGCRiLDZma?dl=0

Поздрави,

Жоро

 

Тагове:
0
C++ Programming
IvanMitkov avatar IvanMitkov 19 Точки

Да попитам за втората задача, има ли някакво предимство ръчно де се превръща в hex число, а да не се използва stoi(). И getchar не е ли по-бързо от cin?

0
georgi.stef.georgiev avatar georgi.stef.georgiev 916 Точки

Здравей,

Не, няма предимство ръчно да се превръща в hex вместо да се ползва stoi(). Аз го правя го правя ръчно най-вече за да покажа как би било направено ако не ползвате stoi() (пък и stoi() е от C++11, което в някаква ситуация е възможно да не може да ползвате - на изпита ще може, но тук-там има реални проекти, които стоят на стария стандарт). То като цяло за тази задача няма голям смисъл да се превръща в число изобщо, достатъчно е да въвеждаш в масив от 6 char-а и да го обработваш като 6 байта върху които правиш XOR - но го направих така за да е по-четимо.

Спорно е дали getchar е по-бързо от cin (зависи как го направиш, ако четеш по 6 наведнъж сигурно ще има забързване), обикновено когато cin e бавен, е бавен заради рендерирането на самата конзола (местене на маркера примерно) - в Judge системата cin е пренасочен към RAM паметта и не рендирира конзола, така че е сравнително бърз. Да, има забавяне, защото трябва да знае какво cin-ва и как да го обработи, но за случая на char обработка няма (ако беше int щеше да трябва да направи нещо еквивалентно на stoi за да го прочете). И, отново, cin ви е по-познато от лекциите, затова гледам да ползвам него. Като цяло задачите ги правя така, че скоростта на четене от конзолата да не ви определя резултата на решението, защото това бързо четене е нещо с доста ограничено приложение в истинския свят (повечето истински проекти или нямат големи четения на данни, или тези четения се извършват от някакви специални библиотеки, които са специализирани да бъдат бързи в това). Но е хубаво, че се интересуваш, така можеш да си спечелиш няколко допълнителни милисекунди на изпита и да компенсираш ако решението ти има някоя не-оптимална част :)

Поздрави,

Жоро

0
IvanMitkov avatar IvanMitkov 19 Точки

Ок, мерси много за отговора. Тази задача доста успя да ме поизпоти и може би за това търсих подобни дребни оптимизации. :)

0
gydigydi avatar gydigydi 12 Точки

Ей тoва нещо std::ios::sync_with_stdio(false);

от програмата за 2 задача със cin, направи от 3 секунди и нещо да върви на 1,7 сек и нещо.

Не че знам какво прави.

0
17/05/2017 17:49:18
fantom4e avatar fantom4e 24 Точки

Здравей.
Аз също ползвах sync_with_stdio, на кратко казано С++ има 8 стреама които имат връзка със съответни  3 стреама от С езика. По подразбиране те са свързани/синхронизирани, когато избереш false опцията прекъсваш връзката и С++ стреамовете работят самостоятелно и в някои от случайте работят по бързо.
Това е поне което успях да разбера аз.
Ето един линк в който е обяснено подробно http://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio

П.П. И все пак не успях да направя задачката за 100 то4ки :)

0
MartinBG avatar MartinBG 780 Точки

Към std::cin.sync_with_stdio(false) може да използваш и std::cin.tie(nullptr) - ще забърза нещата още малко.

Допълнителна скорост може да се получи при използване на буфериран вход.

 

Ето едно от решенията ми на задачата, което ползва тези оптимизации:

 

#include<iostream>

#pragma GCC optimize ("O3")

const int DNA_STR_LENGTH = 6;
const int BUFFER_SIZE = 10000 * (DNA_STR_LENGTH - 1) + 1; // +1 for '\0'

int main()
{
    static char res[DNA_STR_LENGTH];
    static char buffer[BUFFER_SIZE];
    int read_chars, index;

	// Tweaks for faster cin execution
    std::cin.sync_with_stdio(false);
    std::cin.tie(nullptr);

    while (std::cin.get(buffer, BUFFER_SIZE) && !std::cin.eof())
    {
        read_chars = std::cin.gcount();
        read_chars -= read_chars % (DNA_STR_LENGTH - 1);
        index = 0;

        while (read_chars > index)
        {
            res[0] ^= buffer[index++];
            res[1] ^= buffer[index++];
            res[2] ^= buffer[index++];
            res[3] ^= buffer[index++];
            res[4] ^= buffer[index++];
        }
    }

    std::cout << res;

    return 0;
}

 

 

0