W dniu 2014-06-12 14:36, RoMan Mandziejewicz pisze:
> Hello Adam,
>
> Thursday, June 12, 2014, 2:29:36 PM, you wrote:
>
>>> Tu jakiś pierwszy z brzegu przykład:
>>> http://www.algorytm.org/algorytmy-sortowania/sortowa
nie-przez-laczenie-naturalne.html
>> Rodzaj sortowania bąbelkowego? Dość ciekawe. Może dla zabawy rozpiszę
>> sobie to choćby we wspomnianym QBasicu, i zapodam mu jakieś dane do
>> "przegryzienia" - choćby listę kontrahentów z bazy SQL.
>
> A jak duża ta baza, bo możesz potrzebować sporo czasu ;)
>

No i o to chodzi ;)
Bo może być, że czas przetwarzania rośnie z kwadratem ilości rekordów.

Sortowanie bąbelkowe powoli się bąbelkowało - z tego co pamiętam, był to
jeden z najwolniejszych algorytmów.


--
Pozdrawiam.

Adam

do góry

On 12-06-2014 12:31, Robert Wańkowski wrote:
> Pytałem w różnych miejscach, ale brak odpowiedzi, dlatego pozwoliłem
> sobie tu.
>
> Ktoś pamięta/zna ten język.
> Jak to jest z tablicami (DIM) w tym języku? Podobno ograniczone są do 64k.
> Da się posortować w tym języku tablicę o wielkości 7x100000?

Coś więcej o systemie powiesz? Z reguły każda implementacja Basic-a jest
inna.
Na pewno da się posortować tablicę tej wielkości, z tym zastrzeżeniem,
że jeśli RAMu nie starczy, to będzie to trwało odpowiednio długo.
K.

do góry

On 12.06.2014 13:59, RoMan Mandziejewicz wrote:
> Hello bartekltg,
>
> Thursday, June 12, 2014, 1:15:54 PM, you wrote:
>
>>>> Jak to jest z tablicami (DIM) w tym języku? Podobno ograniczone są do 64k.
>>>> Da się posortować w tym języku tablicę o wielkości 7x100000?
>>> Przy takiej wielkości używa się już baz danych do sortowania (szybciej
>>> będzie zaindeksować).
>> Że co?
>
> Że masz zastrzeżenia co do tego, że indeksowanie bazy

"Bazy"? Zbiór danych;>

> jest szybsze od
> jej fizycznego posortowania? ;)

To jest zależne od rozmiaru pojedyńcxzego klocka.

Posortowanie intów (czy kwaternionów na doublach;)) będzie
znacznie szybsze (do tego znacząco mniej pamięciożerne,
a potem użycie tej struktury znów będzie znacznie szybsze*)
Jeśli natomiast klockiem jest kilobajtowi struktura,
a do tego jej porównanie jest szybkie, to posortowanie
listy indeksów/wskaźników będzie szybsze, bo omijamy spore
kopiowania.


>> ...a, no chyba że w QBasic.. ;-)
>
> Zapomnij o QBasic. Nawet w dużych systemach nie sortuje się już baz
> fizycznie, zawsze przez indeks - tak jest szybciej. Choć niekoniecznie
> użytkownik/programatoł (programista wie) musi o tym wiedzieć.

Nikt nie mówił o _bazie_. Pytacz ma małą (no, chyba, że siedzi na
atmedze 'tablicę'. Baz się nie sortuje, bo najczęściej klocek
jest tam duży, a potrzebujemy _wielu_ indeksów.

Bazy danych i ich zastosowania to szczególny dział programowania.
I poza nim cały czas sortuje się bezpośrednio dane gdy jest to
szybsze, bo nierzadko jest to szybsze.

Zresztą, nie ma co wierzyć, każdy może sam sprawdzić.



*) posortowane dane służą w uproszczeniu do dwóch rzeczy,
wyszukania czegoś i przetworzenia w kolejności jakiegoś porządku.

Głupie wyszukiwanie binarne będzie miało 2 razy więcej cache miss
w przypadku posortowania indeksów. Przetwaranie sekwencyjne
to przejście jednej tablicy po kolei i drugiej praktycznie losowo
(to też dobrze zobaaczyć).
Tak będzie zawsze, oczywiście dla odpowiednio dużych klocków
samo sortowanie będzie na tyle dłuższe, że pochłonie jakikolwiek
zysk z naddatkiem.


pzdr
bartekltg

do góry

"John Smith"
> Coś więcej o systemie powiesz? Z reguły każda implementacja Basic-a jest
> inna.
> Na pewno da się posortować tablicę tej wielkości, z tym zastrzeżeniem,
> że jeśli RAMu nie starczy, to będzie to trwało odpowiednio długo.


System to XP, RAM ileś tam GB.
Niby taki program działa. Zapisuję wartość 33 i ją oczytuję.

DIM Tablica(100000, 8)
Tablica(100000, 8) = 33
PRINT Tablica(100000, 8)

Ale w wielu miejscach czytałem w tym tonie podobne stwierdzenia:
"Najmniejsza tablica moze zajmowac 1 bajt, najwieksza 64KB.
Z danych tych mozna wyliczyc, ze tablica typu SINGLE PRECISION moze miec
najwyzej 16384 elementy (64x1024/4).
Deklaracja DIM kub(30,30,30) usiluje stworzyc tablice o 29791 elementach
(31x31x31), a to jest ok. 13000 elementow wiecej niz pozwala na to jezyk
QBasic."
http://infgeo.strefa.pl/Kl2/qbasic.htm

Dlatego chciałem zapytac mądrzejszych czy obliczenia i sorotwanie na takiej
ilości danych zrobię w QBasic-u.
Gdyby ktoś chciał znać szczegóły do czego to potrzebne to tu:
http://forum.pclab.pl/topic/967834-QBasic/
http://www.excelforum.pl/topics15/konwerter-import-d
anych-vt41365.htm?sid=1c6c0e0481198c886bc2762096c0de
86
Gdyby sie link połamał:
http://tinyurl.com/o55gn9x

Robert

do góry

W dniu 2014-06-12 16:52, Robert Wańkowski pisze:
> "John Smith"
>> Coś więcej o systemie powiesz? Z reguły każda implementacja Basic-a
>> jest inna.
>> Na pewno da się posortować tablicę tej wielkości, z tym zastrzeżeniem,
>> że jeśli RAMu nie starczy, to będzie to trwało odpowiednio długo.
>
>
> System to XP, RAM ileś tam GB.
> Niby taki program działa. Zapisuję wartość 33 i ją oczytuję.
>
> DIM Tablica(100000, 8)
> Tablica(100000, 8) = 33
> PRINT Tablica(100000, 8)
>
> Ale w wielu miejscach czytałem w tym tonie podobne stwierdzenia:
> "Najmniejsza tablica moze zajmowac 1 bajt, najwieksza 64KB.
> Z danych tych mozna wyliczyc, ze tablica typu SINGLE PRECISION moze miec
> najwyzej 16384 elementy (64x1024/4).
> Deklaracja DIM kub(30,30,30) usiluje stworzyc tablice o 29791 elementach
> (31x31x31), a to jest ok. 13000 elementow wiecej niz pozwala na to jezyk
> QBasic."
> http://infgeo.strefa.pl/Kl2/qbasic.htm
>
> Dlatego chciałem zapytac mądrzejszych czy obliczenia i sorotwanie na
> takiej ilości danych zrobię w QBasic-u.
> Gdyby ktoś chciał znać szczegóły do czego to potrzebne to tu:
> http://forum.pclab.pl/topic/967834-QBasic/
> http://www.excelforum.pl/topics15/konwerter-import-d
anych-vt41365.htm?sid=1c6c0e0481198c886bc2762096c0de
86
>
> Gdyby sie link połamał:
> http://tinyurl.com/o55gn9x
>

Czy ty czasem nie mylisz QBasic (DOS) z VBasic (Visual Basic, Windows)?

JK

do góry

Hello bartekltg,

Thursday, June 12, 2014, 4:38:22 PM, you wrote:

>>>>> Jak to jest z tablicami (DIM) w tym języku? Podobno ograniczone są do 64k.
>>>>> Da się posortować w tym języku tablicę o wielkości 7x100000?
>>>> Przy takiej wielkości używa się już baz danych do sortowania (szybciej
>>>> będzie zaindeksować).
>>> Że co?
>> Że masz zastrzeżenia co do tego, że indeksowanie bazy
> "Bazy"? Zbiór danych;>

7x100000

>> jest szybsze od jej fizycznego posortowania? ;)
> To jest zależne od rozmiaru pojedyńcxzego klocka.

I umiejętności programisty... I użytych narzędzi. Bo sortowanie takiej
tablicy w pamięci banalne nie jest.

> Posortowanie intów (czy kwaternionów na doublach;)) będzie
> znacznie szybsze (do tego znacząco mniej pamięciożerne,
> a potem użycie tej struktury znów będzie znacznie szybsze*)
> Jeśli natomiast klockiem jest kilobajtowi struktura,
> a do tego jej porównanie jest szybkie, to posortowanie
> listy indeksów/wskaźników będzie szybsze, bo omijamy spore
> kopiowania.
>>> ...a, no chyba że w QBasic.. ;-)
>> Zapomnij o QBasic. Nawet w dużych systemach nie sortuje się już baz
>> fizycznie, zawsze przez indeks - tak jest szybciej. Choć niekoniecznie
>> użytkownik/programatoł (programista wie) musi o tym wiedzieć.
> Nikt nie mówił o _bazie_. Pytacz ma małą (no, chyba, że siedzi na
> atmedze 'tablicę'. Baz się nie sortuje, bo najczęściej klocek
> jest tam duży, a potrzebujemy _wielu_ indeksów.

Pytacz chciał to robić w QBasicu... Ja, mając takie narzędzia jak mam,
niemal z zamkniętymi oczami zassałbym dane do bazy (bo jakoś one są
zapisane, nieprawdaż?) i za chwilę byłyby posortowane ,,z palca" -
komendami xBase, nawet bez pisania programu.
Ewentualnie program musiałbym napisać do samego zaimportowania danych.

> Bazy danych i ich zastosowania to szczególny dział programowania.
> I poza nim cały czas sortuje się bezpośrednio dane gdy jest to
> szybsze, bo nierzadko jest to szybsze.

> Zresztą, nie ma co wierzyć, każdy może sam sprawdzić.

Różnie bywa, zależy od skali.

[...]

--
Best regards,
RoMan
Nowa strona: http://www.elektronika.squadack.com (w budowie!)

do góry

"JK"
> Czy ty czasem nie mylisz QBasic (DOS) z VBasic (Visual Basic, Windows)?


Nie, problem próbowano rozwiązać w Excelu (VB), ale to sortowanie jest
specyficzne i muszę to zrobić sam. A potrafię jedeynie coś napisać w
Basic-u.

Robert

do góry

On 12.06.2014 16:52, Robert Wańkowski wrote:
> "John Smith"
>> Coś więcej o systemie powiesz? Z reguły każda implementacja Basic-a
>> jest inna.
>> Na pewno da się posortować tablicę tej wielkości, z tym zastrzeżeniem,
>> że jeśli RAMu nie starczy, to będzie to trwało odpowiednio długo.
>
>
> System to XP, RAM ileś tam GB.

To czemu qbasic?


> Niby taki program działa. Zapisuję wartość 33 i ją oczytuję.
>
> DIM Tablica(100000, 8)
> Tablica(100000, 8) = 33
> PRINT Tablica(100000, 8)

> Ale w wielu miejscach czytałem w tym tonie podobne stwierdzenia:
> "Najmniejsza tablica moze zajmowac 1 bajt, najwieksza 64KB.

A piszą to o Twojej wersji QBasica? Bo ta uwaga możę dotyczy
interpretera w MS-DOS?

BTW, Dla danych powyżęj pewnej wielkośći lepiej użyć pamięci
dynamicznej.
Visual Basic na pewno to umożliwiał, Q chyba też:
http://rosettacode.org/wiki/Arrays#Dynamic


> Z danych tych mozna wyliczyc, ze tablica typu SINGLE PRECISION moze miec
> najwyzej 16384 elementy (64x1024/4).
> Deklaracja DIM kub(30,30,30) usiluje stworzyc tablice o 29791 elementach
> (31x31x31), a to jest ok. 13000 elementow wiecej niz pozwala na to jezyk
> QBasic."
> http://infgeo.strefa.pl/Kl2/qbasic.htm

To jest o tym dosowym starociu.


> Dlatego chciałem zapytac mądrzejszych czy obliczenia i sorotwanie na
> takiej ilości danych zrobię w QBasic-u.



> Gdyby ktoś chciał znać szczegóły do czego to potrzebne to tu:
> http://forum.pclab.pl/topic/967834-QBasic/
> http://www.excelforum.pl/topics15/konwerter-import-d
anych-vt41365.htm?sid=1c6c0e0481198c886bc2762096c0de
86

Problem chyba tu już opisywałeś.

Jeśli wybór QBasica bierze się z tego, że ten język znasz
to ściągnij choćby to:

http://www.visualstudio.com/downloads/download-visua
l-studio-vs#DownloadFamilies_4

darmowa wersja visual basica, starsza, ale dzięki temu pójdzie pod
windows XP.

Na zachętę:

http://social.msdn.microsoft.com/Forums/vstudio/en-U
S/d88d332d-5fce-4f2a-bb9d-eb7b2e13e356/maximum-size-
of-an-array-vbnet?forum=vbgeneral

http://msdn.microsoft.com/en-us/library/x397t1yt%28V
S.71%29.aspx

żadnych problemów z ograniczeniem wielkości. Ile RAMu i przestrzeni
adresowej, taka tablica.

pzdr
bartekltg

do góry

On 12.06.2014 17:47, RoMan Mandziejewicz wrote:
> Hello bartekltg,
>
> Thursday, June 12, 2014, 4:38:22 PM, you wrote:
>
>>>>>> Jak to jest z tablicami (DIM) w tym języku? Podobno ograniczone są do 64k.
>>>>>> Da się posortować w tym języku tablicę o wielkości 7x100000?
>>>>> Przy takiej wielkości używa się już baz danych do sortowania (szybciej
>>>>> będzie zaindeksować).
>>>> Że co?
>>> Że masz zastrzeżenia co do tego, że indeksowanie bazy
>> "Bazy"? Zbiór danych;>
>
> 7x100000

Siedemset tysiety klocków czy tablica dwuwymiarowa 7x100 000,
tego dalej nie wiem.

>>> jest szybsze od jej fizycznego posortowania? ;)
>> To jest zależne od rozmiaru pojedyńcxzego klocka.
>
> I umiejętności programisty... I użytych narzędzi. Bo sortowanie takiej
> tablicy w pamięci banalne nie jest.

Takiej? Jeśli mieści się w pamięci, jest trywialne.
Autor napsiał, że ma kilka GB dostępnej.



>
> Pytacz chciał to robić w QBasicu... Ja, mając takie narzędzia jak mam,
> niemal z zamkniętymi oczami zassałbym dane do bazy (bo jakoś one są
> zapisane, nieprawdaż?) i za chwilę byłyby posortowane ,,z palca" -
> komendami xBase, nawet bez pisania programu.


Czyli jednak moja uwaga 'a, no chyba, ze w Qbasicu' była słuszna.

W czymkolwiek innym, gdzie nie masz ograniczeń co do wielkości
tablicy zwykłe sortowanie będzie szybsze. Choćby o komunikacje.

> Ewentualnie program musiałbym napisać do samego zaimportowania danych.

I machać taką garstką danych tam i z powrotem, miedzy 10 programami,
wyciągać kombajn jak baza danych... Autor wyraźnie chce przetwarzać
te dane dalej.



>> Bazy danych i ich zastosowania to szczególny dział programowania.
>> I poza nim cały czas sortuje się bezpośrednio dane gdy jest to
>> szybsze, bo nierzadko jest to szybsze.
>
>> Zresztą, nie ma co wierzyć, każdy może sam sprawdzić.
>
> Różnie bywa, zależy od skali.

Skala była podana. <1M elementów.
Jeśli byłoby ich na TBajty, rzeczywiście baza danych byłaby
wartym rozważenie rozwiązaniem. Sortowanie z użyciem dysku nie
jest bardzo trudne, ale napisanie już będzie czasochłonne (jest
fajny algorytm z dwoma przebiegami zapisu i odczytu, obecnie chyba
najszybszy do takich zdań przy niazbyt wielkich danych (TB) ).

pzdr
bartekltg

do góry

"bartekltg"
> A piszą to o Twojej wersji QBasica? Bo ta uwaga możę dotyczy
> interpretera w MS-DOS?


I tu chyba trafiłeś. Myślałem że jak coś się nazywa QBasic to niezależnie
pod jakim system będzie działać to możliwości będa takie same.

Ten mój QBasic jakiś nowszy.
Cytaty z jego helpa "QB64 is a BASIC compatible Editor and C++ compiler that
creates working
Executable files from Qbasic BAS files that can be run on 32 or 64 bit PC's
using WINDOWS(XP, Vista and newer), LINUX or MAC(OSX only). The goal is to
be
100% compatible with QuickBasic 4.5 plus add hundreds of new abilities such
as
program icons and custom sized windows and a great Editor with a new Help
Menu."
Po wpisaniu LPRINT 10*8 drukarka USB (Win XP) wydrukowała wynik.

Robert

do góry