🚀 go-pugleaf

On 2010-05-25, sdh <staszekdh@gmail.com> wrote:
> czesc wszystkim,
>
> mam liste obiektow oraz funkcje "porownaj(a,b)", ktora dla danych
> dwoch obiektow a i b zwraca wartosc 'odleglosci' miedzy nimi. jesli
> 'odleglosc'  rowna sie 0 to znaczy, ze sa one identyczne (wg jakiejś
> tam hierarchii). ale w rzeczywistosci wartosc odleglosci bedzie sie
> wahac w zakresie 1-kilkadziesiat.
>
> pytanie: jak posortowac ta liste tak, aby elementy (obiekty)
> najblizsze sobie (najnizsza 'odleglosc' w rozumieniu porownaj(a,b))
> znalazly sie kolo siebie na liscie?

A sprawdzałeś metodę sort() klasy list? Nie? To sprawdź.

-- 
Secunia non olet.
Stanislaw Klekot

>
> A sprawdzałeś metodę sort() klasy list? Nie? To sprawdź.


Sprawdzalem (http://wiki.python.org/moin/HowTo/Sorting/), ale nie
widze rozwiazania.
W moim przypadku porownanie dwoch obiektow zwraca liczbe (to, co
nazwalem 'odleglosc' ) a nie 0/1 (ktory wiekszy)

Pozdr
S

epsilon$ while read LINE; do echo \>"$LINE"; done < "Stachu 'Dozzie' K."
>> mam liste obiektow oraz funkcje "porownaj(a,b)", ktora dla danych
>> dwoch obiektow a i b zwraca wartosc 'odleglosci' miedzy nimi. jesli
>> 'odleglosc'  rowna sie 0 to znaczy, ze sa one identyczne (wg jakiejś
>> tam hierarchii). ale w rzeczywistosci wartosc odleglosci bedzie sie
>> wahac w zakresie 1-kilkadziesiat.
>>
>> pytanie: jak posortowac ta liste tak, aby elementy (obiekty)
>> najblizsze sobie (najnizsza 'odleglosc' w rozumieniu porownaj(a,b))
>> znalazly sie kolo siebie na liscie?
>A sprawdzałeś metodę sort() klasy list? Nie? To sprawdź.

Poczekaj, ale trick polega na tym, że "porównanie" tutaj nie porównuje
elementów, tylko wyznacza pewną wartość dla danej pary elementów.
Poza tym zadanie w ogóle jest źle zdefiniowane.

-- 
[------------------------] 
[  Kruk@epsilon.eu.org   ] 
[ http://epsilon.eu.org/ ] 
[------------------------] 

>
> >> pytanie: jak posortowac ta liste tak, aby elementy (obiekty)
> >> najblizsze sobie (najnizsza 'odleglosc' w rozumieniu porownaj(a,b))
> >> znalazly sie kolo siebie na liscie?
> >A sprawdzałeś metodę sort() klasy list? Nie? To sprawdź.
>
> Poczekaj, ale trick polega na tym, że "porównanie" tutaj nie porównuje
> elementów, tylko wyznacza pewną wartość dla danej pary elementów.

no wlasnie :)

> Poza tym zadanie w ogóle jest źle zdefiniowane.
>

chetnie jest zredefiniuje

Staszek

epsilon$ while read LINE; do echo \>"$LINE"; done < "sdh"
>> >> pytanie: jak posortowac ta liste tak, aby elementy (obiekty)
>> >> najblizsze sobie (najnizsza 'odleglosc' w rozumieniu porownaj(a,b))
>> >> znalazly sie kolo siebie na liscie?
>> >A sprawdzałeś metodę sort() klasy list? Nie? To sprawdź.
>> Poczekaj, ale trick polega na tym, że "porównanie" tutaj nie porównuje
>> elementów, tylko wyznacza pewną wartość dla danej pary elementów.
>no wlasnie :)
>
>> Poza tym zadanie w ogóle jest źle zdefiniowane.
>chetnie jest zredefiniuje

Zastanów się najpierw nad rozwiązywalnością zadania w ogóle.
Czy "odległość" jest zdefiniowana dla każdej pary elementów?
Jak się mają wzajemnie te "odległości" do siebie?
W ogólności - żeby posortować zbiór - musisz mieć jasne kryterium. W tej
chwili masz kryterium pozwalające posortować nie zbiór danych elementów,
a jedynie zbiór par elementów. Jak to przełożyć na pojedyncze elementy?
To już zależy od ciebie. Skąd my mamy wiedzieć?
Wyobraź sobie np. sytuację w której masz rozmieszczone mniej-więcej
równo na okręgu punkty i jako "odległość" masz zwykłą euklidesową
metrykę na płaszczyźnie. Każdy z punktów będzie najbliżej swoich
bezpośrednich sąsiadów, ale stosunkowo daleko do pozostałych punktów.
Jak chciałbyś sortować w takiej sytuacji?

-- 
\------------------------/ 
|  Kruk@epsilon.eu.org   | 
| http://epsilon.eu.org/ | 
/------------------------\ 

On May 25, 2:48 pm, Mariusz Kruk <Mariusz.K...@epsilon.eu.org> wrote:
> epsilon$ while read LINE; do echo \>"$LINE"; done < "sdh"
>
> >> >> pytanie: jak posortowac ta liste tak, aby elementy (obiekty)
> >> >> najblizsze sobie (najnizsza 'odleglosc' w rozumieniu porownaj(a,b))
> >> >> znalazly sie kolo siebie na liscie?
> >> >A sprawdzałeś metodę sort() klasy list? Nie? To sprawdź.
> >> Poczekaj, ale trick polega na tym, że "porównanie" tutaj nie porównuje
> >> elementów, tylko wyznacza pewną wartość dla danej pary elementów.
> >no wlasnie :)
>
> >> Poza tym zadanie w ogóle jest źle zdefiniowane.
> >chetnie jest zredefiniuje
>
> Zastanów się najpierw nad rozwiązywalnością zadania w ogóle.
> Czy "odległość" jest zdefiniowana dla każdej pary elementów?
> Jak się mają wzajemnie te "odległości" do siebie?
> W ogólności - żeby posortować zbiór - musisz mieć jasne kryterium. W tej
> chwili masz kryterium pozwalające posortować nie zbiór danych elementów,
> a jedynie zbiór par elementów. Jak to przełożyć na pojedyncze elementy?
> To już zależy od ciebie. Skąd my mamy wiedzieć?
> Wyobraź sobie np. sytuację w której masz rozmieszczone mniej-więcej
> równo na okręgu punkty i jako "odległość" masz zwykłą euklidesową
> metrykę na płaszczyźnie. Każdy z punktów będzie najbliżej swoich
> bezpośrednich sąsiadów, ale stosunkowo daleko do pozostałych punktów.
> Jak chciałbyś sortować w takiej sytuacji?
>

ok,

sprawa jest nieco bardziej zlozona.

mamy drzewo. mamy korzen, do korzenia podlaczonych n wezlow, do kazego
z tych wezlow kolejne wezly itd. drzewo jest duze (700.000 wezlow).
mamy kilkaset lisci (ostatecznych wezlow, ktore sie juz nie
rozdzielaja) z tego drzewa. chce pogrupwac te liscie (jako liste), tak
zeby ich kolejnosc odzwierciedlala topologie drzewa. stad pomysl na ta
odleglosc, ktora jest po prostu iloscia wezlow, ktora odziela dwa
liscie.

pozdr
s

epsilon$ while read LINE; do echo \>"$LINE"; done < "sdh"
>> >> >> pytanie: jak posortowac ta liste tak, aby elementy (obiekty)
>> >> >> najblizsze sobie (najnizsza 'odleglosc' w rozumieniu porownaj(a,b))
>> >> >> znalazly sie kolo siebie na liscie?
>> >> >A sprawdzałeś metodę sort() klasy list? Nie? To sprawdź.
>> >> Poczekaj, ale trick polega na tym, że "porównanie" tutaj nie porównuje
>> >> elementów, tylko wyznacza pewną wartość dla danej pary elementów.
>> >no wlasnie :)
>>
>> >> Poza tym zadanie w ogóle jest źle zdefiniowane.
>> >chetnie jest zredefiniuje
>>
>> Zastanów się najpierw nad rozwiązywalnością zadania w ogóle.
>> Czy "odległość" jest zdefiniowana dla każdej pary elementów?
>> Jak się mają wzajemnie te "odległości" do siebie?
>> W ogólności - żeby posortować zbiór - musisz mieć jasne kryterium. W tej
>> chwili masz kryterium pozwalające posortować nie zbiór danych elementów,
>> a jedynie zbiór par elementów. Jak to przełożyć na pojedyncze elementy?
>> To już zależy od ciebie. Skąd my mamy wiedzieć?
>> Wyobraź sobie np. sytuację w której masz rozmieszczone mniej-więcej
>> równo na okręgu punkty i jako "odległość" masz zwykłą euklidesową
>> metrykę na płaszczyźnie. Każdy z punktów będzie najbliżej swoich
>> bezpośrednich sąsiadów, ale stosunkowo daleko do pozostałych punktów.
>> Jak chciałbyś sortować w takiej sytuacji?
>ok,
>
>sprawa jest nieco bardziej zlozona.
>
>mamy drzewo. mamy korzen, do korzenia podlaczonych n wezlow, do kazego
>z tych wezlow kolejne wezly itd. drzewo jest duze (700.000 wezlow).
>mamy kilkaset lisci (ostatecznych wezlow, ktore sie juz nie
>rozdzielaja) z tego drzewa. chce pogrupwac te liscie (jako liste), tak
>zeby ich kolejnosc odzwierciedlala topologie drzewa. stad pomysl na ta
>odleglosc, ktora jest po prostu iloscia wezlow, ktora odziela dwa
>liscie.

Wciąż nie do końca rozumiem z jakim kryterium chciałbyś sortować. Wciąż
piszesz o kryterium określonym dla pary.
Jeśli chcesz pojedyncze kryterium, możesz wziąć głębokość węzła.

-- 
  Kruk@ -\                   | 
          }-> epsilon.eu.org | 
http:// -/                   | 
                             | 

On May 25, 3:37 pm, Mariusz Kruk <Mariusz.K...@epsilon.eu.org> wrote:
> epsilon$ while read LINE; do echo \>"$LINE"; done < "sdh"
>
>
>
> >> >> >> pytanie: jak posortowac ta liste tak, aby elementy (obiekty)
> >> >> >> najblizsze sobie (najnizsza 'odleglosc' w rozumieniu porownaj(a,b))
> >> >> >> znalazly sie kolo siebie na liscie?
> >> >> >A sprawdzałeś metodę sort() klasy list? Nie? To sprawdź.
> >> >> Poczekaj, ale trick polega na tym, że "porównanie" tutaj nie porównuje
> >> >> elementów, tylko wyznacza pewną wartość dla danej pary elementów.
> >> >no wlasnie :)
>
> >> >> Poza tym zadanie w ogóle jest źle zdefiniowane.
> >> >chetnie jest zredefiniuje
>
> >> Zastanów się najpierw nad rozwiązywalnością zadania w ogóle.
> >> Czy "odległość" jest zdefiniowana dla każdej pary elementów?
> >> Jak się mają wzajemnie te "odległości" do siebie?
> >> W ogólności - żeby posortować zbiór - musisz mieć jasne kryterium. W tej
> >> chwili masz kryterium pozwalające posortować nie zbiór danych elementów,
> >> a jedynie zbiór par elementów. Jak to przełożyć na pojedyncze elementy?
> >> To już zależy od ciebie. Skąd my mamy wiedzieć?
> >> Wyobraź sobie np. sytuację w której masz rozmieszczone mniej-więcej
> >> równo na okręgu punkty i jako "odległość" masz zwykłą euklidesową
> >> metrykę na płaszczyźnie. Każdy z punktów będzie najbliżej swoich
> >> bezpośrednich sąsiadów, ale stosunkowo daleko do pozostałych punktów.
> >> Jak chciałbyś sortować w takiej sytuacji?
> >ok,
>
> >sprawa jest nieco bardziej zlozona.
>
> >mamy drzewo. mamy korzen, do korzenia podlaczonych n wezlow, do kazego
> >z tych wezlow kolejne wezly itd. drzewo jest duze (700.000 wezlow).
> >mamy kilkaset lisci (ostatecznych wezlow, ktore sie juz nie
> >rozdzielaja) z tego drzewa. chce pogrupwac te liscie (jako liste), tak
> >zeby ich kolejnosc odzwierciedlala topologie drzewa. stad pomysl na ta
> >odleglosc, ktora jest po prostu iloscia wezlow, ktora odziela dwa
> >liscie.
>
> Wciąż nie do końca rozumiem z jakim kryterium chciałbyś sortować. Wciąż
> piszesz o kryterium określonym dla pary.
> Jeśli chcesz pojedyncze kryterium, możesz wziąć głębokość węzła.
>

chodzio o to zeby podobne (blisko na drzewie) liscie byly kolo siebie
na liscie i tworzyly w niej kiscie ;)
myslalem o zastosowaniu klastrowania UPGMA...

On May 25, 2:20 pm, sdh <stasze...@gmail.com> wrote:
> czesc wszystkim,
>
> mam liste obiektow oraz funkcje "porownaj(a,b)", ktora dla danych
> dwoch obiektow a i b zwraca wartosc 'odleglosci' miedzy nimi. jesli
> 'odleglosc'  rowna sie 0 to znaczy, ze sa one identyczne (wg jakiejś
> tam hierarchii). ale w rzeczywistosci wartosc odleglosci bedzie sie
> wahac w zakresie 1-kilkadziesiat.
>
> pytanie: jak posortowac ta liste tak, aby elementy (obiekty)
> najblizsze sobie (najnizsza 'odleglosc' w rozumieniu porownaj(a,b))
> znalazly sie kolo siebie na liscie?

Nie posortować, a poklastrować. Robi się macierz odległości, wylicza
jej wektory własne, redukuje jej stopień do liczby klastrów które
chcesz mieć i gotowe. Nie pytaj mnie o szczegóły, to ten wykład miałem
pare lat temu.

Tutaj możesz zacząć szukać od strony matematycznej:
http://en.wikipedia.org/wiki/Cluster_analysis
A pythonowe narzędzia znajdziesz w SciPy http://docs.scipy.org/doc/scipy/reference/linalg.html

Update: jest chyba nawet gotowe rozwiązanie. http://code.google.com/p/scipy-cluster/
Ciebie interesuje normal euklidesowa.

> > mam liste obiektow oraz funkcje "porownaj(a,b)", ktora dla danych
> > dwoch obiektow a i b zwraca wartosc 'odleglosci' miedzy nimi. jesli
> > 'odleglosc'  rowna sie 0 to znaczy, ze sa one identyczne (wg jakiejś
> > tam hierarchii). ale w rzeczywistosci wartosc odleglosci bedzie sie
> > wahac w zakresie 1-kilkadziesiat.
>
> > pytanie: jak posortowac ta liste tak, aby elementy (obiekty)
> > najblizsze sobie (najnizsza 'odleglosc' w rozumieniu porownaj(a,b))
> > znalazly sie kolo siebie na liscie?
>
> Nie posortować, a poklastrować. Robi się macierz odległości, wylicza
> jej wektory własne, redukuje jej stopień do liczby klastrów które
> chcesz mieć i gotowe. Nie pytaj mnie o szczegóły, to ten wykład miałem
> pare lat temu.
>
> Tutaj możesz zacząć szukać od strony matematycznej:http://en.wikipedia.org/wiki/Cluster_analysis
> A pythonowe narzędzia znajdziesz w SciPyhttp://docs.scipy.org/doc/scipy/reference/linalg.html
>
> Update: jest chyba nawet gotowe rozwiązanie.http://code.google.com/p/scipy-cluster/
> Ciebie interesuje normal euklidesowa.

Dzieki!

Ktory z algorytmow (i dlaczego?) powinienem wykorzystac?

http://docs.scipy.org/doc/scipy/reference/cluster.hierarchy.html

tak jak wspominalem, myslalem o the average/UPGMA algorithm

On 2010-05-25, Mariusz Kruk <Mariusz.Kruk@epsilon.eu.org> wrote:
> epsilon$ while read LINE; do echo \>"$LINE"; done < "Stachu 'Dozzie' K."
>>> mam liste obiektow oraz funkcje "porownaj(a,b)", ktora dla danych
>>> dwoch obiektow a i b zwraca wartosc 'odleglosci' miedzy nimi. jesli
>>> 'odleglosc'  rowna sie 0 to znaczy, ze sa one identyczne (wg jakiejś
>>> tam hierarchii). ale w rzeczywistosci wartosc odleglosci bedzie sie
>>> wahac w zakresie 1-kilkadziesiat.
>>>
>>> pytanie: jak posortowac ta liste tak, aby elementy (obiekty)
>>> najblizsze sobie (najnizsza 'odleglosc' w rozumieniu porownaj(a,b))
>>> znalazly sie kolo siebie na liscie?
>>A sprawdzałeś metodę sort() klasy list? Nie? To sprawdź.
>
> Poczekaj, ale trick polega na tym, że "porównanie" tutaj nie porównuje
> elementów, tylko wyznacza pewną wartość dla danej pary elementów.

noi?
pydoc list, szukasz po sort. Mariusz, po tobie bym się spodziewał że
będziesz pamiętać jak to było rozwiązane w C (stdlib.h, qsort()).

> Poza tym zadanie w ogóle jest źle zdefiniowane.

Fakt, źle sformułowane. Nie spałem całą noc, więc włączył mi się moduł
automatycznej korekcji warunków.

-- 
Secunia non olet.
Stanislaw Klekot

On May 25, 4:02 pm, sdh <stasze...@gmail.com> wrote:
> > > mam liste obiektow oraz funkcje "porownaj(a,b)", ktora dla danych
> > > dwoch obiektow a i b zwraca wartosc 'odleglosci' miedzy nimi. jesli
> > > 'odleglosc'  rowna sie 0 to znaczy, ze sa one identyczne (wg jakiejś
> > > tam hierarchii). ale w rzeczywistosci wartosc odleglosci bedzie sie
> > > wahac w zakresie 1-kilkadziesiat.
>
> > > pytanie: jak posortowac ta liste tak, aby elementy (obiekty)
> > > najblizsze sobie (najnizsza 'odleglosc' w rozumieniu porownaj(a,b))
> > > znalazly sie kolo siebie na liscie?
>
> > Nie posortować, a poklastrować. Robi się macierz odległości, wylicza
> > jej wektory własne, redukuje jej stopień do liczby klastrów które
> > chcesz mieć i gotowe. Nie pytaj mnie o szczegóły, to ten wykład miałem
> > pare lat temu.
>
> > Tutaj możesz zacząć szukać od strony matematycznej:http://en.wikipedia.org/wiki/Cluster_analysis
> > A pythonowe narzędzia znajdziesz w SciPyhttp://docs.scipy.org/doc/scipy/reference/linalg.html
>
> > Update: jest chyba nawet gotowe rozwiązanie.http://code.google.com/p/scipy-cluster/
> > Ciebie interesuje normal euklidesowa.
>
> Dzieki!
>
> Ktory z algorytmow (i dlaczego?) powinienem wykorzystac?

To chyba zależy od tego w jakis dokładnie sposób chcesz je mieć
pogrupowane.
Tu masz ich opis:
http://www.stanford.edu/~maureenh/quals/html/ml/node73.html

epsilon$ while read LINE; do echo \>"$LINE"; done < "Stachu 'Dozzie' K."
>>>> mam liste obiektow oraz funkcje "porownaj(a,b)", ktora dla danych
>>>> dwoch obiektow a i b zwraca wartosc 'odleglosci' miedzy nimi. jesli
>>>> 'odleglosc'  rowna sie 0 to znaczy, ze sa one identyczne (wg jakiejś
>>>> tam hierarchii). ale w rzeczywistosci wartosc odleglosci bedzie sie
>>>> wahac w zakresie 1-kilkadziesiat.
>>>>
>>>> pytanie: jak posortowac ta liste tak, aby elementy (obiekty)
>>>> najblizsze sobie (najnizsza 'odleglosc' w rozumieniu porownaj(a,b))
>>>> znalazly sie kolo siebie na liscie?
>>>A sprawdzałeś metodę sort() klasy list? Nie? To sprawdź.
>> Poczekaj, ale trick polega na tym, że "porównanie" tutaj nie porównuje
>> elementów, tylko wyznacza pewną wartość dla danej pary elementów.
>noi?
>pydoc list, szukasz po sort. Mariusz, po tobie bym się spodziewał że
>będziesz pamiętać jak to było rozwiązane w C (stdlib.h, qsort()).

Ja wiem jak działa sort. Tyle, że sort wymaga funkcji
porównującej _elementy_. Tu nie jest powiedzianie, że porownaj(a,b) ma
cokolwiek wspólnego z a<b. Tu możemy co najwyżej stwierdzić, że
porownaj(a,b)<porownaj(c,d).
Albo ja coś przespałem.

-- 
\.\.\.\.\.\.\.\.\.\.\.\.\.\ 
.\.Kruk@epsilon.eu.org.\.\. 
\.http://epsilon.eu.org/\.\ 
.\.\.\.\.\.\.\.\.\.\.\.\.\. 

On 2010-05-25, Mariusz Kruk <Mariusz.Kruk@epsilon.eu.org> wrote:
> epsilon$ while read LINE; do echo \>"$LINE"; done < "Stachu 'Dozzie' K."
>>>>> mam liste obiektow oraz funkcje "porownaj(a,b)", ktora dla danych
>>>>> dwoch obiektow a i b zwraca wartosc 'odleglosci' miedzy nimi. jesli
>>>>> 'odleglosc'  rowna sie 0 to znaczy, ze sa one identyczne (wg jakiejś
>>>>> tam hierarchii). ale w rzeczywistosci wartosc odleglosci bedzie sie
>>>>> wahac w zakresie 1-kilkadziesiat.
>>>>>
>>>>> pytanie: jak posortowac ta liste tak, aby elementy (obiekty)
>>>>> najblizsze sobie (najnizsza 'odleglosc' w rozumieniu porownaj(a,b))
>>>>> znalazly sie kolo siebie na liscie?
>>>>A sprawdzałeś metodę sort() klasy list? Nie? To sprawdź.
>>> Poczekaj, ale trick polega na tym, że "porównanie" tutaj nie porównuje
>>> elementów, tylko wyznacza pewną wartość dla danej pary elementów.
>>noi?
>>pydoc list, szukasz po sort. Mariusz, po tobie bym się spodziewał że
>>będziesz pamiętać jak to było rozwiązane w C (stdlib.h, qsort()).
>
> Ja wiem jak działa sort. Tyle, że sort wymaga funkcji
> porównującej _elementy_. Tu nie jest powiedzianie, że porownaj(a,b) ma
> cokolwiek wspólnego z a<b. Tu możemy co najwyżej stwierdzić, że
> porownaj(a,b)<porownaj(c,d).
> Albo ja coś przespałem.

Słusznie. To ja miałem przespać (się). Wyłączam się z wątku, bo bzdury
gadam.

-- 
Secunia non olet.
Stanislaw Klekot