Pomóżcie, bo spać nie mogę.

Po paru latach przerwy dopadła mnie konieczność napisania programu.
Problem był dość banalny: Na wejściu dostajemy paręnaście tysięcy list składających
się z kilkudziesięciu elementów (stringów), listy są posortowane, elementy list mogą
się powtarzać i robią to nagminnie - zadaniem programu jest "odfiltrowanie"
powtórzonych elementów i zapisanie tak wyczyszczonych list do pliku.

Zadanie jest już rozwiązane, ale gnębi mnie mało elegancki sposób jego rozwiązania.
Kod "filtrujący":


c = 1; // A)

for (i = 0; i < nElem; i++)
{
for (k = 0; k < i; k++)
{
c = strcmp(Tab[i], Tab[k]);
if (c == 0) // B)
break;
}
if (c != 0) // C)
MyOutFile << Tab[i] << ...
}


Pomijając kwestię optymalizacji dostępu do tablic i skorzystania ze "zbicia"
powtarzających się elementów - jak to to ucywilizować?
Zestawienie instrukcji C i B, niestety, kłuje w oczy...
Tak samo, jak "sztuczna" instrukcja A.

Da się coś z tym zrobić?
Jedyne, co mi przychodzi do głowy, to posłużenie się instrukcją goto, ale to - jak
wiadomo - samo zło...

do góry

On 05.10.2014 21:26, m...@g...com wrote:
> Pomóżcie, bo spać nie mogę.
>
> Po paru latach przerwy dopadła mnie konieczność napisania programu.
> Problem był dość banalny: Na wejściu dostajemy paręnaście tysięcy
> list
>składających się z kilkudziesięciu elementów (stringów), listy są
>posortowane, elementy list mogą się powtarzać i robią to nagminnie -
>zadaniem programu jest "odfiltrowanie" powtórzonych elementów i
>zapisanie tak wyczyszczonych list do pliku.
>
> Zadanie jest już rozwiązane, ale gnębi mnie mało elegancki sposób
> jegorozwiązania.
> Kod "filtrujący":
>

> c = 1; // A)
>
> for (i = 0; i < nElem; i++)
> {
> for (k = 0; k < i; k++)
> {
> c = strcmp(Tab[i], Tab[k]);
> if (c == 0) // B)
> break;
> }
> if (c != 0) // C)
> MyOutFile << Tab[i] << ...
> }
>
>
> Pomijając kwestię optymalizacji dostępu do tablic i skorzystania ze
> "zbicia" powtarzających się elementów - jak to to ucywilizować?
> Zestawienie instrukcji C i B, niestety, kłuje w oczy... Tak samo, jak
> "sztuczna" instrukcja A.
>
> Da się coś z tym zrobić? Jedyne, co mi przychodzi do głowy, to
> posłużenie się instrukcją goto, ale to - jak wiadomo - samo zło...


Nie mówiłeś czasem, że lista jest posortowana?
Skoro jest posortowana, to powtarzające się elementy
są obok siebie.
BTW, chyba to nie listy, skoro mają dostęp przez indeks.


int i=0;

while ( i<nElem )
{
MyOutFile << Tab[i] << ...;
int j=i+1;
while( (j<nElem) && (strcmp(Tab[j],Tab[i])==0) ) j++;
i=j;
}


Widzę, że używasz c++, (znaczki <<).
To czemu nie użyjesz stringów. Tab to wtedy
vector<string>.

while ( i<nElem )
{
MyOutFile << Tab[i] << ...;
int j=i+1;
while( (j<nElem) && ( Tab[j] == Tab[i] ) ) j++;
i=j;
}

Już wygląda lepiej.

Można też użyć od razu użyć unique
http://www.cplusplus.com/reference/algorithm/unique/

pzdr
bartekltg

do góry

On Sun, 5 Oct 2014 12:26:42 -0700 (PDT), m...@g...com wrote:

>Pomóżcie, bo spać nie mogę.
>
>Po paru latach przerwy dopadła mnie konieczność napisania programu.
>Problem był dość banalny: Na wejściu dostajemy paręnaście tysięcy list składających
się z kilkudziesięciu elementów (stringów), listy są posortowane, elementy list mogą
się powtarzać i robią to nagminnie - zadaniem programu jest "odfiltrowanie"
powtórzonych elementów i zapisanie tak wyczyszczonych list do pliku.
>
>Zadanie jest już rozwiązane, ale gnębi mnie mało elegancki sposób jego rozwiązania.
>Kod "filtrujący":
>
>
>c = 1; // A)
>
>for (i = 0; i < nElem; i++)
>{
> for (k = 0; k < i; k++)
> {
> c = strcmp(Tab[i], Tab[k]);
> if (c == 0) // B)
> break;
> }
> if (c != 0) // C)
> MyOutFile << Tab[i] << ...
>}
>
>
>Pomijając kwestię optymalizacji dostępu do tablic i skorzystania ze "zbicia"
powtarzających się elementów - jak to to ucywilizować?
>Zestawienie instrukcji C i B, niestety, kłuje w oczy...
>Tak samo, jak "sztuczna" instrukcja A.
>
>Da się coś z tym zrobić?
>Jedyne, co mi przychodzi do głowy, to posłużenie się instrukcją goto, ale to - jak
wiadomo - samo zło...

Jak listy sa posortowane, to powtarzajace sie elementy sa jeden za
drugim. Wystarczy wiec "jechac" po liscie z indeksem i, i porownywac
element [i] z [i+1]. Jezeli sa takie same, usunac element [i+1].
Reszta to szczegoy

Jezeli listy sa nieduze, moana ja konwertowac do struktury Set, ktora
jak wiadomo nie ma duplikatow, a potem Set z powrotem do listy jezeli
potzrebne jest sortowanie

A.L.

do góry

W dniu niedziela, 5 października 2014 22:11:26 UTC+2 użytkownik bartekltg napisał:

> int i=0;
>
> while ( i<nElem )
> {
> MyOutFile << Tab[i] << ...;
> int j=i+1;
> while( (j<nElem) && (strcmp(Tab[j],Tab[i])==0) ) j++;
> i=j;
> }


O, proszę! Ładne! :-)

Skojarzyłem, że kiedyś musiałem różnie reagować w zależności od liczby wyrazów we
wczytanym wierszu i męczył mnie podobny problem, więc tylko na nim się skupiłem...
Zakładając, że elementy NIE sa posortowane, przychodzi mi tylko coś takiego do głowy:


for (i = 0; i < nElem; i++)
{
for (k = 0; k < i; k++)
if (strcmp(Tab[i], Tab[k]) == 0)
goto NEXT;

for (k = i + 1; k < nElem; k++)
if (strcmp(Tab[i], Tab[k]) == 0)
goto NEXT;

MyOutFile << Tab[i] << ...

NEXT:
}


Takie continue, tylko nieco dalej skaczące...



> Widzę, że używasz c++, (znaczki <<).
> To czemu nie użyjesz stringów.

Tak jak wspominałem - musiałem napisać "jednorazówkę" do rozwiązania topornego
zadania.
Zanim program poczyścił zestawienia, wcześniej dokonywał operacji na pojedynczych
znakach i tu było mi poręczniej użyć tablic.
Zresztą, jak w zeszłym tysiącleciu przechodziłem z Pascala na C, strasznie irytował
mnie brak zmiennej typu String, tylko te dziadowskie tablice znakow.
Ale potem poczułem w tym pałera i trudno mi się znowu odkręcić. ;-)


> Tab to wtedy vector<string>.

Abstrachuje Pan od układu odniesienia. ;-)
Jestem "niedzielnym" programista, a o tym czymś z klamerkami czytałem kiedyś może z
raz u Grębosza... ;-)
Rozkminienie tematu zajęłoby mi więcej czasu, niż rozwiązanie całego zadania - w
zaoszczędzonym czasie wolę sobie popisać na usenecie. ;-)

do góry

On 06.10.2014 21:04, m...@g...com wrote:
> W dniu niedziela, 5 października 2014 22:11:26 UTC+2 użytkownik bartekltg napisał:
>
>> int i=0;
>>
>> while ( i<nElem )
>> {
>> MyOutFile << Tab[i] << ...;
>> int j=i+1;
>> while( (j<nElem) && (strcmp(Tab[j],Tab[i])==0) ) j++;
>> i=j;
>> }
>
>
> O, proszę! Ładne! :-)
>
> Skojarzyłem, że kiedyś musiałem różnie reagować w zależności od
> liczby
>wyrazów we wczytanym wierszu i męczył mnie podobny problem, więc tylko
>na nim się skupiłem...
> Zakładając, że elementy NIE sa posortowane, przychodzi mi tylko coś
>takiego do głowy:
>

> for (i = 0; i < nElem; i++)
> {
> for (k = 0; k < i; k++)
> if (strcmp(Tab[i], Tab[k]) == 0)
> goto NEXT;
>
> for (k = i + 1; k < nElem; k++)
> if (strcmp(Tab[i], Tab[k]) == 0)
> goto NEXT;
>
> MyOutFile << Tab[i] << ...
>
> NEXT:
> }

To jest kwadratowe.
Sortowanie jest n log(n) + algorytm powyżej (czy z std:z unique),
który jest linowy.

Nie ma porównania;-) Posortuj i rób jak poprzednio.


Jeśli chcesz je wypisywać w kolejności, w jakiej nadeszły,
możesz zapisać numer na pierwotnej liście, posortować
puścić unique, posortować po numerach nadejścia.
4 linijki, nadużywając języka.

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
typedef pair<string, int> tt;
vector<tt> tab;

int licznik=0;
for(;;){ //odczyt
string str;
cin>>str;
if (str=="koniec") break;
tab.push_back(make_pair(str,++licznik));
}


//mięsko
sort(tab.begin(),tab.end());
auto it = unique(tab.begin(),tab.end(), [](const tt &a,const tt &b
) {return a.first==b.first;});
tab.resize( distance(tab.begin(),it) );
sort(tab.begin(),tab.end(), [](const tt &a,const tt &b ) {return
a.second<b.second;});
//i po mięsku.

for (int i=0;i<tab.size();i++)
{
cout<<tab[i].second<<" "<<tab[i].first<<endl;
}
return 0;
}

" [](const tt &a,const tt &b ) {return a.first==b.first;} "
to "lambda", stworzenie funkcji, która ma arguymenty jak w nawiasie ()
i robi to, co jest w nawiasie {}. Są one używane jako trzcie argument
unique (zeby sprawdzić, co traktujemy jako 'to samo' i sort)

Prościej być może byłoby wykorzystać pomysł A.L, wykorzystać jakiś
kontener asocjacyjny, set (drzewo binarne) albo unordered_ser (tablica
haszująca).

Ale to wszytko tylko, jeśli chcesz zachować oryginalną kolejność,
jeśli tylko wypisać bez powtórzeń, posortuj i postępuj jak post
wcześniej.


> Takie continue, tylko nieco dalej skaczące...




>> Widzę, że używasz c++, (znaczki <<). To czemu nie użyjesz
>> stringów.
>
> Tak jak wspominałem - musiałem napisać "jednorazówkę" do rozwiązania
> topornego zadania. Zanim program poczyścił zestawienia, wcześniej
> dokonywał operacji na pojedynczych znakach i tu było mi poręczniej
> użyć tablic. Zresztą, jak w zeszłym tysiącleciu przechodziłem z
> Pascala na C, strasznie irytował mnie brak zmiennej typu String,
> tylko te dziadowskie tablice znakow. Ale potem poczułem w tym pałera
> i trudno mi się znowu odkręcić. ;-)

Kto co lubi. Ale cięzko korzystać z nowych zabawek nie uzywając
std::string.


>> Tab to wtedy vector<string>.
>
> Abstrachuje Pan od układu odniesienia. ;-) Jestem "niedzielnym"

Ty też. To usenet, 'panowanie' najczęściej występuje tu w bardzo
zaawansowanej kłótni ;-)

> programista, a o tym czymś z klamerkami czytałem kiedyś może z raz u
> Grębosza... ;-) Rozkminienie tematu zajęłoby mi więcej czasu, niż
> rozwiązanie całego zadania - w zaoszczędzonym czasie wolę sobie
> popisać na usenecie. ;-)


Jakiś czas temu znajoma poprosiła mnie o przypomnienie jej c++.
Miała to na studiach (politechnika). Po 20 minutach zrobiła
wielkie oczy i zdziwiona rzekła: to tu da się pisać jak w normalnym
języku.
Te wszystkie zabawki pozwalają pisać łatwiej i szybciej.

Oczywiście, niestety, trzeba trochę czasu w ich poznanie zainwestować.

BTW. C i C++ to ambitny wybór do niedzielnego programowania;-)


pzdr
bartekltg

do góry

On Sun, 05 Oct 2014 15:13:08 -0500, A.L. <a...@a...com> wrote:
> Jak listy sa posortowane, to powtarzajace sie elementy sa jeden za
> drugim. Wystarczy wiec "jechac" po liscie z indeksem i, i porownywac

Funkcja skrótu przydać się może. Drzewko buduj a posortujesz. Taka
kompresja.

do góry

jesli chodzi ci o osiagniecie poczucia 'prawie
doskonalego kawalka kodu' (tak jak da sie to zrobic w asemblerze) to w c jest ten
problem
ze c niejako nie supportuje tego odczucia ;/
i jest to pewien problem

nie wiem z czego to wynika ale raczej nie
wynika to w wiekszosci z 'semantyki' wygenerowanego programu - bardziej to chyba
wynika ze srodków zapisu

w c czesto po napisaniu programu mam poczucie ze jest on napisany 'jako
tako'/'przyzwoicie'
(i w zaleznosci ile ktos ma doswiadczenia itp
naprawde mozna napisac program krzepko itp)
ale ciezko jest osiagnac poczucie ze jakis pojedynczy fragment jest napisany
(prawie)doskonale

[jeszcze gorsza sytuacja jest gdy piszac jakis program musisz sie z jakichs powodow
godzic
na pewne dozy niedoskonalosci w programie,
(wynikajace z roznych czynnikow, glownie z niejasnosci i niedoskonalosci wiedzy) ]

- ogolnie to do czego pewnie nalzy dazyc w c to maksymalna prostota

do góry

On Sunday, October 5, 2014 10:11:26 PM UTC+2, bartekltg wrote:
> Nie mówiłeś czasem, że lista jest posortowana?
Moze sa posortowane po innym kryterium niz to, po ktorym sie
porownuje przy usuwaniu :D


> Skoro jest posortowana, to powtarzające się elementy
> są obok siebie.
Bylo powtarzajace sie elemnty "list" a nie "kazdej listy", moze
chodzi o powtorzenia we wszystkich listach a nie w jednej? :D



> BTW, chyba to nie listy, skoro mają dostęp przez indeks.
Moze taka moda nazewnicza? W QT do jednej z list tez jest (szybki!)
dostep przez indeksy. Nazywaja te strukture lista a nie wektorem.
Dlaczego zdecydowali sie na taka nazwe? Nie wiem. Moze dlatego zeby
ktos nie zrobil tak:

typ *ptr = &lista[i];
bool x = *(ptr+1) == lista[i+1]; // UB


Pozdrawiam

do góry

On Sunday, October 5, 2014 10:13:08 PM UTC+2, A. L. wrote:

> Jak listy sa posortowane, to powtarzajace sie elementy sa jeden za
> drugim. Wystarczy wiec "jechac" po liscie z indeksem i, i porownywac
> element [i] z [i+1]. Jezeli sa takie same, usunac element [i+1].
> Reszta to szczegoy

> Jezeli listy sa nieduze, moana ja konwertowac do struktury Set, ktora
> jak wiadomo nie ma duplikatow, a potem Set z powrotem do listy jezeli
> potzrebne jest sortowanie

Ja nie wiem co to znaczy odfiltrowac duplikaty. Moze jesli napis X
wystepuje N > 1 razy, to trzeba usnac go N razy, a nie N-1 razy?
Jesli N razy, to chyba potrzebne sa dwa Sety.

Pozdrawiam

do góry

On 10.10.2014 15:28, M.M. wrote:
> On Sunday, October 5, 2014 10:11:26 PM UTC+2, bartekltg wrote:
>> Nie mówiłeś czasem, że lista jest posortowana?
> Moze sa posortowane po innym kryterium niz to, po ktorym sie
> porownuje przy usuwaniu :D
>
>
>> Skoro jest posortowana, to powtarzające się elementy
>> są obok siebie.
> Bylo powtarzajace sie elemnty "list" a nie "kazdej listy", moze
> chodzi o powtorzenia we wszystkich listach a nie w jednej? :D

Też tak początkowo podejrzewałem, ale kod sugerował przetwarzanie
pojedynczej listy.

Jeśli jednak trzeba te listy połączyć, można to ładnie zespolić
z mergesortem. CHoć qsort i unique nadal może być szybsze ;-)

>
>> BTW, chyba to nie listy, skoro mają dostęp przez indeks.
> Moze taka moda nazewnicza? W QT do jednej z list tez jest (szybki!)

OT?

Pythonowa lista też chyba nie jest listą.

> dostep przez indeksy. Nazywaja te strukture lista a nie wektorem.
> Dlaczego zdecydowali sie na taka nazwe? Nie wiem. Moze dlatego zeby
> ktos nie zrobil tak:
>
> typ *ptr = &lista[i];
> bool x = *(ptr+1) == lista[i+1]; // UB

Tego chyba nikt nie napisze nawet, jak tam będzie vector.
Sensu za dużo nie ma;-)

pzdr
bartekltg

do góry