Migliore struttura dati

di
morellik
il
15 risposte
morellik
morellik
Utente Attivo
Iscritto da
ott, 2013
Messaggi:
171

Migliore struttura dati

Ho un file excel contenente una serie di coppie chiave/valore che devo portare in una struttura dati Java per poi utilizzarle per stampare il valore in base alla chiave. Fin qui la struttura dati migliore parrebbe una HashMap. Ma dato che ho 192 chiavi e la maggioranza dei valori sono uguali (ho un totale di 9 valori univoci), esiste qualcosa che posso usare per evitare la ridondanza dei valori?

Ecco un pezzo dell'excel:

NOX1_HUMAN The predicted protein contains an iron-binding Pfam domain with a conserved MBP
STEA2_HUMAN The predicted protein contains an iron-binding Pfam domain with a conserved MBP
NOX4_HUMAN The predicted protein contains an iron-binding Pfam domain with a conserved MBP
STEA1_HUMAN The predicted protein contains an iron-binding Pfam domain with a conserved MBP
STEA4_HUMAN The predicted protein contains an iron-binding Pfam domain with a conserved MBP
NOX5_HUMAN The predicted protein contains an iron-binding Pfam domain with a conserved MBP
NPAS2_HUMAN The predicted protein contains an iron-binding Pfam domain with a conserved MBP
FADS1_HUMAN The predicted protein contains a conserved MBP (based on local search)
FADS2_HUMAN The predicted protein contains a conserved MBP (based on local search)
FA2H_HUMAN The predicted protein contains a conserved MBP (based on local search)
SHIP2_HUMAN The predicted protein contains a conserved MBP (based on local search)
GCYA2_HUMAN The predicted protein contains a conserved MBP (based on local search)


Grazie

15 Risposte

  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: Migliore struttura dati

    morellik ha scritto:

    Ma dato che ho 192 chiavi e la maggioranza dei valori sono uguali (ho un totale di 9 valori univoci), esiste qualcosa che posso usare per evitare la ridondanza dei valori?
    Beh, non sembra un grosso problema (poi per "sole" 192 entry). Se i valori li prendi e inserisci nella mappa come oggetti String distinti, allora sì, c'è ridondanza (e spreco) in memoria. Al limite puoi realizzare un meccanismo di "sharing" (riuso) delle stringhe (che tanto sono "immutabili").
  • morellik
    morellik
    Utente Attivo
    Iscritto da
    ott, 2013
    Messaggi:
    171

    Re: Migliore struttura dati

    Se uso una HashMap la coppia chiave/valore è formata sicuramente da due stringhe (potrei fare diversamente?). La seconda frase mi è totalmente oscura. Mi puoi fare qualche esempio?
  • +
    +m2+
    Utente Famoso
    Iscritto da
    mag, 2017
    Messaggi:
    3548

    Re: Migliore struttura dati

    Te lo dico io.
    Nessuno.
    La più semplice che ti viene in mente.
    Un argomento che, quasi sempre, viene tralasciato è che per cardinalità minime va bene "qualsiasi cosa", non serve alcun risparmio di memoria, nè addirittura di complessità computazionale.

    Ti faccio un esempio banale: secondo te qual'è l'algoritmo migliore per ordinare X numeri interi?
    Rifletti un secondo, prima di dare la risposta più banale (e tipicamente sbagliata)
  • morellik
    morellik
    Utente Attivo
    Iscritto da
    ott, 2013
    Messaggi:
    171

    Re: Migliore struttura dati

    +m2+ ha scritto:

    Te lo dico io.
    Nessuno.
    La più semplice che ti viene in mente.
    Un argomento che, quasi sempre, viene tralasciato è che per cardinalità minime va bene "qualsiasi cosa", non serve alcun risparmio di memoria, nè addirittura di complessità computazionale.
    Più che altro era un problema di ridondanza sia nella stesura che nella manutenibilità. Se mi cambiano un valore, lo devo modificare in n righe di codice.
    Se potessi avere una struttura che mi permettesse un legame molti a uno, sarei a cavallo. Potrei utilizzare due HashMap. Una con la chiave e l'altra con un valore che in realtà e' la chiave dell'altra HashMap che restituisce il valore che mi serve.
    Ti faccio un esempio banale: secondo te qual'è l'algoritmo migliore per ordinare X numeri interi?
    Rifletti un secondo, prima di dare la risposta più banale (e tipicamente sbagliata)
    Boh, userei una Collection.sort
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: Migliore struttura dati

    morellik ha scritto:

    Più che altro era un problema di ridondanza sia nella stesura che nella manutenibilità. Se mi cambiano un valore, lo devo modificare in n righe di codice.
    Se potessi avere una struttura che mi permettesse un legame molti a uno, sarei a cavallo.
    Se anche si mettesse in atto un meccanismo di "pooling" degli oggetti String, per averli "unici" per contenuto, non risolverebbe comunque quello che dici.
    Se hai una map e due chiavi "pippo" e "paperino", entrambe associate allo STESSO oggetto String, siccome String è immutabile, non puoi farci nulla su quello. Dovresti per forza rifare il put sulle due chiavi con un ALTRO oggetto String "aggiornato".
  • morellik
    morellik
    Utente Attivo
    Iscritto da
    ott, 2013
    Messaggi:
    171

    Re: Migliore struttura dati

    andbin ha scritto:

    Se anche si mettesse in atto un meccanismo di "pooling" degli oggetti String, per averli "unici" per contenuto, non risolverebbe comunque quello che dici.
    Se hai una map e due chiavi "pippo" e "paperino", entrambe associate allo STESSO oggetto String, siccome String è immutabile, non puoi farci nulla su quello. Dovresti per forza rifare il put sulle due chiavi con un ALTRO oggetto String "aggiornato".
    L'uso di due HashMap come la vedi?

    ["k1", "1"] -> ["1", "Stringa"]
    ["k2", "1"] --------|
    ["k3", "1"]--------/
    ["k4", "2"] -> ["2", "String"]
    ["k5", "2"] ------/
  • +
    +m2+
    Utente Famoso
    Iscritto da
    mag, 2017
    Messaggi:
    3548

    Re: Migliore struttura dati

    morellik ha scritto:

    Se mi cambiano un valore, lo devo modificare in n righe di codice.
    Se potessi avere una struttura che mi permettesse un legame molti a uno, sarei a cavallo.
    Ma che ti frega?
    Fai un banale vettore. Perchè vuoi deduplicarla?
    Ha senso?
    No
    Ti faccio un esempio banale: secondo te qual'è l'algoritmo migliore per ordinare X numeri interi?
    Rifletti un secondo, prima di dare la risposta più banale (e tipicamente sbagliata)
    Boh, userei una Collection.sort
    In realtà no, ecco l'esempio classico (è la tipica domanda trabocchetto di ingegneria del software, ne avrò fatte 1000 )
    Dipende da X.
    Se dovessi ordinare due numeri, useresti una qualche struttura?
    E per 4?
  • morellik
    morellik
    Utente Attivo
    Iscritto da
    ott, 2013
    Messaggi:
    171

    Re: Migliore struttura dati

    +m2+ ha scritto:

    Ma che ti frega?
    Fai un banale vettore. Perchè vuoi deduplicarla?
    Ha senso?
    No
    Abbi pazienza, ma qui non ti seguo. Un vettore (se intendi un oggetto List) di cosa? Delle chiavi o dei valori?
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: Migliore struttura dati

    morellik ha scritto:

    +m2+ ha scritto:

    Abbi pazienza, ma qui non ti seguo. Un vettore (se intendi un oggetto List) di cosa? Delle chiavi o dei valori?
    Probabilmente intendeva un List<DatiRiga> (o Vector o array) dove DatiRiga (o altro nome che si vuole) sarebbe una tua classe che "modella" i dati di una singola riga.

    La questione principale è: COME intendi usare quei dati nella applicazione Java? Ti basta scorrere ciascun oggetto DatiRiga nella lista per fare "qualcosa"? A fronte di un valore come "NOX1_HUMAN" vuoi rintracciare velocemente il testo associato? Altro?
    Devi chiarire insomma COSA ci devi fare con i dati ...
  • morellik
    morellik
    Utente Attivo
    Iscritto da
    ott, 2013
    Messaggi:
    171

    Re: Migliore struttura dati

    Data la chiave, devo ritornare il valore. Il tutto velocemente.
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: Migliore struttura dati

    morellik ha scritto:

    Data la chiave, devo ritornare il valore. Il tutto velocemente.
    Detto così, allora una map (HashMap), indubbiamente.

    Ma riguardo la questione del "Se mi cambiano un valore, lo devo modificare in n righe di codice", è da valutare. Perché cose di questo tipo, cioè la deduplicazione di un dato, generalmente non si fanno. Poi tecnicamente, se si vuole, si fa senza grossi problemi (ma non con la doppia mappa come dicevi!).
  • morellik
    morellik
    Utente Attivo
    Iscritto da
    ott, 2013
    Messaggi:
    171

    Re: Migliore struttura dati

    Ok. Quindi se due HashMap non si usano (mi piacerebbe nella mia ignoranza, capire il perchè) quale potrebbe essere la soluzione ideale per la deduplicazione dei valori (a questo punto la curiosità di imparare qualcosa di nuovo è tanta)?
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: Migliore struttura dati

    morellik ha scritto:

    Ok. Quindi se due HashMap non si usano (mi piacerebbe nella mia ignoranza, capire il perchè)
    Perché è un "giro" scomodo, poco utile e fumoso.

    morellik ha scritto:

    quale potrebbe essere la soluzione ideale per la deduplicazione dei valori (a questo punto la curiosità di imparare qualcosa di nuovo è tanta)?
    Allora. Partiamo da un aspetto. Se si vogliono deduplicare gli oggetti, ad esempio le stringhe per evitare di avere più oggetti String distinti con lo stesso contenuto (cosa che avviene es. se leggi dati da file o da input utente, ecc...) si può fare. Basta creare un sistema di "pooling" delle stringhe, ad esempio con una piccola classettina che contiene una banale map.
    Questo PUO' avere senso in contesti in cui si trattano grosse quantità di dati e si vuole sprecare meno memoria possibile.

    Discorso diverso se dici che cambiando un valore vuoi che cambino le associazioni di PIU' chiavi a quello stesso valore. Con le stringhe non lo fai, String è immutabile. Devi proprio ri-settare tutte le associazioni di tutte le chiavi interessate.
    Ma questa è una cosa MOLTO particolare e specifica .... davvero serve? Se sì, beh, si fa tecnicamente anche questo. Banalmente il valore non è direttamente una stringa ma un contenitore "mutabile" (banale classettina) che contiene la stringa.
    Se più chiavi sono associate allo stesso contenitore, se cambi solo il contenuto stringa del contenitore .... ovviamente questa modifica la "vedi" attraverso tutte le chiavi correlate!
    Ma ripeto, questa sarebbe una gestione molto particolare ... DOVE serve e a QUALE scopo?
  • +
    +m2+
    Utente Famoso
    Iscritto da
    mag, 2017
    Messaggi:
    3548

    Re: Migliore struttura dati

    Allora giusto per dare qualche idea.
    Nulla ti vieta, considerata una cardinalità così modesta, di definirti una classe "povera" dove mantieni proprio chiave e valore.
    farai poi 2 metodi: inserisci, cerca.
    con una cardinalità così bassa puoi fare banalmente una ricerca sequenziale, proprio un ciclo for, per ogni elemento.
    puoi utilizzare una lista, o addirittura un array (in questo caso io userei un array).
    Addirittura nulla ti vieta di codificare chiave-valore in una singola stringa, tipo chiave;valore.
    E fare una banale funzioncella di ricerca del testo fino alla parte iniziale, decodificando a "mano" (esplodendo stile PHP) i valori [mai e poi mai una cosa così complicata, nel tuo caso banale]

    se fai tanti inserimenti, avrai una complessità o(9) per trovare un duplicato, e non inserirlo.
    Una ventina di righe.

    ---
    Il problema si pone se vuoi deduplicare qualcosa di molto più grande, ove si utilizza, tipicamente, proprio una tecnica hash.
    Mai posto il problema di come funziona una hashmap, e grosso modo come e perchè usarla?
Devi accedere o registrarti per scrivere nel forum
15 risposte