[задача] Оптимальный ffs через fls

(под кат):

echo ZGVjLCB4b3IsIGZscyA/Cg== | base64 -d

> Решение это поистине банально и элементарно, но

здесь недостаточно места, чтобы привести его :)

сдвигать вправо (или делить на два, как по командам получается). Как только в переносе появится 1 то и стоп.

NOT?

Нет, т.к. длительность выполнения этого алгоритма зависит от позиции бита в числе. Так для нахождения ffs(1) потребуется только 1 деление, а для нахождения ffs(8) потребуется уже 3 деления. Т.о. Ваш алгоритм имеет сложность O(n). А требуется найти решение со сложностью O(1) т.е. всегда исполняющееся постоянное время.

Если машина M разрядная, то в числе (2^M - q) все биты младше ffs (q) будут такие же как в q, а остальные - инвертированные.

В итоге:

ffs (q) = ffl (not (not 0 - q + 1) xor q) + 1

Только это вроде не O (1).

:)

По Вашему посту вообще не понятно было, что же Вы такое хотите сказать :)

Почему не O(1)?

Ну смотря как смотреть. Если кол-во разрядов ограниченно, то любая функция есть O (1), так как кол-во вариантов исходных данных конечно.

Если устремлять кол-во разрядов в бесконечность, то возможность организовать сложение за O(1), а также ffl мне не очевидна.

> Если устремлять кол-во разрядов в бесконечность, то возможность организовать сложение за O(1), а также ffl мне не очевидна.

Ну так я специально написал в самой формулировке про _процессор_, который имеет встроенную команду fls. Это сделано именно для того, чтобы показать, что условия в общем-то реальные.

Я Вам больше скажу: это процессор TMS320C6713 с 32-разрядной шиной :)

Ну смотря как смотреть. Если кол-во разрядов ограниченно, то любая функция есть O (1), так как кол-во вариантов исходных данных конечно.

Опять не соглашусь. Силовой метод реализации алгоритма ffs для 32-разрядной шины такой:

for(int bit = 0; !(word & (1 << bit)); ++bit) {}

Вы легко можете убедиться, что время выполнения этой функции для разных значений word различное. В частности при word = 0 и word = 1 оно соответственно максимально и минимально.

Процессор же выполняет fls за один такт. Вычисления, представленные в решении тоже всегда выполняются за фиксированное число тактов. Таким образом на вычисление ffs потребуется всегда фиксированное число тактов процессора.

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

В конце можно дописать несколько холостых тактов чтобы функция всегда вычислялась как в худшем случае.

Если есть всюду положительные функции f,g: N->R, то по определению f = O (g) если существует константа C, такая что для всех натуральных n: f (n) < C*g (n)

Распространять это определение на конечное множество бессмысленно, так как любая функция есть O большое от другой.

> Если есть всюду положительные функции f,g: N->R, то по определению f = O (g) если существует константа C, такая что для всех натуральных n: f (n) < C*g (n)

Распространять это определение на конечное множество бессмысленно, так как любая функция есть O большое от другой.

Ну если так рассуждать, то и теория сложности вычислений вообще не может существовать, ведь все конечные алгоритмы оперируют с конечными множествами данных. И в таком случае, по-вашему, сложность всех алгоритмов получается одинакова. Однако это противоречит простейшим эмпирическим наблюдениям.

В теории сложности оценка сложности через О-символику даётся асимптотически путём устремления мощности конечного множества к бесконечности. И при этом у Вас же не возникает возражений, что: «не существует компьютера с бесконечным объёмом памяти, который мог бы сортировать бесконечный массив, когда мы пытаемся определить сложность алгоритма сортировки».

Вот считайте, что и тут мы устремляем разрядность процессора к бесконечности. Сам факт позволяет наращивать разрядность неограниченно, но это же не значит, что команды процессора теряют свои фундаментальные свойства, правда? Команда по-прежнему выполняется за один такт.

Вы в своём рассуждении попытались получить антиномию, смешав идеализированный математический приём с реальными посылками. Естественно это у Вас получилось т.к. сам факт такого смешивания уже антиномичен сам по себе :)

В конце можно дописать несколько холостых тактов чтобы функция всегда вычислялась как в худшем случае.

Так а какое конкретно количество холостых тактов? Бесконечное (если вы говорите о времени выполнения инструкции над бесконечным набором данных)?

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

Ничего не понял.

Команда по-прежнему выполняется за один такт.

Неверное утверждение

Так а какое конкретно количество холостых тактов? Бесконечное (если вы говорите о времени выполнения инструкции над бесконечным набором данных)?

Дан M разрядный процессор. На вход ffs может быть подано 2^M различных вариантов входных данных. M - конечно (ну пусть M = 1000 для наглядности). 2^M варианов это много, но все равно конечно. Какой-то из них заставляет работать ffs дольше всех (для наглядности предположим 15 тактов). Тогда можно вообразить функцию ffs2, которая будет сначала запускать ffs, а затем крутится в холостую (например, если ffs справилась за 7, то делать вид, что работает она будет 15 - 7 = 8 тактов)

Теперь рассмотрим функцию f:N->N, такую что f (M) есть время работы функции ffs на M разрядном процессоре в худшем случае. И вот у этой функции f уже можно смотреть асимптотику.

Скорее всего f (M) = O (log M) по глубине схемы (времени работы) и f (M) = O (M) по кол-ву логических элементов (ну или транзисторов). Но это нужно доказать.

Я понял, что Вы хотите сказать. И по-моему Вы не правы :)

Ещё раз.

С чем связана необходимость увеличения M?

С тем, что при оценке сложности алгоритма мы ОБЯЗАНЫ перейти к асимптоте. Асимптота достигается при неограниченном увеличении мощности множества данных (количества элементов в множестве данных).

Таким образом мы должны устремить M→∞. Ну хорошо, согласен.

Теперь вопрос: бывают ли на свете процессоры с бесконечно большой шиной данных?

Ответ: Нет, не бывают.

Вопрос: Что в процессоре выполняет операцию fls?

Ответ: АЛУ. Во всех известных мне процессорах (за исключением быть может каких-то самых экзотических) АЛУ выполняет свои операции за один такт процессора.

И это является фундаментальным свойством объекта «процессор». Конечно, можно опуститься на уровень схемотехники и отдельных логических элементов. Можно. Можно даже до отдельных транзисторов дойти. А можно и на уровне отдельных частиц попытаться описывать происходящее. Можно. А нужно?

Достаточно ограничится постулатом: АЛУ процессора срабатывает за один такт. Почему? До потому что это так для _всех реальных процессоров_. А наша задача в конце концов свести описание именно к реальному процессору.

Нам просто нет необходимости описывать свойства процессора со сколь угодно большой шиной данных, если таких процессоров не существует.

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

------------------

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

Подробнее: Пусть есть задача сортировки пузырьком (ололо). Для того, чтобы найти её асимптотику необходимо неограниченно увеличивать объём входных данных, хранящихся в памяти компьютера. Однако при этом ресурсов одного компьютера не хватит. А раз так, то давайте рассматривать конечно-скоростную сеть компьютеров, образующих вычислительное облако.

Сам факт наличия облака наложит некоторые изменения на алгоритм сортировки пузырьком. Учтём эти изменения и оценим его сложность.

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

------------------

И важное замечание. Вы привязались к определению О-большое. И напрасно это сделали :)

В данном случае О-символика лишь удобный способ записи, показывающий некоторую асимптоту. То что на конечном множестве значений любая функция является О-большое от любой другой лишь говорит о том, что любую задачу можно решить перебором.

Однако, такое решение лишено минималистичности и оптимальности. Метод, который Вы предлагаете с выравниванием времени выполнения — он в некотором роде является вариантом перебора.