Ya, saya tahu subjek ini telah dibahas sebelumnya (di sini , di sini , di sini , di sini ), tetapi sejauh yang saya tahu, semua solusi, kecuali satu, gagal pada daftar seperti ini:
L = [[[1, 2, 3], [4, 5]], 6]
Di mana output yang diinginkan
[1, 2, 3, 4, 5, 6]
Atau mungkin lebih baik, sebuah iterator. Satu-satunya solusi yang saya lihat yang berfungsi untuk bersarang sembarang ditemukan dalam pertanyaan ini :
def flatten(x):
result = []
for el in x:
if hasattr(el, "__iter__") and not isinstance(el, basestring):
result.extend(flatten(el))
else:
result.append(el)
return result
flatten(L)
Apakah ini model terbaik? Apakah saya mengabaikan sesuatu? Masalah apapun?
python
list
optimization
nested-lists
flatten
telliott99
sumber
sumber
list
yang dimaksudkan untuk menjadi homogen) tidak berarti itu adalah kesalahan Python dan kita membutuhkan builtin untuk tugas tersebutJawaban:
Menggunakan fungsi generator dapat membuat contoh Anda sedikit lebih mudah dibaca dan mungkin meningkatkan kinerja.
Python 2
Saya menggunakan Iterable ABC ditambahkan pada 2.6.
Python 3
Dalam Python 3,
basestring
tidak lebih, tetapi Anda bisa menggunakan tuplestr
danbytes
untuk mendapatkan efek yang sama di sana.The
yield from
Operator mengembalikan sebuah item dari satu generator pada suatu waktu. Ini sintaks untuk mendelegasikan ke subgenerator sebuah ditambahkan dalam 3,3sumber
l = ([[chr(i),chr(i-32)] for i in xrange(ord('a'), ord('z')+1)] + range(0,9))
dalam sekejap ketika saya melakukan inilist(flatten(l))
. Yang lainnya, akan mulai bekerja dan mengambil selamanya!collections.Sequence
bukancollections.Iteratable
?for i in flatten(42): print (i)
. Ini bisa diperbaiki dengan memindahkanisinstance
-test dan yang lain-klausa di luarfor el
-loop. (Maka Anda bisa melempar apa saja padanya, dan itu akan membuat daftar yang rata dari itu)collections.Iterable
sudah tidak digunakan lagi. Gunakancollections.abc.Iterable
sebagai gantinya.Solusi saya:
Sedikit lebih ringkas, tetapi hampir sama.
sumber
try: iter(x)
ingin menguji apakah itu dapat diubah ... Tapi saya tidak berpikir harus mengimpor modul stdlib adalah kerugian yang patut dihindari.int
def flatten(x): return [a for i in x for a in flatten(i)] if isinstance(x, collections.Iterable) else [x]
- tetapi keterbacaan mungkin subjektif di sini.if isinstance(x, collections.Iterable) and not isinstance(x, basestring)
Generator menggunakan rekursi dan mengetik bebek (diperbarui untuk Python 3):
sumber
for i in flatten(item): yield i
Versi generator dari solusi non-rekursif @ unutbu, seperti yang diminta oleh @Andrew dalam komentar:
Versi generator ini sedikit disederhanakan:
sumber
Ini adalah versi fungsional saya dari perataan rekursif yang menangani tupel dan daftar, dan memungkinkan Anda untuk melempar semua campuran argumen posisi. Mengembalikan generator yang menghasilkan seluruh urutan, arg oleh arg:
Pemakaian:
sumber
e
,a
,n
merujuk keargs
untukn
,intermediate
(atau yang lebih pendekmid
atau Anda lebih sukaelement
) untuka
danresult
untuke
, jadi:flatten = lambda *args: (result for mid in args for result in (flatten(*mid) if isinstance(mid, (tuple, list)) else (mid,)))
compiler.ast.flatten
. Bagus, kode ringkas, bekerja untuk semua jenis objek (saya pikir).Versi ini
flatten
menghindari batas rekursi python (dan dengan demikian bekerja dengan iterables yang bersarang mendalam). Ini adalah generator yang dapat menangani string dan iterables sewenang-wenang (bahkan yang tak terbatas).Berikut adalah beberapa contoh yang menunjukkan penggunaannya:
Meskipun
flatten
dapat menangani generator yang tak terbatas, ia tidak dapat menangani sarang yang tak terbatas:sumber
sets
,dicts
,deques
,listiterators
,generators
, Filehandles, dan kelas kustom dengan__iter__
didefinisikan semua contohcollections.Iterable
, tapi tidakcollections.Sequence
. Hasil meratakan adict
agak rapuh, tetapi jika tidak, saya pikircollections.Iterable
adalah default yang lebih baik daripadacollections.Sequence
. Ini jelas lebih liberal.collections.Iterable
adalah ini termasuk generator yang tak terbatas. Saya sudah mengubah jawaban saya menangani kasus ini.StopIteration
. Juga, sepertinyawhile True: first = next(remainder)
bisa diganti olehfor first in remainder:
.try-except StopIteration block
.Inilah jawaban lain yang bahkan lebih menarik ...
Pada dasarnya, ini mengubah daftar bersarang menjadi string, menggunakan regex untuk menghapus sintaks bersarang, dan kemudian mengubah hasilnya kembali ke daftar (diratakan).
sumber
[['C=64', 'APPLE ]['], ['Amiga', 'Mac', 'ST']]
:) Di sisi lain, mengingat daftar yang berisi dirinya sendiri, itu akan melakukan sedikit lebih baik daripada jawaban lain, menaikkan pengecualian alih-alih hanya mengulang sampai kehabisan memori / berulang hingga Anda kehabisan tumpukan ...[x for x in c]
hanya cara lambat dan verbal untuk membuat salinanc
, jadi mengapa Anda melakukan itu? Kedua, kode Anda jelas akan dikonversi'APPLE ]['
menjadi'APPLE '
, karena tidak menangani penawaran, hanya mengasumsikan bahwa tanda kurung adalah tanda kurung daftar.arr_str = str(arr)
dan[int(s) for s in re.findall(r'\d+', arr_str)]
benar-benar. Lihat github.com/jorgeorpinel/flatten_nested_lists/blob/master/…sumber
Anda bisa menggunakan
deepflatten
dari paket pihak ke-3iteration_utilities
:Ini adalah iterator sehingga Anda harus mengulanginya (misalnya dengan membungkusnya dengan
list
atau menggunakannya dalam satu lingkaran). Secara internal ia menggunakan pendekatan berulang bukan pendekatan rekursif dan itu ditulis sebagai ekstensi C sehingga bisa lebih cepat daripada pendekatan python murni:Saya penulis
iteration_utilities
perpustakaan.sumber
Itu menyenangkan mencoba untuk membuat fungsi yang bisa meratakan daftar tidak teratur di Python, tapi tentu saja itu untuk apa Python (untuk membuat pemrograman menyenangkan). Generator berikut bekerja dengan cukup baik dengan beberapa peringatan:
Ini akan meratakan tipe data yang mungkin ingin ditinggalkan sendirian (seperti
bytearray
,bytes
, danstr
benda-benda). Juga, kode bergantung pada fakta bahwa meminta iterator dari non-iterable memunculkan aTypeError
.Edit:
Saya tidak setuju dengan implementasi sebelumnya. Masalahnya adalah Anda seharusnya tidak bisa meratakan sesuatu yang tidak bisa diubah. Ini membingungkan dan memberikan kesan yang salah dari argumen.
Generator berikut hampir sama dengan yang pertama tetapi tidak memiliki masalah mencoba meratakan objek yang tidak dapat diubah. Gagal seperti yang diharapkan ketika argumen yang tidak tepat diberikan padanya.
Menguji generator berfungsi dengan baik dengan daftar yang disediakan. Namun, kode baru akan memunculkan
TypeError
ketika objek yang tidak dapat diubah diberikan padanya. Contoh ditunjukkan di bawah ini dari perilaku baru.sumber
Meskipun jawaban yang elegan dan sangat pythonic telah dipilih, saya akan menyajikan solusi saya hanya untuk ulasan:
Tolong beri tahu seberapa baik atau buruk kode ini?
sumber
isinstance(i, (tuple, list))
. Menginisialisasi variabel kosong adalah tanda bagi saya untuk mencari struktur kode alternatif, biasanya pemahaman, generator, rekursi, dll.return type(l)(ret)
akan membuat Anda mendapatkan jenis kontainer yang sama seperti yang diteruskan, juga. :)Saya lebih suka jawaban sederhana. Tidak ada generator. Tidak ada batas rekursi atau rekursi. Hanya iterasi:
Ini bekerja dengan dua daftar: bagian dalam untuk loop dan loop sementara luar.
Bagian dalam untuk loop berulang melalui daftar. Jika ia menemukan elemen daftar, itu (1) menggunakan list.extend () untuk meratakan bagian itu satu tingkat bersarang dan (2) beralih keepChecking ke True. keepchecking digunakan untuk mengontrol loop sementara luar. Jika loop luar disetel ke true, itu memicu loop dalam untuk lintasan lain.
Pass tersebut terus terjadi sampai tidak ada lagi daftar bersarang yang ditemukan. Ketika pass akhirnya terjadi di mana tidak ada yang ditemukan, keepChecking tidak pernah tersandung ke true, yang berarti listIsNested tetap salah dan loop keluar sementara keluar.
Daftar yang rata kemudian dikembalikan.
Uji coba
[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]
sumber
Berikut adalah fungsi sederhana yang meratakan daftar kedalaman sewenang-wenang. Tanpa rekursi, untuk menghindari stack overflow.
sumber
Saya terkejut tidak ada yang memikirkan hal ini. Rekursi sial Saya tidak mendapatkan jawaban rekursif yang dibuat oleh orang-orang lanjut di sini. Lagi pula di sini adalah upaya saya dalam hal ini. peringatan itu sangat spesifik untuk kasus penggunaan OP
keluaran:
sumber
Saya tidak membahas semua jawaban yang sudah tersedia di sini, tetapi di sini ada satu liner yang saya buat, meminjam dari cara Lisp tentang pemrosesan daftar pertama dan sisanya
di sini adalah satu kasus sederhana dan satu tidak terlalu sederhana -
sumber
def foo():
adalah baris yang terpisah. Juga, ini sangat tidak bisa dibaca.Ketika mencoba menjawab pertanyaan seperti itu, Anda benar-benar perlu memberikan batasan kode yang Anda usulkan sebagai solusi. Jika itu hanya tentang kinerja saya tidak akan terlalu keberatan, tetapi sebagian besar kode yang diusulkan sebagai solusi (termasuk jawaban yang diterima) gagal untuk meratakan daftar yang memiliki kedalaman lebih dari 1000.
Ketika saya mengatakan sebagian besar kode saya maksud adalah semua kode yang menggunakan segala bentuk rekursi (atau memanggil fungsi pustaka standar yang rekursif). Semua kode ini gagal karena untuk setiap panggilan rekursif yang dibuat, tumpukan (panggilan) bertambah satu unit, dan tumpukan panggilan python (default) memiliki ukuran 1000.
Jika Anda tidak terlalu terbiasa dengan tumpukan panggilan, maka mungkin yang berikut ini akan membantu (jika tidak, Anda bisa menggulir ke Implementasi ).
Panggil ukuran tumpukan dan pemrograman rekursif (analogi penjara)
Menemukan harta dan keluar
Bayangkan Anda memasuki ruang bawah tanah besar dengan kamar-kamar bernomor , mencari harta karun. Anda tidak tahu tempat itu tetapi Anda memiliki beberapa indikasi tentang bagaimana menemukan harta karun itu. Setiap indikasi adalah teka-teki (kesulitan bervariasi, tetapi Anda tidak dapat memprediksi seberapa sulit mereka akan). Anda memutuskan untuk berpikir sedikit tentang strategi menghemat waktu, Anda membuat dua pengamatan:
Saat memasuki ruang bawah tanah, Anda melihat notebook kecil di sini. Anda memutuskan untuk menggunakannya untuk menuliskan setiap kamar yang Anda keluar setelah menyelesaikan teka-teki (saat memasuki ruangan baru), dengan cara ini Anda akan dapat kembali ke pintu masuk. Itu ide jenius, Anda bahkan tidak akan menghabiskan satu sen menerapkan strategi Anda.
Anda memasuki ruang bawah tanah, menyelesaikan dengan sukses besar teka-teki 1001 pertama, tetapi inilah sesuatu yang belum Anda rencanakan, Anda tidak memiliki ruang tersisa di notebook yang Anda pinjam. Anda memutuskan untuk meninggalkan pencarian karena Anda lebih suka tidak memiliki harta daripada hilang selamanya di dalam penjara bawah tanah (yang memang terlihat pintar).
Menjalankan program rekursif
Pada dasarnya, itu sama persis dengan menemukan harta karun itu. Penjara bawah tanah adalah memori komputer , tujuan Anda sekarang bukan untuk menemukan harta tetapi untuk menghitung beberapa fungsi (temukan f (x) untuk x yang diberikan ). Indikasinya sederhana adalah sub-rutin yang akan membantu Anda memecahkan f (x) . Strategi Anda sama dengan strategi tumpukan panggilan , notebook adalah tumpukan, kamar-kamar adalah alamat pengirim fungsi:
Masalah yang Anda temui di ruang bawah tanah akan sama di sini, tumpukan panggilan memiliki ukuran yang terbatas (di sini 1000) dan oleh karena itu, jika Anda memasukkan terlalu banyak fungsi tanpa kembali maka Anda akan mengisi tumpukan panggilan dan memiliki kesalahan yang terlihat seperti
"Sayang petualang, aku sangat menyesal tapi notebook Anda penuh":RecursionError: maximum recursion depth exceeded
. Perhatikan bahwa Anda tidak perlu rekursi untuk mengisi tumpukan panggilan, tetapi sangat tidak mungkin bahwa program non-rekursif memanggil 1000 fungsi tanpa pernah kembali. Penting juga untuk memahami bahwa begitu Anda kembali dari suatu fungsi, tumpukan panggilan dibebaskan dari alamat yang digunakan (karenanya nama "tumpukan", alamat pengirim didorong masuk sebelum memasukkan suatu fungsi dan ditarik keluar ketika kembali). Dalam kasus khusus rekursi sederhana (fungsif
panggilan itu sendiri sekali - lagi dan lagi -) Anda akan masukf
berulang sampai perhitungan selesai (sampai harta ditemukan) dan kembali darif
sampai Anda kembali ke tempat di mana Anda memanggilf
tempat pertama. Tumpukan panggilan tidak akan pernah dibebaskan dari apa pun sampai akhir di mana ia akan dibebaskan dari semua alamat pengirim satu demi satu.Bagaimana cara menghindari masalah ini?
Itu sebenarnya cukup sederhana: "jangan menggunakan rekursi jika Anda tidak tahu seberapa dalam itu bisa terjadi". Itu tidak selalu benar seperti dalam beberapa kasus, rekursi Tail Call dapat Dioptimalkan (TCO) . Tetapi dalam python, ini tidak terjadi, dan bahkan fungsi rekursif "ditulis dengan baik" tidak akan mengoptimalkan penggunaan stack. Ada pos menarik dari Guido tentang pertanyaan ini: Penghapusan Rekursi Ekor .
Ada teknik yang dapat Anda gunakan untuk membuat fungsi berulang berulang, teknik ini bisa kita sebut membawa notebook Anda sendiri . Misalnya, dalam kasus khusus kami, kami hanya menjelajahi daftar, memasuki ruangan sama dengan memasukkan sublist, pertanyaan yang harus Anda tanyakan pada diri sendiri adalah bagaimana saya bisa kembali dari daftar ke daftar induknya? Jawabannya tidak rumit, ulangi yang berikut sampai
stack
kosong:address
danindex
distack
saat memasuki sublist baru (catatan bahwa alamat daftar + indeks juga alamat, oleh karena itu kita hanya menggunakan teknik yang sama persis digunakan oleh panggilan stack);yield
itu (atau menambahkannya dalam daftar);stack
pengembalianaddress
(danindex
) .Perhatikan juga bahwa ini setara dengan DFS di pohon di mana beberapa node adalah daftar
A = [1, 2]
dan beberapa item sederhana:0, 1, 2, 3, 4
(untukL = [0, [1,2], 3, 4]
). Pohon itu terlihat seperti ini:Pre-order traversal DFS adalah: L, 0, A, 1, 2, 3, 4. Ingat, untuk menerapkan iteratif DFS Anda juga "perlu" tumpukan. Implementasi yang saya usulkan sebelum menghasilkan negara-negara berikut (untuk
stack
danflat_list
):Dalam contoh ini, ukuran maksimum tumpukan adalah 2, karena daftar input (dan karenanya pohon) memiliki kedalaman 2.
Penerapan
Untuk implementasinya, dalam python Anda dapat menyederhanakan sedikit dengan menggunakan iterator dan bukan daftar sederhana. Referensi ke (sub) iterator akan digunakan untuk menyimpan sublists mengembalikan alamat (bukan memiliki kedua daftar alamat dan indeks). Ini bukan perbedaan besar tapi saya merasa ini lebih mudah dibaca (dan juga sedikit lebih cepat):
Juga, perhatikan bahwa di
is_list_like
I haveisinstance(item, list)
, yang bisa diubah untuk menangani lebih banyak tipe input, di sini saya hanya ingin memiliki versi paling sederhana di mana (iterable) hanya daftar. Tetapi Anda juga bisa melakukannya:Ini menganggap string sebagai "item sederhana" dan karenanya
flatten_iter([["test", "a"], "b])
akan kembali["test", "a", "b"]
dan tidak["t", "e", "s", "t", "a", "b"]
. Komentar bahwa dalam kasus itu,iter(item)
disebut dua kali pada setiap item, mari kita berpura-pura sebagai latihan bagi pembaca untuk membuat ini lebih bersih.Menguji dan memberi komentar tentang implementasi lain
Pada akhirnya, ingat bahwa Anda tidak dapat mencetak daftar jauh bersarang
L
menggunakanprint(L)
karena internal akan menggunakan panggilan rekursif untuk__repr__
(RecursionError: maximum recursion depth exceeded while getting the repr of an object
). Untuk alasan yang sama, solusi untukflatten
melibatkanstr
akan gagal dengan pesan kesalahan yang sama.Jika Anda perlu menguji solusi Anda, Anda dapat menggunakan fungsi ini untuk menghasilkan daftar bersarang sederhana:
Yang memberi:
build_deep_list(5)
>>>[4, [3, [2, [1, [0]]]]]
.sumber
Berikut
compiler.ast.flatten
implementasinya di 2.7.5:Ada metode yang lebih baik, lebih cepat (Jika Anda sudah sampai di sini, Anda sudah melihatnya)
Juga mencatat:
sumber
benar-benar gila tapi saya pikir itu akan berhasil (tergantung pada data_type Anda)
sumber
Cukup gunakan
funcy
perpustakaan:pip install funcy
sumber
Berikut ini adalah pendekatan py2 lain, saya tidak yakin apakah ini yang tercepat atau yang paling elegan ...
Itu dapat mengabaikan jenis spesifik (atau turunan) yang Anda inginkan, mengembalikan iterator, sehingga Anda dapat mengonversinya ke wadah tertentu seperti daftar, tuple, dict atau cukup mengkonsumsinya untuk mengurangi jejak memori, baik atau buruk dapat menangani objek non-iterable awal seperti ...
Perhatikan sebagian besar pengangkatan berat dilakukan dalam C, karena sejauh yang saya tahu itulah cara itertools diimplementasikan, jadi saat ini bersifat rekursif, AFAIK tidak dibatasi oleh kedalaman rekursi python karena pemanggilan fungsi terjadi di C, meskipun ini tidak berarti Anda dibatasi oleh memori, khususnya di OS X di mana ukuran tumpukannya memiliki batas yang sulit pada hari ini (OS X Mavericks) ...
ada pendekatan yang sedikit lebih cepat, tetapi metode yang lebih portabel, hanya gunakan jika Anda dapat mengasumsikan bahwa elemen dasar dari input dapat ditentukan secara eksplisit, jika tidak, Anda akan mendapatkan rekursi tak terbatas, dan OS X dengan ukuran stack yang terbatas, akan melempar kesalahan segmentasi dengan cukup cepat ...
di sini kita menggunakan set untuk memeriksa jenis sehingga dibutuhkan O (1) vs O (jumlah jenis) untuk memeriksa apakah suatu elemen harus diabaikan, meskipun tentu saja nilai apa pun dengan jenis turunan dari jenis yang diabaikan akan dinyatakan gagal. , ini sebabnya penggunaannya
str
,unicode
jadi gunakan dengan hati-hati ...tes:
sumber
Tanpa menggunakan perpustakaan apa pun:
sumber
Menggunakan
itertools.chain
:Atau tanpa rantai:
sumber
Saya menggunakan rekursif untuk memecahkan daftar bersarang dengan kedalaman apa pun
Jadi setelah saya mendefinisikan fungsi fungsi_next, mudah untuk menggunakan fungsi ini melakukan flatting. Atau Anda bisa menggabungkannya menjadi satu fungsi. Saya suka solusi saya karena dapat diterapkan ke daftar bersarang.
hasil
sumber
current_value = combiner(current_value,each_item) RecursionError: maximum recursion depth exceeded
Cara termudah adalah menggunakan perpustakaan morf menggunakan
pip install morph
.Kode tersebut adalah:
sumber
Saya sadar bahwa sudah ada banyak jawaban yang luar biasa tetapi saya ingin menambahkan jawaban yang menggunakan metode pemrograman fungsional untuk menyelesaikan pertanyaan. Dalam jawaban ini saya menggunakan rekursi ganda:
keluaran:
sumber
Saya tidak yakin apakah ini perlu lebih cepat atau lebih efektif, tetapi inilah yang saya lakukan:
The
flatten
Fungsi sini ternyata daftar ke string, mengeluarkan semua dari kurung persegi, menempel kurung kembali ke ujung, dan mengubahnya kembali ke dalam daftar.Meskipun, jika Anda tahu Anda akan memiliki tanda kurung siku dalam daftar dalam string
[[1, 2], "[3, 4] and [5]"]
, Anda harus melakukan sesuatu yang lain.sumber
Ini adalah alat sederhana ratakan pada python2
sumber
Ini akan meratakan daftar atau kamus (atau daftar daftar atau kamus kamus dll). Itu mengasumsikan bahwa nilai-nilai adalah string dan itu menciptakan string yang menyatukan setiap item dengan argumen pemisah. Jika mau, Anda bisa menggunakan pemisah untuk membagi hasilnya menjadi objek daftar sesudahnya. Ini menggunakan rekursi jika nilai berikutnya adalah daftar atau string. Gunakan argumen kunci untuk mengetahui apakah Anda ingin kunci atau nilai-nilai (atur kunci ke salah) dari objek kamus.
hasil:
sumber
Jika Anda menyukai rekursi, ini mungkin solusi yang menarik bagi Anda:
Saya sebenarnya mengadaptasi ini dari beberapa kode praktek Skema yang saya tulis beberapa waktu lalu.
Nikmati!
sumber
Saya baru mengenal python dan berasal dari latar belakang cadel. Inilah yang saya buat (lihat nama var untuk lulz):
Tampaknya bekerja. Uji:
pengembalian:
sumber