Problema algoritmo lento...

di il
31 risposte

Problema algoritmo lento...

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

  • Re: Problema algoritmo lento...

    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
  • Re: Problema algoritmo lento...

    Ma si può rendere molto più efficiente con delle librerie ? Qual'è l'alternativa ?
  • Re: Problema algoritmo lento...

    @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
  • Re: Problema algoritmo lento...

    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.
  • Re: Problema algoritmo lento...

    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.
  • Re: Problema algoritmo lento...

    @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.
  • Re: Problema algoritmo lento...

    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!
  • Re: Problema algoritmo lento...

    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.
  • Re: Problema algoritmo lento...

    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.
  • Re: Problema algoritmo lento...

    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.
  • Re: Problema algoritmo lento...

    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.
  • Re: Problema algoritmo lento...

    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).
  • Re: Problema algoritmo lento...

    Grazie per le ulteriori indicazioni.

    Sto gia' facendo alcune letture ed esperimenti.

    Vedro' cosa si puo' fare.
  • Re: Problema algoritmo lento...

    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