Projekt badawczy Polska-Namibia 2010

Damian 'legion' Szuberski <legionna@onet.eu.cutthisjunkwrites:

Zastosować (Odwrotną) Notację Polską?


Lepiej nie. Prościej przekształcić na drzewo wyrażenia, je się potem
łatwiej liczy.

Jak przekształcić - szukać pod hasłem "parsowanie metodą zejść
rekurencyjnych" tudzież "parser zstępujący" tudzież "recursive
descent parsing".

W prostym programie można nawet liczyć wartość na bieżąco w trakcie
parsowania zamiast budowania drzewo, ale to ma sens tylko kiedy dane
wyrażenie jest liczone tylko raz i wyrażenie składa się tylko ze
stałych i operacji arytmetycznych (a nie jest to język programowania
ze zmiennymi, pętlami itp.).

Marcin 'Qrczak' Kowalczyk wrote:
On Tue, 24 Aug 2004 09:29:30 +0200, Jakub Laskowski wrote:

| Eeee... pytanie podstawowe - jak przechowujesz w pamięci wyrażenia?

| Pomijajac ze na pewno trzymamam jako char * ;) To mam wyrazenia w postaci
| tablicy unii, tutaj kazda z nich jest osobnym tokenem, a mam 9 typow
| tokenow:

Do obliczeń symbolicznych taka reprezentacja się nie nadaje.
Lepiej zrobić drzewo (z operacjami w węzłach).


Myslalem wlasnie o takim drzewie przy wyznaczaniu tych pochodnych - jednak
wymagalo by to troche zmian w kodzie, musze to przemyslec. Moze udaloby mi
sie napisac cos w stylu tabl2tree przerabiajacy moja tablice na odpowiednie
drzewko.
W sumie moj parser wyrazen nie jest chyba super profesjonalnie wykonany - w
ksiazce C. Programowanie() znalazlem parser dzialajacy na troche innej idei
- tzw. rekurencyjno zstepujacy, ale wtedy mialem juz moj napisany, wiec nie
chcialem nic zmieniac. A sprawdzac - sprawdza sie, i tak jestem bardzo z
niego dumny ;) to jest 100% moja praca, nie posilkowlaem sie zadnymi innymi
pomyslami :)

PS. C jest jednym z najgorszych języków do implementowania obliczeń
symbolicznych.


Moge sie spytac czemu?

Pozdrawiam,

Pine.LNX.4.05.9811031921060.29269-100@fanthom.math.put.poznan.pl...

On Tue, 3 Nov 1998, Krzysiek Mazur wrote:
...policy makers followed concepts of a more or less top down approach


:Na wykladzie z informatyki [...] wykladowca [...] tlumaczyl "top
:down approach" jako takie podejscie, ktore przechodzi od najbardziej
:ogolnej idei do najdrobniejszych szczegolow [...]

Jest to podejście (w szczególności projektowanie lub programowanie)
zstępujące. Łatwo się domyślić, że odwrotny proces nazywa się podejściem
wstępującym. Ale to jest termin informatyczny i w powyższym tekście może nie
być zrozumiały. Proponował bym mimo wszystko "podejście od ogółu do
szczegółu".

Marek Gierliński
g@camk.edu.pl
+++++++++++++++++++++++++++
Kobieta jest jak przekład literacki --
-- im piękniejsza, tym mniej wierna

Maciej Sobczak wrote:
Etam (tm). Teraz wkręcasz tu jakieś cuda.


Jakie znowu cuda? Chcesz się posługiwać
pojęciami z zakresu złożoności obliczeniowej,
to stosuj ten formalizm konsekwentnie.

Pokazałem Ci algorytm rozwiązujący zupełnie
praktyczny problem, który nie jest rekurencyjny,
a przynajmniej w normalnym pojmowaniu tego
słowa. Jest za to rekurencyjny w sensie Kryterium
Sobczaka, co się twórcy owego kryterium jak
widzę nie podoba. Cieszy mnie to ogromnie. :-)

Pod pojęciem stałej (ilości) pamięci rozumiem sytuację, w której dany
algorytm może wykonać się modyfikując znany statycznie zbiór osobnych
wartości (bytów).


Czy dwa liczniki o nieograniczonej z góry pojemności spełniają to kryterium?

Nie wnikam w zakres tych wartości.


To lepiej szybko zacznij, bo ten zakres wprost przenosi się
na złożoność pamięciową. Wszystko kończy jako ciąg bitów.

W przeciwnym razie musiałbym uznać, że algorytm
std::count też nie potrafi działać w stałej pamięci.


No bo nie działa, wymaga pamięci logarytmicznej.
A to, że size_t wystarcza na pokrycie "dostatecznie
wielu" praktycznych przypadków to szczegół, który
czyni programowanie znośniejszym.

Mam. I będąc praktykiem biorę unsigned long long do obsługi licznika i
przy strumieniu nawiasów 1GHz problemy zaczną się najprędzej w 2591
roku - i to zakładając, że do tego czasu były same otwierające.


No to ja jestem jeszcze większym praktykiem i stwierdzam,
że wszystkie programy działają w pamięci stałej. Nie zmieniam
kostek w slotach RAM, a one jakoś dalej działają.

Porównaj to z obrzydliwie rekurencyjnym parserem zstępującym.


Widzę różnicę w złożoności pamięciowej: Omega(n) dla parsera
i Omega(log n) dla licznika. Żadna z tych wielkości nie mówi nic
o stopniu rekurencyjności programu, no ale ja truskawki cukrem
posypuję...

Bądźmy poważni. :-)


Również o to proszę. Złapałeś się jednego formalizmu, to
trzymaj się go konsekwentnie, albo porzuć. Dobieranie sobie
w danej chwili pasujących pojęć i podlanie tego sosem "a bo
mnie się wydaje" nie robi na mnie dobrego wrażenia. :-)

    Pozdrawiam
    Piotr Wyderski

Marek Luch wrote:
Mi tez ;) Chodzilo mi o zstepujace dzielenie operacji na juz niepodzielne
podoperacje (atomy). Nie wiem, czy ma to jakas swoja wlasciwa nazwe.
Rozdrobnienie? ;)


Calkiem dobra nazwa, ale to podejscie sie "dziel i zwyciezaj" nazywa.

Uzylem nieprecyzyjnego terminu. Chodzilo mi o kod, ktory bedzie w jak
najwiekszym stopniu zdatny do ponownego uzytku (reusability).


Ale jaki to ma zwiazek z wydajnoscia, o ktorej pisales?

Staram sie jak najbardziej myslec obiektowo ;)


Tylko z tym nie przesadz. ;-) Jest wiele ciekawych metodologii, innych
niz podejscie obiektowe -- tu nawet orwellowskie dwojmyslenie nie
wystarcza, warto nauczyc sie "wielomyslenia" i wybrac taka metodologie,
ktora najlepiej pasuje do problemu. Naprawde nie warto robic niczego
na sile.

A na ile Wasz kod obiektowy jest reusable, tzn. czy nigdy nie
musicie robic copy-paste i cos tam modyfikowac?


Klade duzy nacisk na mozliwosc wielokrotnego wykorzystania mojego
kodu, ale robie to wylacznie z powodu checi oszczedzenia sobie ilosci
pracy podczas programowania i testowania w przyszlosci. Nie opieram
sie na tlumaczeniach mowiacych o zwiekszaniu poziomu abstrakcji,
oddzielenia interfejsu od implementacji itp. rzeczach wpajanych studentom
podczas studiow informatycznych. Te zalecenia sa sluszne, ale maja nieco
inny sens. Zauwaz, ze majac do rozwiazania _konkretny_ problem
uabstrakcyjniamy go i w efekcie zabieramy sie za stworzenie rozwiazania
znacznie obszerniejszej klasy problemow, co czesto niekorzystnie przeklada
sie na strukture kodu, patrzac z punktu widzenia wydajnosci. Nie korzystamy
z mozliwosci kodowania wielu informacji w malej ilosci pamieci, zamiast tego
wprowadzajac pola danych o jasno okreslonym znaczeniu, nie budujemy kodu
uzalezniajacego wybor sciezki przeplywu sterowania od stanu pamietanego
w obszarze globalnym, rezygnujac tym samym z wielkich automatow
skonczonych, nie uzywamy  nieprzenosnych konstrukcji, decydujac sie na
wykonanie tego samego obliczenia "w bardziej elegencki" sposob itd. Dlatego
jestem zagorzalym zwolennikiem automatycznego generowania kodu
niskopoziomowego wprost ze specyfikacji formalnych, np. jezyka Z, semantyk
algebraicznych i aksjomatycznych itp. systemow i porzucenia recznego
programowania. Problemem jest ich mala czytelnosc dla 95% programistow
i koniecznosc absolutnie scislego specyfikowania zadanych operacji, co moze
byc trudne dla Java i VB kids klepiacych aplikacje bazodanowe i sklepy
internetowe. Za dowod moze posluzyc np. mala popularnosc jezykow
prologopodobnych w tych kregach. Drugim powodem jest wzglednie slaby
stopien rozwoju automatycznych generatorow kodu; teraz jest moze 1/10 tego,
co IMO powinno byc.

    Pozdrawiam
    Piotr Wyderski

Chcialbym podzielić się pewną refleksją (na koniec tygodnia może).

Pisałem sobie dzisiaj coś sporo w eklipsie i zauważyłem że jeśli
poszukac w eklipsie miejsc gdzie jest wywoływana dana procedura
to eklips w trakcie tego wyszukiwania pisze "finding a children of
(nazwaprocedury)" to spowodowało że zastanowiłem się chwilę oraz
pobudziło moją wyobraźnie - w swietle tego krotkiego tekstu - stare
procedury (te które opadają na dno w procesie abstrakcji, jak to
by powiedział mój kolega panki, który lubiwyrażenie "proces
abstrakcji") te które są wywoływane spod nowszych,
czyli również zwłaszcza te niskopoziomowe, stają się jakby
PRZODKAMI a nawet prehistorycznymi przodkami (żyjącymi
w swoim pokrytym śniegiem sąsiedztwie innych podobnych procedur
pokrytych śniegiem). Nie bardzo wiem co właściwie chcę przez to
powiedzieć ale uważam - ciekawe. pzdr, miłego weekendu, daj boże
siłę nie włączać kompa, rok temu już pływałem w jeziorze, a teraz...

J Shade


Coś mi sie jednak pomieszało gdy myślałem o tym ale napisałem to trochę
dla żartu a bardziej pod wpływem nagłego przypływu wyobraźni w tym
prehistorycznym ośnieżonym temacie zgrzytających stalą procedur.
Ciągle mam problemy z perfekcyjnym skumaniem tematu projektowania
obiektowo (a to o czym napisałem powyżej więże się z tym tematem).
Najłatwiej mi teraz zapamiętać tę asymetrię wywołań w językach
programowania przez windowsową analogię z okienkami: child i rodzic
- widać w świetle tego że funkcja z której są wywoływane
inne funkcje jest rodzicem a nie odwrotnie jak napisałem (ale zmyliło
mnie to że - pominąwszy gusta co do ulubionych sposobów projektowania
zstępującego czy wstępującego to ZWYKLE dodajemy kolejne pokolenia
rodziców na plecy już istniejących rodziców swocich dzieci - czyli
to jest w drugą stronę - można oczywiście przepisywać całe gałęzie
albo optymalizować końcówki ale zwykle jednak dodaje się rodziców
na bazie tego co już jest. Ta analogia z okienkami pozwala mi
też widzieć jasno pewne inne rzeczy - jesli przeniesiemy ją na
kwestie widzialności obiektów w hierarchi - widać tu wyraźnie
że parent widzi bez problemów wnętrza swoich dzieci natomiast dzieci
nie widzą swoich rodziców bezpośrednio bo dziecko nie wie kto w danym
momencie jest jego rodzicem - moga byc wywolane z roznych kontekstów.
Ta sprawa mnie jeszcze niedawno konfundowała ale i tutaj widać przez
realizację w programowaniu okienek i dialogów co się robi - przekazuje
się dziecku  uchwyt na okno macierzyste albo obiektowi wskaznik do
obiektu macierzystego i sprawa jasna. Obiektowość ma kilka płaszczyzn
i mieszają mi się one co nieco, zwłaszcza te kwestie wzajemnej widzialonści
 - jeszcze ciągle czuję nie wszystko tu zrozumiałem. Jesli ktos ma coś do
dodania w tym temacie to chętnie przeczytam.

pzdr JFS

Vax wrote:
| Znacznie wiecej "podrecznikowych madrosci" _swiadomie_ zlewam :D

Twoj wybor, ja wole uczyc sie na cudzych bledach ;)


Kluczem jest tu "uczyc".
Zapewniam Cie, ze gdy sie _uczylem_, to nastepnego dnia
czesto nie wiedzialem, co wykombinowalem poprzedniego.

Mimo, ze "czlowiek uczy sie cale zycie", kilku ostatnich
jezykow programowania to ja sie nie tyle "uczylem", co _poznawalem_.
Zwazywszy poziom wielu podrecznikow i kursow - z korzyscia dla siebie.

| Jesli ktos nie potrafi zrozumiec wlasnego, jak sie wyraziles "prostego"
| kodu, to mu zadne komentarze zbytnio nie pomoga.

Tu nie chodzi o zrozumienie, w koncu jesli sam to napisales to czemu
mialbys nie zrozumiec. Ale po co marnowac pozniej czas na analizowanie
kodu aby go zrozumiec, skoro mozna przeczytac i od razu poznac jego
znaczenie. Nie miales nigdy okazji wrocic do swojego kodu po paru latach i
zastanwiac sie co autor mial na mysli?


Okazje wracac miewalem. I recze, ze nie musialem "analizowac".
Jeden rzut oka wystarczal, bym wiedzial, co, jak i dlaczego.
Drugi rzut pozwalal znalezc fragmenty, ktore po latach
moglem napisac lepiej.

| Bo co tu komentowac?
| Przeznaczenie funkcji/metody/partii kodu;
| Przeznaczenie zmiennych/parametrow;
| Ok. Ale wyjasniac algorytm?
| Toz on jest zawarty w kodzie.

Ja zawieram w komentarzu glownie to co mialem na mysli piszac dany kawalek
kodu, zebym pozniej nie musial zgadywac.


A ja nie pisze tasiemcowych ciagow instrukcji.
Dziele zadania na mniejsze, niezalezne bloki,
rownolegle tworze "klocki" - takie polaczenie metod
"zstepujacej" i "wstepujacej".
Unikam tym samym pokreconych drzew decyzyjnych itp.
Problemy jak Twoje, sa mi obce.
Ale to kwestia wypracowanej metodologii.

v.
PS. mozesz nie wierzyc, ale jak ogladam np. swoj kod,
dla postronnych nawet "zagmatwany", to rozumiem "ten jezyk".
Nie musze sobie "tlumaczyc", tak jak majac w glowie algorytm
nie zastanawiam sie "jak to teraz zakodowac" tylko zapisuje.
Natomiast prawda jest, ze zarowno w takim PHP jak i jezyku
polskim mozna napisac belkot (dowody chocby na grupie).
Jesli ktos belkocze, to faktycznie, moze sobie na marginesie wyjasniac,
o co mu chodzilo.
Ale nie probuj juz mi wmawiac, ze sam wlasnego kodu nie zrozumie.
Za dlugo tak robie, by po latach w to uwierzyc.
Raz sie zdarzylo. Po pijaku napisalem procedure perlokacji
na liscie dwukierunkowej, nie uzywajacej zadnego bufora,
najmniejszego nawet wskazniczka nawet. Tak, dla sportu czy zakladu,
by udowodnic, ze mozna lepiej, niz twierdza skrypty i podreczniki.
Rankiem ze dwie godziny analizowalismy te glupie 6 czy 7 instrukcji
z pomoca kilku kolegow ze studiow. Nie, nie nauczylem sie komentowac,
nauczylem sie myslec w konkretnym jezyku. I tak mi juz zostalo.