Соотношение между ресурсами памяти и ресурсами процессора

[Sender]

Mihaylo в сообщении #1400757 писал(а):

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

Тем не менее, ещё есть куда расти. Хотелось бы видеть устойчивую сортировку с временем выполнения $O(n)$ на почти отсортированных массивах, $O(n \log n)$ в худшем случае и использованием дополнительной памяти $O(1)$ .

[mihaild]

Sender в сообщении #1400791 писал(а):

устойчивую сортировку с временем выполнения $O(n)$ на почти отсортированных массивах, $O(n \log n)$ в худшем случае и использованием дополнительной памяти $O(1)$ .

Запускайте Insertion sort, ждете линейное время, если не отсортировал - запускаете inplace merge sort.

Pavia в сообщении #1400759 писал(а):

Это не так.

Как это не так? Формулировка, конечно, неформальная, но вроде бы раскрывается стандартно: для любого алгоритма сортировки, которому за $O(1)$ доступна арифметика с индексами и операции "сравнить два элемента по индексам" и "переставить два элемента по индексам", и для любого $n$, существует вход, на котором этот алгоритм делает хотя бы $\frac{n \ln n}{100}$ сравнений. Вы какую-то другую формализацию предлагаете?

[Mihaylo]

Pavia в сообщении #1400759 писал(а):

Вы ещё поразрядную сортировку забыли
Поразрядную сортировка (RadixSort): сложность вычислений $O(n)$, используемая память $O(n)$.

Я не забыл, она просто не совсем законная. Она пригодна лишь для сортировки целых чисел или других объектов с ограниченной категорийностью.

[Munin]

mihaild в сообщении #1400795 писал(а):

Запускайте Insertion sort, ждете линейное время

с каким коэффициентом?

[Sender]

Вот, кстати, интересно, каково минимально возможное значение времени работы алгоритма сортировки $n$ элементов, усреднённое по всем возможным перестановкам некоторого массива $n$ попарно различных элементов, подаваемым на его вход?

[mihaild]

Munin в сообщении #1400813 писал(а):

Изображение с каким коэффициентом?

С каким-то.
На самом деле можно даже $n\cdot \ln n$ операций подождать. Все требования всё равно будут выполнены.

[B@R5uk]

Sender в сообщении #1400824 писал(а):

Вот, кстати, интересно, каково минимально возможное значение времени работы алгоритма сортировки $n$ элементов, усреднённое по всем возможным перестановкам некоторого массива $n$ попарно различных элементов, подаваемым на его вход?

Вот это как раз легко прикинуть. Размер в $n$ элементов (пускай они все будут различные, не ограничивая общность) подразумевает, что у нас имеется $n!$ перестановок, причём только одна из них правильная. Это означает, что чтобы правильно расставить элементы нам нужно $\log_2n!$ бит информации. Эти биты информации берутся из сравнений элементов друг с другом. При оптимальном алгоритме каждое сравнение — один бит. Дальше формула Стирлинга:

$$\log_2n!\approx\log_2\left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\right)= \frac{1}{2}\log_2\left(2\pi\right)+\frac{1}{2}\log_2n+n\log_2n-n\log_2e= O\left(n\log n\right)$$

Но это только количество сравнений. Что там будет с операциями копирования/перемещения надо думать. Вообще, нам надо $n$ элементов с одного несортированного массива перенести в новый в правильном расположении. В идеальном случае, на это требуется $n$ операций перемещения.

-- 22.06.2019, 20:22 --

Munin в сообщении #1400661 писал(а):

А что на что умножается? Потому что умножение на 10 делается из тех же сложений и сдвигов.

Ну, чтобы, например, выделить десятичную цифру сотен из байта, можно воспользоваться такой формулой:

(Byte * 41) >> 12

(Оффтоп)

( 99 * 41) >> 12 = 0
(100 * 41) >> 12 = 1
(199 * 41) >> 12 = 1
(200 * 41) >> 12 = 2

Сразу надо заметить, что сдвиги на обоих разновидностях МК (с аппаратным умножителем и без) выполняются по одному разряду, а не разом как на x86. Впрочем, сдвиг на 12 разрядов реально на этих МК делается в три операции: старший байт произведения загоняется в верхний регистр МК (операция MOV), у него меняются местами полубайты (операция SWAP), а потом результат логически умножается на 0x0F (операция ANDI).

Фактически этот приём выделения десятичной цифры сотен использует тот факт, что для небольших чисел (вмещающихся в один байт) величина $41/4096$ — это с высокой точностью $1/100$.

Для выделения десяток можно использовать формулу

(Byte * 205) >> 11

Она работает для всех чисел байта. Для диапазона 0...99, возможно, можно придумать формулу с множителем по-меньше, но это надо проверять.

[Munin]

Осталось заметить, что 41=0b101001, и заменить сложениями и сдвигами. Может получиться даже быстрее, чем на аппаратном умножении.
205 - похуже, 205=0b11001101. Впрочем, тоже три сложения, но с тремя промежуточными значениями, а не с двумя.

[Dmitriy40]

Вот в этом и "теоретичность" этих оценок, что учитывают только строго оговорённые вещи типа количества сравнений, а на остальные забивают, а ведь даже единичная произвольная перестановка большого массива может занять больше времени чем все $O(n \log n)$ сравнений, чисто из-за случайности доступа (особенно по записи). Пример: медленные по записи устройства типа flash, hdd.
И потому реально представляют интерес не только оценки количества сравнений, но и количество перестановок, и особенно для почти отсортированных входных данных (такие на практике встречаются достаточно часто).

С другой стороны, знать асимптотику применённого алгоритма всё равно полезно, как только данные вылезут за кэши, она встанет в полный рост и будет определять время работы. И тут важно не попасть в ловушку слишком коротких тестов, когда проверяешь на малом объёме и всё прекрасно, а при удесятерении (не будем о грустном х1000 и более) объёма или получении сильно более случайных (а то и неслучайных) данных время работы внезапно лезет в небеса ...

Munin в сообщении #1400866 писал(а):

Осталось заметить, что 41=0b101001, и заменить сложениями и сдвигами. Может получиться даже быстрее, чем на аппаратном умножении.

Думаю вряд ли: если уж есть аппаратный умножитель, то он обычно быстрее чем три сдвига с тремя сложениями, даже включая команды пересылок множителей и произведений. И кстати быстрые сдвиги на несколько битов даже бОльшая редкость в микроконтроллерах (а про процессоры не будем, там всё прекрасно) чем аппаратный умножитель, имхо.

[B@R5uk]

Munin в сообщении #1400866 писал(а):

Может получиться даже быстрее, чем на аппаратном умножении.

Нет, аппаратное умножение AVR — это два такта. Логический сдвиг двух байтов на один бит тоже два такта (две операции), так что судите сами. И всё равно, без аппаратного умножителя самый быстрый алгоритм будет именно линейный: крутить циклы, вычитая сначала сотни, потом десятки. Единицы получатся автоматически. Причём этот алгоритм имеет кроме скорости имеет ещё одно важное достоинство: количество задействованных регистров минимально возможное.

-- 22.06.2019, 21:53 --

Dmitriy40 в сообщении #1400875 писал(а):

Вот в этом и "теоретичность" этих оценок, что учитывают только строго оговорённые вещи типа количества сравнений, а на остальные забивают

Если вы про мои выкладки, то я прикидывал оценку снизу. На сколько я понял это имелось в виду (поскольку конкретный алгоритм не был указан).

[Munin]

Dmitriy40 в сообщении #1400875 писал(а):

Вот в этом и "теоретичность" этих оценок, что учитывают только строго оговорённые вещи типа количества сравнений, а на остальные забивают

Нет, вы ошибаетесь. Можно посчитать сложность по количеству сравнений. Можно - по количеству копирований. Можно - по количеству операций с адресами и указателями. Что хотите, на ваш выбор.

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

И во-вторых, часто сравнение оказывается самой дорогостоящей операцией. Например, когда вы сортируете строки, то каждое сравнение строк - это отдельный цикл $O(L).$ (Кстати, если строки длины $L,$ но самих строк $\ll 26^L,$ что обычно и имеет место, то можно сначала их как-то "умно похэшировать" с хэш-функцией, примерно сохраняющей порядок.) Иногда ещё дорогостоящей операцией является копирование, но в сортировке можно этого избежать: сортировать указатели.

Dmitriy40 в сообщении #1400875 писал(а):

Пример: медленные по записи устройства типа flash, hdd.

Это не новость и не секрет, и в таких ситуациях разрабатывают специальные алгоритмы и структуры данных. Можно просто частично кэшировать вычисления в более быстродействующей памяти.

Dmitriy40 в сообщении #1400875 писал(а):

И потому реально представляют интерес не только оценки количества сравнений, но и количество перестановок, и особенно для почти отсортированных входных данных (такие на практике встречаются достаточно часто).

Вообще если данные почти отсортированы, то лучше применять другую стратегию: не добавлять ворох мусора, а потом снова сортировать; а сразу при добавлении новых данных insert-ить их в нужное место, сохраняя отсортированность. Впрочем, опять же, это вариант, а надо сравнивать конкретику.

Dmitriy40 в сообщении #1400875 писал(а):

С другой стороны, знать асимптотику применённого алгоритма всё равно полезно, как только данные вылезут за кэши

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

B@R5uk в сообщении #1400880 писал(а):

И всё равно, без аппаратного умножителя самый быстрый алгоритм будет именно линейный: крутить циклы

Странно, ну да ладно. Раз вы говорите, что три сложения медленнее, чем десять вычитаний, то наверное, вы проверяли.

[B@R5uk]

Munin в сообщении #1400889 писал(а):

три сложения медленнее, чем десять вычитаний, то наверное, вы проверяли.

Не забывайте, что там ещё 8 сдвигов по 2 такта каждый и сами сложения занимают 2 такта, так как работа идёт с двубайтными величинами, плюс выделение цифры и перекладывание. Итого: около 25 тактов. Цикл вычитаний для первой цифры длиться от 5 тактов (цифра 0) до 15 тактов (цифра 2). Дальше больше: прежде, чем считать десятки, надо отщепить от исходной величины полученные сотни. Это умножение на 10 и вычитание, технически же получается 4 сдвига, два вычитания и пара копирований, то есть около 8 тактов, после чего приступаем к вычислению десятков, что займёт приблизительно те же 25 тактов. Потом вычитание десятков для получения единиц, то есть ещё 8 тактов. В сумме выходит где-то 66-70 тактов (это ещё я не уточнял как много придётся копировать промежуточные величины). В это время цикл десяток покрутившись от 5 тактов (цифра 0) до 50 тактов (цифра 9) даёт две последние цифры байта сразу. Реально время выполнения с циклами выходит

10 + 5 * {сумма первой и второй цифр}

тактов. То есть максимум 60 тактов для цифр вида 19x. Я уж молчу про разницу в размерах кода в обоих случаях. Наличие аппаратного умножителя, разумеется, переворачивает всё с головы на ноги.

[Sender]

B@R5uk в сообщении #1400860 писал(а):

Вот это как раз легко прикинуть.

Да, похоже, что так. Спасибо.

[Dmitriy40]

B@R5uk в сообщении #1400880 писал(а):

И всё равно, без аппаратного умножителя самый быстрый алгоритм будет именно линейный: крутить циклы, вычитая сначала сотни, потом десятки.

Не согласен, самый быстрый будет очевидно табличный (но памяти сожрёт 780, 528, 284 байтов):

;<ZL - число, >R18R17R16 - десятичное представление
;Трёхтабличное решение
        ldi     ZH,tab100       ;1
        lpm     R18,Z           ;3
        ldi     ZH,tab10        ;1
        lpm     R17,Z           ;3
        ldi     ZH,tab1         ;1
        lpm     R16,Z           ;3      =12
;Экономия третьей таблицы
        ldi     ZH,tab100       ;1
        lpm     R18,Z           ;3
        ldi     ZH,tab10_1      ;1
        lpm     R17,Z           ;3
        mov     R16,R17         ;1
        swap    R17             ;1
        andi    R16,0x0F        ;1
        andi    R17,0x0F        ;1      =12
;Экономия первой таблицы
        ldi     R18,0           ;1
        subi    ZL,100          ;1
        brcs    l100            ;1/2
        inc     R18             ;1
        subi    ZL,100          ;1
        brcs    l100            ;1/2
        inc     R18             ;1
        subi    ZL,100          ;1
l100:   ldi     ZH,tab10_1_100  ;1
        lpm     R17,Z           ;3
        mov     R16,R17         ;1
        swap    R17             ;1
        andi    R16,0x0F        ;1
        andi    R17,0x0F        ;1      =12..16

[B@R5uk]

Dmitriy40, подловили! Про таблицу я в курсе, правда запихивать две цифры в байт как-то не догадался. Наверное, потому что ещё не пробовал её реализовывать (дуже много памяти жрёт), и ещё потому, что хочется запихнуть в таблицу сразу код семисегментного индикатора (чтобы два раза по таблицам не прыгать). Спасибо за идею.