OberonCore

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

Вы о чём? Об инкапсуляции тут не было ни слова. Вопрос именно о механизме доступа к страничной структуре данных при поиске в ней: с помощью одного цикла Дейкстры (Илья Ермаков) или двух вложенных циклов с break (Vlad). С тем что этот поиск нужно оформить в виде процедуры никто и не спорит.

Ну вот Илья же ответил выше - структура задачи линейна. По сути нужен ОДИН цикл.

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

Про то, чтобы поиск оформить в виде процедуры, говорил не я Я говорил, что в процедуру надо упихать ДОСТУП К ДАННЫМ, где и будут учтены все страницы и т.п. Т.е. это совсем другая задача!

Вы какой вариант выберете?

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

Не забывайте про третий вариант с обычным WHILE. За отсутствием цикла Дейкстры используется именно он (если, конечно, не изворачиваться с упаковкой поиска в процедуру с RETURN).

Насчёт его и цикла Дейкстры я не уверен, что выразительнее - одинаково...

(Для справки: LEN вычисляется компилятором статически)

Страницу вернуть не проблема, но цикл(ы) поиска от этого не поменяются

А-а, до меня дошло: потом можно вызвать функцию "Получить элемент по номеру позиции".
А в принципе, первый вариант понятнее (или, по крайней мере, привычнее).

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

А мне второй эстетически больше нравится/кажется проще; даже не вчитываясь в код... Может потому, что в первом случае в одном структурном операторе сидит другой, а во втором - нет.

Ну что ж вы так... Вот как надо:
И вот теперь доступ к данным отделён от алгоритма задачи. И может выглядеть по-всякому, например:
То есть, повторяю, есть задача, а есть (вспомогательные) подзадачи. И задачу от подзадач целесообразно отделять явно. Поэтому мне одинаково не нравятся два предложенных варианта, и даже вариант Ильи тоже не нравится, поскольку он таки смешивает все слои в общую кучу... Отчего понятность кода существенно проигрывает...

Позорная дискуссия. Всех уволить.

Упражнение. Возьмите первый нетривиальный алгоритм в "Алгоритмах и структурах данных" Вирта (поиск Кнута-Морриса-Пратта, раздел 1.12.5 в старом издании) и перепишите двойной цикл по Дейкстре, т.е. в виде однократного с двумя ветвями.

Увидите две вещи:

1) Рассуждения по Дейкстре позволяют привести нестандартный цикл к стандартному виду ("циклу Дейкстры"), который по-стандартному объясняется, что, естественно, несравненно облегчает понимание-конструирование-объяснение-верификацию.

2) Сам Вирт, хотя и использует инвариант цикла, возится с двойным циклом (скорее всего, он просто "причесал" с помощью WHILE оригинальный код КМП; надо думать, он эти алгоритмы изучал в связи с компиляторами). Отсюда, видимо, объяснение, почему цикл Дейкстры появился в Обероне только в версии 07 не без внешних влиянияний.

Но то, что простительно Вирту, научившемуся уже прилично программировать до 1970 г., непростительно программерам, родившимся после 1970.
(Товарисчи постарше are exempted
---------------------
---------------------
Еще видно, какая там лабуда в пояснениях, причем русский перевод-без-понятия только запутывает дело. И это не одно такое место в книжке, где перевод-по-словам-к-сроку лажает.
А советская теория перевода гласит, что перевод технического текста может и должен быть лучше оригинала

У кого только электронный обероновский вариант (pdf), то там это раздел 1.9.5.

А то, что для рассматриваемой страничной структуры алгоритм поиска станет не линейным, а квадратичным волновать не должно?

Не уволить, а забанить. Начать с меня, как обычно...

А с чего бы ему становиться квадратичным?
Вот я написал пример с прямым доступом к страницам - так он и останется линейным (за вычетом накладных расходов на вызов процедуры и пары команд целочисленной арифметики...

Разумеется, на случай жёсткой оптимизации лучше ничего не придумаешь, чем два цикла Но, согласитесь, это уже совсем другая постановка задачи...

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

Пример, конечно, утрированный, абстрактный и тривиальный... Но тем не менее...

Там вроде главная структура -- список (содержащий страницы). А доступ к n-му элементу списка обычно имеет сложность O(n), а не O(1) как у массива. Получается, что сложность перебора в цикле 0(n) умножается на сложность доступа к элементам массива и получается O(n^2)...

Ну я же подчеркнул - пример с прямым доступам к страницам...

Если однонаправленный список страниц И требование жёсткой оптимизации, тогда решение Ильи выглядит методически более интересным, чем два цикла в той или иной форме. На Драконе будет ещё красивее из-за устранения чисто текстового оверхеда...

Если однонаправленный список страниц И требование масштабируемости, тогда:

а) учёт "аппаратных" ограничений => направление просмотра, совпадающее со списком;
б) кеширование:

Заметим, что это тот же алгоритм Ильи, но с разнесёнными слоями задачи и подзадачи...

Для универсальности и произвольного доступа кэширование, конечно, будет чуть сложнее... Но всё равно для сонаправленного со списком просмотра затратность всё равно будет О(1), а для противоположного, самого неприятного случая, значительно хуже 1, но всё-таки никак не в квадрате

2 замечания
1. Насколько быстродействущим является цикл Дейкстры? IMHO, стандартный цикл с двумя (тремя) for-ами (примеры выше) все таки будет пошустрее.
2. Некоторые компиляторы могут из вложенных циклов сделать один суперцикл.

PS. Не понимаю, о чем спор? Вирт и Дейкстра - все таки не божки, их мнения не являются абсолютизмом. Вам решать, как строить циклы на свой вкус и стиль.

Речь не о вкусах, а о понимании/не понимании смысла, лежащего под составлением алгоритмов.
viewtopic.php?p=21375#p21375