🚀 go-pugleaf

On Wed, 29 Oct 1997 15:22:02 +0100, "B. Kustowski st."
<bo...@geolog.geol.agh.edu.pl> wrote:

>
>	Potrzebuje posortowac plik (kilkadziesiat mln danych) pod unixem.
>Bylbym wdzieczny za namiary na odpowiedni programik sortujacy i jego
>algorytm.
>	Dzieki

Przychodzi mi do glowy pomysl potworny, ale za to prosty:

Wybrac najmniejsza dana i zapisac do wyniku;
while (nie wybralismy jeszcze wszystkiego)
  Wybrac najmniejsza dana wieksza od ostatniej i zapisac do wyniku;

Jest to takie BFI, ze mozg staje, ale proste i skuteczne, jezeli
masz danych za duzo dla pamieci i na szybkosci ci nie zalezy.

		Pawel Pluta


I niechaj mowa wasza bedzie 1, 1, 0, 0.
         A wszystko co wiecej jest, ode zlego jest.

Pawe=B3 Pluta wrote:
> =

> On Wed, 29 Oct 1997 15:22:02 +0100, "B. Kustowski st."
> <bo...@geolog.geol.agh.edu.pl> wrote:
> =

> >
> >       Potrzebuje posortowac plik (kilkadziesiat mln danych) pod unixe=
m.
> >Bylbym wdzieczny za namiary na odpowiedni programik sortujacy i jego
> >algorytm.
> >       Dzieki
> =

> Przychodzi mi do glowy pomysl potworny, ale za to prosty:
> =

> Wybrac najmniejsza dana i zapisac do wyniku;
> while (nie wybralismy jeszcze wszystkiego)
>   Wybrac najmniejsza dana wieksza od ostatniej i zapisac do wyniku;

O matko... To znaczy, ze chcesz za kazdym razem przegladac wszystkie
dane? To bedzie n^2 porownan. Jezeli to n jest rzedu kilkudziesieciu
milionow, to ladnie...

	pozdrawiam :)

-- =

gracjan zi=F3=B3ek
administrator system=F3w
mailto:gz...@celebris.bdk.lublin.pl
http://ajax.umcs.lublin.pl/~gracjanz/

Inst.Maszyn Matemat. wrote:
> =

> Gracjan =3D?iso-8859-2?Q?Zi=3DF3=3DB3ek?=3D (gzio@celebris.bdk.lublin.p=
l) wrote:
> : Jezeli jest to plik tekstowy (watpie :)), to zawsze mozna uzyc 'sort'=
=2E
> : Algorytm jest do sprawdzenia w pliku zrodlowym (a jezeli nie masz
> : takiego, to mozesz znalezc na sieci). Natomiast jezeli dane sa w post=
aci
> : jakichs rekordow itp., to nie pozostaje nic innego, niz napisac samem=
u.
> : Bo uniwersalnych narzedzi do sortowania wszystkiego, to raczej nie ma=
 :)
> =

>   Poprawka: jesli dane sa w "postaci rekordow", to tez mozna uzyc
> standardowej funkcji bibliotecznej qsort (quick-sort). Jest on
> oparty zazwyczaj na szybkim sortowaniu Hoare'a. Trzeba tylko
> napisac odpowiednia funkcje porownujaca rekordy.
>   Inna sprawa jest sortowanie tak wielu elementow, ze nie mieszcza
> sie one np. w jednej tablicy, czy szerzej: w pamieci operacyjnej.
> Wtedy trzeba uzyc takiej czy innej formy sortowania czastkowego:
[...]
>   Jest to typowy sposob sortowania duzych plikow. Program taki
> mozna napisac w dosc krotkim czasie (pomijam sprawe doboru
> rozmiaru plikow roboczych, ich liczby itd.)

Troche dluzej ujales to, co i ja chcialem napisac - ze na tak postawione
pytanie nie sposob precyzyjnie odpowiedziec. Wszystko zalezy od formatu
danych. Bo jezeli plik jest binarny i sklada sie z rekordow, przy czym =

ma on (plik) naglowek, w ktorym zapisana jest np. ich liczba, to nie da
sie juz tak po protsu go dzielic i sortowac. Trzeba cos napisac :)

	pozdrawiam

-- =

gracjan zi=F3=B3ek
administrator system=F3w
mailto:gz...@celebris.bdk.lublin.pl
http://ajax.umcs.lublin.pl/~gracjanz/

On Wed, 29 Oct 1997 16:33:55 -0800, Gracjan =?iso-8859-2?Q?Zi=F3=B3ek?=
<gz...@celebris.bdk.lublin.pl> wrote:

>Pawe=B3 Pluta wrote:
[...]
>> Przychodzi mi do glowy pomysl potworny, ale za to prosty:
>> =
>
>> Wybrac najmniejsza dana i zapisac do wyniku;
>> while (nie wybralismy jeszcze wszystkiego)
>>   Wybrac najmniejsza dana wieksza od ostatniej i zapisac do wyniku;
>
>O matko... To znaczy, ze chcesz za kazdym razem przegladac wszystkie
>dane? To bedzie n^2 porownan. Jezeli to n jest rzedu kilkudziesieciu
>milionow, to ladnie...

Racja, nie liczylem zlozonosci, ale rzeczywiscie n^2. No ale pisalem:
pomysl jest potworny. :-)

>
>	pozdrawiam :)
>
>-- =
>
>gracjan zi=F3=B3ek
>administrator system=F3w
>mailto:gz...@celebris.bdk.lublin.pl
>http://ajax.umcs.lublin.pl/~gracjanz/

		Pawel Pluta


I niechaj mowa wasza bedzie 1, 1, 0, 0.
         A wszystko co wiecej jest, ode zlego jest.

Andrzej Bialecki (ab...@korin.warman.org.pl) wrote:

: Oj, chyba niezupelnie... :-) To jest owszem sposob dobry na DOSa, ktory
: sam w sobie ma zarzadzania pamiecia tyle, co kot naplakal. Ale w kazdym
: przyzwoitym unixie (BSD, Linux, Sun) od tego jest zarzadzanie pamiecia
: wirtualna, zeby nie musiec sie tym przejmowac. Oczywiscie, kiedy system
: zacznie page'owac, bedzie to znacznie wolniej szlo, ale pewnie i tak szybciej,
: niz wlasnorecznie napisany algorytm page'owania :-)

: Ja bym po prostu wzial qsort() i nie przejmowal sie - byleby wystarczylo swapa.

  Byc moze, tyle ze przy takim sposobie pracy tworzy Pan program
w jezyku C, ktory jest calkowicie nieprzenosny. Musi Pan uzywac
modeli pamieci, ktore pozwola obslugiwac tak duze obszary pamieci
(chodzi glownie o sposoby adresowania, dodatkowe handles, itp.)
To sa rzeczy zalezne i od kompilatora i od systemu operacyjnego.
Wersja przeze mnie zaproponowana ma te zalete, ze jest calkowicie
przenosna do dowolnych kompilatorow i systemow operacyjnych.
A jednym z przykazan dobrego stylu programowania jest, by
programowac maksymalnie przenosnie. 

  Marek Kotowski

  Instytut Maszyn Matematycznych

Inst.Maszyn Matemat. (ima...@warman.com.pl) wrote:
: Andrzej Bialecki (ab...@korin.warman.org.pl) wrote:

: : Oj, chyba niezupelnie... :-) To jest owszem sposob dobry na DOSa, ktory
: : sam w sobie ma zarzadzania pamiecia tyle, co kot naplakal. Ale w kazdym
: : przyzwoitym unixie (BSD, Linux, Sun) od tego jest zarzadzanie pamiecia
: : wirtualna, zeby nie musiec sie tym przejmowac. Oczywiscie, kiedy system
: : zacznie page'owac, bedzie to znacznie wolniej szlo, ale pewnie i tak szybciej,
: : niz wlasnorecznie napisany algorytm page'owania :-)

: : Ja bym po prostu wzial qsort() i nie przejmowal sie - byleby wystarczylo swapa.

:   Byc moze, tyle ze przy takim sposobie pracy tworzy Pan program
: w jezyku C, ktory jest calkowicie nieprzenosny. Musi Pan uzywac

??? No, niezupelnie calkowicie.... Na dowolnym systemie operacyjnym z
prawdziwego zdarzenia (==obslugujacym pamiec wirtualna) bedzie to chodzic.
Nie zapominajmy, ze DOS to nie *system operacyjny*, tylko bootloader :-)

Ze znanymi mi *systemami* (czyli BSD, Linux, SCO, SunOS i pewnie NT) nie
byloby problemow.

: modeli pamieci, ktore pozwola obslugiwac tak duze obszary pamieci
: (chodzi glownie o sposoby adresowania, dodatkowe handles, itp.)
: To sa rzeczy zalezne i od kompilatora i od systemu operacyjnego.

J/w. Oj, pachnie mi tu DOSem...

: Wersja przeze mnie zaproponowana ma te zalete, ze jest calkowicie
: przenosna do dowolnych kompilatorow i systemow operacyjnych.
: A jednym z przykazan dobrego stylu programowania jest, by
: programowac maksymalnie przenosnie. 

To prawda. Ale wydaje mi sie, ze patrzy Pan na ten problem z perspektywy
DOSu, a jest to raczej wyjatkowy przypadek, i pisanie w C pod tym katem
na pewno nie przyczynia sie do przenosnosci.

A po przeniesieniu takiego programu z DOSa do unixa okzaloby sie wlasnie,
ze robi on to samo, co robi jadro systemu, tyle ze zalosnie nieefektywnie.

I na koniec jeszcze chcialem zwrocic uwage, ze autor pytania ma to zrobic
wlasnie pod unixem.

--

Andrzej Bialecki

---------------------+---------------------------------------------------------
ab...@warman.org.pl  | if(halt_per_mth > 0) { fetch("http://www.freebsd.org") }
Research & Academic  | "Be open-minded, but don't let your brains to fall out."
Network in Poland    | All of the above (and more) is just my personal opinion.
---------------------+---------------------------------------------------------

B. Kustowski st. napisał(a) w artykule ...

>
> Potrzebuje posortowac plik (kilkadziesiat mln danych) pod unixem.
>Bylbym wdzieczny za namiary na odpowiedni programik sortujacy i jego
>algorytm.
> Dzieki
>
>

Proponowalbym uzyc do tego B-drzewa. Jest to o ile wiem najszybsza znana
dotychczas metoda sortowania tak duzych ilosci danych i w odróznieniu od
pomyslów przedstawionych na liscie przede mna jest ona praktyczna.
Niestety nie znam nazwy programiku który by to robil, nie jest jednak
duza filozofia napisac taki program samemu, aczkolwiek troche
napracowac sie trzeba jezeli sie nie dysponuje gotowa biblioteka z
zaimplementowanym B-drzewem.

pozdrawiam
Porkis

porkis@kki.net.pl - jesli nie dziala spróbuj:
@bbs.chip.pl, @polbox.com, @tempus.ii.uni.wroc.pl
http://polbox.com/p/porkis, http://www.kki.net.pl/porkis

On 30 Oct 1997 17:16:58 GMT, piotras@zeus.polsl.gliwice.pl (Piotr
Auksztulewicz) wrote:

[...]
>: Wybrac najmniejsza dana i zapisac do wyniku;
>: while (nie wybralismy jeszcze wszystkiego)
>:   Wybrac najmniejsza dana wieksza od ostatniej i zapisac do wyniku;
>
>Zwariowales?! Zlozonosc n^2! dla 100 rekordow to pal szesc, ale dla ~ 10^7 ???

No dobra, nie zebym sie upieral przy metodzie, ale mozna to tak zmodyfikowac,
zeby alokowac ile sie da pamieci (nie wnikam, co to znaczy 'ile sie da')
i zrobic tam strukture, ktora bedzie trzymac, powiedzmy, dla rownego rachunku,
1024 najmniejsze rekordy. A tyle to i tak jeszcze nie bedzie duzo, bo troche
RAMu przy takich plikach danych pewnie tez jest. Inna sprawa, ze zalezy ile to
jest jeden rekord. Po wybieraniu takich blokow to juz roboty bedzie mniej,
nie? Tylko jeszcze szybki algorytm porownywania. Z tego, co pamietam drzewo
sie calkiem ladnie nada.

>: Jest to takie BFI, ze mozg staje, ale proste i skuteczne, jezeli
>: masz danych za duzo dla pamieci i na szybkosci ci nie zalezy.
>
[...]

		Pawel Pluta


I niechaj mowa wasza bedzie 1, 1, 0, 0.
         A wszystko co wiecej jest, ode zlego jest.

Andrzej Bialecki (abial@korin.warman.org.pl) wrote:
[...]
: To prawda. Ale wydaje mi sie, ze patrzy Pan na ten problem z perspektywy
: DOSu, a jest to raczej wyjatkowy przypadek, i pisanie w C pod tym katem
: na pewno nie przyczynia sie do przenosnosci.
[...]

  Pozwolilem sobie zachowac tylko te czesc Pana wypowiedzi,
bo jest ona chyba typowa dla calosci.
  Czesciowo juz odpowiedzial na Pana watpliwosci Pan Grzegorz
Grudzinski. Dodam do tego dwie uwagi:

1. Pracuje teraz w Windows'95 i uzywam kompilatora BC 4.5. Tu jest
   rowniez ograniczenie na rozmiar tablic, jakie mozna deklarowac
   w programie jako statyczne, czy alokowac dynamicznie. Model
   huge, jakiego mozna uzyc, nie jest bynajmniej rozwiazaniem,
   albowiem dziala on roznie na roznych kompilatorach. Ponadto
   i jego mozliwosci sa ograniczone. Pisze o tym, by Pan nie
   sadzil, ze problem dotyczy tylko DOS-u.

2. Obawiam sie, ze roznimy sie zupelnie w rozumieniu tego, co
   to jest przenosnosc programu. Nie wdajac sie w definicje
   powiem, ze z punktu widzenia standardu ANSI C najwiekszy
   obiekt danych, jaki sie w programie tworzy, nie moze prze-
   kraczac 32767 bajtow. W przeciwnym razie program staje 
   sie formalnie nieprzenosny (kompilatory zgodne ze standardem
   nie musza obslugiwac wiekszych obiektow). Wszystkie znane 
   mi definicje programu przenosnego zakladaja, ze nie przekracza 
   on tego limitu rozmiaru danych. Panskie rozwiazanie limit
   ten przekracza - moje nie. Tym samym Panskie rozwiazanie
   z zasady jest nieprzenosne.

3. Inna sprawa, ze jak sie ma problem np. z sortowaniem 
   wielkich plikow, to sie czesto o przenosnosci programu
   nie mysli. Byleby udalo sie go gdziekolwiek uruchomic
   i wykonac poprawnie.
   
   Marek Kotowski

   Instytut Maszyn Matematycznych

Jacek: [pl.comp.lang.c: Thu, 30 Oct 1997 23:00:57 +0100]
: Proponowalbym uzyc do tego B-drzewa. Jest to o ile wiem najszybsza znana
[...]

w zasadzie racja... ale po co sie tak meczyc;
wystarczy:
- podzielic plik na czesci tak duze, jak duze porcje mozemy sortowac
  w pamieci, 
- posortowac kazda
- potem parami merdzowac
- wyniki znowu parami merdzowac, itd.

to bedzie bardzo szybkie, a w unixie da sie zaimplementowac kilkulinijkowym
skryptem, pod dosem/winda kilkunastolinijkowym programem...

robert
-- 
robmar@mimuw.edu.pl                  http://zls.mimuw.edu.pl/~robmar/

On 30 Oct 1997, Grzegorz Grudzinski wrote:

> abial@korin.warman.org.pl (Andrzej Bialecki) writes:
> 
> > ??? No, niezupelnie calkowicie.... Na dowolnym systemie operacyjnym

> Nie, pachnie raczej znajomoscia analizy algorytnow, a nie mysleniem
> zyczeniowym i brakiem zrozumienia zastosowan pamieci wirtualnej.

Z ciekawosci jednak sprobowalem (napisanym na kolanie programem o dlugosci
kilkudziesieciu linii - bo tez musialem sobie stworzyc odpowiednie dane). 
Programik posortowal mi plik 100MB w 5 minut (na Pentium 133/FreeBSD),
uzywajac metody qsort(). Oczywiscie swapowal co nie miara (dlatego tez tak
dlugo to trwalo), ale na systemie dalo sie sensownie pracowac. 

Mysle, ze jak na poczatek, nie byl to taki zly czas :-) a cel zostal
osiagniety.

Natomiast rzeczywiscie, gdybym mial to robic kilka razy na dzien, to
pobawilbym sie we wlasne algorytmy.

Andrzej Bialecki

PS. Jakby ktos chcial sprobowac, to zalaczam programik.

---------------------+---------------------------------------------------------
abial@warman.org.pl  | if(halt_per_mth > 0) { fetch("http://www.freebsd.org") }
Research & Academic  | "Be open-minded, but don't let your brains to fall out."
Network in Poland    | All of the above (and more) is just my personal opinion.
---------------------+---------------------------------------------------------


#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <sys/types.h>
#include <unistd.h>

#define DATASIZE 200
#define ELCOUNT	500000

struct proba {
	char data[DATASIZE];
};

int
proba_cmp(struct proba *first, struct proba *second)
{
	return(strncmp(first->data,second->data,DATASIZE));
}

int
main(int argc, char *argv[])
{
	int i,j,k;
	int fd;
	char c;
	struct proba p;
	struct proba *beast;

	fd=open("proba.dat",O_RDWR|O_CREAT|O_TRUNC,0600);
	if(fd==0) {
		perror("open");
		exit(1);
	}
	printf("Writing file...\n");
	c=' ';
	for (i=0;i<ELCOUNT;i++) {
		for(j=0;j<DATASIZE;j++) {
			p.data[j]=c++;
			if(c>'}') c=' ';
		}
		write(fd,&p,sizeof(struct proba));
	}
	beast=malloc(ELCOUNT*sizeof(struct proba));
	lseek(fd,(off_t)0,SEEK_SET);
	printf("Reading it back...\n");
	for(i=0;i<ELCOUNT;i++) {
		read(fd,(beast+i),sizeof(struct proba));
	}
	close(fd);
	printf("Sorting it...\n");
	qsort(beast,ELCOUNT,sizeof(struct proba),proba_cmp);
	printf("Writing output...\n");
	fd=open("proba.out",O_RDWR|O_CREAT|O_TRUNC,0600);
	c='\n';
	for(i=0;i<ELCOUNT;i++) {
		write(fd,(beast+i),sizeof(struct proba));
		write(fd,&c,sizeof(char));
	}
	close(fd);
	free(beast);
	exit(0);
}

On 30 Oct 1997, Grzegorz Grudzinski wrote:

> abial@korin.warman.org.pl (Andrzej Bialecki) writes:
> 
> > Inst.Maszyn Matemat. (imasmat@warman.com.pl) pisze:
> > : Andrzej Bialecki (abial@korin.warman.org.pl) wrote:
> > 
> > ??? No, niezupelnie calkowicie.... Na dowolnym systemie operacyjnym

> No jednak calkowicie. Pomijajac to, ze ilosc wolnego miejsca na dysku

[ciach]

> Nie, pachnie raczej znajomoscia analizy algorytnow, a nie mysleniem
> zyczeniowym i brakiem zrozumienia zastosowan pamieci wirtualnej.

No niee... Moze rzeczywiscie zbyt jednostronnie to ujalem. Zgadzam sie, ze
sa przypadki, kiedy nalezy samemu oprogramowac pamiec wirtualna, i
rzeczywiscie sortowanie (ktore tworzy duzy zbior roboczy stron) w
ogolnosci jest takim przypadkiem. Howgh.

ALE... w sporej czesci takich przypadkow mechanizmy systemowe sa
wystarczajace (i na poczatku lepsze, niz proby stworzenia czegos od zera).
Chodzilo mi o to, ze latwiej i szybciej bedzie gosciowi skorzystac z
gotowych mechanizmow, jesli ma posortowac od czasu do czasu jeden plik. 

Przykro mi, ze zabrzmialo to jak wymadrzanie. Chcialem facetowi
zaoszczedzic pracy (moim zdaniem, niepotrzebnej na tym etapie - moglby
sobie potem to zoptymalizowac).

> Przepraszam za zbyt ostry ton wypowiedzi, ale irytuje mnie wymadrzanie
> sie w sytuacji, gdy nalezy raczej przyznac racje komus, kto sie
> ewidentnie zna lepiej.

Nie szkodzi - chetnie sie ucze od innych, byleby dyskusja byla cenzuralna
:-)). Wydaje mi sie, ze rozumiem, jak dziala pamiec wirtualna, ale chetnie
sie dowiem czegos nowego.  Powaznie :-) 

Andrzej Bialecki

---------------------+---------------------------------------------------------
abial@warman.org.pl  | if(halt_per_mth > 0) { fetch("http://www.freebsd.org") }
Research & Academic  | "Be open-minded, but don't let your brains to fall out."
Network in Poland    | All of the above (and more) is just my personal opinion.
---------------------+---------------------------------------------------------

Inst.Maszyn Matemat. (imasmat@warman.com.pl) wrote:
: Andrzej Bialecki (abial@korin.warman.org.pl) wrote:
: [...]
: : To prawda. Ale wydaje mi sie, ze patrzy Pan na ten problem z perspektywy
: : DOSu, a jest to raczej wyjatkowy przypadek, i pisanie w C pod tym katem
: : na pewno nie przyczynia sie do przenosnosci.
: [...]

: 1. Pracuje teraz w Windows'95 i uzywam kompilatora BC 4.5. Tu jest

:    i jego mozliwosci sa ograniczone. Pisze o tym, by Pan nie
:    sadzil, ze problem dotyczy tylko DOS-u.

Jasne. Odwoluje moje zbyt pochopne wnioski.

: 2. Obawiam sie, ze roznimy sie zupelnie w rozumieniu tego, co
:    to jest przenosnosc programu. Nie wdajac sie w definicje
:    powiem, ze z punktu widzenia standardu ANSI C najwiekszy
:    obiekt danych, jaki sie w programie tworzy, nie moze prze-
:    kraczac 32767 bajtow. W przeciwnym razie program staje 
:    sie formalnie nieprzenosny (kompilatory zgodne ze standardem
:    nie musza obslugiwac wiekszych obiektow). Wszystkie znane 
:    mi definicje programu przenosnego zakladaja, ze nie przekracza 
:    on tego limitu rozmiaru danych. Panskie rozwiazanie limit
:    ten przekracza - moje nie. Tym samym Panskie rozwiazanie
:    z zasady jest nieprzenosne.

Hmmm... A jak to definiuje POSIX? Pytam, bo nie wiem. Wydaje mi sie, ze 
jest to nowszy standard, ktory na wielu systemach jest mniej lub bardziej
realizowany.

: 3. Inna sprawa, ze jak sie ma problem np. z sortowaniem 
:    wielkich plikow, to sie czesto o przenosnosci programu
:    nie mysli. Byleby udalo sie go gdziekolwiek uruchomic
:    i wykonac poprawnie.

Wlasnie o to mi chodzilo. Zrozumialem, ze autorowi pytania nie chodzilo
o rozwiazanie, ktore by mu dzialalo zawsze i wszedzie, ale ze mial
konkretny problem do rozwiazania. Dlatego tez osmielilem sie wyprobowac
na wlasnej skorze proponowane przeze mnie rozwiazanie (opisalem je w
innym postingu). IMVHO, nie jest jednak takie najgorsze :-) a napisalem
je w kilka chwil. Natomiast nie zabralbym sie za to, gdybym musial od
razu wymyslac obsluge pamieci.

--

Andrzej Bialecki

---------------------+---------------------------------------------------------
abial@warman.org.pl  | if(halt_per_mth > 0) { fetch("http://www.freebsd.org") }
Research & Academic  | "Be open-minded, but don't let your brains to fall out."
Network in Poland    | All of the above (and more) is just my personal opinion.
---------------------+---------------------------------------------------------

Andrzej Bialecki wrote:
> Hmmm... A jak to definiuje POSIX? Pytam, bo nie wiem. Wydaje mi sie, ze
> jest to nowszy standard, ktory na wielu systemach jest mniej lub bardziej
> realizowany.

  Tez chcialbym wiedziec, ale w Internecie nie ma opisu POSIX-a,
chociaz, jak mi odpowiedziano na email, pracuje sie nad tym. 
Niemniej watpie, by POSIX dawal tu wieksze mozliwosci. W istocie
rzecz bardziej w adresacji pamieci w komputerach, niz w tym, co
sie deklaruje w standardach, ktore przeciez staraja sie na ogol
obejmowac mozliwosci maksymalnie duzej liczby roznych maszyn.

  Powiem jeszcze, ze w nowym przygotowywanym standardzie ANSI C
(rok ukonczenia 1999) proponuje sie, by limit rozmiaru obiektu 
danych w programie przenosnym zwiekszyc dwukrotnie (64K). Oznaczaloby
to, ze kazdy kompilator zgodny z ANSI C musialby umozliwiac prace
na takich obiektach. 

  I na koniec: POSIX mial kilka wersji. Ale powolywanie sie na to, ze
jest "nowszy", jest, moim zdaniem, dyskusyjne. Nie chodzi o "nowszosc".
Za wersje standardowa jezyka C lub - wprost - za jezyk C przyjmuje
sie wersje ANSI C. I w odniesieniu do niej definiuje przenosnosc.

  Marek Kotowski
  Instytut Maszyn Matematycznych

Inst.Maszyn Matemat. wrote:
> 
> 1. Pracuje teraz w Windows'95 i uzywam kompilatora BC 4.5. Tu jest
>    rowniez ograniczenie na rozmiar tablic, jakie mozna deklarowac
>    w programie jako statyczne, czy alokowac dynamicznie. Model
>    huge, jakiego mozna uzyc, nie jest bynajmniej rozwiazaniem,
>    albowiem dziala on roznie na roznych kompilatorach. Ponadto
>    i jego mozliwosci sa ograniczone. Pisze o tym, by Pan nie
>    sadzil, ze problem dotyczy tylko DOS-u.
> 
Radze przestawic sie na 32-bitowe programowanie. Nie ma takich
ograniczen, ani zadnych roznych modeli, tylko jeden: flat. Bardzo
przyjemnie sie pisze wtedy programy :-)
-- 
 __________________________________________________________________
| full name: Krzysztof Goworek, sex: male, occupation: developer   |
| mailto:kabel@zeus.polsl.gliwice.pl || mailto:krzys@aplusc.com.pl |
|__________________________________________________________________|

On 30 Oct 1997, Andrzej Bialecki wrote:

> Oj, chyba niezupelnie... :-) To jest owszem sposob dobry na DOSa, ktory
> sam w sobie ma zarzadzania pamiecia tyle, co kot naplakal. Ale w kazdym
> przyzwoitym unixie (BSD, Linux, Sun) od tego jest zarzadzanie pamiecia
> wirtualna, zeby nie musiec sie tym przejmowac. Oczywiscie, kiedy system
> zacznie page'owac, bedzie to znacznie wolniej szlo, ale pewnie i tak
> szybciej, niz wlasnorecznie napisany algorytm page'owania :-)
> 
> Ja bym po prostu wzial qsort() i nie przejmowal sie - byleby wystarczylo
> swapa.

Oj, niekoniecznie! Różne algorytmy sortowania mają różny styl dostępu do
elementów tablicy - jedne działają bardziej lokalnie, inne skaczą po całej
tablicy. Ponieważ w naszym przypadku to nie jest wszystko jedno i dostęp
do pamięci zajmuje różny czas w zależności od kolejności tych dostępów,
lepiej zastosować jakiś algorytm z'optymalizowany pod tym kątem, a nie
ten, który ma najmniejszy formalny koszt.

QSort nie powinien być tragiczny - najwolniej będzie na początku, ale
później będzie sortował w obrębie niewielkich kawałków. Jednak na pewno są
algorytmy lepsze do tego przypadku.

                                QRCZAK
    __("<             Marcin Kowalczyk
    \__/             qrczak@knm.org.pl
     ^^      http://kki.net.pl/qrczak/

Robert Maron wrote:
> 
> Jacek: [pl.comp.lang.c: Thu, 30 Oct 1997 23:00:57 +0100]
> : Proponowalbym uzyc do tego B-drzewa. Jest to o ile wiem najszybsza znana
> [...]
> 
> w zasadzie racja... ale po co sie tak meczyc;
> wystarczy:
> - podzielic plik na czesci tak duze, jak duze porcje mozemy sortowac
>   w pamieci,
> - posortowac kazda
> - potem parami merdzowac
> - wyniki znowu parami merdzowac, itd.
> 
> to bedzie bardzo szybkie, a w unixie da sie zaimplementowac kilkulinijkowym
> skryptem, pod dosem/winda kilkunastolinijkowym programem...

W takich przypadkach merging to jedyne sensowne rozwiazanie :). Ale zeby
tak rekordy skryptem?... Ja to bym wolal C :)

	pozdrawiam

-- 
gracjan ziółek
administrator systemów
mailto:gzio@celebris.bdk.lublin.pl
http://ajax.umcs.lublin.pl/~gracjanz/

Gracjan Ziółek napisał(a) w artykule
<345A351B.26F4@celebris.bdk.lublin.pl>...

>Robert Maron wrote:
>>
>> Jacek: [pl.comp.lang.c: Thu, 30 Oct 1997 23:00:57 +0100]
>> : Proponowalbym uzyc do tego B-drzewa. Jest to o ile wiem najszybsza
znana
>> [...]
>>
>> w zasadzie racja... ale po co sie tak meczyc;
>> wystarczy:
>> - podzielic plik na czesci tak duze, jak duze porcje mozemy sortowac
>>   w pamieci,
>> - posortowac kazda
>> - potem parami merdzowac
>> - wyniki znowu parami merdzowac, itd.
>>
>> to bedzie bardzo szybkie, a w unixie da sie zaimplementowac
kilkulinijkowym
>> skryptem, pod dosem/winda kilkunastolinijkowym programem...
>
>W takich przypadkach merging to jedyne sensowne rozwiazanie :). Ale zeby
>tak rekordy skryptem?... Ja to bym wolal C :)

Zapomnieliście (R.M. i G.Z.) że w przypadku "mergowania" trzeba się
trochę tych danych "naprzerzucać" co powoduje że już nie jest tak szybko
jakbyście chcieli. I mój algorytm (b-drzewa) i wasz (mergowanie) ma
złożoność O(n log n) ze względu na liczbę dostępów do dysku.
Jednakże mój operuje tylko na "kluczach" służących do indeksowania a
wasz na całych rekordach. Jeżeli te rekordy to na int'y to rzeczywiście
wasz jest lepszy, jeżeli jednak mają one po np 1000 bajtów to wasza
metoda "wysiada". W "mojej" metodzie każdy rekord jest dokładnie dwa razy
czytany z dysku i raz zapisywany.

pozdrawiam
Porkis

porkis@kki.net.pl - jeśli nie działa spróbuj:
@bbs.chip.pl, @polbox.com, @tempus.ii.uni.wroc.pl
http://polbox.com/p/porkis, http://www.kki.net.pl/porkis

Jacek: [pl.comp.lang.c: Sat, 1 Nov 1997 13:30:10 +0100]
: Zapomnieliście (R.M. i G.Z.) że w przypadku "mergowania" trzeba się
: trochę tych danych "naprzerzucać" co powoduje że już nie jest tak szybko
: jakbyście chcieli. I mój algorytm (b-drzewa) i wasz (mergowanie) ma
: złożoność O(n log n) ze względu na liczbę dostępów do dysku.
: Jednakże mój operuje tylko na "kluczach" służących do indeksowania a
: wasz na całych rekordach. Jeżeli te rekordy to na int'y to rzeczywiście
: wasz jest lepszy, jeżeli jednak mają one po np 1000 bajtów to wasza
: metoda "wysiada". W "mojej" metodzie każdy rekord jest dokładnie dwa razy
: czytany z dysku i raz zapisywany.
nie rozumiem, po co merdzowac dlugie rekordy? jak dlugie, to zawsze
sortujesz wskazniki, to chyba oczywiste...

robert
-- 
robmar@mimuw.edu.pl                  http://zls.mimuw.edu.pl/~robmar/

Jacek: [pl.comp.lang.c: Sat, 1 Nov 1997 13:30:10 +0100]
: Zapomnieliście (R.M. i G.Z.) że w przypadku "mergowania" trzeba się
: trochę tych danych "naprzerzucać" co powoduje że już nie jest tak szybko
: jakbyście chcieli. I mój algorytm (b-drzewa) i wasz (mergowanie) ma
: złożoność O(n log n) ze względu na liczbę dostępów do dysku.
: Jednakże mój operuje tylko na "kluczach" służących do indeksowania a
: wasz na całych rekordach. Jeżeli te rekordy to na int'y to rzeczywiście
: wasz jest lepszy, jeżeli jednak mają one po np 1000 bajtów to wasza
: metoda "wysiada". W "mojej" metodzie każdy rekord jest dokładnie dwa razy
: czytany z dysku i raz zapisywany.
nie rozumiem, po co merdzowac dlugie rekordy? jak dlugie, to zawsze
sortujesz wskazniki, to chyba oczywiste...

robert
-- 
robmar@mimuw.edu.pl                  http://zls.mimuw.edu.pl/~robmar/
ps. przepraszam, jesli ten artykul pojawi sie dwukrotnie...

Robert Maron napisał(a) w artykule <63fe2s$50l$4@domek.slodki.domek>...

>nie rozumiem, po co merdzowac dlugie rekordy? jak dlugie, to zawsze
>sortujesz wskazniki, to chyba oczywiste...

Racja, moja wina (tu trzy uderzenia w klatkę piersiową).

pozdrawiam
Porkis

porkis@kki.net.pl - jeśli nie działa spróbuj:
@bbs.chip.pl, @polbox.com, @tempus.ii.uni.wroc.pl
http://polbox.com/p/porkis, http://www.kki.net.pl/porkis

Jacek Szpyrka wrote:
> 
> Robert Maron napisał(a) w artykule <63fe2s$50l$4@domek.slodki.domek>...
> 
> >nie rozumiem, po co merdzowac dlugie rekordy? jak dlugie, to zawsze
> >sortujesz wskazniki, to chyba oczywiste...
> 
> Racja, moja wina (tu trzy uderzenia w klatkę piersiową).

No to ja już nie muszę się odzywać. Jacek chyba (bez obrazy..) mało
pisze w C :). Tam w takim przypadku najpierw przychodzą do głowy
wskaźniki, dopiero potem 'że można inaczej' :)

	pozdrawiam

-- 
gracjan ziółek
administrator systemów
mailto:gzio@celebris.bdk.lublin.pl
http://ajax.umcs.lublin.pl/~gracjanz/

Gracjan Ziółek napisał(a) w artykule
<345DF500.6778@celebris.bdk.lublin.pl>...

>Jacek Szpyrka wrote:
>>
>> Robert Maron napisał(a) w artykule <63fe2s$50l$4@domek.slodki.domek>...
>>
>> >nie rozumiem, po co merdzowac dlugie rekordy? jak dlugie, to zawsze
>> >sortujesz wskazniki, to chyba oczywiste...
>>
>> Racja, moja wina (tu trzy uderzenia w klatkę piersiową).
>
>No to ja już nie muszę się odzywać. Jacek chyba (bez obrazy..) mało
>pisze w C :). Tam w takim przypadku najpierw przychodzą do głowy
>wskaźniki, dopiero potem 'że można inaczej' :)

Ja jednak się odezwę.
Jeżeli chodzi o pisanie w C to:
1. Codziennie przez 8 godzin programuję w C++ w pracy i nie jest to proste
programowanie interfejsów a projektowanie i analiza algorytmów.
2. Oprócz tego piszę programy zaliczeniowe (jeszcze studiuję) także w
C++.
3. Czasami piszę jakieś programiki dla siebie, też w C++.

To tyle jeżeli chodzi o programowanie w C++.

Jeżeli chodzi o merge-sort to oprócz wskażników trzeba sortować od razu
klucze bo inaczej i tak trzeba będzie wiele razy czytać z bazy.

Wydaje mi się że przy odpowiednio dużym stosunku ilości rekordów do
ilości dostępnego ramu b-drzewa jednak wygrywają. Chociaż przy
stosowanych dzisiaj powszechnie ilościach pamięci musiało by to być
NAPRAWDĘ DUŻO rekordów.

pozdrawiam
Porkis

porkis@kki.net.pl - jeśli nie działa spróbuj:
@bbs.chip.pl, @polbox.com, @tempus.ii.uni.wroc.pl
http://polbox.com/p/porkis, http://www.kki.net.pl/porkis

Jacek Szpyrka wrote:
> 
> Gracjan Ziółek napisał(a) w artykule
> <345DF500.6778@celebris.bdk.lublin.pl>...
> 
> >Jacek Szpyrka wrote:
> >>
> >> Robert Maron napisał(a) w artykule <63fe2s$50l$4@domek.slodki.domek>...
> >>
> >> >nie rozumiem, po co merdzowac dlugie rekordy? jak dlugie, to zawsze
> >> >sortujesz wskazniki, to chyba oczywiste...
> >>
> >> Racja, moja wina (tu trzy uderzenia w klatkę piersiową).
> >
> >No to ja już nie muszę się odzywać. Jacek chyba (bez obrazy..) mało
> >pisze w C :). Tam w takim przypadku najpierw przychodzą do głowy
> >wskaźniki, dopiero potem 'że można inaczej' :)
[...]

> 1. Codziennie przez 8 godzin programuję w C++ w pracy i nie jest to proste
> programowanie interfejsów a projektowanie i analiza algorytmów.

W fazie projektowania nie myśli się jeszcze o sposobie reprezentacji
zmiennych (np. wskaźniki). To na pewno dlatego ;)

[...]

> Jeżeli chodzi o merge-sort to oprócz wskażników trzeba sortować od razu
> klucze bo inaczej i tak trzeba będzie wiele razy czytać z bazy.

Nikt nie zgłasza sprzeciwu :)

> Wydaje mi się że przy odpowiednio dużym stosunku ilości rekordów do
> ilości dostępnego ramu b-drzewa jednak wygrywają. Chociaż przy
> stosowanych dzisiaj powszechnie ilościach pamięci musiało by to być
> NAPRAWDĘ DUŻO rekordów.

Zdaje się, że to miało być kilka(naście?) milionów rekordów. Czy to
dostatecznie dużo? Poza tym, nie każdy system inny niż PC w domu pozwoli
uzytkownikowi (jednemu z kilkudziesięciu) skorzystać z 90% pamięci.
Wcale nie uważam za pozytywne myślenia typu 'eee, mam duzo RAMu, to se
mogę pakować tam, co chcę'. Może i pod DOSem takie myślenie się
sprawdza, ale to już prawie historia :).

	pozdrawiam

-- 
gracjan ziółek
administrator systemów
mailto:gzio@celebris.bdk.lublin.pl
http://ajax.umcs.lublin.pl/~gracjanz/

TEST







-------------------------------------------------------------------------------
 Adam A.Ligieza, 
                                       e-mail: Adam.Ligieza@ii.uni.wroc.pl
                                                      aligieza@hotmail.com
-------------------------------------------------------------------------------