🚀 go-pugleaf

Marcin Gajda wrote:

> Tak więc - macie może jakiś pomysł na coś szybszego? Mógłbym posortować w
> O(nlogn) jakimś merdżsortem, ale nie jestem pewien, czy tędy droga...

Mozna posortować standardową funkcją sort, a potem sprawdzić, czy nie ma
powtórzeń wśród sąsiednich. Nie widzę, jak można prościej.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

Dnia Sun, 15 Jun 2003 20:09:33 +0000 (UTC), Marcin Gajda napisał(a):
> Witam,
  
> Tak więc - macie może jakiś pomysł na coś szybszego? Mógłbym posortować w
> O(nlogn) jakimś merdżsortem, ale nie jestem pewien, czy tędy droga...

tak jak Qrczak już napisał sort + przeleciec sie po liscie, mi też nie
przychodzi nic prostszego do głowy
 
> Wszelkie uwagi (krytyczne!) na temat stylu i podejścia miło widziane - dopiero
> się zapoznaję z tym Haskellem :P

Przeczytałem ten kod i nie bardzo rozumiem, po co wyznaczasz tam medianę
ze środkowego i skrajnych elementów listy. Quicksort działa dla 
dowolnego, wybranego do podziału elementu - niekoniecznie środkowego.
W ten sposób parę razy niepotrzebnie biegasz po liście (drop,
reverse). Być może bredzę (czegoś nie zrozumiałem), ale wydaje mi się,
że takie coś również zadziała i to pewnie szybciej:

#v+
rozna_lista2 :: Ord a => [ a ] -> Bool
rozna_lista2 [] = True 
rozna_lista2 l = let m = head l
                     in
                 length ( [a | a <- l, a == m] ) == 1 &&
                 rozna_lista2 [ a | a <- l , a < m ] &&
                 rozna_lista2 [ a | a <- l , a > m ]
#v-

Jest w miarę zwięźle ale biegamy po liście 3 razy. Z akumulatorem byłoby
tylko raz.

-- 
Pasza
JMS dla MIDP - http://jmsme.sf.net
pasza (at) zodiac.mimuw.edu.pl

> Przeczytałem ten kod i nie bardzo rozumiem, po co wyznaczasz tam medianę
> ze środkowego i skrajnych elementów listy. Quicksort działa dla 
> dowolnego, wybranego do podziału elementu - niekoniecznie środkowego.
> W ten sposób parę razy niepotrzebnie biegasz po liście (drop,
> reverse). Być może bredzę (czegoś nie zrozumiałem), ale wydaje mi się,
> że takie coś również zadziała i to pewnie szybciej:

Wyznaczam medianę, gdyż w Twoim przypadku QuickSort robi się kwadratowy
dla posortowanego ciągu. A akurat listy, które potem przeglądam mają w
przeważnie postać [a..b] ++ [c..d], b < c.

QuickSort z glibca też tak działa, więc jest to chyba spoko. Oczywiście
takiego też można ukwadracić, ale to już raczej ciężkie jest.

Pozdrawiam,
-- 
Marcin Gajda ________________________
Dieu me pardonerra - c'est son metier

Dnia Sun, 15 Jun 2003 21:35:45 +0000 (UTC), Marcin Gajda napisał(a):
> Wyznaczam medianę, gdyż w Twoim przypadku QuickSort robi się kwadratowy
> dla posortowanego ciągu. A akurat listy, które potem przeglądam mają w
> przeważnie postać [a..b] ++ [c..d], b < c.
> 
> QuickSort z glibca też tak działa, więc jest to chyba spoko. Oczywiście
> takiego też można ukwadracić, ale to już raczej ciężkie jest.

QuickSort w glibc`u działa jak się spodziewam na tablicach, a nie na
listach. Tam sięgasz do środkowego elementu w czasie stałym, tutaj
liniowo. Nic nie wiem o rodzaju danych, które chcesz przetwarzać, ale
dla losowego przypadku wybieranie pierwszego elementu jest zupełnie
znośne. Czy tak często zamierzasz sprawdzać listy uporządkowane? Nie 
wiem czy w tym przypadku narzut na bieganie po liście nie kosztuje
więcej niż daje korzyści.

-- 
Pasza
JMS dla MIDP - http://jmsme.sf.net
pasza (at) zodiac.mimuw.edu.pl

> QuickSort w glibc`u działa jak się spodziewam na tablicach, a nie na
> listach. Tam sięgasz do środkowego elementu w czasie stałym, tutaj
> liniowo. Nic nie wiem o rodzaju danych, które chcesz przetwarzać, ale
> dla losowego przypadku wybieranie pierwszego elementu jest zupełnie
> znośne. Czy tak często zamierzasz sprawdzać listy uporządkowane? Nie 
> wiem czy w tym przypadku narzut na bieganie po liście nie kosztuje
> więcej niż daje korzyści.

Jak już wcześniej napisałem - listy są "prawie" zawsze "prawie" posortowane.
Mógłbym użyć innego, sprytnego algorytmu, ale miałem nadzieję na znośne
działanie tego naiwnego. Tymczasem kicha.

Liniowość wyboru mediany nie psuje złożoności Quicksorta (w sensie
notacji O), choć tutaj masz rację - w tym przypadku pozostaje już chyba
tylko walka o stałą pożeraną przez tę notację.

Pozdrawiam i dzięki,
	
	PS: Jutro, w miarę wolnego czasu postaram się opisać problem, do
	którego to było mi potrzebne i moje rozwiązanie - może to pomoże
	w jego zoptymalizowaniu.
-- 
Marcin Gajda ________________________
Dieu me pardonerra - c'est son metier

Marcin Gajda napisał:
> Witam,

Nie mam teraz za dużo czasu, więc tylko rzucę dwie propozycje:

module A where

import Control.Monad.Cont
import Control.Monad
import Data.Set
import List

powt1 :: Ord a => [a] -> Bool
powt1 l = 
    runCont (callCC (\exit -> foldM (step exit) emptySet l >> return False)) id
  where
    step exit set x = do
        when (x `elementOf` set) (exit True)
        return (addToSet set x)

powt2 :: Ord a => [a] -> Bool
powt2 l = any (> 1) (map length (group (sort l)))

> Pozdrawiam,

pozdrawiam,
tomek

-- 
.signature: Too many levels of symbolic links

Marcin Gajda napisał:
> Witam,
> 
> nie szukałem za bardzo w Prelude i modułach, ale potrzebuję funkcji
> określającej, czy w liście nie ma powtórzeń. Do głowy przyszło mi takie
> cudo poniżej, lecz na hugsie dla [1..10000] (specjalnie złośliwy
> przypadek, aby wywalić naiwnego quicksorta) działa już trochę za długo:

Dlaczego nie używasz GHC/GHCi ?

pozdrawiam,
tomek

-- 
.signature: Too many levels of symbolic links

> Dlaczego nie używasz GHC/GHCi ?

Ponieważ nie mogę doprosić się u Qboosha, aby zrobił paczkę z GHC dla
PLD. A sam nie mogę, bo ghc.spec do zbudowania wymaga ... ghc.

A nie chcę sobie śmiecić po systemie instalkami spoza paczek.

Pozdrawiam,
-- 
Marcin Gajda ________________________
Dieu me pardonerra - c'est son metier

> powt2 :: Ord a => [a] -> Bool
> powt2 l = any (> 1) (map length (group (sort l)))

Dzięki. Przez pierwsze poprzegryzam się wieczorem. A to wygląda badzo
fajnie - gdybym wiedział o istnieniu group, może nawet sam bym na wpadł.

Pozdrawiam,
-- 
Marcin Gajda ________________________
Dieu me pardonerra - c'est son metier

Dnia Mon, 16 Jun 2003 12:45:08 +0000 (UTC), Marcin Gajda napisał(a):
>> Dlaczego nie używasz GHC/GHCi ?
> 
> Ponieważ nie mogę doprosić się u Qboosha, aby zrobił paczkę z GHC dla
> PLD. A sam nie mogę, bo ghc.spec do zbudowania wymaga ... ghc.
> 
> A nie chcę sobie śmiecić po systemie instalkami spoza paczek.

A jakie masz glibc w tym PLD? Ja w swoim mam 2.3 i zainstalowałem
paczkę dla rh 9 (jest na stronie ghc) i działa. Rozrzucenie plików
po katalogach jest takie jakie pewnie by było w PLD. Jeśli masz 2.2
to raczej nie pójdzie.

Próbowałem potem dla sportu przebudować pakiet z cvs`a PLD, ale
nie udało mi się (jakiś błąd podczas kompilacji).

ps. niedawno wyszedł nowy ghc: 6
ps2. zawsze możesz zainstalować w /usr/local, to chyba do tego służy,
     ja mam tak zainstalowanego sml-nj, bo dystrybucyjny jest schrzaniony

-- 
Pasza
JMS dla MIDP - http://jmsme.sf.net
pasza (at) zodiac.mimuw.edu.pl

Marcin Gajda napisał:
>> powt2 :: Ord a => [a] -> Bool
>> powt2 l = any (> 1) (map length (group (sort l)))
> 
> Dzięki. Przez pierwsze poprzegryzam się wieczorem. A to wygląda badzo
> fajnie - gdybym wiedział o istnieniu group, może nawet sam bym na wpadł.

Można to prościej zapisać:

  powt2 :: Ord a => [a] -> Bool
  powt2 = any (> 1) . map length . group . sort

Jeśli jednak sort jest zaimplementowany przez qsort, to chyba nadal masz
problem?

> Pozdrawiam,

pozdrawiam,
tomek

-- 
.signature: Too many levels of symbolic links

Marcin Gajda napisał:
>> Dlaczego nie używasz GHC/GHCi ?
> 
> Ponieważ nie mogę doprosić się u Qboosha, aby zrobił paczkę z GHC dla
> PLD. A sam nie mogę, bo ghc.spec do zbudowania wymaga ... ghc.
> 
> A nie chcę sobie śmiecić po systemie instalkami spoza paczek.

To zainstaluj sobie GHC na swoim koncie, in-place. Ściągasz sobie np.
http://www.haskell.org/ghc/dist/5.04.3/ghc-5.04.3-i386-unknown-linux.tar.bz2,
rozpakowujesz, robisz ./configure i make in-place, dodajesz
.../ghc-5.04.3/bin/i386-unknown-linux do PATH i masz (przy założeniu, że
pracujesz na i386 i masz odpowiednie wersje bibliotek).

Ostatnio wyszła wersja 6.0, której jednak nie polecam na początek, bo ma
jeden odstraszający błąd w trybie interaktywnym.

> Pozdrawiam,

pozdrawiam,
tomek

-- 
.signature: Too many levels of symbolic links

> A jakie masz glibc w tym PLD? Ja w swoim mam 2.3 i zainstalowałem
> paczkę dla rh 9 (jest na stronie ghc) i działa. Rozrzucenie plików
> po katalogach jest takie jakie pewnie by było w PLD. Jeśli masz 2.2
> to raczej nie pójdzie.

No... nesta mam oczywiście! Tak chyba zrobię - nie musiałeś samemu
zgadywać jakichś dependencji?

-- 
Marcin Gajda ________________________
Dieu me pardonerra - c'est son metier

Dnia Mon, 16 Jun 2003 20:54:49 +0000 (UTC), Marcin Gajda napisał(a):
> No... nesta mam oczywiście! Tak chyba zrobię - nie musiałeś samemu

:)), to nie upgradeuj X`ow ani glibc`a (glibc się nie instaluje, a w
X`ach jakieś problemy z klawiaturą) :)

> zgadywać jakichś dependencji?

Nie - poszedł od razu. Jest sensownie zrobiony bo nie wymaga
konkretnych pakietów tylko bibliotek luzem (libc.so.6, libgmp.so.3,
...).

-- 
Pasza
JMS dla MIDP - http://jmsme.sf.net
pasza (at) zodiac.mimuw.edu.pl

> :)), to nie upgradeuj X`ow ani glibc`a (glibc się nie instaluje, a w
> X`ach jakieś problemy z klawiaturą) :)

Pisząc nesta mam na myśli właśnie m.in. glibc 2.3 i X 4.3. I wszystko mi
to bangla ładnie. Prawie wszystko - gv mi się wywala. Tak samo zbudować
się nie chce. Ale to już inna historia....

> Nie - poszedł od razu. Jest sensownie zrobiony bo nie wymaga
> konkretnych pakietów tylko bibliotek luzem [...]

Ok - to już zasysam.

Pozdrawiam,
-- 
Marcin Gajda ________________________
Dieu me pardonerra - c'est son metier

Dnia Mon, 16 Jun 2003 21:27:40 +0000 (UTC), Marcin Gajda napisał(a):
>> :)), to nie upgradeuj X`ow ani glibc`a (glibc się nie instaluje, a w
>> X`ach jakieś problemy z klawiaturą) :)
 
> Pisząc nesta mam na myśli właśnie m.in. glibc 2.3 i X 4.3. I wszystko mi
> to bangla ładnie. Prawie wszystko - gv mi się wywala. Tak samo zbudować
> się nie chce. Ale to już inna historia....

tak, ja też - tylko teraz jakiś nowy build 2.3 jest i X`y 4.3.99,
na laptopie upgradenąłem i się średnio pracować daje :), z gv akurat 
nie mam problemów, ale to tak OT :)

-- 
Pasza
JMS dla MIDP - http://jmsme.sf.net
pasza (at) zodiac.mimuw.edu.pl