Un Set nella programmazione Python è un tipo di dati di raccolta non ordinato che è iterabile, mutabile e non ha elementi duplicati.
I set sono rappresentati da { } (valori racchiusi tra parentesi graffe)
Il vantaggio principale dell'utilizzo di un set, rispetto a a elenco , è che dispone di un metodo altamente ottimizzato per verificare se un elemento specifico è contenuto nell'insieme. Questo si basa su una struttura dati nota come tabella hash. Poiché gli insiemi non sono ordinati, non possiamo accedere agli elementi utilizzando gli indici come facciamo negli elenchi.
Esempio di set Python
Python3
var>=> {>'Geeks'>,>'for'>,>'Geeks'>}> type>(var)> |
>
>
Produzione:
set>
Complessità temporale: O(1)
Spazio ausiliario: O(1)
Digitare Casting con il metodo Python Set
Il metodo Python set() viene utilizzato per il casting del tipo.
Python3
# typecasting list to set> myset>=> set>([>'a'>,>'b'>,>'c'>])> print>(myset)> # Adding element to the set> myset.add(>'d'>)> print>(myset)> |
>
>
Produzione:
Il set Python è un tipo di dati non ordinato, il che significa che non possiamo sapere in quale ordine sono memorizzati gli elementi del set.
{'c', 'b', 'a'} {'d', 'c', 'b', 'a'}> Complessità temporale: O(n)
Spazio ausiliario: O(n)
Verifica unico e immutabile con Python Set
I set Python non possono avere un valore duplicato e una volta creato non possiamo modificarne il valore.
Python3
# Python program to demonstrate that> # a set cannot have duplicate values> # and we cannot change its items> # a set cannot have duplicate values> myset>=> {>'Geeks'>,>'for'>,>'Geeks'>}> print>(myset)> # values of a set cannot be changed> myset[>1>]>=> 'Hello'> print>(myset)> |
>
>
Produzione:
Il primo codice spiega che l'insieme non può avere un valore duplicato. Ogni oggetto in esso contenuto ha un valore unico.
Il secondo codice genera un errore perché non possiamo assegnare o modificare un valore una volta creato il set. Possiamo solo aggiungere o eliminare elementi nel set.
{'Geeks', 'for'} TypeError: 'set' object does not support item assignment> Elemento eterogeneo con set Python
I set Python possono memorizzare elementi eterogenei al suo interno, ovvero un set può memorizzare una miscela di tipi di dati stringa, interi, booleani, ecc.
Python3
# Python example demonstrate that a set> # can store heterogeneous elements> myset>=> {>'Geeks'>,>'for'>,>10>,>52.7>,>True>}> print>(myset)> |
>
>
Produzione:
{True, 10, 'Geeks', 52.7, 'for'}> Complessità temporale: O(n)
Spazio ausiliario: O(n)
Set congelati in pitone
Set congelati in Python sono oggetti immutabili che supportano solo metodi e operatori che producono un risultato senza influenzare l'insieme o gli insiemi congelati a cui vengono applicati. Può essere fatto con il metodo frozenset() in Python.
Mentre gli elementi di un set possono essere modificati in qualsiasi momento, gli elementi del set congelato rimangono gli stessi dopo la creazione.
Se non vengono passati parametri, restituisce un frozenset vuoto.
Pitone
# Python program to demonstrate differences> # between normal and frozen set> # Same as {'a', 'b','c'}> normal_set>=> set>([>'a'>,>'b'>,>'c'>])> print>(>'Normal Set'>)> print>(normal_set)> # A frozen set> frozen_set>=> frozenset>([>'e'>,>'f'>,>'g'>])> print>(>'
Frozen Set'>)> print>(frozen_set)> # Uncommenting below line would cause error as> # we are trying to add element to a frozen set> # frozen_set.add('h')> |
>
>
Produzione:
Normal Set {'a', 'c', 'b'} Frozen Set {'e', 'g', 'f'}> Complessità temporale: O(n)
Spazio ausiliario: O(n)
Funzionamento interno del set
Questo si basa su una struttura dati nota come tabella hash. Se sono presenti più valori nella stessa posizione di indice, il valore viene aggiunto a quella posizione di indice per formare un elenco collegato.
In, i set Python vengono implementati utilizzando un dizionario con variabili fittizie, in cui gli elementi chiave vengono impostati dai membri con maggiori ottimizzazioni rispetto alla complessità temporale.
Imposta implementazione:
Set con numerose operazioni su una singola HashTable:
Metodi per gli insiemi
Aggiunta di elementi ai set Python
L'inserimento nel set avviene tramite il set.add( ), in cui viene creato un valore record appropriato da archiviare nella tabella hash. Equivale al controllo di un elemento, ovvero O(1) in media. Tuttavia, nel peggiore dei casi, può diventarlo SU) .
Python3
# A Python program to> # demonstrate adding elements> # in a set> # Creating a Set> people>=> {>'Jay'>,>'Idrish'>,>'Archi'>}> print>(>'People:'>, end>=> ' '>)> print>(people)> # This will add Daxit> # in the set> people.add(>'Daxit'>)> # Adding elements to the> # set using iterator> for> i>in> range>(>1>,>6>):> >people.add(i)> print>(>'
Set after adding element:'>, end>=> ' '>)> print>(people)> |
>
>
Produzione:
People: {'Idrish', 'Archi', 'Jay'} Set after adding element: {1, 2, 3, 4, 5, 'Idrish', 'Archi', 'Jay', 'Daxit'}> Complessità temporale: O(n)
Spazio ausiliario: O(n)
Operazione di unione su set Python
Due insiemi possono essere uniti utilizzando la funzione union() o | operatore. Entrambi i valori della tabella hash sono accessibili e attraversati con l'operazione di unione eseguita su di essi per combinare gli elementi, allo stesso tempo vengono rimossi i duplicati. La complessità temporale di questo è O(lente(s1) + lente(s2)) dove s1 e s2 sono due insiemi di cui occorre fare l'unione.
Python3
# Python Program to> # demonstrate union of> # two sets> people>=> {>'Jay'>,>'Idrish'>,>'Archil'>}> vampires>=> {>'Karan'>,>'Arjun'>}> dracula>=> {>'Deepanshu'>,>'Raju'>}> # Union using union()> # function> population>=> people.union(vampires)> print>(>'Union using union() function'>)> print>(population)> # Union using '|'> # operator> population>=> people|dracula> print>(>'
Union using '|' operator'>)> print>(population)> |
>
>
Produzione:
Union using union() function {'Karan', 'Idrish', 'Jay', 'Arjun', 'Archil'} Union using '|' operator {'Deepanshu', 'Idrish', 'Jay', 'Raju', 'Archil'}> Complessità temporale: O(n)
Spazio ausiliario: O(n)
Operazione di intersezione su insiemi Python
Questo può essere fatto tramite l'intersezione() o l'operatore &. Gli elementi comuni sono selezionati. Sono simili all'iterazione sugli elenchi Hash e combinano gli stessi valori su entrambe le tabelle. La complessità temporale di questo è O(min(len(s1), len(s2)) dove s1 e s2 sono due insiemi di cui è necessario eseguire l'unione.
Python3
# Python program to> # demonstrate intersection> # of two sets> set1>=> set>()> set2>=> set>()> for> i>in> range>(>5>):> >set1.add(i)> for> i>in> range>(>3>,>9>):> >set2.add(i)> # Intersection using> # intersection() function> set3>=> set1.intersection(set2)> print>(>'Intersection using intersection() function'>)> print>(set3)> # Intersection using> # '&' operator> set3>=> set1 & set2> print>(>'
Intersection using '&' operator'>)> print>(set3)> |
>
>
Produzione:
Intersection using intersection() function {3, 4} Intersection using '&' operator {3, 4}> Complessità temporale: O(n)
Spazio ausiliario: O(n)
Trovare le differenze tra insiemi in Python
Trovare le differenze tra gli insiemi. Simile alla ricerca di differenze nell'elenco collegato. Questo viene fatto tramite l'operatore differenza() o –. La complessità temporale nel trovare la differenza s1 – s2 è O(len(s1))
Python3
# Python program to> # demonstrate difference> # of two sets> set1>=> set>()> set2>=> set>()> for> i>in> range>(>5>):> >set1.add(i)> for> i>in> range>(>3>,>9>):> >set2.add(i)> # Difference of two sets> # using difference() function> set3>=> set1.difference(set2)> print>(>' Difference of two sets using difference() function'>)> print>(set3)> # Difference of two sets> # using '-' operator> set3>=> set1>-> set2> print>(>'
Difference of two sets using '-' operator'>)> print>(set3)> |
>
>
Produzione:
Difference of two sets using difference() function {0, 1, 2} Difference of two sets using '-' operator {0, 1, 2}> Complessità temporale: O(n)
Spazio ausiliario: O(n)
Cancellazione dei set Python
Il metodo Set Clear() svuota l'intero set sul posto.
Python3
# Python program to> # demonstrate clearing> # of set> set1>=> {>1>,>2>,>3>,>4>,>5>,>6>}> print>(>'Initial set'>)> print>(set1)> # This method will remove> # all the elements of the set> set1.clear()> print>(>'
Set after using clear() function'>)> print>(set1)> |
>
>
Produzione:
Initial set {1, 2, 3, 4, 5, 6} Set after using clear() function set()> Complessità temporale: O(n)
Spazio ausiliario: O(n)
Tuttavia, ci sono due principali insidie nei set Python:
- L'insieme non mantiene gli elementi in un ordine particolare.
- Solo istanze di tipi immutabili possono essere aggiunte a un set Python.
Complessità temporale degli insiemi
| Operazione | Caso medio | Caso peggiore | Appunti |
|---|---|---|---|
| x nella s | O(1) | SU) | |
| Unione s|t | O(lente(i)+lente(t)) | ||
| Intersezione s&t | O(min(lente(i), lente(t)) | O(lente(i) * lente(t)) | sostituire min con max se t non è un insieme |
| Intersezione multipla s1&s2&..&sn | (n-1)*O(l) dove l è max(len(s1),..,len(sn)) | ||
| Differenza st | O(solo(i)) |
Operatori per insiemi
I set e i set congelati supportano i seguenti operatori:
| Operatori | Appunti |
|---|---|
| digitare s | controllo del contenimento |
| chiave non in s | controllo di non contenimento |
| s1 == s2 | s1 equivale a s2 |
| s1!= s2 | s1 non è equivalente a s2 |
| s1 <= s2 | s1 è un sottoinsieme di s2 |
| s1 | s1 è un sottoinsieme proprio di s2 |
| s1>= s2 | s1 è un superinsieme di s2 |
| s1> s2 | s1 è un soprainsieme corretto di s2 |
| s1 | s2 | l'unione di s1 e s2 |
| s1 e s2 | l'intersezione di s1 e s2 |
| s1 – s2 | l'insieme degli elementi in s1 ma non in s2 |
| s1ˆs2 | l'insieme degli elementi esattamente in uno tra s1 o s2 |
Articoli recenti su Python Set.
insieme di dattiloscritti