-
X-Received: by 10.157.10.18 with SMTP id 18mr80966otg.2.1459859528939; Tue, 05 Apr
2016 05:32:08 -0700 (PDT)
X-Received: by 10.157.10.18 with SMTP id 18mr80966otg.2.1459859528939; Tue, 05 Apr
2016 05:32:08 -0700 (PDT)
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!goblin3!goblin.stu.neva.ru!news.ripco.com!news.glorb.com!n
t3no7963133igb.0!news-out.google.com!u9ni543igk.0!nntp.google.com!nt3no7963128i
gb.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Tue, 5 Apr 2016 05:32:08 -0700 (PDT)
In-Reply-To: <nduusf$m9d$1@node2.news.atman.pl>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=77.254.35.242;
posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
NNTP-Posting-Host: 77.254.35.242
References: <ndu0or$nm8$1@node2.news.atman.pl> <ndu1kr$tdf$1@node1.news.atman.pl>
<nduusf$m9d$1@node2.news.atman.pl>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <a...@g...com>
Subject: Re: Masowe wyszukiwanie anagramów
From: "M.M." <m...@g...com>
Injection-Date: Tue, 05 Apr 2016 12:32:08 +0000
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:209265
[ ukryj nagłówki ]On Tuesday, April 5, 2016 at 1:54:56 AM UTC+2, bartekltg wrote:
> On 04.04.2016 17:35, Borneq wrote:
> > W dniu 04.04.2016 o 17:20, Borneq pisze:
> >> Jak najszybciej wyszukać anagramy? Mam słownik 100-200 tyś słów, i
> >> kolejne słowa próbuję.
> >> Może tak, że słownik przestawię w postaci pary - słowa
> >> posortowanego,słowa?
> >> np.
> >> abcino,bocian
> >> ?
>
> Całkowicie wysatrczy.
>
> > Tylko jak to sortować?,
>
> funckją sort? ;-)
>
>
> > sortowanie kubełkowe? czy to sortowanie nie
> > stwarza problemów, gdy jakaś litera się powtarza,
>
> Nie.
>
> > Kubełków mogło by byc
> > mało dla ASCII, ale trzeba by dużej liczby dla Unicodu
>
> Hmm, ciekawostka, patrząc na tabelkę utf-8 traktując
> wyrazy jak ciagi bajtów i sortując te bajty nie spowodujesz
> niezamierzonej kolizji;-) żadne "ęąń" nie okaże się tym samym ciągiem
> co "ółś"
>
>
> Albo czegoś nie mówisz, albo przekombinowujesz:
>
>
> #include <vector>
> #include <string>
> #include <iostream>
> #include <algorithm>
>
>
>
> using namespace std;
>
>
> int main()
> {
>
> vector <pair<string, string > > S;
> string str,strs;
>
> while ( cin>>str )
> {
> strs=str;
> sort(strs.begin(),strs.end());
>
> S.emplace_back( strs,str );
> }
>
> sort(S.begin(),S.end());
>
> for (auto it = S.begin(); it!=S.end();)
> {
> auto itend = next(it);
> while (itend!=S.end() && itend->first == it->first) ++itend;
> if (distance(it, itend)>1)
> {
> cout<<"-- "<<distance(it, itend)<<endl;
> while (it!=itend)
> cout<<(it++)->second<<endl;
>
> }
> else it++;
> }
>
> return 0;
> }
>
> Dłużej piszę posta niż pisałem ten kod,
> http://sjp.pl/slownik/growy/
> 2.7 mln słow, 38MB,
> time ./untitled <slowa.txt >bla.txt
> real 0m5.638s
>
> Nie jest poprawny dla unikodu, ale dzięki uwadze powyżej - działa ;-)
>
> Rekordzista
> -- 13
> akrom
> arkom
> kamor
> karmo
> karom
> komar
> makro
> marko
> mokra
> morka
> okarm
> rakom
> ramko
>
>
> pzdr
> bartekltg
Na hash-table z QT działa z kompilacją 02 na procesorze i3 działa
ciut wolniej:
int main(int argc, char *argv[])
{
QTextStream in(stdin);
in.setCodec("UTF-8");
QString line;
QMultiHash<QString,QString> hash;
while( ! ( line = in.readLine() ).isEmpty() ) {
QString sort = line;
qSort( sort.begin() , sort.end() );
hash.insert( sort , line );
}
QStringList max;
QStringList keys = hash.uniqueKeys();
for( int i=0 ; i<keys.size() ; i++ ) {
if( max.size() < hash.values( keys[i] ).size() )
max = hash.values( keys[i] );
}
for( int i=0 ; i<max.size() ; i++ )
printf("%d %s\n",i+1,qPrintable(max[i]));
fflush(stdout);
return 0;
}
x@x:~/tmp/build-anagrams-Desktop-Release$ time cat ~/Pobrane/slowa.txt | ./anagrams
1 ramko
2 rakom
3 okarm
4 morka
5 mokra
6 marko
7 makro
8 komar
9 karom
10 karmo
11 kamor
12 arkom
13 akrom
real 0m6.810s
user 0m6.535s
sys 0m0.325s
Następne wpisy z tego wątku
- 05.04.16 15:28 M.M.
Najnowsze wątki z tej grupy
- 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??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
Najnowsze wątki
- 2024-10-06 Prawdziwy ekologiczny samochód
- 2024-10-05 Stało się...
- 2024-10-05 skodeczka up
- 2024-10-04 Wieszanie się przy aktywnym SMP
- 2024-10-05 Warszawa => Senior Developer React Native <=
- 2024-10-05 Katowice => Administrator IT - Wirtualizacja i Konteneryzacja <=
- 2024-10-05 Warszawa => Senior Software Engineer (C, Java) <=
- 2024-10-05 Warszawa => Menadżer Okręgu <=
- 2024-10-05 Warszawa => Specjalista/tka ds. Zamówień publicznych <=
- 2024-10-05 Warszawa => Senior C Software Engineer <=
- 2024-10-05 Warszawa => Senior PHP Laravel Developer (e-commerce) <=
- 2024-10-05 Warszawa => Full Stack .Net Engineer <=
- 2024-10-05 Warszawa => Data Scientist / Data Engineer (modele predykcyjne) <=
- 2024-10-05 Warszawa => ADMINISTRATOR SYSTEMÓW IT <=
- 2024-10-04 Katowice => Data Scientist <=