Рубрика «Алгоритмы» - 325

Я долгое время думал, что написать сортировку массива слиянием так, чтобы она не использовала дополнительной памяти, но чтобы время работы оставалось равным O(N*log(N)), невозможно. Поэтому, когда karlicos поделился ссылкой на описание такого алгоритма, меня это заинтересовало. Поиск по сети показал, что про алгоритм люди знают, но никто им особо не интересуется, его считают сложным и малоэффективным. Хотя, может быть, они имеют в виду какую-то «стабильную» версию этого алгоритма, но нестабильная при этом все равно никому не нужна.
Но я все-таки решил попробовать.
Слияние за линейное время

Идея алгоритма довольноЧитать полностью »

Пример из практики. Понадобилось разобрать вот такие строки из 0 и 1, что на фото 1 в ячейке A2.

image

Это кусочки BMP, что, впрочем, неважно.

Каждая последовательность длиной 4 байта, т.е. 32 бит. Нужно было извлечь из таких последовательностей серии единиц и измерить длину этих серий.

Для данного примера нужно было получить на выходе 1 2 1 2 7.

Можно было начать с распределения символов по столбцам, использовав штатную Экселевскую приблуду Данные/Текст по столбцам. Однако, это требует ручной установки 31 разделителя, что, конечно же, влом. Хотелось, чтобы было так: загрузил на лист кучку байт и сразу получил результат.

Поэтому пришлось нагородить набор костыликов.

В ячейке B2 избавился от лишних нулей формулой СЖПРОБЕЛЫ. Предварительно пришлось нули заменить на пробелы формулой ПОДСТАВИТЬ, а после сжатия вернуть их на место этой же формулой.

В C2 заехал 0. Это чисто служебный нолик, для дальнейшего копирования формул вправо и вниз.

В D2 — формула (видна на фото 2).

image

Находит позицию первого нуля. В E2 — второго и т.д. Как видим, в сжатой последовательности (B2) первый ноль — в позиции 2, второй — в 5-й, третий — в 7-й и 4-й ноль — в 10-й. В последовательности всего 4 нуля, и поэтому в H2 отобразилась бы ошибка #ЗНАЧ, если бы не обработка этой ошибки формулой ЕСЛИОШИБКА. Она заменяет #ЗНАЧ на 99. «Почему 99?» — вы можете спросить. Это число нам понадобится в дальнейших расчетах, терпение.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js