Problema algoritmo lento...

aleasia

il 04 feb 2017, 09:02

31 risposte

aleasia

Utente Attivo

Iscritto da: feb, 2015

Messaggi:: 168

Problema algoritmo lento...

04 feb 2017, 09:05

Ciao,

Vi riassumo brevemente il problema, nel forum di Mersenneforum . Org su miscellaneous math , sul thread " Can I decrease the factorization time with this formula? " non capisco cosa intendono dire quando dicono alla fine della 5a pagina che l'algoritmo è lento perché è homegrown bignum library , che in pratica è un algoritmo di supernumeri di un utente di questo forum.

Vi lascio comunque il link http://www.mersenneforum.org/showthread.php?t=21996&page=5

31 Risposte

oregon

Super Famoso

Iscritto da: nov, 2011

Messaggi:: 21791

Re: Problema algoritmo lento...

04 feb 2017, 09:22

Ti sta dicendo che è un "codice inefficiente, fatto in casa" come ce ne sono tanti.

Del resto, funzioni come queste


    // dato in input un carattere che rappresenta una cifra, 
    // rende in uscita il byte corrispondente
char char_byte(char n)
 {
  if (n=='0') return 0;
  if (n=='1') return 1;
  if (n=='2') return 2;
  if (n=='3') return 3;
  if (n=='4') return 4;
  if (n=='5') return 5;
  if (n=='6') return 6;
  if (n=='7') return 7;
  if (n=='8') return 8;
  if (n=='9') return 9;
 }   // fine char_byte()

/* --------------------------------------------------------- */

    // l'inversa della precedente
char byte_char(char n)
 {
  if (n==0) return '0';
  if (n==1) return '1';
  if (n==2) return '2';
  if (n==3) return '3';
  if (n==4) return '4';
  if (n==5) return '5';
  if (n==6) return '6';
  if (n==7) return '7';
  if (n==8) return '8';
  if (n==9) return '9';
 }   // fine byte_char()

mi sembrano ridicole

aleasia
Utente Attivo
Iscritto da
feb, 2015
Messaggi:
168
Re: Problema algoritmo lento...
04 feb 2017, 09:28
Ma si può rendere molto più efficiente con delle librerie ? Qual'è l'alternativa ?
M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6073
Re: Problema algoritmo lento...
04 feb 2017, 10:04
@aleasia, scrivere codice efficiente NON E' QUASI MAI un problema di codifica.
QUASI MAI non vuol dire mai: in questo caso, come indicato da @oregon, e' ovvia l'estrema inesperienza dell'autore.
La scrittura di codice efficiente coinvolge, nel 99.9% dei casi, lo sfruttare PROPRIETA' dell'oggetto che si sta' implementando. E questo lo di puo' fare SOLO avendo una conoscenza MOLTO APPROFONDITA della materia.
Questo implica che chiunque non abbia almeno una decina di anni di esperienza, non puo' sapere come scrivere codice efficiente.

In generale, nel caso in cui si sia alle prime armi, la regola da seguire e' semplice: mai fare due volte la stessa cosa.

Si, le librerie, se scritte da persone con i contro..., possono migliorare SIGNIFICATIVAMENTE le performance di un algoritmo. POSSONO perche' poi entra in gioco COME la libreria viene usata.

Tanto per fare un esempio, le due funzioncine possono essere ridotte a questo:
```
    // dato in input un carattere che rappresenta una cifra, 
    // rende in uscita il byte corrispondente
inline char char_byte(char n)
 {
  return n - '0';
 }   // fine char_byte()

/* --------------------------------------------------------- */

    // l'inversa della precedente
inline char byte_char(char n)
 {
   return '0' + n;
 }   // fine byte_char()
 
```
Oppure usare una MACRO
O
oregon
Super Famoso
Iscritto da
nov, 2011
Messaggi:
21791
Re: Problema algoritmo lento...
04 feb 2017, 10:14
aleasia ha scritto:
Ma si può rendere molto più efficiente con delle librerie ? Qual'è l'alternativa ?
L'alternativa è buttare quel codice e riscriverlo.
Chi lo ha scritto, aveva un'esperienza di programmazione di qualche settimana - al massimo.

Ovvero usare librerie già esistenti ed affermate.
Korr
Pochi posts
Iscritto da
mag, 2015
Messaggi:
41
Re: Problema algoritmo lento...
05 feb 2017, 17:48
Nella pagina "Notizie sul sito" ho scritto espressamente
che nei miei listati non si trovano algoritmi superefficienti
e che a me basta che i programmi funzionino, considerate
le mie esigenze.

www.corradodamiano.it/notizie_sito.ht

Non pretendo che questi programmi siano i migliori del Mondo,
ne' che siano adottati dalla NASA.

Chi non apprezza il mio modo di programmare puo' benissimo
cercare listati migliori in altri siti, farseli da se'
o perfezionare i miei.

Per quanto riguarda le due funzioni incriminate,
char_byte() e byte_char(), queste vengono utilizzate
solo per l'input/output dei dati;

char_byte() viene chiamata da leggi_sup() (inserimento supernumero
da tastiera) e da leggi_sup_file() (lettura di supernumero-stringa
da file);

byte_char() viene chiamata da mostra_sup() (visualizzazione supernumero)
e da salva_sup_file() (salvataggio di supernumero-stringa in file).

Nessuna delle due funzioni viene usata nei calcoli; e' verificabile
da chiunque che i tempi di elaborazione (nei puri calcoli) non variano
usando la mia versione o quella proposta da Migliorabile.

Pertanto, le critiche rivoltemi sono del tutto campate in aria.

Ed e' anche gravemente ingiusto sentenziare su di me e sulla mia opera
basandosi (ed erroneamente) su una sola delle varie centinaia
di funzioni che ho creato.

La lentezza delle mie funzioni per supernumeri e' provocata piuttosto
dal fatto che ho usato algoritmi di calcolo ingenui (cioe' che presuppongono
solo una cultura scolastica); invece le librerie "ufficiali" sono fatte
da persone che hanno studiato in modo approfondito
teoria dei numeri e possono usare algoritmi piu' sofisticati.
M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6073
Re: Problema algoritmo lento...
05 feb 2017, 18:36
@Korr, anche se l'implementazione non e' super efficiente, E' NECESSARIO che sia scritta in modo da dimostrare che l'autore ha adeguate competenze.

Le due funzioncine DIMOSTRANO che le competenze dell'autore sono sotto il livello minimo necessario per SUPPORE che il lavoro POSSA avere qualche validita'.

L'implementazione SUPEREFFICIENTE RARAMENTE migliora una BUONA implementazione DI ORDINI DI GRANDEZZA, al piu' lo fa con qualche fattore < 10.

La BUONA implementazione e' sinonimo di competenza tecnica da una parte e di conoscenza del dominio dall'altra.

E no, NON BASTA che funzionino, altrimenti anche implementare una moltiplicazione mediante delle somme, per funzionare, funziona!
O fare una divisione per tentativi, o controllare se N e' primo provando a dividere il numero per tutti i numero < N.
Per funzionare, funziona, ma e' robbbbba da elementari.

Sia chiaro: per l'implementazione di algoritmi, l'analisi delle performance, e dimostrane la validita', NON SERVE essere programmatori con 20 anni di esperienza, con conoscenza di 10 linguaggi di programmazione e 10.000 librerie di terze parti!
BASTA SAPERE programmare, conoscere bene il linguaggio di programmazione che si vuole utilizzare, ESSERE ORDINATI, e CURARE i dettagli.

Basta un po' di ricerca bibliografica, senza andare a cercare testi superspecialistici, per trovare la descrizione di algoritmi efficienti e facilmente implementabili per un''infinita' di argomenti. Non ultimi la teoria dei numeri.
E basta qualche testo introduttivo di programmazione, epr acquisire i concetti fondamentali di programmazione!

Tutte cose che uno che programma da quando esisteva il Turbo Pascal (1983) ed il Turbo C++ (1990) dovrebbe ormai aver abbbondantemente digerito.
M.A.W. 1968
Utente Attivo
Iscritto da
ott, 2011
Messaggi:
321
Re: Problema algoritmo lento...
06 feb 2017, 01:20
Korr ha scritto:
Nella pagina "Notizie sul sito" ho scritto espressamente
che nei miei listati non si trovano algoritmi superefficienti
e che a me basta che i programmi funzionino, considerate
le mie esigenze.

http://www.corradodamiano.it/notizie_sito.ht

Non pretendo che questi programmi siano i migliori del Mondo,
ne' che siano adottati dalla NASA.

Chi non apprezza il mio modo di programmare puo' benissimo
cercare listati migliori in altri siti, farseli da se'
o perfezionare i miei.
Questa retorica è intrinsecamente autocontraddittoria. Lo scopo intrinseco nella condivisione di codice sorgente è innanzitutto quello di offrire un esempio di codice, non un semplice "programma funzionante". Esistono degli standard ingegneristici minimi da rispettare, che piaccia o meno, per una sorta di responsabilità morale nei confronti degli insipienti e degli studenti che nessuna liberatoria "as is" può mitigare o cassare.

Non ha il benché minimo senso dichiarare di non essere in possesso della patente di guida e di spingere a mano l'automobile da casa al supermercato e viceversa, una assurdità che certamente "funziona" ma è totalmente fuori da ogni razionalità. Nel caso dell'automobile esiste il Codice della Strada e le relative violazioni sono sanzionabili a norma di legge: nel caso del software engineering, non si va in galera né si finisce per qualche anno nelle cave ai lavori forzati (purtroppo!) ma comunque si stanno violando regole di stile e anche convenzioni non scritte accettate dall'intera comunità dei practitioners professionisti, i quali trovano doveroso rimarcarlo in presenza di codice praticamente privo di progettazione e basato su algoritmi totalmente inaccettabili.

In ambedue i casi "la legge non ammette ignoranza": non si può semplicemente dire "per i miei scopi" o "non conosco le regole MISRA/C o lo standard CERT". Perché se è solo "per i tuoi scopi" allora anche bene che resti "sul tuo hard disk", diffonderlo è totalmente controproducente, sia per i curiosi e i meno scafati, sia nei confronti della comunità professionale.
In caso contrario, c'è un obbligo non scritto ad un livello minimo di qualità dei sorgenti, progettazione, leggibilità, documentazione e soprattutto uso di algoritmi con prestazioni quantomeno accettabili, non dell'equivalente del bogosort in qualsiasi altro campo.

Il famigerato "basta che funzioni" non ha il benché minimo senso, specialmente in ambiti delicati come la teoria computazionale del numero!
Korr
Pochi posts
Iscritto da
mag, 2015
Messaggi:
41
Re: Problema algoritmo lento...
06 feb 2017, 15:31
Gentili Migliorabile e MAW1968,
terro' conto dei vostri consigli e ammonimenti,
pero' sara' una cosa lunga.

Infatti sto rivedendo e perfezionando anche gli altri listati
e non posso dedicarmi a tempo pieno a queste attivita'.

Vi comunico che ho anche provato una nuova versione dei supernumeri,
con allocazione dinamica della memoria, per occupare solo lo spazio
necessario alle cifre di ogni singolo numero. Pero' l'elaborazione
e' ancora piu' lenta; ipotizzo che sia dovuto al lavoro aggiuntivo
richiesto al s.o. per collocare e mappare i dati in memoria heap.
M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6073
Re: Problema algoritmo lento...
06 feb 2017, 15:57
Nessuno richiede un'attivita' al 100%: basta che il risultato sia di qualita' accettabile

Invece, tu CONOSCI gia' 'GMP'?
Libreria che fa gia' tutto quello che serve in modo STRAEFFICIENTE (implementazione in assembler, quando possibile) per gli interi a precisione arbitraria

https://gmplib.org

Per le 4 operazioni, tu CONOSCI GIA' TAOP (The Art Of Computer Programming), vol 2 - Seminumerical Alghoritms, cap 4 - Arithmetic?
La BIBBIA per quanto riguardano gli algoritmi per implementare le 4 operazioni per gli interi

In alternativa: Handbook of Applied Cryptography, cap 2, par 4 - Number Theory

Probabilmente M.A.W puo' fornire ulteriori riferimenti bibliografici.

Se non li conosci, e' l'occasione buona per leggere qualcosa sull'argomento.
In particolare, "Handbook of Applied Cryptography" lo trovi gratuitamente in formato PDF

http://cacr.uwaterloo.ca/hac

NON SERVE essere super esperti per capire l'implementazione degli algoritmi descritti

Domandona di rito, ma il supernumero lo stai rappresentando in base 10, 2, 16, 128 o 32768?

Per ridurre i tempi di allocazione, ci sono trucchi truchettosi: ad esempio usare dei pool di buffer.
INVECE di allocare SOLO la memoria che ti serve, allocchi blocchi di dimensione predefinita (16 byte, 64, 256, 1024, ...) abbastanza grandi per le necessita' del momento. Invece di deallocarla, la metti nel pool, che interrogerai all'allocazione successiva.
O
oregon
Super Famoso
Iscritto da
nov, 2011
Messaggi:
21791
Re: Problema algoritmo lento...
07 feb 2017, 10:50
Korr ha scritto:
Nella pagina "Notizie sul sito" ho scritto espressamente
che nei miei listati non si trovano algoritmi superefficienti
e che a me basta che i programmi funzionino, considerate
le mie esigenze.
Io ho solo fatto notare, a chi aveva adottato quel codice, che era scritto in maniera "banale" e ho anche evidenziato un paio di funzioni in cui la cosa era evidente. Scrivere quelle funzioni in modo "corretto" non significava affatto essere "superefficienti" ma normali programmatori C.

Come già evidenziato ampiamente, non basta affatto che i "programmi funzionino", mi sembra un fatto così scontato in programmazione che ho un po' di ritegno a doverlo evidenziare.

Questo non inficia il tuo lavoro, ma quando lo esponi alle "critiche" sul web, non puoi fare a meno di considerarle.
Korr
Pochi posts
Iscritto da
mag, 2015
Messaggi:
41
Re: Problema algoritmo lento...
08 feb 2017, 08:19
Ho visto in vari siti che ci sono algoritmi piu' efficienti
di quelli da me usati:

Karatsuba, Toom, Schonhage-Strasser, Fuhrer, ecc.

Mi pare di capire che la base 10 (che ho utilizzato per i supernumeri)
non va bene, ma che devo imparare a padroneggiare anche altre basi (non solo 2 e 16).

Su GMP avevo letto qualcosa, ma non ho mai usato questa libreria.

Per adesso mi sono procurato su internet i seguenti materiali:

C Style Guide. August 1994. NASA

SEI CERT C Coding Standard. Rules for Developing Safe, Reliable
and Secure Systems. 2016. Software Engineering Institute. Carnegie Mellon University

Nel sito di MISRA ho visto che ci sono parecchie guide;
devo individuare quella piu' adatta.

In una celebre libreria di Milano vendono The CERT Secure Coding Standard
di Robert Seacord; hanno anche The Art... di Knuth (l'opera completa
e' mastodontica, anche come prezzo, pero' e' possibile comprare
singoli volumi; so che e' un classico, ma non l'ho mai nemmeno visto).

Il trucco del pool di buffer devo studiarlo perche' non l'avevo mai sentito/letto;
esistono libri o documenti in rete? C'e' bisogno di librerie non standard
o posso implementarlo solo con calloc/malloc/free?

Ringrazio tutti per gli input che mi avete dato.

Le vs critiche non erano campate in aria; sono state, invece, una scossa
benefica per spingermi a progredire.
D
dvaosta
Molto attivo
Iscritto da
lug, 2012
Messaggi:
962
Re: Problema algoritmo lento...
08 feb 2017, 09:42
Per il pool devi creare una lista linkata in cui vai mettere i blocchi di memoria quando non li usi più, insieme alla loro dimensione (quindi al posto della free farai qualcosa del tipo insert(list_ptr, block_ptr, block_size)). Quando vuoi allocare nuova memoria, prima di tutto guardi se nella lista hai a disposizione un blocco di dimensioni sufficienti, altrimenti fai una malloc. Se devi fare una realloc e nella lista hai un blocco abbastanza grande, fai una insert per mettere in lista il blocco vecchio e poi una get per prendere quello nuovo; se non c'è un blocco adeguato nella lista, la cosa migiore sarebbe cercare di capire se la realloc riuscirebbe ad espandere il blocco corrente o dovrebbe allocarne uno nuovo: nel secondo caso potresti fare una insert prima della realloc. Però non è così facile predire cosa farebbe la realloc, quindi la cosa più semplice è non fare la insert.

Puoi poi migliorare i tempi di ricerca del blocco, ad esempio usando una lista ordinata in ordine crescente in base alla dimensione, oppure fondendo tra loro i blocchi adiacenti. Se poi allochi solo per potenze di 2 (o di qualsiasi altro numero), come suggerito da migliorabile, potresti usare al posto di una lista un array di liste, dove l'indice dell'array è la potenza del due, per cui all'indice 1 hai la lista di tutti i blocchi di lunghezza 2, all'indice 2 tutti i blocchi di lunghezza 4 e così via. In questo modo velocizzi sia la ricerca che l'inserimento, ma puoi fondere tra loro solo blocchi della stessa dimensione, e solo 2^N alla volta (perché il blocco fuso deve avere sempre una dimensione potenza di 2).
Korr
Pochi posts
Iscritto da
mag, 2015
Messaggi:
41
Re: Problema algoritmo lento...
14 feb 2017, 01:30
Grazie per le ulteriori indicazioni.

Sto gia' facendo alcune letture ed esperimenti.

Vedro' cosa si puo' fare.
M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6073
Re: Problema algoritmo lento...
14 feb 2017, 08:10
Le parole maggggiche, da usare per una ricerca con Google sono:

"teoria computazionale dei numeri"
"computational number theory"
"basic algorithms in number theory"
"elementary number theory"

Devi accedere o registrarti per scrivere nel forum

31 risposte