“Сжать” список, переместив все ненулевые элементы в левую часть списка, не меняя их порядок, а все нули - в правую часть

@lookatthis · Регистрация: 14.07.2018

Студворк — интернет-сервис помощи студентам

Дан список целых чисел. Требуется “сжать” его, переместив все ненулевые элементы в левую часть списка, не меняя их порядок, а все нули - в правую часть. Порядок ненулевых элементов изменять нельзя, дополнительный список использовать нельзя, задачу нужно выполнить за один проход по списку. Распечатайте полученный список.

Входные данные
Вводится список чисел. Все числа списка находятся на одной строке.

Выходные данные
Выведите ответ на задачу.

Примеры
входные данные
4 0 5 0 3 0 0 5
выходные данные
4 5 3 5 0 0 0 0

@Garry Galler · 06.08.2020, 16:57

Сообщение от ФедосеевПавел

такой разброс в скорости - 1,5 раза - то чем объяснить?

Python циклы не самые (мягко говоря) быстрые во вселенной программирования.
Поэтому для более эффективной работы с последовательностями в Python существуют встроенные функции, которые работают на порядок эффективнее: sort/map/filter и и т.д.
И надо заметить, что питоновски sort (TimSort) на самом деле еще быстрее. Но только не на полном рандоме, который мы тут ему даем, а на частично отсортированных данных, которые в жизни встречаются чаще.
На полном рандоме быстрее будет quick_sort.

@Viktorrus · 06.08.2020, 16:58

Сообщение от ФедосеевПавел

Но при сортировке такой оптимальности не будет - будет обмен значениями

Если я не ошибаюсь сортировка в питоне написана на Си и поэтому работает значительно быстрее.

ФедосеевПавел · 06.08.2020, 17:05

Получается, что "полная пошаговая роспись алгоритма" будет медленно интерпретироваться, а использование "казалось бы неоптимального" алгоритма (применение избыточных типов данных, избыточных функций) на встроенных средствах - быстро выполняться нативным для процессора кодом.
Ясно.

Спасибо.

@Garry Galler · 06.08.2020, 17:16

Сообщение от ФедосеевПавел

"полная пошаговая роспись алгоритма" будет медленно интерпретироваться

Да, такова суть динамических интерпретируемых языков. Интерпретатор проверяет тип переменной на каждом шаге ее использования. Поэтому в математич. библиотеке numpy (написанной, естественно, на Python-Си-API) существует собственный векторный язык работы с числовыми массивами - и применение Python циклов и функций там вообще ограничено только разовыми вызовами, чтобы не замедлять исполнение машинного кода.

vic5710 · 07.08.2020, 02:16

Сообщение от ФедосеевПавел

Получается, что "полная пошаговая роспись алгоритма" будет медленно интерпретироваться, а использование "казалось бы неоптимального" алгоритма (применение избыточных типов данных, избыточных функций) на встроенных средствах - быстро выполняться нативным для процессора кодом.

не совсем так. для сортировки "на месте" нужна минимум одна временная переменная для свопа двух значений. в Си массивы однородные, доступ через указатель, никаких рантаймовых проверок нет - все проверяет прогер когда пишет. поэтому и скорость выше

vic5710 · 07.08.2020, 19:45

если интересно - гляньте
https://ru.wikibooks.org/wiki/... Сортировка
классика

ФедосеевПавел · 07.08.2020, 22:12

Спасибо.
По сортировке qsort похожее видел для msvcrt.
По ссылке с интересом почитал о необычных рекурсивных решениях других задач.

vic5710 · 07.08.2020, 23:17

Дональд Кнут в "Искусстве программирования" 3 том посвятил именно сортировке и поиску.
тут интересный обзор

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@lookatthis 0 / 0 / 0 Регистрация: 14.07.2018 Сообщений: 23

	“Сжать” список, переместив все ненулевые элементы в левую часть списка, не меняя их порядок, а все нули - в правую часть 26.07.2018, 00:20. Показов 48360. Ответов 47 Метки нет (Все метки) Дан список целых чисел. Требуется “сжать” его, переместив все ненулевые элементы в левую часть списка, не меняя их порядок, а все нули - в правую часть. Порядок ненулевых элементов изменять нельзя, дополнительный список использовать нельзя, задачу нужно выполнить за один проход по списку. Распечатайте полученный список. Входные данные Вводится список чисел. Все числа списка находятся на одной строке. Выходные данные Выведите ответ на задачу. Примеры входные данные 4 0 5 0 3 0 0 5 выходные данные 4 5 3 5 0 0 0 0 0

ФедосеевПавел Модератор 8655 / 4490 / 1669 Регистрация: 01.02.2015 Сообщений: 13,898 Записей в блоге: 12
	06.08.2020, 17:05
	Получается, что "полная пошаговая роспись алгоритма" будет медленно интерпретироваться, а использование "казалось бы неоптимального" алгоритма (применение избыточных типов данных, избыточных функций) на встроенных средствах - быстро выполняться нативным для процессора кодом. Ясно. Спасибо. 0

vic5710 963 / 718 / 276 Регистрация: 10.12.2016 Сообщений: 1,764
	07.08.2020, 19:45
	если интересно - гляньте https://ru.wikibooks.org/wiki/... Сортировка классика 1

ФедосеевПавел Модератор 8655 / 4490 / 1669 Регистрация: 01.02.2015 Сообщений: 13,898 Записей в блоге: 12
	07.08.2020, 22:12
	Спасибо. По сортировке qsort похожее видел для msvcrt. По ссылке с интересом почитал о необычных рекурсивных решениях других задач. 0

vic5710 963 / 718 / 276 Регистрация: 10.12.2016 Сообщений: 1,764
	07.08.2020, 23:17
	Дональд Кнут в "Искусстве программирования" 3 том посвятил именно сортировке и поиску. тут интересный обзор 1