Wystarczy wypisać wszystkie słowa w dwu kolumnach, dwa razy obok
siebie. Litery z pierwszej kolumny posortować wiersz po wierszu.
Potem posortować wiersze jako klucza używając ciągów znaków z
pierwszej kolumny. Klasyka.

Pierwsze sortowanie kosztuje O(N) zakładając że ilość liter na słowo
jest mniejsza niż pewna stała. Drugie to O(N log N). Czyli tyle ma
cały algorytm.

Pamięciowo jest przyzwoicie: circa 2 razy tyle co słownik.

Hale fun.

do góry

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

do góry

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

do góry

On Tuesday, April 5, 2016 at 2:32:10 PM UTC+2, M.M. wrote:
> 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

A samoróbka na hashach szybsza:


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 0m2.962s
user 0m2.666s
sys 0m0.348s



#include <QString>
#include <QTextStream>

#define HASH_SIZE (1024*1024*12)
#define STACK_SIZE (1024*1024*3)
#define KEYS_SIZE (1024)

struct Item {
QString str;
QString sort;
Item *next;
};

static int count[HASH_SIZE];
static Item *hash[HASH_SIZE];
static Item stack[STACK_SIZE];
static int stack_size = 0;
static unsigned int keys[KEYS_SIZE];


static void initKeys() {
for( int i=0 ; i<KEYS_SIZE*1 ; i++ )
keys[i % KEYS_SIZE] = (keys[ i % KEYS_SIZE ] * 16) ^ qrand();
}


static unsigned int mkKey( const QString &str ) {
unsigned int key = 0;
for( int i=0 ; i<str.size() ; i++ )
key ^= keys[ str[i].unicode() % KEYS_SIZE ];
return key % HASH_SIZE;
}

static void insert( QString &str ) {
unsigned int key = mkKey( str );
stack[stack_size].str = str;
qSort( str.begin() , str.end() );
stack[stack_size].sort = str;
while( hash[key] && hash[key]->sort != str )
key = (key+1) % HASH_SIZE;
if( hash[key] ) {
stack[stack_size].next = hash[key];
}
hash[key] = stack + stack_size ++;
count[key] ++ ;
}

int main( int argc, char *argv[] )
{
qsrand(123);

QTextStream in(stdin);
in.setCodec("UTF-8");

initKeys();

QString line;

while( ! ( line = in.readLine() ).isEmpty() ) {
insert( line );
}

int max = 0;
for( int i=1 ; i<HASH_SIZE ; i++ )
if( count[max] < count[i] )
max = i;
Item *entry = hash[max];
int nr=1;
while( entry ) {
printf("%d %s\n",nr++,qPrintable(entry->str));
entry = entry->next;
}


return 0;
}

do góry