-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.cyf-kr.edu.pl!news.nask
.pl!news.nask.org.pl!news.internetia.pl!not-for-mail
From: Michoo <m...@v...pl>
Newsgroups: pl.comp.programming
Subject: Re: zadanie z netu
Date: Thu, 28 Mar 2013 21:50:48 +0100
Organization: Netia S.A.
Lines: 112
Message-ID: <kj2av2$go4$1@mx1.internetia.pl>
References: <2...@g...com>
<0...@g...com>
<kj047e$kbo$1@node1.news.atman.pl> <kj1535$k5f$1@mx1.internetia.pl>
<kj1o8h$mg9$1@node2.news.atman.pl>
NNTP-Posting-Host: 83.238.197.12
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: mx1.internetia.pl 1364504354 17156 83.238.197.12 (28 Mar 2013 20:59:14 GMT)
X-Complaints-To: a...@i...pl
NNTP-Posting-Date: Thu, 28 Mar 2013 20:59:14 +0000 (UTC)
In-Reply-To: <kj1o8h$mg9$1@node2.news.atman.pl>
X-Tech-Contact: u...@i...pl
User-Agent: Mozilla/5.0 (X11; Linux i686 on x86_64; rv:10.0.11) Gecko/20121123
Icedove/10.0.11
X-Server-Info: http://www.internetia.pl/
Xref: news-archive.icm.edu.pl pl.comp.programming:202370
[ ukryj nagłówki ]On 28.03.2013 16:39, bartekltg wrote:
> W dniu 2013-03-28 11:04, Michoo pisze:
>> On 28.03.2013 01:51, bartekltg wrote:
>>> W dniu 2013-03-27 19:24, M.M. pisze:
>>>> W dniu środa, 27 marca 2013 19:18:28 UTC+1 użytkownik firr kenobi
>>>> napisał:
>>>>> jak by nalezalo napisac taki program ?
>>>> Chyba zahaszować pary (słowo,częstość).
>>>
>>> Ogolnie jakakolwiek mapa i powinno pójść w miarę sprawnie.
>>>
>>> Hashowana pewnie będzie sprawniejsza. Unorderet_set
>>> ma co najmniej iterator z inkrementacją, więc
>>> i ze znalezieniem na koniec maksimum problemu nie będzie.
>>>
>>> Można by się ewentualnie zastanowić nad czymś w rodzaju
>>> drzew trie czy patricia, ale skoro nie
>>> musimy się przejmować pamięcią, nic nie zyskujemy,
>>> a wydajność leci.
>>>
>>> No to stl, szybki hash i sprawny odczyt (pewnie trzebaby
>>> wyhakować sobie własny, bo strumienie wolne;)
>>
>> I ty brutusie?
>>
>> sync_with_stdio?? iostream jest od pewnego czasu już równie szybkie co
>> stdio
>
> Wiem wiem;)
>
> BTW, czy taki printf w pętli za każdym razem parsuje ten
> swój napis typu "%d"?
W znanych mi implementacjach tak - jest automat zjadający wejście i
wypluwający wyjście (pobierając/zapisując kolejne rekordy ze stosu)
(hmmm, ciekawe, czy printf jest turing complete ;) ).
>
>> No chyba, ze extreme: jak po linuxem to można użyć czystego read albo
>> jeszcze lepiej mmap
>
> W przykładzie który widziałem (właśnie z takich konkursików)
> gość użył fgets + bufor + własne przerabianie na liczby.
Na potyczkach używałem kiedyś atoi - jest dostatecznie szybkie. fgets ma
jedną dodatkową wartwę po drodze do read.
> Tak akurat było to na zasadzie kto zrobi + limit czasu na tyle długi,
> aby czytać to odpaloną javą bit po bicie;) ale jakby to był
> wyścig 'kto szybciej', pewnie było by warto.
Kiedyś w pociągu zrobiłem jako "bonus" do sprawozdania o algorytmach
sortujących implementację heapsorta w asm byłem w sumie pozytywnie
zaskoczony wynikiem. (A wyszły w tym takie kwiatki jak np to, procesor
chyba trzymał szczyt stosu w rejestrach - operacje na [esp], [esp+4]...
były równie szybkie jak na eax,ebx...)
>
> U nas tablica mieszająca i tak pewnie zasłoniłaby swoim czasem
> działania szczegóły wczytywania.
Dla takich problemów dobra funkcja mieszająca to taka, która działa
możliwie liniowo. Zrobiłbym wektor wskaźników na funkcję do wykrywania
końca linii i lookup do robienia to_lower - w takiej konfiguracji
czytanie bajt-po-bajcie kontra czytanie blokami da duuużą różnicę.
>
>> Trzeba zrobić szybkie lower/upper (pewnie lookup table, nieduże w sumie).
>
> O zapomnialem o tym. Tablica na 256 elementów to nie problem,
O ile wejście jest 8-bit/znak - wtedy użyłbym w sumie jumptable.
> a dzieki temu za darmo mamy utożsamienie wszystkich białych
> znaków, interpunkcji etc.
256*4/8bajty na wskaźnik całkiem nieźle rezyduje w cache. O ile tylko
jumptable nie zepsuje za bardzo pipeline to powinna wymiatać.
Tak w ogóle teraz mnie deadline ścigają ale za jakieś 2 tygodnie to może
skrobnę programik - będzie można zrobić konkurs ;)
>
>>
>> Hash podejrzewam, że sprawdzi się w postaci:
>>
>> uint_least32_t hash=0;
>> uint_fast16_t len=0;
>
> Ech, piękne te typy;)
Hm? Właśnie do takich zastosowań one w końcu są.
>
>> for(char c:str){
>> hash^=c;
>> hash<<=1;
>> len++;
>> }
>> hash=(hash<<4)^len;
>
> Widzę, jak działa, ale dlaczego sądzisz, że będzie dobry?
Taki strzał - kiedyś używałem w bardzo podobnym zadanku sumy znaków i
dodanie długość bardzo poprawiło wynik - to jest lekka rozbudowa tej
koncepcji.
--
Pozdrawiam
Michoo
Następne wpisy z tego wątku
- 28.03.13 22:12 Michoo
- 28.03.13 23:55 bartekltg
- 29.03.13 11:41 firr kenobi
- 29.03.13 11:44 firr kenobi
- 29.03.13 12:21 M.M.
- 29.03.13 12:23 M.M.
- 29.03.13 13:07 firr kenobi
- 29.03.13 13:52 firr kenobi
- 29.03.13 15:33 M.M.
- 29.03.13 16:07 firr kenobi
- 29.03.13 19:04 M.M.
- 29.03.13 20:23 firr kenobi
- 29.03.13 21:16 M.M.
- 29.03.13 22:14 firr kenobi
- 30.03.13 00:31 Edek Pienkowski
Najnowsze wątki z tej grupy
- Alg. kompresji LZW
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
Najnowsze wątki
- 2025-03-15 Na co komu okna
- 2025-03-15 Mój elektryk
- 2025-03-15 Fejk muzyczny czy nie fejk
- 2025-03-15 China-Kraków => Senior PHP Symfony Developer <=
- 2025-03-15 Wrocław => Konsultant wdrożeniowy Comarch XL (Logistyka, WMS, Produk
- 2025-03-15 Błonie => Analityk Systemów Informatycznych (TMS SPEED) <=
- 2025-03-15 Warszawa => Senior Frontend Developer (React + React Native) <=
- 2025-03-15 Warszawa => Java Full Stack Developer (Angular2+ experience) <=
- 2025-03-15 Warszawa => Java Full Stack Developer (Angular2+) <=
- 2025-03-15 KOMU w RP3 pasuje "Rumuńska łatwość gmerania w wyborach" i dlaczego nie PO-Trzaskanym?
- 2025-03-15 China-Kraków => Key Account Manager IT <=
- 2025-03-14 Spalił się autobus :-)
- 2025-03-14 Policjanci z Piątku
- 2025-03-14 Lublin => JavaScript / Node / Fullstack Developer <=
- 2025-03-14 Warszawa => Account Manager - Sprzedaż Usług Rekrutacyjnych <=