[C] Identificazione univoca insiemi

[fracarro]

Salve ragazzi,
ho un problemino da risolvere e mi servirebbe qualche esperto in matematica e programmazione. Allora, io ho il mio insieme di elementi N={1,2,3,......,1000} da cui in base a certe operazioni genero un sottoinsieme di dimensione variabile, es. S1={5,24,134,432,567,700,876}. Ora il mio problema è trovare un sistema per assegnare una chiave univoca a questo insieme di elementi che lo distingua da qualsiasi altro insieme (di dimensione anche differente da S1) generabile da N.

Un modo per ottenere questo risultato è assegnare ad ogni elemento di N un numero primo. Dopodichè dato S1 mi basta moltiplicare i numeri primi associati ai suoi elementi per ottenere una chiave univoca. Il problema però è che moltiplicare tanti numeri primi mi genera delle chiavi spaventose quindi avrei bisogno di qualche altro modo per generare queste chiavi. Qualche idea?

[gugoXX]

se vuoi la certezza matematica avrai chiavi spaventosamente lunghe.
Se invece ti bassta un'ottima coperatura con una probabilita' decisamente bassa di conflitti allora ti puo' bastare una Hash.
Es: Metti tutti i numeri in fila, magari mettendoci anche la dimensione di ciascuno dei sotto-array, e passi tutti il flusso ad un algoritmo come
MD5
Ce ne sono tanti altri, questo e' uno dei piu' usati.

[fracarro]

Originariamente inviato da gugoXX

se vuoi la certezza matematica avrai chiavi spaventosamente lunghe.
Se invece ti bassta un'ottima coperatura con una probabilita' decisamente bassa di conflitti allora ti puo' bastare una Hash.
Es: Metti tutti i numeri in fila, magari mettendoci anche la dimensione di ciascuno dei sotto-array, e passi tutti il flusso ad un algoritmo come
MD5
Ce ne sono tanti altri, questo e' uno dei piu' usati.

Esiste qualche implementazione in C di questo algoritmo? Inoltre il range delle "diverse" chiavi generate dall'algoritmo lo posso decidere io?

[gugoXX]

MD5 e' un algoritmo che restituisce sempre lo stesso spazio di 16byte di firma.
Come detto ce ne sono tanti altri, ma lo spazio della firma mi risulta sia fisso su ciascuno di essi. Cerca quello che ti piace di piu' e provalo.
Altri sono quelli della famiglia SHA
Ci sono anche quelli della famiglia CRC.

Per quanto riguarda l'implementazione invece ovviamente penso esistano implementazioni e librerie di tutti questi algoritmi in C, ma in C non saprei dove dirti di guardare. Piu' probabile C++, anche se su alcune librerie embedded si trova veramente di tutto.
In C# per esempio MD5 e' gia' in libreria, gia' dentro il framework, quindi e' una sola semplice chiamata. Se ti stai rivolgendo al mondo embedded prova anche a valutare il MicroFramwork, che si puo' montare su molti microprocessori del campo (ma non sono assolutamente esperto).

Per quanto riguarda il CRC vesione 32 pensa che negli x86, nella estensione delle istruzioni macchina SSE4.2 (introdotta sui Pentium4 Nehalem) esiste gia' addirittura hardware, sotto il codice opcode appunto CRC32.
Ti basterebbe quindi aprire una

__asm{
  //qualcosina
  CRC32
  //qualcos'altro
}

[fracarro]

Originariamente inviato da gugoXX

MD5 e' un algoritmo che restituisce sempre lo stesso spazio di 16byte di firma.
Come detto ce ne sono tanti altri, ma lo spazio della firma mi risulta sia fisso su ciascuno di essi. Cerca quello che ti piace di piu' e provalo.
Altri sono quelli della famiglia SHA
Ci sono anche quelli della famiglia CRC.

Per quanto riguarda l'implementazione invece ovviamente penso esistano implementazioni e librerie di tutti questi algoritmi in C, ma in C non saprei dove dirti di guardare. Piu' probabile C++, anche se su alcune librerie embedded si trova veramente di tutto.
In C# per esempio MD5 e' gia' in libreria, gia' dentro il framework, quindi e' una sola semplice chiamata. Se ti stai rivolgendo al mondo embedded prova anche a valutare il MicroFramwork, che si puo' montare su molti microprocessori del campo (ma non sono assolutamente esperto).

Per quanto riguarda il CRC vesione 32 pensa che negli x86, nella estensione delle istruzioni macchina SSE4.2 (introdotta sui Pentium4 Nehalem) esiste gia' addirittura hardware, sotto il codice opcode appunto CRC32.
Ti basterebbe quindi aprire una

__asm{
  //qualcosina
  CRC32
  //qualcos'altro
}

Purtroppo a me serve in C e da utilizzare sia sotto windows che sotto linux. Ad ogni modo credo di aver trovato la soluzione qui: http://www.hwupgrade.it/forum/showth...&highlight=md5

Non mi resta che provare. Ad ogni modo grazie per l'aiuto.

P.S. Dati due insiemi per verificare se sono uguali mi basta generare le stringhe ad essi associate (concatenando semplicemente i numeri), passarle all'MD5 e poi usare la strcmp sulle due stringhe ritornate da questo algoritmo.

[gugoXX]

Originariamente inviato da fracarro

P.S. Dati due insiemi per verificare se sono uguali mi basta generare le stringhe ad essi associate (concatenando semplicemente i numeri), passarle all'MD5 e poi usare la strcmp sulle due stringhe ritornate da questo algoritmo.

Esatto. Nel caso in cui le 2 stringhe del MD5 siano diverse sei sicuro che i due insiemi erano diversi gia' in origine.
Se invece le 2 stringhe sono uguali, per avere la certezza dovrai controllarle direttamente. Cosi' funzionano le Hastable.

[fracarro]

Originariamente inviato da gugoXX

Esatto. Nel caso in cui le 2 stringhe del MD5 siano diverse sei sicuro che i due insiemi erano diversi gia' in origine.
Se invece le 2 stringhe sono uguali, per avere la certezza dovrai controllarle direttamente. Cosi' funzionano le Hastable.

Tutto chiaro. Ora stabilito come assegnare ad ogni insieme una chiave diverse dovrei risolvere il secondo problema riguardante l'efficienza. Io ho una lista di insiemi (e quindi di rispettive chiavi) e un nuovo insieme S1. Per controllare se S1 già appartiene a questa lista il modo più semplice è scorrerla e verificare ad uno ad uno le stringhe generate dall'MD5. Non esiste un modo più furbo per fare la ricerca in tempo costante? ( O(1) per intenderci?).

Per esempio poichè le stringhe sono tutte differenti non c'è una funzione che restituisce un numero a seconda della stringa datagli in input? Se invoco l'atoi per fare una cosa del genere i numeri restituiti saranno differenti? Perchè in questo modo potrei generarmi un array booleano e verificare in tempo costante se S1 appartiene alla lista.

[gugoXX]

Stai reinventando l'hashtable, che ha proprio complessita' O(1)

Cerca una libreria per l'hashtable, una per l'MD5, cucini a fuoco lento ed hai finito.

[fracarro]

Originariamente inviato da gugoXX

Stai reinventando l'hashtable, che ha proprio complessita' O(1)

Cerca una libreria per l'hashtable, una per l'MD5, cucini a fuoco lento ed hai finito.

non potresti indicarmene qualcuna? Magari che hai utilizzato in passato e con cui ti sei trovato bene?

[gugoXX]

Purtroppo in C non ne conosco, anche se cercando con google ne ho appena trovate tantissime. Non saprei consigliarti, ma ovviamente sembrano abbastanza complesse.
Personalmente le hastable le uso tutti i giorni, ma in C# (conosciute con il nome di Dictionary)
Ma perche' proprio C e non almeno C++? Forse in C++ qualche template samplice riesci a trovarlo.
Davvero penso che oggi il C sia limitato al mondo embedded, e anche li' piano piano lo stanno lasciando.

Fra l'altro, se la tua utility non e' un'utility grafica, oppure se fa uso regolare delle finestre allora potresti valutare di scrivere il codice in C# e farlo funzionare sia sotto Windows che sotto Linux (progetto MONO), oppure in Java, e farlo funzionare poi sotto qualche java virtual machine.
Io oggi seguirei questa strada, per non perdersi in tecnicismi che possono deviare i tuoi sforzi da quello che e' il vero studio della tua utility.

[Manbearpig]

se hai bisogno di identificare solo sottoinsiemi semplici e non multiinsiemi allora potresti vedere ogni sottoinsieme come una stringa di bit dove un bit e' posto a 1 se l'elemento e' presente ed e' posto a 0 se l'elemento non e' presente. Es. {0,3,7} = 1001000100000000000...
trasformi la stringa binaria in un intero e hai una chiave.

[gugoXX]

Se non ho capito male il problema e' diverso.
Vorrebbe che i 2 insiemi
{2,4,8} e {4,8,2} siano considerati diversi.

[Manbearpig]

Beh per definizione un isieme non e' ordinato. In ogni caso ho detto una stronzata prima convertirlo in un intero non e' possibile... (1000 bit)
Cmq potrebbe tenersi la stringa di bit come identificatore

[fracarro]

Allora per quanto riguarda {2,4,6} e {2,6,4} per me sono la stessa cosa proprio perchè insiemi. Tuttavia la soluzione con i bit se da un lato risparmia in memoria e mi permette di effettuare il confronto tra due insiemi velocemente tramite l'and bit a bit dall'altro mi costringerebbe a verificare la lista dei insiemi per intero, per questo ho scartato l'ipotesi dei bit.

A questo punto l'unica soluzione mi sembra quella di trovare una libreria (più semplice possibile) per l'hashtable come consigliato gugoXX.

Riguardo il mio codice sono algoritmi di ottimizzazione quindi niente grafica e finestre. Una semplice linea di comando per risolvere un determinato problema di ottimizzazione. (Gli insiemi registrati nella hash table non sono altro che gli elementi di una tabu list e siccome devo verificare velocemente se una "mossa" è tabu devo sapere velocemente se un insieme appartiene o meno all'hashtable).

[Manbearpig]

Il problema dell'hashtable sono le collisioni, avrai quindi insiemi diversi con lo stesso hash in quel caso dovrai confrontare tutti gli elementi dell'insieme con tutti gli insiemi che hanno lo stesso hash. nel peggiore dei casi hai 1000*1000*k confronti, dove k e' il numero di collisioni.

[Manbearpig]

Una soluzione ibrida probabilmente e' la cosa migliore, usi una hashtable nella quale memorizzi i tuoi valori sotto forma di stringhe di bit, in questo modo in caso di collisione puoi fare i confronti molto velocemente.

[gugoXX]

No, guarda, allora ti consiglio di utilizzare un ibrido della mia soluzione e quella di Manbearpig, perche' avevo sopravvalutato il problema.

Con la soluzione di Manbearpig ti calcoli la chiave di ogni tuo insieme. (1000bit = 62byte invece che 32 dell'MD5)
Con una hashtable mantieni l'insieme di tutti gli elementi, controllando l'esistenza in O(1).

La hastable non e' altro che un vettore di oggetti, il cui indice, chiamato chiave, non e' un intero come nei vettori normali, ma sono altri oggetti.
Giusto per spiegarti un funzionamento:

Se sei su linea di comando JAVA o C# e vai a nozze sia sotto Linux che sotto Windows.
Forse bisogna aggiungere qualcosa sul comparatore di eguaglianza del tipo byte[], ma non sono sicuro.

class Program
    {
        static void Main(string[] args)
        {
            //Inizializzo la hastable
            //TaleHashTable in questa implementazione restituisce, dato un risultato compattato in bit, quello che era l'insieme degli interi originari.
            // Se la hash la usi solo per testare l'esistenza del tuo risultato allora e' ancora piu' semplice.
            Dictionary<byte[], List<int>> MyMem = new Dictionary<byte[], List<int>>();
                       
            do
            {
                //Leggo una nuova lista in qualche modo
                List<int> nuovo=GenerateNuovoInsieme();
                //Ne calcolo il risultato;
                List<int> risultato = FromInisiemeToRisultato(nuovo);
                //Compatto il risultato in bit, invece che usare l'MD5
                byte[] RisultatoCompattato=CompactRisultato(risultato);

                //Lavoro sulla hash
                if (MyMem.ContainsKey(RisultatoCompattato))
                {
                    //Qui il codice di che faccio se gia' ce l'ho
                }
                else
                {                    
                    //Qui il codice di che faccio se non ce l'ho, oltre a memorizzarlo nella hash
                    MyMem[RisultatoCompattato] = nuovo;
                }                
            } while (Console.ReadKey().Key!=ConsoleKey.Escape);

        }        

        static List<int> FromInisiemeToRisultato(List<int> Insieme)
        {            
            List<int> ret = new List<int>();
            // qui il codice per calcolare l'insieme risultato dato l'insieme di ingresso
            return ret;
        }

        static byte[] CompactRisultato(List<int> risultato)
        {
            byte[] ret=new byte[64];
            //Qui il codice di ManBearPig per compattare una lista in un array di byte
            return ret;
        }

        static List<int> GenerateNuovoInsieme()
        {
            List<int> ret = new List<int>();
            // qui il codice per riempire l'insieme;
            return ret;
        }
    }

[fracarro]

Originariamente inviato da gugoXX

No, guarda, allora ti consiglio di utilizzare un ibrido della mia soluzione e quella di Manbearpig, perche' avevo sopravvalutato il problema.

Con la soluzione di Manbearpig ti calcoli la chiave di ogni tuo insieme. (1000bit = 62byte invece che 32 dell'MD5)
Con una hashtable mantieni l'insieme di tutti gli elementi, controllando l'esistenza in O(1).

La hastable non e' altro che un vettore di oggetti, il cui indice, chiamato chiave, non e' un intero come nei vettori normali, ma sono altri oggetti.
Giusto per spiegarti un funzionamento:

Se sei su linea di comando JAVA o C# e vai a nozze sia sotto Linux che sotto Windows.
Forse bisogna aggiungere qualcosa sul comparatore di eguaglianza del tipo byte[], ma non sono sicuro.

....

A me sembra invece più efficiente usare soltanto la hashtable senza creare la chiave tramite i bit (anche perchè non mi interessa risolvere eventuali conflitti nella hashtable). Mi spiego meglio. Se per esempio devo rappresentare l'insieme {2,7,4,9} io prima me lo ordino e poi genero la stringa str=2,7,4,9 che rappresenta la mia chiave. Da li poi uso la hashtable. Se invece la chiave la devo generare usando i bit sono costretto (almeno credo) a a inizializzarli tutti a zero e poi a settare ad uno solo quelli corrispondenti agli elementi dell'insieme. Se è così la prima soluzione è più efficiente.

[Manbearpig]

Originariamente inviato da fracarro

A me sembra invece più efficiente usare soltanto la hashtable senza creare la chiave tramite i bit (anche perchè non mi interessa risolvere eventuali conflitti nella hashtable). Mi spiego meglio. Se per esempio devo rappresentare l'insieme {2,7,4,9} io prima me lo ordino e poi genero la stringa str=2,7,4,9 che rappresenta la mia chiave. Da li poi uso la hashtable. Se invece la chiave la devo generare usando i bit sono costretto (almeno credo) a a inizializzarli tutti a zero e poi a settare ad uno solo quelli corrispondenti agli elementi dell'insieme. Se è così la prima soluzione è più efficiente.

Beh si e' una buona soluzione, in ogni caso i conflitti in qualche modo dovrai gestirli... ordinando gli insiemi riduci il costo del confronto in caso di conflitto ma hai il costo di ordinare tutti gli insiemi. Cosa in effetti sia piu' efficente dipende molto dall'istanza del problema.
Per quanto riguarda il settare i bit a zero ti basterebbe una memset che ha costo pari a zero, e per settare i bit a 1 ti basta scorrere una volta gli elementi dell'insieme.

[lovaz]

Risposta da ignorante: e se invece ti costruisci degli alberi del tipo:

2
| - 3 - 4
| - 145

7
| - 456

per rappresentare ad es. gli insiemi {2,3,4}, {2,145}, {7,456}
e mentre crei un nuovo insieme confronti il primo elemento con le radici,
se non lo trovi l'insieme è nuovo (crei un nuovo albero),
se lo trovi confronti il secondo el. con i figli della radice, e così via,
finché non trovi l'elemento (insieme nuovo -> aggiungi un sottoalbero).

Nel caso sopra se generi l'insieme {2, 145, 146} al terzo tentativo saprai che
è nuovo, in quanto 145 non ha figli.

Forse questa roba ha anche un nome, ma io che sono un pozzo di ignoranza non lo so