2015-12-01 14 views
32

Sto provando a risolvere l'esercizio # 1.4 "Go go programming lanaguage" che richiede di avere un set. Posso creare un tipo di set, ma perché il linguaggio non ne ha uno? vai, provenendo da google, dove è nato anche guava, perché i progettisti linguistici non hanno optato per aggiungere il supporto per le strutture dati fondamentali? perché costringere i tuoi utenti a creare le proprie implementazioni per qualcosa di così semplice come un set?golang perché non abbiamo una datastruttura impostata

+0

hmmm. chiedendo perché i voti negativi? Vengo dal mondo java in cui avevamo un set quasi fin dall'inizio, anche senza generici. Quindi, trovo che questo comportamento sia un po 'bizzarro – anjanb

risposta

29

In parte, perché Go non dispone di generici (quindi è necessario un tipo di set per ogni tipo o si può ricorrere al riflesso, che è piuttosto inefficiente).

In parte, perché se tutto ciò che serve è "aggiungere/rimuovere singoli elementi di un insieme" e "relativamente efficiente dello spazio", è possibile ottenere un bel po 'di che semplicemente utilizzando un map[yourtype]bool (e impostare il valore a true per qualsiasi elemento dell'insieme) o, per una maggiore efficienza di spazio, è possibile utilizzare una struttura vuota come valore e utilizzare _, present = the_setoid[key] per verificare la presenza.

+0

Inoltre, sembra essere nello spirito di Go solo scriverlo nel proprio codice, sia "inserendo" l'insieme in altro codice, sia definendo il proprio tipo di set quando necessario. Ad ogni modo, usando per esempio un codice std :: set in C++ avviene sempre come parte di un'implementazione di funzione o implementando qualche altra struttura di dati. Pertanto, è sufficiente implementare l'altra struttura di dati direttamente utilizzando mappe e sezioni e qualsiasi altro elemento di base necessario, ma senza alcun set predefinito. Ogni utilizzo di un set lo userà comunque in modo leggermente diverso :) –

+0

Beh, se Go avesse generici, probabilmente implementerei e contribuirò a un'implementazione di un set generico (costruito sopra le mappe, almeno inizialmente). Ma Go non ha generici, il codice necessario è piuttosto piccolo e il side-tracking attraverso la riflessione probabilmente sta andando a prendere abbastanza colpi di velocità che non ne vale la pena. Ma c'è un mondo di differenza nella scrittura di una robusta biblioteca generale e solo di scrivere quello che ti serve, per ora. – Vatine

+1

Ma di solito non hai davvero bisogno di un set da solo, si utilizza un set come parte dell'implementazione di qualcosa di più grande. Ho visto tonnellate di codice in cui le cose che devi fare per includere un componente "riutilizzabile" è molto peggio che evitarlo. Quindi qui abbiamo un set , quella funzione laggiù ha bisogno di un set , oops, abbiamo ancora la covarianza, o che ne dici di creare una WrapperFactory per rendere questa cosa simile a questa cosa, ecc. Forse quell'altra funzione in realtà solo ha bisogno di un'interfaccia in grado di verificare l'appartenenza, quindi non inviare un set . –

14

Uno dei motivi è che è facile creare un set da mappa:

s := map[int]bool{5: true, 2: true} 
_, ok := s[6] // check for existence 
s[8] = true // add element 
delete(s, 2) // remove element 

dell'Unione

s_union := map[int]bool{} 
for k, _ := range s1{ 
    s_union[k] = true 
} 
for k, _ := range s2{ 
    s_union[k] = true 
} 

Intersezione

s_intersection := map[int]bool{} 
for k,_ := range s1 { 
    if s2[k] { 
    s_intersection[k] = true 
    } 
} 

non è poi così difficile da implementare tutto altre operazioni di set.

+3

Il controllo dell'esistenza sta semplicemente indicizzando la mappa. Dal momento che se non è in esso, il valore zero (che è 'false') lo dirà correttamente. Non è necessario l'idioma virgola-ok per il test. – icza

+2

L'implementazione per l'intersezione sembra quella per differenza. – musiphil

+1

@ Kittsil grazie. Aggiornato. –

1

Come Vatine ha scritto: Dato che manca generici, dovrebbe essere parte della lingua e non della libreria standard. Per questo bisognerebbe poi inquinare la lingua con le parole chiave set, union, intersezione, differenza, sottoinsieme ...

L'altro motivo è che non è affatto chiaro quale sia l'implementazione "giusta" di un set:

  1. C'è un approccio funzionale:

    func IsInEvenNumbers(n int) bool { 
        if n % 2 == 0 { 
         return true 
        } 
        return false 
    } 
    

Questo è un insieme di tutti anche int. Ha una ricerca molto efficiente e unione, intersezione, differenza e sottoinsieme possono essere facilmente fatti dalla composizione funzionale.

  1. Oppure si esegue un approccio simile a quello mostrato da Dali.

Una mappa non presenta questo problema, poiché si memorizza qualcosa associato al valore.

+1

Per gestire gli insiemi buit-in, Pascal sovraccarica un gruppo di operatori binari (due argnent): '+' per unione, '-' per differenza,' * 'per intersezione,' <= 'per sottoinsieme,'> = ' per superset, '=' per l'uguaglianza, '<>' per disuguaglianza e 'in' per l'appartenenza. Quindi, in Go, sarebbe solo una singola nuova parola chiave: 'in'. D'altra parte, i set predefiniti di Pascal funzionano solo sugli "ordinali", cioè su qualsiasi tipo che abbia una rappresentazione sottostante di un valore intero di una certa dimensione. – kostix

+1

Il fatto che ci siano diversi modi per implementare un set non ha impedito a molte altre lingue di fornirli. – augurar

+0

@kostix: Go potrebbe anche usare la 's [key]' della sintassi (come se 's' fosse un' map [T] bool') invece di 'key in s'. – musiphil

1

Un'altra possibilità è utilizzare i set di bit, per i quali è presente almeno uno package oppure è possibile utilizzare il pacchetto integrato big. In questo caso, in pratica, devi definire un modo per convertire il tuo oggetto in un indice.

+1

Devo notare che ho scritto la versione originale del pacchetto bitset di cui sopra. –

Problemi correlati