Linux за българи: Форуми

Здравейте,

Написах програмка за търсене на рими. Програмата има версия за linux и Win. За Win я писах на C++, като използвах wxWidgets (IDE-wxDevC++). Много тромаво се получи, но кода е елементарен и който иска може да го промени и отимизира.
PoetryHaxor for Windows ($2)

За linux използвах perl, а за GUI използвах GTK2, че ми се стори най-лесно и бързо ;D. Пък и в тая комбинация би трябвало да върви на всички системи с инсталиран GTK2.:
PoetryHaxor for Linux ($2)
(http://blog.nediko.info/examples/poetryhaxor/PoetryHaxor_for_Linux.png)

И двата архива са с приложен сорскод. Нямам лицензни условия, защото си нямам на идея как може да се лицензира такъв софтуер примерно под няква OpenSource форма.
Ако имате идеи свиркайте, особено за оптимизирането на C++-версията. Предварително благодаря!

Браво!

И на мен ми хареса :) ! Имам две незабележки :) първо - според мен, няма дума "вакумен". Има "вакуумен", но предполагам, че си взел наготово някой речник за проверка на грешки.
Другото е, че може като опция да се взима предвид мястото на ударението. Например в "умен" и "изумен" ударението е на различни места и римата се загубва.
Сега остава с един генератор на случайни числа да почне да пише стихове :)

Слушайки Георги Минчев,
"... ... ... ... у дома си
.... запазените маси."

Като гледам кода на С++ и Пърл е нормално на С++ да е по-бавен, цикълът на Пърл не борави със стрингове при всяка итерация, а именно:

GeSHi (Perl):
my $duma1 = substr $duma, -(length($duma))+1;
my $duma2 = substr $duma, -(length($duma))+2;
my $duma3 = substr $duma, -(length($duma))+3;
my $duma4 = substr $duma, -(length($duma))+4;
my $duma5 = substr $duma, -(length($duma))+5;
my $duma6 = substr $duma, -(length($duma))+6;
my $duma7 = substr $duma, -(length($duma))+7;
my $duma8 = substr $duma, -(length($duma))+8;
my $duma9 = substr $duma, -(length($duma))+9;
my $duma10 = substr $duma, -(length($duma))+10;
my $duma11 = substr $duma, -(length($duma))+11;
 
        open(MYFILE, "< :encoding(UTF-8)", "dic.txt");
	while(<MYFILE>){
	my($line) = $_;
 
	chomp($line);
	if($duma){
	if($line =~ m/($duma)$/i){
		#$buffer->insert ($buffer->get_end_iter, "$line\n");
		$line1 .= "$line\n";
	}
	elsif(length($duma)-1>=2 && $line =~ m/($duma1)$/i){
		$line2 .= "$line\n";
...

докато С++ цикълът "пере" здраво за всеки ред и всяка отделна под-дума, което забавя драстично целият процес

GeSHi (C++):
  wxString filename = _T("dic.txt");
    wxFileInputStream fsIn(filename);
    if ( !fsIn.Ok() )
    {
        wxPuts(_T("ERROR: couldn't open file."));
    }
    else
    {
        wxTextInputStream tis(fsIn);
 
        for ( ;; )
        {
            const wxString s = tis.ReadLine();
 
            // line could be non empty if the last line of the file isn't
            // terminated with EOL
            if ( fsIn.Eof() && s.empty() )
                break;
 
            if(duma){
		if(wxRegEx (duma+"$").Matches(s)){
			list1 += s+"\n";
		}
		else if((dsize-1 >= 2) && wxRegEx (duma.substr(1)+"$").Matches(s)){
			list2 += s+"\n";
		}
		else if((dsize-2 >= 2) && wxRegEx (duma.substr(2)+"$").Matches(s)){
			list3 += s+"\n";
		}
...

С++ дори много бързо извършва огромния ти цикъл, Пърл ще е съществено по-бавен при равноправни условия. Имам следните препоръки, кода си твой ти решаваш как ще изглежда, зареждай файла само веднъж в конструктора и използвай вектор от стрингове, като после само ще обикаляш вектора и ще "мачваш". В Project1Dlg.h

GeSHi (C++):
#include <vector>
...
private:
	void OnClose(wxCloseEvent& event);
	void CreateGUIControls();
	std::vector<wxString>dict;
};

после в конструктора го попълваш Project1Dlg.cpp

GeSHi (C++):
Project1Dlg::Project1Dlg(wxWindow *parent, wxWindowID id, const wxString &title, const wxPoint &position, const wxSize& size, long style)
: wxDialog(parent, id, title, position, size, wxDEFAULT_DIALOG_STYLE | wxRESIZE_BORDER)
{
	CreateGUIControls();
	wxString filename = _T("dic.txt");
    wxFileInputStream fsIn(filename);
    if ( !fsIn.Ok() )
    {
        wxPuts(_T("ERROR: couldn't open file."));
    }
    else
    {
        wxTextInputStream tis(fsIn);
 
        for ( ;; )
        {
            const wxString s = tis.ReadLine();
 
            // line could be non empty if the last line of the file isn't
            // terminated with EOL
            if ( fsIn.Eof() && s.empty() )
                break;
	    if(!s.empty())
		dict.push_back(s);
	}
    }
}

и при всяко натискане на бутон всичко ще става за по-малко от секунда, като обхождаш само вектора и търсиш за съвпадение

GeSHi (C++):
        std::vector<wxString>::iterator it;
        for (it = dict.begin(); it != dict.end(); it++ )
        {
            const wxString s = (*it);
 
            if(duma){
		if(wxRegEx (duma+"$").Matches(s)){
			list1 += s+"\n";
		}
		else if((dsize-1 >= 2) && wxRegEx (duma.substr(1)+"$").Matches(s)){
			list2 += s+"\n";
		}
...

bvbfan, много ти благодаря за добрите идеи!
Пробвах по начина, който си описал. Искрено се надявах да ускоря процеса. Но при мен не се получи. При тест с едни и същи думи се получава почти еднакво забавяне от 5-6 секунди. Т.е. дори и да има разлика е незабележима при WinXP SP3. Предполагам, че може би се дължи и на спецификата на операционната система.
Ето втората версия с предварително кеширане на речника: PoetryHaxor-v.02 ($2)

Предполагам, че остава варианта за разделяне на процеси и динамично вадене на проверените думи. Обаче не съм толкова добър, за да напиша подобно нещо.

Аз не съм ползвам wxDevC++ нито wxWidgets и реших да видя какво е положението и защо се изпълнява бавно и наистина проблема е непрекъснатото извикване на substr. И едното решение е да реализираш точно както на perl

GeSHi (C++):
void Project1Dlg::WxButton1Click(wxCommandEvent& event)
{
	WxEdit1->Clear();
	wxString duma = WxEdit2->GetValue();
	int dsize = duma.length();
	if(dsize < 2) return;
 
	wxRegEx Duma(duma+wxT("$"));
	wxRegEx subDuma1(duma.substr(1)+wxT("$"));
	wxRegEx subDuma2(duma.substr(2)+wxT("$"));
	wxRegEx subDuma3(duma.substr(3)+wxT("$"));
	wxRegEx subDuma4(duma.substr(4)+wxT("$"));
	wxRegEx subDuma5(duma.substr(5)+wxT("$"));
	wxRegEx subDuma6(duma.substr(6)+wxT("$"));
	wxRegEx subDuma7(duma.substr(7)+wxT("$"));
	wxRegEx subDuma8(duma.substr(8)+wxT("$"));
	wxRegEx subDuma9(duma.substr(9)+wxT("$"));
	wxRegEx subDuma10(duma.substr(10)+wxT("$"));
	wxRegEx subDuma11(duma.substr(11)+wxT("$"));
 
	wxString result;
 
	wxPuts(_T("\n*** wxTextInputStream test ***"));
 
	std::vector<wxString>::iterator it;
	for (it = dict.begin(); it != dict.end(); it++ )
	{
                bool find = false;
		const wxString s = (*it);
 
		if(Duma.Matches(s)){
			find = true;
		}
                else if((dsize-1 >= 2) && subDuma1.Matches(s)){
			find = true;
		}
		else if((dsize-2 >= 2) && subDuma2.Matches(s)){
			find = true;
		}
		else if((dsize-3 >= 2) && subDuma3.Matches(s)){
			find = true;
		}
		else if((dsize-4 >= 2) && subDuma4.Matches(s)){
			find = true;
		}
		else if((dsize-5 >= 2) && subDuma5.Matches(s)){
			find = true;
		}
		else if((dsize-6 >= 2) && subDuma6.Matches(s)){
			find = true;
		}
		else if((dsize-7 >= 2) && subDuma7.Matches(s)){
			find = true;
		}
		else if((dsize-8 >= 2) && subDuma8.Matches(s)){
			find = true;
		}
		else if((dsize-9 >= 2) && subDuma9.Matches(s)){
			find = true;
		}
		else if((dsize-10 >= 2) && subDuma10.Matches(s)){
			find = true;
		}
		if(find) {
                     result += s+wxT("\n");
                }
	}
	WxEdit1->AppendText(result);
	WxEdit1->SetInsertionPoint(0); // Set cursor to first line
 

Тествах и се изпълнява за по-малко от секунда  ;) , имам и мой вариант, който зависи от дължината на търсената дума и възможно да отнеме повече време при по-дълги думи, но може да се подобри, стига да има желание. Премахвам всички суб-думи и с един цикъл решавам за съпадения

GeSHi (C++):
       if(Duma.Matches(s)){
	    find = true;
       }
       else
       {
            int start = 0;
            size_t ssize = s.size();
            if(dsize > (int)ssize)
                start = dsize-ssize;
            for(int i = start+1; i < dsize-2; i++)
            {
                if(wxRegEx(duma.substr(i)+wxT("$")).Matches(s))
                {
                    find = true;
                    break;
                }
            }
        }
 

bvbfan, ценя високо желанието ти да ми помогнеш! Благодаря ти за интересните кодове! Научавам страшно много неща!
Наистина програмата така работи по-бързо. В един първоначален вариант бях направил нещо подобно, но се губи идеята. Целта ми е да изкарам първо думите с най-дълго съвпадение, а не просто всички думи, които съвпадат с шаблоните.
Отново ти благодаря за ценния код, а още повече за желанието ти да съдействаш!

В един първоначален вариант бях направил нещо подобно, но се губи идеята. Целта ми е да изкарам първо думите с най-дълго съвпадение, а не просто всички думи, които съвпадат с шаблоните.

Идеята не се губи и 2-та варианта целта е да се намери най-дългото възможно съвпадение, освен това ги проверих, че дават един и същ резултат. Защо си помисли, че се сменя идеята  ???

Възможно е нещо да съм объркал кода от последния ти пост, но след компиране, при тест с една и съща дума се получава следния резултат:
(http://i43.tinypic.com/qso51z.png)
Десният вариант е програмата от първия ми пост, левият е копилацията от кода по-горе. Надявам се да е ясно какво искам да постигна. Първи да излизат думите с максимално дълго съвпадение.

Просто са подредени както във файла, а не по най-дълго съвпадение, махни флага find и си върни пак стринг променливите, 1:1 с Пърл-а и става много бързо и точно както искаш find = true; ->  line1 += s+wxT("\n"); и така пак 11 и пак поотделно ги слагаш на прозореца.

Понеже нямам време да чета кодове в момента искам да попитам дали сте си играли да правите някакво организиране на информацията и да я кодирате, така че търсенето да става много бързо или просто правите някакъв цикъл в масива от думи и върху всяка дума извършвате операции с регулярни изрази? Имам интересна идея за реализирането на въпросната програма, просто ще трябва да си поиграя малко с числа преди да пиша... :)

ОК сега. Идеята ми е следната. Да вземем дума "оксиморон", Която е от 9 символа.
и я представвяме по следния начин: нором последните 5 байта(макар че това символ = байт май е само в аски.) все тая правим "нором" = м*100000000 + 0* 1000000 + р*10000 + о*100 + н
като всяки символ отговаря на някакво число от 1 до 34
после всичко после примерно търсим рима на газпром думата се кодира по същия начин с последните 5 символа и обчият стринг ром ще се открие доста бързо. Тъй като най-важни са последните букви, колкото е голяма "приликата" толкова повече функциите от думате ще дават по-близък резултат. Като сложност на алгоритъма имаме комплекситет в О(log n) ако предварително си си сметнал думите в масива:)

Поздрави,
Тодор

В Българския тълковен речник (изд. 1994) пише, че в него има около 60'000
при комплекситет log(n) като базиса ти е 2 смятай колко пъти ще правиш сондиране :) 16 :) отделно веднъж, ще трявба да ги подредиш в някаква структора като ги кодираш, което с един мърджсорт би трябвало да ти излезе с граница до 60 000 * 16. Ако ти се занимава може да постигнеш по-добра сложност с някакъв рандомизиран куиксорт, ама не си струва да си го пишеш това, след като веднъж ще кодираш и сортираш. Също може да ползваш инсърт сорт кодирай, сортирай, кодирай, сортирай и тн... не знам колко си струва упражнението като не сортираш някакъв обем от 2^200 обекта примерно :) [_]3

Добавих Уникод и направих ново търсене
http://www.multiupload.com/ATZ824YUWP

само 1 предложение, виж какво е DAWG и как можеш да го използваш, за да забързаш програмата си

поздрави
нас

Предложението с ДАЛГ е интересно... ако инвертира всяка дука и после разглежда всеки символ като обект от  символ и 28 възможни поинтъра към следващия убект, много лесто може да свива търсенето. Аз до сега не съм реализирал подобно дърво до сега, но би ми било интересно да го видя в практиката... Ако за корен са сложи един епсилон а.к.а. празната дума/символ ще се получи интересно... ако има някой да му се занимава, ще е интересно...