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