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;
}