Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 27.08.2002, 02:25   #1
Moderator
 
Mono's Avatar
 
Join Date: 10 2001
Location: Yerevan
Posts: 5,466
Downloads: 1
Uploads: 0
Blog Entries: 1
Reputation: 110 | 5
Post Duplicates

PPL-ner

Uremn ayspisi harc.

Yes unem mi inch vor list. Liste shat metz e. Mot mi 100000-ic minchev 1.000.000 elementner. Uremn uzum em __effektif___ algoritm vore kkaroghana ayd listic hani duplikatnere inchkan hnaravor e arag.

PS. I dep mi hat algoritm ei grel vorov uzeci 32000-anoc string listic duplicatnere hanel ( PERL-ov ) mot 15 rope tevec ed antere
__________________
---------------
Արատտայի ու Խալդեյի հովանավոր .
Reply With Quote
Old 27.08.2002, 05:06   #2
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Post

пока что такой (c - контейнер, содержащий элементы):
Code:
 
#include <algorithm>
using namespace std;

sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
сложность - n * log n + n (т.е. фактически n * log n). но! результирующая последовательность будет отсортирована.
или:
Code:
 
#include <algorithm>
using namespace std;

for(C::iterator it = c.begin(), end = c.end(); it != end; ++it)
{
	end = remove(it + 1, end, *it);
}
c.erase(end, c.end());
сложность - n(n+1)/2, т.е. n^2. зато без сортировки.
сложность erase-а в обоих случаях не учитывалась, но она добавит всего лишь слагаемое n.
Reply With Quote
Old 27.08.2002, 18:59   #3
Moderator
 
Mono's Avatar
 
Join Date: 10 2001
Location: Yerevan
Posts: 5,466
Downloads: 1
Uploads: 0
Blog Entries: 1
Reputation: 110 | 5
Post

Spasibo Aram djan

Ya ispolzoval vtoroy varyant no vidimo problema medlennosti moyevo scripta ne iz za Algoritma a iz za PERL-a ili je iz za kompa
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 07:36.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.