[Python] (deep)flat di sequenze
- crap0101
- Rampante Reduce
- Messaggi: 8242
- Iscrizione: martedì 30 ottobre 2007, 6:33
- Desktop: LXDE
- Distribuzione: Ubuntu 18.04.1 LTS
- Sesso: Maschile
- Località: TO
- Contatti:
[Python] (deep)flat di sequenze
Ciao :-)
Per uno script mi serviva 'flattare' (appiattire, in italiano?) una sequenza, quindi ottenere una sequenza in output che contenesse tutti gli elementi di una data in input, i cui elementi potrebbero essere a loro volta sequenze (anch'esse quindi da "appiattire") ...e ottenerli possibilmente "ordinati" come nell'input (come bonus: lavorare su input infinitamente lunghi).
Qui sul forum non ho trovato discussioni in cui se ne parlava e, nonostante l'apparente semplicità ho "faticato" un po' a trovare soluzioni ottimali.
Scrivo qui così se qualcuno conosce qualche lib che mi è sfuggita (probabile) che implementa la cosa, o ne ha scritta una versione sua, si può fare qualche confronto.
Io sono giunto a questa conclusione: https://github.com/crap0101/laundry_bas ... flatten.py
Al link ci sono tre diverse funzioni scritte da me (qualche variante per testare la velocità con oggetti diversi) e confronti con implementazioni di altre note e meno note librerie (più una versione presa - come commentato - dal post di un tizio su stackoverflow, che è abbastanza simile alla "conclusione" a cui sono arrivato io e una delle poche funzionanti!).
Dicevo, la cosa pur nella sua semplicità è interessante perchè pone comunque di fronte a un paio di problemi su cui è interessante ragionare, in generale come procedura e in particolare se la si implementa in Python.
Infatti, quello che ho purtroppo notato, è che anche librerie "famose" e molto utilizzate che implementano questa procedura sono, di fondo, buggate, come lo sono le centinaia di versioni su SO e in giro per la rete (bè, molte evidentemente scritte su due piedi e senza tante verifiche).
Il problema più comune è che generalmente vengono implementate in modo ricorsivo... che se da una parte è certamente il modo più comodo, dall'altra - e in python - non è sicuramente nè il più efficiente nè il più sensato.
Un altro problema che ho notato è stato nell'uso (o un certo uso) degli iteratori che, seppur apparentemente "legittimo" finisce per portare allo stesso problema [¹].
Tipo per pandas e matplotlib mi è quasi venuta voglia di aprire un bug report perchè mi sembra assurdo presentino un bug del genere, e tra l'altro non sono molto performanti. Certo il problema non è nei casi d'uso "normali", però... pero...
Per cui, se conoscete altro che funziona (o non funziona ^|^), postate! così si fa qualche altro confronto.
[¹] problema che mi aveva un po' interdetto mentre scrivevo un oggetto iterabile qui: https://github.com/crap0101/laundry_bas ... ecretor.py
mentre testavo due cose che mi avevano incuriosito nella discussione ( viewtopic.php?f=33&t=649418&start=20] ) sul merge sort di gila75.
Per uno script mi serviva 'flattare' (appiattire, in italiano?) una sequenza, quindi ottenere una sequenza in output che contenesse tutti gli elementi di una data in input, i cui elementi potrebbero essere a loro volta sequenze (anch'esse quindi da "appiattire") ...e ottenerli possibilmente "ordinati" come nell'input (come bonus: lavorare su input infinitamente lunghi).
Qui sul forum non ho trovato discussioni in cui se ne parlava e, nonostante l'apparente semplicità ho "faticato" un po' a trovare soluzioni ottimali.
Scrivo qui così se qualcuno conosce qualche lib che mi è sfuggita (probabile) che implementa la cosa, o ne ha scritta una versione sua, si può fare qualche confronto.
Io sono giunto a questa conclusione: https://github.com/crap0101/laundry_bas ... flatten.py
Al link ci sono tre diverse funzioni scritte da me (qualche variante per testare la velocità con oggetti diversi) e confronti con implementazioni di altre note e meno note librerie (più una versione presa - come commentato - dal post di un tizio su stackoverflow, che è abbastanza simile alla "conclusione" a cui sono arrivato io e una delle poche funzionanti!).
Dicevo, la cosa pur nella sua semplicità è interessante perchè pone comunque di fronte a un paio di problemi su cui è interessante ragionare, in generale come procedura e in particolare se la si implementa in Python.
Infatti, quello che ho purtroppo notato, è che anche librerie "famose" e molto utilizzate che implementano questa procedura sono, di fondo, buggate, come lo sono le centinaia di versioni su SO e in giro per la rete (bè, molte evidentemente scritte su due piedi e senza tante verifiche).
Il problema più comune è che generalmente vengono implementate in modo ricorsivo... che se da una parte è certamente il modo più comodo, dall'altra - e in python - non è sicuramente nè il più efficiente nè il più sensato.
Un altro problema che ho notato è stato nell'uso (o un certo uso) degli iteratori che, seppur apparentemente "legittimo" finisce per portare allo stesso problema [¹].
Tipo per pandas e matplotlib mi è quasi venuta voglia di aprire un bug report perchè mi sembra assurdo presentino un bug del genere, e tra l'altro non sono molto performanti. Certo il problema non è nei casi d'uso "normali", però... pero...
Per cui, se conoscete altro che funziona (o non funziona ^|^), postate! così si fa qualche altro confronto.
[¹] problema che mi aveva un po' interdetto mentre scrivevo un oggetto iterabile qui: https://github.com/crap0101/laundry_bas ... ecretor.py
mentre testavo due cose che mi avevano incuriosito nella discussione ( viewtopic.php?f=33&t=649418&start=20] ) sul merge sort di gila75.
Ultima modifica di crap0101 il domenica 12 giugno 2022, 20:49, modificato 1 volta in totale.
http://www.gnu.org/ http://boinc.berkeley.edu/ http://www.python-it.org/
- Ricorda le ultime parole di suo padre: «Sta' alla larga dalle chiese, figlio. La sola cosa per cui hanno la chiave è il merdaio. E giurami che non porterai mai un distintivo della legge» - W.S. Burroughs
- Ricorda le ultime parole di suo padre: «Sta' alla larga dalle chiese, figlio. La sola cosa per cui hanno la chiave è il merdaio. E giurami che non porterai mai un distintivo della legge» - W.S. Burroughs
- DoctorStrange
- Imperturbabile Insigne
- Messaggi: 2854
- Iscrizione: mercoledì 14 ottobre 2015, 9:33
- Desktop: Gnome3
- Distribuzione: Ubuntu 22.04 LTS Jammy Jellyfish
- Sesso: Maschile
- Località: Roma, Italia
Re: [Python] flat di sequenze
Ammesso che io Python non lo conosco, sono convinto che, se hai a che fare con dati entranti "infinitamente" lunghi, python potrebbe non essere la scelta miglòiore. Esistoo altri liunguaggi maggiormente votati al Big Data. Ad esempio in scala avresti a disposizione le funzioni che cerchi, direttamente integrate nel compilatore. Rispettivamente"flatMap" e "flatten", fanno esattamente ciò che cerchi. In ogni caso, puoi sviluppare queste procedure anche in Python, ti consiglio in particolare "Pyspark" che è un dialetto di python sviluppato per funzionare su un framework che si chiama Spark, che fa queste cose di mestiere. Qualora tu ne avessi bisogno potrasi poi pensare anche di fare una migrazione dei tuoi dati ed i tuoi codici verso un framework maggiormente votato al Big Data, nel caso tu dovessi aver bisogno proprio di "dati infinitoi", da come hai detto tu stesso.
- crap0101
- Rampante Reduce
- Messaggi: 8242
- Iscrizione: martedì 30 ottobre 2007, 6:33
- Desktop: LXDE
- Distribuzione: Ubuntu 18.04.1 LTS
- Sesso: Maschile
- Località: TO
- Contatti:
Re: [Python] flat di sequenze
Per il lavorare su sequenze teoricamente infinite, non era proprio una necessità, più che altro una possibilità teorica (del tipo: non facciamo subito crashare tutto appena ci si ritrova con input più grandi di tot ).
Ecco, un bonus ulteriore sarebbe poter scegliere fino a che livello flattare! (tra quelli che ho provato, iteration_utilities è l'unico che lo fà)
Ho modificato il titolo così si evitano fraintendimenti: flatMap e flatten di scala *non* fanno quello di cui parlo, si limitano a togliere un livello di nesting, stessa cosa per spark, da quanto si legge nella doc.DoctorStrange ha scritto: ↑domenica 12 giugno 2022, 17:36Ad esempio in scala avresti a disposizione le funzioni che cerchi, direttamente integrate nel compilatore. Rispettivamente"flatMap" e "flatten", fanno esattamente ciò che cerchi. In ogni caso, puoi sviluppare queste procedure anche in Python, ti consiglio in particolare "Pyspark" che è un dialetto di python sviluppato per funzionare su un framework che si chiama Spark, che fa queste cose di mestiere.
Ecco, un bonus ulteriore sarebbe poter scegliere fino a che livello flattare! (tra quelli che ho provato, iteration_utilities è l'unico che lo fà)
http://www.gnu.org/ http://boinc.berkeley.edu/ http://www.python-it.org/
- Ricorda le ultime parole di suo padre: «Sta' alla larga dalle chiese, figlio. La sola cosa per cui hanno la chiave è il merdaio. E giurami che non porterai mai un distintivo della legge» - W.S. Burroughs
- Ricorda le ultime parole di suo padre: «Sta' alla larga dalle chiese, figlio. La sola cosa per cui hanno la chiave è il merdaio. E giurami che non porterai mai un distintivo della legge» - W.S. Burroughs
-
- Imperturbabile Insigne
- Messaggi: 2739
- Iscrizione: mercoledì 16 gennaio 2013, 17:28
- Desktop: ubuntu-2d
- Distribuzione: Ubuntu 12.04.2 LTS i686
- Località: Airuno(Lecco)
Re: [Python] (deep)flat di sequenze
Seguo in modo passivo. Non sono certo io l'utente che ti puo' aiutare, ma m'interessa capire.
Potresti fare un esempio dei dati prima e poi?
Come entrano e come si dovrebbero presentare.
Se hai voglia naturalmente
Potresti fare un esempio dei dati prima e poi?
Come entrano e come si dovrebbero presentare.
Se hai voglia naturalmente
- crap0101
- Rampante Reduce
- Messaggi: 8242
- Iscrizione: martedì 30 ottobre 2007, 6:33
- Desktop: LXDE
- Distribuzione: Ubuntu 18.04.1 LTS
- Sesso: Maschile
- Località: TO
- Contatti:
Re: [Python] (deep)flat di sequenze
c'è un esempio verso il fondo del sorgente... in pratica:
Codice: Seleziona tutto
>>> ll = [1, 2, [3, 4, [5]], 'foo', (6, [], [[]], iter((0, range(3), [3,4])), 7), [8, [9, 10]]]
>>> list(iflatten(ll))
[1, 2, 3, 4, 5, 'f', 'o', 'o', 6, 0, 0, 1, 2, 3, 4, 7, 8, 9, 10]
http://www.gnu.org/ http://boinc.berkeley.edu/ http://www.python-it.org/
- Ricorda le ultime parole di suo padre: «Sta' alla larga dalle chiese, figlio. La sola cosa per cui hanno la chiave è il merdaio. E giurami che non porterai mai un distintivo della legge» - W.S. Burroughs
- Ricorda le ultime parole di suo padre: «Sta' alla larga dalle chiese, figlio. La sola cosa per cui hanno la chiave è il merdaio. E giurami che non porterai mai un distintivo della legge» - W.S. Burroughs
- crap0101
- Rampante Reduce
- Messaggi: 8242
- Iscrizione: martedì 30 ottobre 2007, 6:33
- Desktop: LXDE
- Distribuzione: Ubuntu 18.04.1 LTS
- Sesso: Maschile
- Località: TO
- Contatti:
Re: [Python] (deep)flat di sequenze
oh, mi prendo il bonus :P
sorgenti aggiornati, ma per i più lazy:
Codice: Seleziona tutto
def diflatten (seq: Sequence,
ignore: Sequence[Type] =IGNORED_TYPES,
maxdepth: Union[int,float] =float('+inf')) -> Iterable:
"""Deep-flat $seq using deque. Works with infinite sequences.
$ignore must be a type object, or a tuple of types,
which will not be flattered.
$maxdepth should be a positive number of the maximum level
of nesting to flat (default to +inf).
>>> lst = [0,0,[1,1,[2,2,[3,3,[4,4,[5,5,[6,6]]]]]]]
>>> list(diflatten(lst))
[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6]
>>> list(diflatten(lst, maxdepth=1))
[0, 0, 1, 1, [2, 2, [3, 3, [4, 4, [5, 5, [6, 6]]]]]]
>>> list(diflatten(lst, maxdepth=2))
[0, 0, 1, 1, 2, 2, [3, 3, [4, 4, [5, 5, [6, 6]]]]]
"""
d = deque((zip(itertools.repeat(0), iter(seq)),))
depth = 0
while d:
x = d[0]
for depth, item in x:
skip_ignored = isinstance(item, ignore)
if depth >= maxdepth:
yield item
elif isinstance(item, NESTED_TYPES):
if isinstance(item, REC_TYPES):
if skip_ignored:
yield item
else:
for i in item:
yield i
elif skip_ignored:
yield item
else:
d.appendleft(zip(itertools.repeat(depth+1), iter(item)))
break
else:
yield item
else:
d.popleft()
http://www.gnu.org/ http://boinc.berkeley.edu/ http://www.python-it.org/
- Ricorda le ultime parole di suo padre: «Sta' alla larga dalle chiese, figlio. La sola cosa per cui hanno la chiave è il merdaio. E giurami che non porterai mai un distintivo della legge» - W.S. Burroughs
- Ricorda le ultime parole di suo padre: «Sta' alla larga dalle chiese, figlio. La sola cosa per cui hanno la chiave è il merdaio. E giurami che non porterai mai un distintivo della legge» - W.S. Burroughs
-
- Imperturbabile Insigne
- Messaggi: 2739
- Iscrizione: mercoledì 16 gennaio 2013, 17:28
- Desktop: ubuntu-2d
- Distribuzione: Ubuntu 12.04.2 LTS i686
- Località: Airuno(Lecco)
Re: [Python] (deep)flat di sequenze
Guardo il tuo script @crap anche se dubito sia alla mia portata.
Ti posto un programmino riadattato che conta quante liste sono annidate in una lista.
Con qualche modifica fa quello che ti serve.
Molto rudimentale, usa la ricorsione, ma con un po' d'impegno lo si può fare a stack esplicito e iterativo.
Senza pretese, ma magari ti può essere utile:
output:
Ti posto un programmino riadattato che conta quante liste sono annidate in una lista.
Con qualche modifica fa quello che ti serve.
Molto rudimentale, usa la ricorsione, ma con un po' d'impegno lo si può fare a stack esplicito e iterativo.
Senza pretese, ma magari ti può essere utile:
Codice: Seleziona tutto
def sumtree(l,l2):
for x in l:
if not isinstance(x,list):
l2.append(x)
else:
sumtree(x,l2)
l = [15,2,3,[4,[5,99],88],[6],7,8,["vuota"],-100,[]]
l2=[]
sumtree(l,l2)
print (l2)
Codice: Seleziona tutto
gila@gila-pc:~/Scrivania$ python3 y.py
[15, 2, 3, 4, 5, 99, 88, 6, 7, 8, 'vuota', -100]
Chi c’è in linea
Visualizzano questa sezione: 0 utenti iscritti e 10 ospiti