FINÁLNÍ VÝPRODEJ KREDITŮ na ITnetwork je tady. Využij poslední šanci a získej až 80 % extra kreditů ZDARMA na náš interaktivní e-learning. Zjisti více:
NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:
Avatar
Andrej Bátora
Člen
Avatar
Andrej Bátora:27.10.2017 16:23

Dobrý deň,

Riešim primitívne algoritmické cvičenia z tejto stránky: https://testovac.ksp.sk/tasks/
Som pri príklade "Najdi číslo 2" https://testovac.ksp.sk/…3-bsearch03/, ktorý neviem vyriešiť na viac ako 15 bodov z 30.

Pre tých ktorým sa nechce otvárať odkazy, tak je to proste cvičenie na binárne vyhľadávanie v ktorom dostanem postupnosť celých čísiel a prirodzené číslo (1000x) a mám zistiť či sa v postupnosti nachádza jeho absolútna hodnota.

Vyriešil som to tak že som binárne vyhľadal raz práve hľadané číslo a raz jeho zápornú verziu.
(Ak som číslo našiel na prvýkrát, zápornú verziu som už nehľadal)

V zadaní píšu, že vstup čísiel je 5x106, čiže veľký a tak na čítanie vstupu mám použiť scanf(), čo ale mám pocit je C /C++ záležitosť. A ja neviem či mám len zlé (pomalé) riešenie alebo čítanie vstupu z konzole v C# je pomalé tak že by som dostal len polovicu bodov.

Tak sa chcem spýtať či existuje niečo čo dokáže čítať vstup z konzole rýchlejšie a ak nieje problém v tom ale v mojom riešené tak by som chcel poprosiť o nejaké nápady na riešenie.

 
Odpovědět
27.10.2017 16:23
Avatar
Petr Šťastný
Tvůrce
Avatar
Odpovídá na Andrej Bátora
Petr Šťastný:27.10.2017 16:37

Na zadání jsem se nedíval, ale jestli máš problém s tím, že to nemůžeš dostatečně rychle zpracovat, tak zkus buildnout release verzi a spustit ji normálně mimo visual studio a až pak do ní vložit vstup. Na mém počítači to dělá mezi debug a release verzí obrovský rozdíl. Jestli to nepomůže, musíš prostě vymyslet lepší řešení. Když jsem dělal různé algoritmizační cvičení, téměř všude byla nějaká drobnost, díky které jsi mohl několikanásobně zrychlit výpočet.

Třeba jsem měl algoritmus O(n4). Ale ono stačilo vydělit výsledek dvěma (za určitých okolností), aby stačil algoritmus O(n2). Nevím jak to je u tvých úloh, ale u úloh co jsem řešil já tam většinou nějaký podobný chyták byl.

EDIT: Jinak varianta scanf() by mělo být normálně Console.ReadLine(). Možná zkus udělat možnost zadávání vstupu ze souboru, ale nemyslím, že to pomůže. Kdyžtak můžeš zkusit změřit, kolik času ti trvá načítání vstupu a kolik samotné řešení.

Editováno
 
Nahoru Odpovědět
27.10.2017 16:37
Avatar
Andrej Bátora
Člen
Avatar
Andrej Bátora:27.10.2017 16:52

Vďaka za odpoveď, čo sa týka zadávania vstupu do konzole ručne tak by som musel napísať 5 000 000 čísiel a to je trocha na dlho. Na tej stránke to testuje ich program a len dostanem odpoveď ako dlho to trvalo.

Vstup iný ako z konzole je zakázaný takže súbory použiť nemôžem. No a na viacerých miestach som čítal že Java, C# a myslím Python majú pomalé načítanie vstupu oproti C++ takže preto som si myslel že Console.Readline() je v niečom iný ako scanf().

 
Nahoru Odpovědět
27.10.2017 16:52
Avatar
Petr Šťastný
Tvůrce
Avatar
Odpovídá na Andrej Bátora
Petr Šťastný:27.10.2017 18:04

C++ je obecně oproti C# rychlejší snad (skoro) pořád, ale ty testy by měli být navrhnuté tak, aby bylo jedno, jestli to děláš v C# nebo v C++. Načítání z console je v pořádku, spíš někde bude nějaká možnost, jak ten algoritmus zrychlit.

 
Nahoru Odpovědět
27.10.2017 18:04
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 4 zpráv z 4.