[Python] (deep)flat di sequenze

Linguaggi di programmazione: php, perl, python, C, bash e tutti gli altri.
Avatar utente
crap0101
Rampante Reduce
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

Messaggio da crap0101 »

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 :-D 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
Avatar utente
DoctorStrange
Imperturbabile Insigne
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

Messaggio da DoctorStrange »

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.
Avatar utente
crap0101
Rampante Reduce
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

Messaggio da crap0101 »

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 :-D ).
DoctorStrange ha scritto:
domenica 12 giugno 2022, 17:36
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.
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.

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
gila75
Imperturbabile Insigne
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

Messaggio da gila75 »

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
Avatar utente
crap0101
Rampante Reduce
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

Messaggio da crap0101 »

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
Avatar utente
crap0101
Rampante Reduce
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

Messaggio da crap0101 »

crap0101 ha scritto:
domenica 12 giugno 2022, 21:19
Ecco, un bonus ulteriore sarebbe poter scegliere fino a che livello flattare! (tra quelli che ho provato, iteration_utilities è l'unico che lo fà)
oh, mi prendo il bonus :P
sorgenti aggiornati, ma per i più lazy:
:-D

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
Avatar utente
miclab
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 455
Iscrizione: venerdì 18 gennaio 2008, 11:08
Desktop: Gnome 3
Distribuzione: Debian testing
Località: Rho

Re: [Python] (deep)flat di sequenze

Messaggio da miclab »

seguo
gila75
Imperturbabile Insigne
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

Messaggio da gila75 »

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:

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)
output:

Codice: Seleziona tutto

gila@gila-pc:~/Scrivania$ python3 y.py
[15, 2, 3, 4, 5, 99, 88, 6, 7, 8, 'vuota', -100]
Scrivi risposta

Ritorna a “Programmazione”

Chi c’è in linea

Visualizzano questa sezione: 0 utenti iscritti e 10 ospiti