Pagina 3 di 6 primaprima 1 2 3 4 5 ... ultimoultimo
Visualizzazione dei risultati da 21 a 30 su 55

Discussione: [C] Funzione di hashing da 16bit

  1. #21
    Utente di HTML.it
    Registrato dal
    Jun 2008
    Messaggi
    1,192
    Scusate, avendo avuto la settimana piena ho cominciato solo ieri.

    Intanto ho un errore, ho semplificato e commentato il codice per permettervi di capirlo.

    https://pastebin.com/SyzQPsbk

    ==25338== HEAP SUMMARY:
    ==25338== in use at exit: 39 bytes in 3 blocks
    ==25338== total heap usage: 8 allocs, 5 frees, 524,407 bytes allocated

    (possibilmente partite dal main)

  2. #22
    Utente di HTML.it
    Registrato dal
    Jun 2008
    Messaggi
    1,192
    Risolto, ora capisco perchè strdup non fa parte di POSIX...

  3. #23
    Quote Originariamente inviata da zacca94 Visualizza il messaggio
    Risolto, ora capisco perchè strdup non fa parte di POSIX...
    Mm, strdup fa parte di POSIX...
    strdup() conforms to SVr4, 4.3BSD, POSIX.1-2001. strndup() conforms to POSIX.1-2008.
    I miei bot Telegram:
    tube2gif_bot: converte spezzoni di filmati YouTube in gif animate da Telegram
    Polygen bot: Polygen direttamente in Telegram!

  4. #24
    Utente di HTML.it
    Registrato dal
    Jun 2008
    Messaggi
    1,192
    Per qualche motivo ero convinto non facesse parte di POSIX...

    Comunque la dicotomica la escludo dal mio esempio, non penso che sia possibile (e anche se lo fosse, ipotizzo solo con uno sforzo disumano), se potete smentirmi rimedio volentieri...
    Ultima modifica di zacca94; 21-09-2017 a 19:09

  5. #25
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,527
    Scusa, ma leggendo il tuo esempio (di cui non ho capito l'utilità) c'è un metodo molto più efficiente:
    essendo che stai riempendo utilizzando sempre lo stesso ordine dato dall'array ab e senza copie ti basta sapere per ogni riga quanti elementi prendi.

    Un'identificatore univoco della combinazione è quindi la tupla (i, j, k) rispetto ad un array costante ab.

    Ora, sapendo che la lunghezza di ogni riga è 5, ovvero che 0 <= i,j,k < 5 possiamo assegnare un singolo intero identificativo per ogni tupla id = i*5^2+j*5^1+k*5^0.

    Il valore massimo teorico che possiamo avere è quindi id = 4*25+4*5+4 = 124, quindi un array statico di 125 elementi è a sufficienza per avere lookup in tempo costante a discapito della memoria.

    Abbiamo tuttavia altre informazioni, ovvero la lunghezza di ab = 7, prendendo questa in considerazione, essendo che distribuiamo gli elementi da sinistra a destra senza ripetizioni possiamo ottenere come massimo valore l'id corrispondente alla tupla (4,3,0), quindi l'id massimo risulta essere effettivamente 115 e quindi un array di 116 elementi è a sufficienza (non che sia un grande risparmio).
    Ultima modifica di Scara95; 23-09-2017 a 15:40
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  6. #26
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,527
    Per aggiungere a quanto ho detto sopra: questa soluzione ti da accesso in tempo costante O(1) ma va tenuto in considerazione anche l'impatto sulla cache rispetto alla dimensione del problema, cosa che io non stavo considerando minimamente.

    Una trie che utilizza come indice la tupla opera in tempo O(n) dove n è il numero di righe della tabella virtuale sulla quale stai distribuendo. Ora supponendo n fissato a tempo di compilazione e sufficientemente piccolo può essere considerata un'operazione in tempo costante, inoltre per valori più grandi del problema potrebbe avere un rapporto migliore con la cache se implementata coscienziosamente essendo che la rappresentazione spreca meno spazio e i valori risultano più vicini in memoria.
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  7. #27
    Utente di HTML.it
    Registrato dal
    Jun 2008
    Messaggi
    1,192
    L'esempio è fuorviante, la prima riga ha 3 colonne.
    E le possibili combinazioni sono 232 (verificato con il metodo di monte carlo)

    Comunque perdonami ma non ho capito quasi nulla di ciò che hai scritto, eccetto che la tua soluzione è più veloce.

    Il tuo esempio continua ad essere valido, anche se la prima riga ha 3 colonne?

    Comunque a prescindere da tutto, la trie è sicuramente la più veloce soluzione, non l'ho verificata, ma ne sono praticamente certo (ho avuto tempo di buttare giù due righe solo oggi).
    Ultima modifica di zacca94; 23-09-2017 a 18:50

  8. #28
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,527
    Spiegami una cosa: usi sempre gli elementi di ab una e una sola volta prendendoli nell'ordine in cui appaiono in ab?
    Ultima modifica di Scara95; 24-09-2017 a 14:18
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  9. #29
    Utente di HTML.it
    Registrato dal
    Jun 2008
    Messaggi
    1,192
    nell'ordine in cui appaiono in ab
    No, l'ordine è casuale.

    Precisiamo subito che:
    codice:
        +----+----+----+                     +----+----+----+
        | az | bd | ce |                     | ce | bd | az |
        +----+----+----+----+----+           +----+----+----+----+----+
        |    |    |    |    |    |   ______  |    |    |    |    |    |
        +----+----+----+----+----+   ______  +----+----+----+----+----+
        | df | ef |    |    |    |           | ef |    |    |    | df |
        +----+----+----+----+----+           +----+----+----+----+----+

    E questo è l'algoritmo di posizionamento (l'ho riscritto per permetterti di comprenderlo, così sono sicuro che capirai anche l'ordinamento):
    codice:
    int _1row[ 3 ];
    int _2row[ 5 ];
    int _3row[ 5 ];
    
    /* ID delle righe */
    int c1 = 0, c2 = 0, c3 = 0;
    
    int choices[ 5 ] = { 1, 2, 3, 4, 5 };
    
    for ( INT c = 0; c < 5; c++ ) {
        /* Posiziono casualmente i 5 elementi in una delle 3 righe */
        switch ( rand() % 3 ) {
            /* Prima riga */
            case 0:
                /* Se la prima riga ha tutte e 3 le colonne occupate posiziona o nella
                   seconda o nella terza riga */
                if ( c1 != 3 ) {
                    _1row[ c1 ] = choices[ c ];
                    c1++;
                } else if ( rand() % 2 == 0 ) {
                    _2row[ c2 ] = choices[ c ];
                    c2++;
                } else {
                    _3row[ c3 ] = choices[ c ];
                    c3++;
                }
                break;
    
            /* Seconda riga */
            case 1:
                _2row[ c2 ] = choices[ c ];
                c2++;
                break;
    
            /* Terza riga */
            case 2:
                _2row[ c2 ] = choices[ c ];
                c2++;
                break;
        }
    }
    Infine faccio il sorting delle tre righe, così è possibile la condizione secondo la quale le tabelle dell'esempio siano uguali se confrontate.

  10. #30
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,527
    Il problema ha sempre queste dimensioni? O devi applicarlo a dimensioni maggiori?
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2017 vBulletin Solutions, Inc. All rights reserved.