Переместить все нули в начало списка в Python

Вы можете отсортировать список:

 a.sort(key=lambda v: v != 0) 

key функция указывает Python на сортировку значений по умолчанию или нет. False сортируется до True , а затем значения сортируются на основе их исходного относительного положения.

Для 0 возвращается False , сначала сортируя все эти значения. Для остальных True возвращается, оставляя сортировку, чтобы поместить их в последний, но оставить их относительные позиции нетронутыми.

Демо-версия:

 >>> a = [4, 5, 0, 0, 6, 7, 0, 1, 0, 5] >>> a.sort(key=lambda v: v != 0) >>> a [0, 0, 0, 0, 4, 5, 6, 7, 1, 5] 

Это можно сделать без сортировки.

Решения

Инициализация:

 In [8]: a = [4, 5, 0, 0, 6, 7, 0, 1, 0, 5] In [9]: from itertools import compress, repeat, chain 

list.count и itertools.compress

 In [10]: x = [0] * a.count(0); x.extend(compress(a, a)) In [11]: x Out[11]: [0, 0, 0, 0, 4, 5, 6, 7, 1, 5] 

То же, что и раньше, но без list.count

 In [12]: c = list(compress(a, a)); [0] * (len(a) - len(c)) + c Out[12]: [0, 0, 0, 0, 4, 5, 6, 7, 1, 5] 

list.count , itertools.compress , itertools.repeat , itertools.chain

 In [13]: list(chain(repeat(0, a.count(0)), compress(a, a))) Out[13]: [0, 0, 0, 0, 4, 5, 6, 7, 1, 5] 

То же, что и предыдущий, но без list.count

 In [14]: c = list(compress(a, a)); list(chain(repeat(0, len(a) - len(c)), c)) Out[14]: [0, 0, 0, 0, 4, 5, 6, 7, 1, 5] 

Ориентиры

Для небольших списков:

 In [21]: %timeit x = [0] * a.count(0); x.extend(compress(a, a)) 1000000 loops, best of 3: 583 ns per loop In [22]: %timeit c = list(compress(a, a)); [0] * (len(a) - len(c)) + c 1000000 loops, best of 3: 661 ns per loop In [23]: %timeit list(chain(repeat(0, a.count(0)), compress(a, a))) 1000000 loops, best of 3: 762 ns per loop In [24]: %timeit c = list(compress(a, a)); list(chain(repeat(0, len(a) - len(c)), c)) 1000000 loops, best of 3: 900 ns per loop 

Для больших списков:

 In [28]: a *= 10000000 In [29]: %timeit x = [0] * a.count(0); x.extend(compress(a, a)) 1 loops, best of 3: 1.43 s per loop In [30]: %timeit c = list(compress(a, a)); [0] * (len(a) - len(c)) + c 1 loops, best of 3: 1.37 s per loop In [31]: %timeit list(chain(repeat(0, a.count(0)), compress(a, a))) 1 loops, best of 3: 1.79 s per loop In [32]: %timeit c = list(compress(a, a)); list(chain(repeat(0, len(a) - len(c)), c)) 1 loops, best of 3: 1.47 s per loop 

Как вы можете видеть, в некоторых случаях itertools основе itertools имеют тенденцию быть более медленными из-за большого числа вызовов функций.

Вот несколько лучших таймингов с двумя новыми методами:

 SETUP=" from itertools import compress, repeat, chain a = [4, 5, 0, 0, 6, 7, 0, 1, 0, 5] " 

Сначала сортировка:

 python -m timeit -s "$SETUP" "a.sort(key=bool)" # 1000000 loops, best of 3: 1.51 usec per loop 

Тогда методы frostnational:

 python -m timeit -s "$SETUP" "list(chain(repeat(0, a.count(0)), compress(a, a)))" # 1000000 loops, best of 3: 1.16 usec per loop python -m timeit -s "$SETUP" "cs = list(compress(a, a)); list(chain(repeat(0, len(a)-len(cs)), cs))" # 1000000 loops, best of 3: 1.37 usec per loop 

Затем методы, более непосредственно работающие из списков:

 python -m timeit -s "$SETUP" "[0] * a.count(0) + list(filter(bool, a))" # 1000000 loops, best of 3: 1.04 usec per loop python -m timeit -s "$SETUP" "nonzero = list(filter(bool, a)); [0] * (len(a)-len(nonzero)) + nonzero" # 1000000 loops, best of 3: 0.87 usec per loop 

И снова с большим размером ввода:

 SETUP=" from itertools import compress, repeat, chain a = [4, 5, 0, 0, 6, 7, 0, 1, 0, 5] * 1000 " 

Сортировка:

 python -m timeit -s "$SETUP" "a.sort(key=bool)" # 1000 loops, best of 3: 1.08 msec per loop 

frostnational-х:

 python -m timeit -s "$SETUP" "list(chain(repeat(0, a.count(0)), compress(a, a)))" # 1000 loops, best of 3: 333 usec per loop python -m timeit -s "$SETUP" "cs = list(compress(a, a)); list(chain(repeat(0, len(a)-len(cs)), cs))" # 1000 loops, best of 3: 206 usec per loop 

Новое:

 python -m timeit -s "$SETUP" "[0] * a.count(0) + list(filter(bool, a))" # 1000 loops, best of 3: 295 usec per loop python -m timeit -s "$SETUP" "nonzero = list(filter(bool, a)); [0] * (len(a)-len(nonzero)) + nonzero" # 10000 loops, best of 3: 143 usec per loop 

Тем не менее, несмотря на относительно медленное решение Martijn Pieters использовать сортировку на самом деле довольно конкурентоспособно для списков разумного размера, а преждевременная оптимизация – корень всего зла.

FWIW, вот некоторые тайминги для очень длинных списков:

 SETUP=" from itertools import compress, repeat, chain a = [4, 5, 0, 0, 6, 7, 0, 1, 0, 5] * 1000000 " python -m timeit -s "$SETUP" "a.sort(key=bool)" # 10 loops, best of 3: 1.21 sec per loop python -m timeit -s "$SETUP" "list(chain(repeat(0, a.count(0)), compress(a, a)))" # 10 loops, best of 3: 347 msec per loop python -m timeit -s "$SETUP" "cs = list(compress(a, a)); list(chain(repeat(0, len(a)-len(cs)), cs))" # 10 loops, best of 3: 226 msec per loop python -m timeit -s "$SETUP" "[0] * a.count(0) + list(filter(bool, a))" # 10 loops, best of 3: 310 msec per loop python -m timeit -s "$SETUP" "nonzero = list(filter(bool, a)); [0] * (len(a)-len(nonzero)) + nonzero" # 10 loops, best of 3: 153 msec per loop