-
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
- Can you activate BMW 48V 10Ah Li-Ion battery, connecting to CAN-USB laptop interface ?
- We Wrocławiu ruszyła Odra 5, pierwszy w Polsce komputer kwantowy z nadprzewodzącymi kubitami
- Ada-Europe - AEiC 2025 early registration deadline imminent
- John Carmack twierdzi, że gdyby gry były optymalizowane, to wystarczyły by stare kompy
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2025
- Linuks od wer. 6.15 przestanie wspierać procesory 486 i będzie wymagać min. Pentium
- ,,Polski przemysł jest w stanie agonalnym" - podkreślił dobitnie, wskazując na brak zamówień.
- Rewolucja w debugowaniu!!! SI analizuje zrzuty pamięci systemu M$ Windows!!!
- Brednie w wiki - hasło Dehomag
- Perfidne ataki krakerów z KRLD na skrypciarzy JS i Pajton
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- U nas propagują modę na SI, a w Chinach naukowcy SI po kolei umierają w wieku 40-50lat
- C++. Podróż Po Języku - komentarz
Najnowsze wątki
- 2025-07-12 Warszawa => PC Hardware Expert / Specjalista PC <=
- 2025-07-12 Warszawa => Account Manager - Usługi rekrutacyjne <=
- 2025-07-12 Warszawa => Administrator IT <=
- 2025-07-12 Warszawa => IT Administrator <=
- 2025-07-12 Warszawa => Asystent/tka ds. Administracji <=
- 2025-07-12 Warszawa => Specjalista/stka ds. Organizacji <=
- 2025-07-12 Warszawa => MENA New Business Manager <=
- 2025-07-12 Gdynia => Controlling systems Consultant <=
- 2025-07-12 Warszawa => Developer Microsoft Dynamics 365 Finance & Operations (D36
- 2025-07-12 Warszawa => Programista Microsoft Dynamics 365 Finance & Operations (D
- 2025-07-12 Warszawa => Dyrektor IT <=
- 2025-07-12 Warszawa => IT Director <=
- 2025-07-12 Czy wypowiedź Kaczyńskiego o Braunie jest skarżalna? ["działa z OBCEJ inspiracji"]
- 2025-07-11 Rejestrator temperatur - termopara, siec
- 2025-07-11 DPD, przeniesienie numerów z a2mobile i z Orange