Newsgroup: it.comp.lang.visual-basic
Titolo: [spam] Parser espressioni algebriche a cifre arbitrarie

Ho 'finito' la scrittura del parser di espressioni algebriche a cifre
arbitrarie.
I test che ho fatto non sono assolutamente sufficienti per garantire un
minimo di sicurezza sul calcolo.
La cosa più triste è che, anche se è possibile scegliere l'accuratezza
delle dei singoli calcoli, non è possibile prevedere come questa
approssimazione si propagherà nell'intera espressione.
Inoltre, per come ho scritto il parser, eseguo prima le divisioni e poi le
moltiplicazioni; ciò implica pedita di cifre extra nella propagazione
dell'errore.
Quest'ultimo difetto si può correggere dando in pasto un'espressione con
le parentesi attorno alle moltiplicazioni vicine alle divisioni.
La velocità in generale è pessima per espressioni che coinvolgono radici 
quadrate, divisioni o moltiplicazioni di numeri con 500 o più cifre.
Quasi tutti gli algoritmi sono ricorsivi, quindi ci sono grossi limiti
imposti dallo stack sul numero di elementi che compongono l'espressione.
Veniamo ai vantaggi :) 
se inserite i due file .cls in un progetto, potete valutare un'espressione
in questo modo:
Dim pars As parser
set pars=new parser
msgbox pars.valutaEspressione("quello che volete", _ 
                              lngCifreUtilizzatePerDivisioneeRadice)
set pars = nothing
Qui sorgenti ed eseguibile:
http://www.unbelsito.com/vb/lameparser0.1.zip
termoPilucco
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

termoPilucco ha scritto:
[...]
Uh... già trovato un orrore e già fixato:
in caso di esponenziale negativo non gestiva le cifre di precisione
indicate dall'utente ma ne usava 50 fisse.
Inoltre la form chiamante non gestiva l'errore, con conseguente chiusura
applicazione in caso di problemi.


termoPilucco ha scritto:
come non detto:
c'è grosso orrore nella somma... tutto rimandato...


Resto sempre più senza fiato...
Un bel lavoro.
bye
-- 
Esistono 10 tipi di persone: chi conosce il binario e chi no.
Gestione Ottica - Gestionale per Ottici e Programmi Gratuiti su:
http://www.nicolaottomano.it

Un bel lavoro.
Grazie... ma non funziona :(
9000000000/9=0 :''''(
La causa e' l'orrore nella somma... devo debuggare....
termoPilucco

 La causa e' l'orrore nella somma... devo debuggare....
patchato :)


Perchè non inizi a trasformare le tue classi in una libreria DLL in C?
Penso che il codice dovrebbe velocizzarsi parecchio...
-- 
Rivolterò il mondo per trovarlo, e anche se andasse in Indocina uno dei 
nostri starà nascosto in una ciotola di riso pronto a sparargli nel culo.
(Pulp Fiction)

 Penso che il codice dovrebbe velocizzarsi parecchio...
In C sono lento io a scrivere :)
Al limite potrei fare una conversione in C#: non credo si velocizzi molto,
perň diventerebbe tutto piů elegante grazie all'overloading degli
operatori.
Ad ogni modo la lentezza dipende da tre fattori:
-gli algoritmi di base utilizzati (soprattutto quello della
moltiplicazione) sono esosissimi. 
-la scelta deleteria di rappresentare internamente i numeri come strighe.
-la scelta di rappresentare internamente i numeri in forma decimale (che
perň semplifica notevolmente le conversioni ed evita l'effetto
approssimazione per numeri semplici come 0,2)
Se portassi la rappresentazione interna ad array di byte si potrebbe
ottimizzare tantitssimo anche senza cambiare gli algoritmi.
Ma manca la voglia...


 Ma manca la voglia...
Belzebů si č impossessato della tua mente e te la sta offuscando. :-O
Reagisci! Ripeti con me: QuickSort...QuickSort...
Oppure
For i=1 to 100000
debug.print "Quicksort "
next


 ottimizzare tantitssimo anche senza cambiare gli algoritmi.
Dim b() as byte
b = StrConv(stringa, vbFromUnicode)
Magari, non so come funziona la cosa, ma anzichč lavorare concatendando 
stringhe e cose del genere alloca tutta la stringa con String$() e poi 
lavora direttamente nel buffer, in questo modo riduci di parecchio il 
lavoro dello string manager e le tue prestazioni miglioreranno 
notevolmente, anche se, lavorando su stringhe non saranno mai il massimo.
Ciao
-- 
Math Parser : 
http://www.neodatatype.net
Sito Comune : 
http://www.it-lang-vb.net

termoPilucco ha scritto:
Sai cosa sarebbe bello?
Che tu scrivessi una classe BigNumber da poter utilizzare dove si vuole.


Che tu scrivessi una classe BigNumber da poter utilizzare dove si vuole.
Beh, più o meno è quello che fa numero.cls che intenzionalmente (e, credo,
operativamente) dovrebbe essere indipendente dal resto del progetto.
L'avevo provata anche in Excel per fare i calcoli nelle celle con qualche decina
di cifre di precisione e andava benino.
In realtà, essendo un po' particolare da usare, la classe parser.cls può venire
in aiuto ed essere inserita in un progetto per facilitare l'esecuzione di una
sequenza di calcoli.
Non sottovaluterei però il fatto che non è detto che i calcoli fatti siano
corretti  ^_^'''  e che in casi particolari (troppi operatori nell'espressione o
troppe parentesi) il programma va in stack overflow.
Diciamo che se i calcoli sono  +, -, * ci si potrebbe anche fidare, ma lo stesso
vale per VB :)
termoPilucco

notevolmente, anche se, lavorando su stringhe non saranno mai il massimo.
Già, infatti ne ero consapevole quando ho iniziato, ma non pensavo di portare
avanti il progettino.
termoPilucco

next
s="Quicksort " & vbcrlf : debug.print(replace(space(100000),chr(32),s))
termoPilucco

 wrote in message
bd5kc015anfvvl55p...@4ax.com...


;-)
Speriamo che alle donne piacciano :)
termoPilucco 

 vale per VB :)
Sono molto indeciso...
Mi viene quasi voglia di passarti la procedura di parsing della mia classe
:P che è sicuramente funzionante e non utilizza lo stack di VB.
Ciao
--
NeoDataType : 
http://www.neodatatype.net
Sito Comune : 
http://www.it-lang-vb.net

:P che è sicuramente funzionante e non utilizza lo stack di VB.
Il mio parsing è quasi sicuramente funzionante :)
Ho provato a generare casualmente 100.000 espressioni algebriche con gli
operatori gestiti anche da "m$ script control" e verificarne il risultato
rispetto a quello restituito dalla mia classe.
I miei dubbi sono sui calcoli veri e propri:
Dopo aver pubblicato il codice la prima volta ho trovato e patchato almeno tre
errori consistenti (divisione errata, riporto di carry errato e radice quadrata
in loop infinito).
Per quanto riguarda lo stack, utilizzi uno stack virtuale tuo o non usi proprio
la ricorsione?
termoPilucco

 la ricorsione?
Non uso ricorsioni: l'algoritmo per convertire infix to postfix e valutare
il postfix è tutto sommato banale (almeno per gli operatori elementari e le
funzioni a 1 argomento che alla fine si comportano come gli operatori
unari): si utilizza uno stack (inteso come "pila") per gli operatori e uno
per gli operandi.
Dai ad es. un occhio qui:
http://www.spsu.edu/cs/faculty/bbrown/web_lectures/postfix/


 
http://www.spsu.edu/cs/faculty/bbrown/web_lectures/postfix/
Scusa, l'unica cosa un po' interessante qui è l'animazione :)
Lascia stare tutte le storie legate alle tavole di precedenza: basta dare ad
ogni operatore un "peso" diverso.
Guarda qui:
http://scriptasylum.com/tutorials/infix_postfix/infix_postfix.html



http://scriptasylum.com/tutorials/infix_postfix/infix_postfix.html
In effetti per semplicità, negli esempi accademici, si usa proprio questa
notazione :)
Beh.. mi sono complicato la vita e ne pago le conseguenze :)
Comunque il difetto più grave del mio parser (assumendo che funzioni e non vada
in overflow) è che garantisce (nelle intenzioni e spero in pratica) solo ogni
singolo calcolo nella precisione desiderata.
Il problema è la propagazione dell'errore che dipende dall'intera espressione,
cosa di cui non ho controllo:
es: con 5 cifre di precisione
1000*(1-2/3)   = 1000*(1-0,66667)= 1000*(0,33333)=333,33 risultato con solo due
cifre di precisione.
In realtà il mio parser restituisce 333,333 perchè internamente lavora sempre
con una cifra in più in modo da poter arrotondare alla fine, ma il discorso non
cambia.
termoPilucco

 operatori.
Scusa se insisto ma sei tanto fissato con l'ottimizzazione... a volte 
scrivi certe funzioni così compatte e veloci..... e poi non ti metti a 
studiare un tantino il C?
Che poi la cosa un po' brutta lì è la poca disponibilità per l'output... 
insomma VB ci ha viziati troppo con tutto quello che riguarda il debug, 
ma anche solo usando MS VC++ per generare una dll hai a disposizione un 
bell'ambiente di sviluppo (comodo, perchè checchè se ne dica sui 
prodotti di Mamma M$, la comodità nei prodotti non manca mai).
Tanto la maggior parte dei linguaggi di oggi hanno una sintassi 
spiaccicata a quella del C...


spiaccicata a quella del C...
La sintassi non è un problema, provengo dall'assembly del 68000, passando per C,
e perl (ormai l'ho dimenticato ma è un linguaggio favoloso).
E' la voglia che manca :)
Anzi, a proposito di Assembly, chi ha tempo da perdere può vedere la mia
produzione di punta del '92: ovvero una demo grafica che gira su Amiga con
effetti 2d/3d e quant'altro.
http://wuarchive.wustl.edu/aminet/demo/funet/Tangentopoli.lha
Sono 33Kb compresa la musica.
Per chi volesse farla girare su PC, basta un emulatore (consiglio UAE).
termoPilucco

 [3] 1,"molto lunga", null
in realtà il tuo esempio è un'altra cosa ancora, forse più flessibile di
quello che pensavo io
Io intendevo semplicemente che ogni istanza di classe stringa "virtuale",
allocasse non un array di caratteri (nello heap), ma un elemento di tipo
puntatore ad un unità di lista doppiamente concatenata, tipo (beh, scusa se
uso il C .... è che l'idea era più da C che altro, e non mi fungono le
graffe perché ho il tastierino impegnato nel mouse control)
class PezzoDiStringa [
    PezzoDiStringa * Next;
    PezzoDiStringa * Prev;
    char * ChunkContained;
    unsigned long Size;
];
class Stringa [
    PezzoDiStringa * PrimoPezzo;  // è l'entry point
];
nota, la lista andrebbe chiusa ad anello per velocizzare la scansione
antioraria e le InstrBack a ritroso, tanto l'entry point è esogeno alla
lista stessa, e mantenuto nella classe che la usa
all'inizio, nel costtruttore, crei una stringa monolitica, ma quando si
tratta di inserire o accodare caratteri, non liberi la memoria,
semplicemente allochi altra ram dinamica (heap) e una o due ulteriori
istanze di lista (una se devi accodare, due se devi spezzare un blocco come
nell'inserimento).
Tra l'altro pur se in apparenza virtualmente si spezza un array contiguo,
non è affatto necessario riallocare nemmeno in questo caso. E' solo la
sequenza di puntatori che verrà spezzata. Ad es. entro lo stesso array
inizialmente contiguo so che devo leggere i primi 10 caratteri, poi passare
al secondo pezzo scorrendo la lista e leggerne un po' li, poi tornare
dall'11 carattere al vecchio array.
L'incubo è il garbage collector finale, che talvolta deve fare il delete[],
talaltra, sui frammenti virtuali, assolutamente no.
Io aggiungerei un campo boolean per distinguere se un puntatore al contenuto
è realmente un array ottenuto da NEW, o si tratta solo di un puntatore
interno ricavato a posteriori, da non disallocare .... azz, altro casino :
quando è del primo tipo, bisogna che nessun blocco successivo debba restare
attivo.
Beh si può fare, ma proprio immediato non è
La lettura, anche sequenziale come ti serve, è rallentata dal dover spezzare
in più cicli for
for (J=0, J<Size; J++)
e da un numero di salti all'elemento di lista successivo corrispondente al
numero di frammenti della stringa.
ciao x ora
CCCP++Mario


numero di frammenti della stringa.
Sì, così è chiaro...
Si potrebbe usare la lista bidirezionale che contiene come tipo principale un
array sovradimensionato rispetto alla dimensione inizialmente richiesta, in modo
che quando una stringa cresce (magari di un solo carattere come avviene spesso
nelle somme) abbia la possibilità di farlo senza dover necessariamente creare un
nuovo elemento della lista, a meno che non si raggiunga l'ubound dell'array.
termoPilucco

 nuovo elemento della lista, a meno che non si raggiunga l'ubound
dell'array.
E come fai?
Gestisci un array di cosa? Di stringhe?
Quando assegni una stringa hai comunque un overhead dato dall'allocazione
dello spazio della nuova stringa.
La cosa più sensata (e decisamente più semplice) credo sia proprio fare come
fa lo stringbuilder di .Net: alloca una stringa iniziale e lavora su quella,
se gli manca spazio gli aggiunge ancora un blocco, più grande di quello
righiesto.
Dato che su certe cose non vale la pena inventare l'acqua calda puoi dare un
occhio all'implementazione con l'ormai famoso Reflector :)
Ciao
--
NeoDataType : 
http://www.neodatatype.net
Sito Comune : 
http://www.it-lang-vb.net

occhio all'implementazione con l'ormai famoso Reflector :)
C'è sempre da inventare... hai detto anche tu che m$ script control è più lenta
del tuo parser...  allo stesso modo avevo scritto l'equivalente delle collection
usando gli alberi bilanciati e la cosa girava di gran lunga meglio delle
collection.
E poi è più divertente vedere le cose girare su basi "artigianali" piuttosto che
su classi scritte da altri.
termoPilucco

 occhio all'implementazione con l'ormai famoso Reflector :)
Mi sa che termopilucco vuole divertirsi !
Ciao
CCCP++Mario


 questo:
[SNIP]
In effetti la gestione delle stringhe in VB è lenta solo dove vengono
usate delle stringhe dinamiche. L'accodamento ( str1 = str1 & str2,
per capirci) prevede la creazione di stringhe temporanee, e alla fine
anche il GC suda... già con l'uso di copymemory e simili si possono
ottenere dei bei miglioramenti. Vedi per esempio (non ricordo da
dove l'ho preso, ma non è roba mia :-) ):
' in un modulo
Declare Function GetTickCount Lib "kernel32" () As Long
Type SAFEARRAYBOUND
    cElements As Long
    lLbound As Long
End Type
Type SAFEARRAY1D
    cDims As Integer
    fFeatures As Integer
    cbElements As Long
    cLocks As Long
    pvData As Long
    Bounds(0 To 0) As SAFEARRAYBOUND
End Type
Declare Function VarPtrArray Lib "msvbvm50.dll" Alias _
"VarPtr" (Ptr() As Any) As Long
Declare Sub CopyMemory Lib "kernel32" Alias _
"RtlMoveMemory" (pDst As Any, pSrc As Any, ByVal _
ByteLen As Long)
' questa roba va in due tasti:
'__________________
Private Sub Command1_Click()
Label1.Caption = ""
u% = DoEvents
tim& = GetTickCount
'**************
' slow version
'**************
'note the second & is just to prove that joining to strings is
'not inherently slow, only adding a string to itself g$ = g$ & extra
For a% = 1 To 5000
    g$ = g$ & "str" & "g "
Next
'****
Text1.Text = GetTickCount - tim&
Label1.Caption = g$
End Sub
Private Sub Command2_Click()
Label1.Caption = ""
u% = DoEvents
tim& = GetTickCount
Dim pos&
Dim src As String
Dim des As String
'****************
' Fast Version
'****************
'Allocates a big string, then copies the smaller strings into it.
'this means that VB does not need to perform the expensive
'dynamic realocation of string memory!
des = Space$(10000)
For a% = 1 To 5000
    src = "str" & "g "
    If pos& + LenB(src) > LenB(des) Then des = des & Space$(10000)
    CopyMemory ByVal StrPtr(des) + pos&, ByVal StrPtr(src), LenB(src)
    pos& = pos& + LenB(src)
Next
des = Left$(des, pos& \ 2) 'trim back to size
'**********
Text2.Text = GetTickCount - tim&
Label1.Caption = des
End Sub
'__________________
Già che ci sono, segnalo questo articolo (DOC+codice VB):
http://www.Planet-Source-Code.com/vb/scripts/ShowCode.asp?txtCodeId=34787&lngWId=1
Title: Learn How To Make VB Handle Strings As Fast As C
Description: If you want your strings routines to be as fast as
possible, learn C. If you don't want to learn C use string mapping,
its nearly as fast and pure VB. In this article I give you the silver
bullet for strings. If strings are bottlenecking your code, I'm your
new best friend. I've included a project that attempts to visualize
the string for you. It also contains a word count comparision
which uses four methods string mapping being the fastest by
far (compiled).
Ah, vale la pena di guardare anche gli altri progetti dello stesso
autore, che sono sullo stesso soggetto.
Bye, G.


http://www.Planet-Source-Code.com/vb/scripts/ShowCode.asp?txtCodeId=34787&lngWId=1
Letto :)
Interessante, e utilissimo per svariate applicazioni, ma non per le
concatenazioni.
Comunque ho provato a implementare l'accrocchio che avevo abbozzato con la lista
contenenti array di byte sovradimensionati:
ho implementato solo i metodi fromString, toString e concat poi ho provato
qualche benchmark.
Purtroppo il guadagno c'è solo quando la stringa è troppo grande (si arriva
anche a guadagni del 99%, ovvero cento volte più veloce)...
Ma per stringhe standard perdo malamente il confronto.
termoPilucco

Mi sa che termopilucco vuole divertirsi !
In effetti prima di verificare che per stringhe piccole e medie non ci sono
ventaggi ad usare la lista, mi stavo divertendo :P
terrmoPilucco