В большинстве случаев при написании циклов я обычно пишу неправильные граничные условия (например, неверный результат) или мои предположения о завершении цикла неверны (например, бесконечно работающий цикл). Хотя после некоторых проб и ошибок мои предположения были правильными, я слишком расстроился из-за отсутствия правильной вычислительной модели в моей голове.
/**
* Inserts the given value in proper position in the sorted subarray i.e.
* array[0...rightIndex] is the sorted subarray, on inserting a new value
* our new sorted subarray becomes array[0...rightIndex+1].
* @param array The whole array whose initial elements [0...rightIndex] are
* sorted.
* @param rightIndex The index till which sub array is sorted.
* @param value The value to be inserted into sorted sub array.
*/
function insert(array, rightIndex, value) {
for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
array[j + 1] = array[j];
}
array[j + 1] = value;
};
Первоначально я допустил следующие ошибки:
- Вместо j> = 0 я сохранил это j> 0.
- Запутался ли массив [j + 1] = значение или массив [j] = значение.
Каковы инструменты / ментальные модели, чтобы избежать таких ошибок?
programming-practices
loops
CodeYogi
источник
источник
j >= 0
это ошибкой? Я был бы более настороженно относятся к тому , что вы обращаетесьarray[j]
иarray[j + 1]
без предварительной проверки , чтоarray.length > (j + 1)
.Array.prototype
в примере с JS). Это предотвращает возникновение граничных условий, поскольку что-то подобноеmap
работает на всех массивах. Вы можете решить вышеизложенное, используя slice и concat, чтобы избежать зацикливания всего: codepen.io/anon/pen/ZWovdg?editors=0012 Самый правильный способ написать цикл - вообще не писать его.Ответы:
Контрольная работа
Нет, серьезно, тест.
Я занимаюсь программированием более 20 лет и до сих пор не верю себе, что правильно написал цикл с первого раза. Я пишу и запускаю тесты, которые доказывают, что это работает, прежде чем я подозреваю, что это работает. Проверьте каждую сторону каждого граничного условия. Например, что
rightIndex
из 0 должно делать что? Как насчет -1?Будь проще
Если другие сразу не видят, что он делает, ты делаешь это слишком сложно. Пожалуйста, не стесняйтесь игнорировать производительность, если это означает, что вы можете написать что-то простое для понимания. Делайте это быстрее только в том маловероятном случае, который вам действительно нужен. И даже тогда, только когда вы абсолютно уверены, что точно знаете, что вас тормозит. Если вы можете добиться реального улучшения Big O, это действие может быть бессмысленным, но даже в этом случае сделайте свой код максимально читабельным.
От одного
Знайте разницу между подсчетом пальцев и подсчетом промежутков между пальцами. Иногда пробелы - это то, что действительно важно. Не позволяйте своим пальцам отвлекать вас. Знайте, является ли ваш большой палец пальцем. Знайте, считается ли разрыв между вашим мизинцем и большим пальцем пробелом.
Комментарии
Прежде чем потеряться в коде, постарайтесь сказать, что вы имеете в виду на английском языке. Четко изложите свои ожидания. Не объясняйте, как работает код. Объясните, почему у вас есть то, что он делает. Храните детали реализации из этого. Должна быть возможность рефакторинга кода без необходимости изменения комментария.
Лучший комментарий - это доброе имя.
Если вы можете сказать все, что вам нужно, с добрым именем, НЕ говорите это снова с комментарием.
Абстракции
Объекты, функции, массивы и переменные - это абстракции, которые настолько хороши, насколько им даны имена. Дайте им имена, которые гарантируют, что, когда люди заглянут внутрь, они не будут удивлены тем, что они найдут.
Короткие имена
Используйте короткие имена для недолговечных вещей.
i
это хорошее имя для индекса в хорошем узком цикле в небольшом объеме, что делает его смысл очевидным. Еслиi
жизнь длится достаточно долго, чтобы распространяться по строке за строкой с другими идеями и именами, с которыми можно спутать,i
то пришло время датьi
хорошее длинное объяснительное имя.Длинные имена
Никогда не сокращайте имя просто из соображений длины строки. Найдите другой способ выложить свой код.
Пробелы
Дефекты любят прятать в нечитаемый код. Если ваш язык позволяет вам выбрать стиль отступа, по крайней мере, будьте последовательны. Не делайте ваш код похожим на поток шума. Код должен выглядеть так, как будто он находится в процессе формирования.
Петлевые конструкции
Изучите и просмотрите структуры петель на вашем языке. Наблюдение за выделением
for(;;)
цикла отладчиком может быть очень поучительным. Изучите все формы.while
,do while
,while(true)
,for each
. Используйте самый простой, который вы можете избежать. Посмотрите на прокачку насоса . Узнайте , чтоbreak
иcontinue
делать , если у вас есть. Знайте разницу междуc++
и++c
. Не бойтесь возвращаться рано, если вы всегда закрываете все, что нужно закрыть. Наконец, блокирует или, предпочтительно, что-то, что помечает его для автоматического закрытия при открытии: Использование оператора / Попробуйте с ресурсами .Альтернативные петли
Пусть что-то еще делает цикл, если вы можете. На глазах легче и уже отлажено. Они бывают разных форм: коллекции или потоки , которые позволяют
map()
,reduce()
,foreach()
, и другие подобные методы , которые применяют лямбда. Ищите специальные функции, какArrays.fill()
. Существует также рекурсия, но только ожидать, чтобы облегчить ситуацию в особых случаях. Обычно не используйте рекурсию, пока не увидите, как будет выглядеть альтернатива.Ох, и проверить.
Тест, тест, тест.
Я упоминал тестирование?
Была еще одна вещь. Не могу вспомнить Началось с T ...
источник
При программировании полезно подумать о:
и при изучении неисследованной территории (например, манипулирования с индексами) может быть очень и очень полезно не просто думать о них, а фактически делать их явными в коде с утверждениями .
Давайте возьмем ваш оригинальный код:
И проверьте, что у нас есть:
array[0..rightIndex]
отсортированоarray[0..rightIndex+1]
отсортировано0 <= j <= rightIndex
но кажется немного избыточным; или как указано @Jules в комментариях, в конце «раунда»for n in [j, rightIndex+1] => array[j] > value
.array[0..rightIndex+1]
сортируетсяТаким образом, вы можете сначала написать
is_sorted
функцию, а такжеmin
функцию, работающую со срезом массива, а затем подтвердить:Существует также тот факт, что ваше условие цикла немного сложнее; Вы можете захотеть сделать это проще для себя, разделив вещи на части:
Теперь цикл прост (
j
идет отrightIndex
к0
).Наконец, теперь это нужно проверить:
rightIndex == 0
,rightIndex == array.size - 2
)value
чтобы быть меньшеarray[0]
или больше, чемarray[rightIndex]
value
, равнымarray[0]
,array[rightIndex]
или какой - то средний индексТакже не стоит недооценивать пух . У вас есть утверждения для выявления ошибок, поэтому создайте случайный массив и отсортируйте его, используя свой метод. Если утверждение сработало, вы обнаружили ошибку и можете расширить набор тестов.
источник
0 <= j <= rightIndex
илиarray[j] <= value
, он просто повторил бы код. С другой стороны,is_sorted
приносит новую гарантию, поэтому она ценна. После этого для этого и нужны тесты. Если вы вызываетеinsert([0, 1, 2], 2, 3)
свою функцию, а результат - нет,[0, 1, 2, 3]
то вы нашли ошибку.array[j+1] = array[j]; assert(array[j+1] == array[j]);
. В этом случае значение кажется очень низким (это копирование / вставка). Если вы дублируете значение, но выражаете его по-другому, оно становится более ценным.insert()
чтобы он работал путем копирования из старого массива в новый. Это можно сделать, не нарушая другихassert
. Но не этот последний. Просто показывает, насколько хорошоassert
были разработаны ваши другие .Используйте юнит-тестирование / TDD
Если вам действительно нужен доступ к последовательностям через
for
цикл, вы можете избежать ошибок с помощью модульного тестирования , и особенно разработки, управляемой тестированием .Представьте, что вам нужно реализовать метод, который принимает значения, превосходящие ноль, в обратном порядке. Какие тестовые случаи вы могли бы подумать?
Последовательность содержит одно значение, которое больше нуля.
Фактический:
[5]
. Ожидаемый:[5]
.Самая простая реализация, которая удовлетворяет требованиям, состоит в простом возврате исходной последовательности вызывающей стороне.
Последовательность содержит два значения, оба превосходят ноль.
Фактический:
[5, 7]
. Ожидаемый:[7, 5]
.Теперь вы не можете просто вернуть последовательность, но вы должны полностью изменить ее. Будете ли вы использовать
for (;;)
цикл, другую языковую конструкцию или метод библиотеки, не имеет значения.Последовательность содержит три значения, одно из которых равно нулю.
Фактический:
[5, 0, 7]
. Ожидаемый:[7, 5]
.Теперь вы должны изменить код для фильтрации значений. Опять же, это можно выразить с помощью
if
оператора или вызова вашего любимого метода структуры.В зависимости от вашего алгоритма (так как это тестирование белого ящика, реализация имеет значение), вам может понадобиться обрабатывать
[] → []
случай с пустой последовательностью , а может и нет. Или вы можете гарантировать , что крайний случай , когда все значения отрицательны[-4, 0, -5, 0] → []
обрабатываются правильно, или даже что граничные отрицательные значения:[6, 4, -1] → [4, 6]; [-1, 6, 4] → [4, 6]
. Однако во многих случаях у вас будет только три теста, описанных выше: любой дополнительный тест не заставит вас изменить код, и поэтому не будет иметь значения.Работа на более высоком уровне абстракции
Однако во многих случаях вы можете избежать большинства этих ошибок, работая на более высоком уровне абстракции, используя существующие библиотеки / фреймворки. Эти библиотеки / фреймворки позволяют возвращать, сортировать, разбивать и объединять последовательности, вставлять или удалять значения в массивах или списках с двойной связью и т. Д.
Обычно
foreach
его можно использовать вместоfor
проверки граничных условий, что не имеет значения: язык делает это за вас. Некоторые языки, такие как Python, даже не имеютfor (;;)
конструкции, но толькоfor ... in ...
.В C # LINQ особенно удобен при работе с последовательностями.
гораздо более читабелен и менее подвержен ошибкам по сравнению с его
for
вариантом:источник
for(;;)
forEach
,map
,LazyIterator
И т.д., при условии , компилятор или среда выполнения этого языка и , возможно , менее вероятно, будет идти назад к ведру краски на каждую итерации. Это - читабельность и ошибки «по одному» - две причины, по которым эти функции были добавлены в современные языки.Я согласен с другими людьми, которые говорят, проверить свой код. Тем не менее, это также хорошо, чтобы сделать это правильно в первую очередь. Во многих случаях я склонен неправильно понимать граничные условия, поэтому я разработал умственные приемы для предотвращения подобных проблем.
С массивом с 0 индексами ваши нормальные условия будут:
или же
Эти шаблоны должны стать второй натурой, вам вообще не нужно думать о них.
Но не все следует именно этому образцу. Так что, если вы не уверены, что написали правильно, вот ваш следующий шаг:
Вставьте значения и оцените код в своем собственном мозгу. Сделайте так, чтобы о них думали как можно проще. Что произойдет, если соответствующие значения равны 0? Что произойдет, если они 1 с?
В вашем примере вы не уверены, должно ли это быть [j] = значение или [j + 1] = значение. Время начать оценивать это вручную:
Что произойдет, если у вас длина массива 0? Ответ становится очевидным: rightIndex должен быть (length - 1) == -1, поэтому j начинается с -1, поэтому для вставки с индексом 0 необходимо добавить 1.
Таким образом, мы доказали правильность конечного условия, но не внутри цикла.
Что произойдет, если у вас есть массив с 1 элементом, 10, и мы пытаемся вставить 5? С одним элементом rightIndex должно начинаться с 0. Итак, в первый раз в цикле j = 0, поэтому «0> = 0 && 10> 5». Поскольку мы хотим вставить 5 в индекс 0, 10 нужно переместить в индекс 1, поэтому array [1] = array [0]. Так как это происходит, когда j равно 0, массив [j + 1] = массив [j + 0].
Если вы попытаетесь представить какой-то большой массив и что произойдет, вставив его в произвольное место, ваш мозг, вероятно, будет перегружен. Но если вы будете придерживаться простых примеров размером 0/1/2, то будет легко сделать быстрый мысленный анализ и увидеть, где нарушаются ваши граничные условия.
Представьте, что вы никогда раньше не слышали о проблеме столба забора, и я говорю вам, что у меня 100 столбов забора по прямой линии, сколько отрезков между ними. Если вы попытаетесь представить 100 постов забора в вашей голове, вы просто ошеломлены. Так что же самое меньшее количество постов, чтобы сделать правильный забор? Вам нужно 2, чтобы сделать забор, так что представьте 2 поста, и мысленный образ одного сегмента между постами прояснит это. Вам не нужно сидеть и считать посты и сегменты, потому что вы превратили проблему в нечто интуитивно понятное для вашего мозга.
Как только вы думаете, что это правильно, тогда хорошо пройти тест и убедиться, что компьютер делает то, что вы думаете, что должно, но на этом этапе это должно быть просто формальностью.
источник
for (int i = 0; i < length; i++)
. Как только я вошел в эту привычку, я перестал использовать<=
почти так же часто, и почувствовал, что петли стали проще. Ноfor (int i = length - 1; i >= 0; i--)
кажется слишком сложным, по сравнению с:for (int i=length; i--; )
(что, вероятно, было бы еще более разумно записать в видеwhile
цикла, если бы я не пытался сделать такi
, чтобы область действия была меньше). Результат по-прежнему проходит через цикл с i == length-1 (изначально) через i == 0, с той лишь функциональной разницей, чтоwhile()
версия заканчивается на i == -1 после цикла (если он продолжается) вместо i = = 0.> 0
", чтобы получить желаемую функциональность, то такие символы следует использовать, потому что они требуются этим языком. Тем не менее, даже в этих случаях просто использовать «> 0
» проще, чем выполнить процесс, состоящий из двух частей: сначала вычесть один, а затем также использовать «>= 0
». После того, как я узнал об этом, благодаря небольшому опыту, я привык к необходимости использовать знак равенства (например, ">= 0
") в моих тестовых циклах гораздо реже, и с тех пор полученный код, как правило, чувствовал себя проще.i-- > 0
, почему бы не попробовать классическую шуткуi --> 0
,!Это очень интересный момент к этому вопросу, и он породил этот комментарий:
... и Томас прав. Отсутствие четкого намерения для функции должно быть красным флажком - явным признаком того, что вы должны немедленно ОСТАНОВИТЬСЯ, схватить карандаш и бумагу, отойти от IDE и правильно решить проблему; или, по крайней мере, рассудок - проверьте, что вы сделали.
Я видел так много функций и классов, которые превратились в полный беспорядок, потому что авторы пытались определить реализацию до того, как полностью определили проблему. И с этим так легко иметь дело.
Если вы не до конца понимаете проблему, вы также вряд ли будете кодировать оптимальное решение (с точки зрения эффективности или ясности), и при этом вы не сможете создавать действительно полезные модульные тесты в методологии TDD.
Возьмите ваш код здесь в качестве примера, он содержит ряд потенциальных недостатков, которые вы еще не рассмотрели, например: -
Есть несколько других проблем, связанных с производительностью и дизайном кода ...
SortedList<t>
в C #)?Array.Insert(...)
? этот код будет более понятным?Существует множество способов улучшить этот код, но до тех пор, пока вы правильно не определите, что вам нужно для этого кода, вы не разрабатываете код, вы просто взламываете его вместе в надежде, что он будет работать. Вложите в это время, и ваша жизнь станет легче.
источник
Одиночные ошибки - одна из самых распространенных ошибок программирования. Даже опытные разработчики иногда ошибаются. Языки более высокого уровня обычно имеют итерационные конструкции, такие как
foreach
илиmap
которые вообще избегают явной индексации. Но иногда вам нужна явная индексация, как в вашем примере.Задача состоит в том, как определить диапазон ячеек массива. Без четкой ментальной модели становится непонятным, когда включать или исключать конечные точки.
При описании диапазонов массива принято включать нижнюю границу, исключать верхнюю границу . Например, диапазон 0..3 - это ячейки 0,1,2. Это соглашение используется во всех языках с 0 индексами, например,
slice(start, end)
метод в JavaScript возвращает подмассив, начиная с индексаstart
, но не включая индексend
.Это становится понятнее, когда вы думаете об индексах диапазона как об описании границ между ячейками массива. На рисунке ниже показан массив длиной 9, а числа под ячейками выровнены по краям и используются для описания сегментов массива. Например, из иллюстрации ясно, что диапазон 2.,5 - это ячейки 2,3,4.
Эта модель согласуется с тем, чтобы длина массива была верхней границей массива. Массив длиной 5 имеет ячейки 0..5, что означает наличие пяти ячеек 0,1,2,3,4. Это также означает, что длина сегмента является верхней границей минус нижняя граница, то есть сегмент 2..5 имеет 5-2 = 3 ячейки.
Имея в виду эту модель при переборе вверх или вниз, становится намного понятнее, когда включать или исключать конечные точки. При выполнении итерации вверх вам нужно включить начальную точку, но исключить конечную точку. При выполнении итерации вниз необходимо исключить начальную точку (верхняя граница), но включить конечную точку (нижняя граница).
Поскольку в вашем коде вы выполняете итерацию вниз, вам нужно включить нижнюю границу 0, поэтому вы выполняете итерацию while
j >= 0
.Учитывая это, ваш выбор, чтобы
rightIndex
аргумент представлял последний индекс в подмассиве, нарушает соглашение. Это означает, что вы должны включить обе конечные точки (0 и rightIndex) в итерации. Это также затрудняет представление пустого сегмента (который необходим при запуске сортировки). Вы фактически должны использовать -1 как rightIndex при вставке первого значения. Это кажется довольно неестественным. Кажется более естественнымrightIndex
указывать индекс после сегмента, поэтому 0 представляет пустой сегмент.Конечно, ваш код очень запутанный, потому что он расширяет отсортированный подмассив на один, перезаписывая элемент сразу после первоначально отсортированного подмассива. Таким образом, вы читаете из индекса j, но записывает значение в j + 1. Здесь вам должно быть ясно, что j - это позиция в начальном подмассиве перед вставкой. Когда операции с индексами становятся слишком сложными, это помогает мне изобразить это на листе сетки.
источник
myArray.Length
илиmyList.Count
- которое всегда на единицу больше, чем «самый правый» индекс, начинающийся с нуля. ... Длина объяснения противоречит практическому и простому применению этих явных эвристик кодирования. TL; DR толпа отсутствует.Введение в ваш вопрос заставляет меня думать, что вы не научились правильно кодировать. Любой, кто программирует на императивном языке более нескольких недель, должен действительно правильно установить границы цикла в более чем 90% случаев. Возможно, вы спешите начать кодирование до того, как вы достаточно продумали проблему.
Я предлагаю вам исправить этот недостаток путем (пере) обучения написанию циклов - и я бы рекомендовал несколько часов проработать ряд циклов с бумагой и карандашом. Возьмите выходной, чтобы сделать это. Затем потратьте 45 минут или около того дня, работая над темой, пока вы действительно не получите ее.
Это все очень хорошо тестирует, но вы должны тестировать, ожидая, что вы, как правило, получите правильные границы цикла (и остальную часть кода).
источник
Возможно, я должен добавить немного мяса в свой комментарий:
Ваша точка зрения
Когда я читаю
trial and error
, у меня начинают звонить мои будильники. Конечно, многие из нас знают состояние ума, когда кто-то хочет решить небольшую проблему, обдумывает другие вещи и начинает так или иначе угадывать, чтобы заставить кодseem
делать то, что должен делать. Некоторые хакерские решения выходят из этого - и некоторые из них - чистый гений ; но если честно: большинство из них нет . Меня включили, зная это состояние.Независимо от вашей конкретной проблемы, вы задавали вопросы о том, как улучшить:
1) Тест
Это было сказано другими, и мне нечего добавить
2) Анализ проблем
Трудно дать какой-то совет по этому поводу. Я могу дать вам только два совета, которые, вероятно, помогут вам улучшить свои навыки в этой области:
Код Katas - это способ, который может немного помочь.
Код Ката
Один сайт, который мне очень нравится: Code Wars
Это относительно небольшие проблемы, которые помогут вам отточить свои навыки программирования. И что мне больше всего нравится в Code Wars, так это то, что вы можете сравнить свое решение с одним из других .
Или, может быть, вы должны взглянуть на Exercism.io, где вы получите обратную связь от сообщества.
Я знаю - как я уже говорил выше, иногда вы находитесь в таком состоянии - что трудно разбить «простые» вещи на более «мертвые простые» задачи; но это очень помогает.
Я помню, когда я впервые научился профессиональному программированию, у меня были огромные проблемы с отладкой кода. В чем была проблема? Hybris - Ошибка не может быть в той и другой области кода, потому что я знаю, что это не может быть. И как следствие? Я пробежался по коду вместо того, чтобы анализировать его, который мне пришлось выучить - даже если было утомительно разбивать мой код на инструкции для инструкций .
3) Разработка Toolbelt
Помимо знания вашего языка и ваших инструментов - я знаю, что это блестящие вещи, о которых разработчики думают в первую очередь, - изучение алгоритмов (чтение).
Вот две книги для начала:
Введение в алгоритмы
Алгоритмы
Это похоже на изучение некоторых рецептов, чтобы начать готовить. Сначала вы не знаете, что делать, поэтому вам нужно посмотреть, что приготовили для вас предыдущие повара . То же самое касается алгоритмов. Алгоритмы подобны приготовлению рецептов для обычных блюд (структуры данных, сортировка, хеширование и т. Д.). Если вы знаете их (по крайней мере, пытаетесь) наизусть, у вас есть хорошая отправная точка.
3a) Знать программные конструкции
Эта точка является производной - так сказать. Знайте свой язык - и лучше: знайте, какие конструкции возможны на вашем языке.
Общая точка для плохой или inefficent коды иногда, что программист не знает разницу между различными типами петель (
for-
,while-
иdo
-loops). Как-то все они взаимозаменяемы; но в некоторых случаях выбор другой циклической конструкции приводит к более элегантному коду.И есть устройство Даффа ...
PS:
Да, мы должны сделать кодирование снова великолепным!
Новый девиз для Stackoverflow.
источник
pre-post
условия до сих пор, и я ценю это.Если я правильно понял проблему, ваш вопрос заключается в том, как правильно продумать циклы с первой попытки, а не в том, чтобы убедиться, что ваш цикл верен (для чего ответ будет проверяться, как объяснено в других ответах).
Что я считаю хорошим подходом, так это написать первую итерацию без какого-либо цикла. После того, как вы это сделали, вы должны заметить, что следует менять между итерациями.
Это число, например, 0 или 1? Тогда вам, скорее всего, нужно для, и бинго, у вас также есть стартовый я. Затем подумайте, сколько раз вы хотите запустить одно и то же, и у вас также будет конечное состояние.
Если вы не знаете ТОЧНО, сколько раз он будет работать, тогда вам не понадобится время, но какое-то время.
Технически, любой цикл может быть преобразован в любой другой цикл, но код легче прочитать, если вы используете правильный цикл, поэтому вот несколько советов:
Если вы пишете if () {...; break;} внутри for, вам нужно некоторое время, и у вас уже есть условие
«Хотя», возможно, является наиболее часто используемым циклом в любом языке, но это не должно быть imo. Если вы обнаружите, что пишете bool ok = True; while (check) {сделайте что-нибудь и, надеюсь, в какой-то момент измените ok}; тогда вам не нужно время, а время, потому что это означает, что у вас есть все необходимое для запуска первой итерации.
Теперь немного контекста ... Когда я впервые научился программировать (Паскаль), я не говорил по-английски. Для меня слова «for» и «while» не имели особого смысла, но ключевое слово «repeat» (do while in C) на моем родном языке почти одинаково, поэтому я бы использовал его для всего. По моему мнению, повторить (делать пока) - это наиболее естественный цикл, потому что почти всегда вы хотите, чтобы что-то было сделано, а затем вы хотите, чтобы это было сделано снова и снова, пока не будет достигнута цель. «For» - это просто ярлык, который дает вам итератор и странно помещает условие в начало кода, даже если почти всегда вы хотите что-то сделать, пока что-то не произойдет. Кроме того, while это просто ярлык для if () {do while ()}. Ярлыки хороши на потом,
источник
Я собираюсь привести более подробный пример того, как использовать предварительные / последующие условия и инварианты для разработки правильного цикла. Вместе такие утверждения называются спецификацией или контрактом.
Я не предлагаю вам пытаться делать это для каждого цикла. Но я надеюсь, что вам будет полезно увидеть процесс мышления.
Для этого я переведу ваш метод в инструмент под названием Microsoft Dafny , который призван доказать правильность таких спецификаций. Он также проверяет завершение каждого цикла. Обратите внимание, что у Dafny нет
for
цикла, поэтому мне пришлось использоватьwhile
цикл вместо этого.Наконец, я покажу, как вы можете использовать такие спецификации для разработки, возможно, немного более простой версии вашего цикла. Эта более простая версия цикла в действительности имеет условие цикла
j > 0
и присваиваниеarray[j] = value
- как было в вашей первоначальной интуиции.Дафни докажет нам, что обе эти петли верны и делают одно и то же.
Затем я сделаю общее утверждение, основываясь на моем опыте, о том, как написать правильный обратный цикл, который, возможно, поможет вам, если вы столкнетесь с этой ситуацией в будущем.
Часть первая - Написание спецификации для метода
Первая проблема, с которой мы сталкиваемся, - это определение того, что метод должен делать. Для этого я разработал предварительные и последующие условия, которые определяют поведение метода. Чтобы сделать спецификацию более точной, я усовершенствовал метод, чтобы он возвращал индекс, в который
value
был вставлен.Эта спецификация полностью отражает поведение метода. Мое основное замечание по поводу этой спецификации состоит в том, что она будет упрощена, если процедуре будет передано значение,
rightIndex+1
а неrightIndex
. Но так как я не могу понять, откуда вызывается этот метод, я не знаю, какое влияние это изменение окажет на остальную часть программы.Часть вторая - определение инварианта цикла
Теперь у нас есть спецификация для поведения метода, мы должны добавить спецификацию поведения цикла, которая убедит Дафни, что выполнение цикла завершится и приведет к желаемому конечному состоянию
array
.Ниже приведен исходный цикл, переведенный в синтаксис Dafny с добавленными инвариантами цикла. Я также изменил его, чтобы он возвращал индекс, в который было вставлено значение.
Это подтверждается в Дафни. Вы можете увидеть это сами, перейдя по этой ссылке . Таким образом, ваш цикл правильно реализует спецификацию метода, которую я написал в первой части. Вам нужно будет решить, действительно ли эта спецификация метода соответствует желаемому.
Обратите внимание, что Дафни дает здесь подтверждение правильности. Это гораздо более надежная гарантия правильности, чем может быть получена путем тестирования.
Часть третья - более простая петля
Теперь, когда у нас есть спецификация метода, которая фиксирует поведение цикла. Мы можем безопасно изменить реализацию цикла, сохраняя при этом уверенность в том, что мы не изменили поведение цикла.
Я изменил цикл так, чтобы он соответствовал вашей первоначальной интуиции относительно условия цикла и конечного значения
j
. Я бы сказал, что этот цикл проще, чем тот, который вы описали в своем вопросе. Это чаще можно использоватьj
, чемj+1
.Начать с j
rightIndex+1
Измените условие цикла на
j > 0 && arr[j-1] > value
Измените назначение на
arr[j] := value
Уменьшите счетчик цикла в конце цикла, а не в начале
Вот код Обратите внимание, что инварианты цикла также несколько проще написать:
Часть четвертая - совет по обратной петле
После того, как я написал и подтвердил правильность многих циклов в течение нескольких лет, у меня есть следующий общий совет о циклическом обратном цикле.
Почти всегда легче думать и писать обратный (убывающий) цикл, если декремент выполняется в начале цикла, а не в конце.
К сожалению,
for
конструкция цикла во многих языках делает это трудным.Я подозреваю (но не могу доказать), что эта сложность - то, что вызвало разницу в вашей интуиции о том, каким должен быть цикл и каким он должен быть на самом деле. Вы привыкли думать о прямых (инкрементных) циклах. Когда вы хотите написать обратный (убывающий) цикл, вы пытаетесь создать цикл, пытаясь изменить порядок, в котором все происходит в прямом (увеличивающемся) цикле. Но из-за того, как
for
работает конструкция, вы забыли изменить порядок присваивания и обновления переменной цикла - что необходимо для истинного изменения порядка операций между обратным и прямым циклами.Часть пятая - бонус
Просто для полноты, вот код, который вы получите, если перейдете
rightIndex+1
к методу, а неrightIndex
. Это изменение устраняет все+2
смещения, которые в противном случае необходимы, чтобы думать о правильности цикла.источник
Понимание этого легко и свободно - вопрос опыта. Несмотря на то, что язык не позволяет вам выразить это напрямую, или вы используете более сложный случай, чем простое встроенное средство , с которым вы можете справиться, вы думаете, что это более высокий уровень, такой как «посещать каждый элемент в почтенном порядке» и более опытный кодер мгновенно переводит это в нужные детали, потому что он делал это много раз.
Даже тогда, в более сложных случаях легко ошибиться, потому что то, что вы пишете, обычно не является обычным делом. С более современными языками и библиотеками вы не пишете легкую вещь, потому что есть консервированная конструкция или вызов для этого. В C ++ современная мантра гласит: «используйте алгоритмы, а не пишите код».
Таким образом, способ убедиться, что это правильно, особенно для такого рода вещей, это посмотреть на граничные условия . Проследите код в вашей голове для нескольких случаев на краю того, где все меняется. Если
index == array-max
, что происходит? Как насчетmax-1
? Если код делает неправильный поворот, он будет на одной из этих границ. Некоторые циклы должны беспокоиться о первом или последнем элементе, а также о том, что конструкция цикла получает правильные границы; например, если вы ссылаетесьa[I]
иa[I-1]
что происходит, когдаI
минимальное значение?Кроме того, посмотрите на случаи, когда количество (правильных) итераций является предельным: если границы встречаются, и у вас будет 0 итераций, будет ли это работать без особого случая? А как насчет 1 итерации, где самая низкая граница одновременно является самой высокой?
Изучение вариантов ребер (обе стороны каждого ребра) - это то, что вы должны делать при написании цикла, и что вы должны делать в обзорах кода.
источник
Я постараюсь держаться подальше от уже упомянутых тем.
инструменты
Для меня самый большой инструмент для написания лучше
for
иwhile
циклов - это вообще не писать ни циклов,for
ниwhile
циклов.Большинство современных языков так или иначе пытаются решить эту проблему. Например, Java
Iterator
с самого начала, которая была немного неуклюжей в использовании, ввела сокращенный синтаксис, чтобы упростить их использование в более поздней версии. В C # они есть и так далее.Мой любимый в настоящее время язык Ruby полностью использует функциональный подход (
.each
и.map
т. Д.). Это очень сильно. Я только что быстро подсчитал в какой-то кодовой базе Ruby, над которой я работаю: примерно в 10.000 строк кода - нольfor
и около 5while
.Если бы я был вынужден выбрать новый язык, поиск таких функциональных / основанных на данных циклов был бы очень высок в списке приоритетов.
Ментальные модели
Имейте в виду, что
while
это минимальный уровень абстракции, который вы можете получить, всего лишь на шаг вышеgoto
. На мой взгляд,for
это делает его еще хуже, а не лучше, поскольку он плотно объединяет все три части цикла.Так что, если я нахожусь в среде, где
for
используется, то я чертовски уверен, что все 3 части абсолютно просты и всегда одинаковы. Это значит я напишуНо ничего сложнее. Может быть, может быть, иногда у меня будет обратный отсчет, но я сделаю все возможное, чтобы избежать его.
При использовании
while
я остаюсь в стороне от извилистых внутренних феноменов, связанных с состоянием петли. Тест внутриwhile(...)
будет максимально простым, и я буду старатьсяbreak
изо всех сил . Также цикл будет коротким (считая строки кода), и любые большие объемы кода будут учтены.Особенно, если фактическое условие while является сложным, я буду использовать «переменную условия», которую очень легко обнаружить, а не помещать условие в сам
while
оператор:(Или что-то в этом роде, в правильной мере, конечно.)
Это дает вам очень простую ментальную модель, которая гласит: «эта переменная работает от 0 до 10 монотонно» или «этот цикл работает до тех пор, пока эта переменная не станет ложной / истинной». Кажется, что большинство мозгов справляются с этим уровнем абстракции просто отлично.
Надеюсь, это поможет.
источник
В частности, обратные циклы, в частности, трудно рассуждать, потому что многие из наших языков программирования смещены в сторону прямой итерации, как в обычном синтаксисе цикла for, так и с использованием полуоткрытых интервалов, начинающихся с нуля. Я не говорю, что это неправильно, что языки сделали такой выбор; Я просто говорю, что этот выбор усложняет размышления об обратных циклах.
В общем, помните, что цикл for - это просто синтаксический сахар, построенный вокруг цикла while:
эквивалентно:
(возможно, с дополнительным уровнем области видимости для хранения переменных, объявленных на этапе инициализации локально по отношению к циклу).
Это хорошо для многих видов петель, но если шаг идет последним, то неловко, когда вы идете назад. Работая в обратном направлении, я обнаружил, что легче запустить индекс цикла со значением после того, что я хочу, и переместить
step
часть в верхнюю часть цикла, например так:или, как для цикла:
Это может показаться нервирующим, поскольку выражение шага находится в теле, а не в заголовке. Это неприятный побочный эффект прямого смещения в синтаксисе цикла for. Из-за этого некоторые будут утверждать, что вы вместо этого делаете это:
Но это катастрофа, если ваша индексная переменная имеет тип без знака (как это может быть в C или C ++).
Имея это в виду, давайте напишем вашу функцию вставки.
Поскольку мы будем работать в обратном направлении, мы позволим индексу цикла быть записью после «текущего» слота массива. Я бы разработал функцию, которая будет принимать размер целого числа, а не индекса для последнего элемента, потому что полуоткрытые диапазоны - это естественный способ представления диапазонов в большинстве языков программирования, и потому что это дает нам возможность представлять пустой массив, не прибегая к до магического значения, как -1.
Хотя новое значение меньше, чем предыдущий элемент, продолжайте смещаться. Конечно, предыдущий элемент может быть проверено только при наличии в предыдущий элемент, таким образом , мы должны сначала проверить , что мы не в самом начале:
Это оставляет
j
там, где мы хотим новое значение.«Программирование жемчуга » Джона Бентли дает очень четкое объяснение сортировки вставок (и других алгоритмов), которые могут помочь построить ваши ментальные модели для подобных проблем.
источник
Вы просто не понимаете, что на
for
самом деле делает цикл и как он работает?Возможно, вам будет полезно переписать этот код, используя другую конструкцию. Вот то же самое, используя цикл while:
Вот некоторые другие предложения:
for
петлями. Вы будете использовать их все время. Я предлагаю вам пройти через цикл for в отладчике, чтобы посмотреть, как он выполняется.* Обратите внимание, что хотя я использую термин «приращение», это просто некоторый код, который идет после тела и перед проверкой условия. Это может быть уменьшение или вообще ничего.
источник
Попытка дополнительного понимания
Для нетривиальных алгоритмов с циклами вы можете попробовать следующий метод:
i
илиj
, и увеличивайте / уменьшайте эти переменные по мере необходимости (но все еще без какого-либо цикла);Твоя проблема
Напишите тело цикла вручную несколько раз
Давайте использовать фиксированный массив с 4 позициями и попробуем написать алгоритм вручную, без циклов:
Переписать, удалив жестко закодированные значения
Перевести на цикл
С
while
:Рефакторинг / переписать / оптимизировать цикл так, как вы хотите:
С
while
:с
for
:PS: код предполагает, что ввод действителен, и этот массив не содержит повторений;
источник
Вот почему я бы по возможности избегал написания циклов, которые работают с необработанными индексами, в пользу более абстрактных операций.
В этом случае я бы сделал что-то вроде этого (в псевдокоде):
источник
В вашем примере тело цикла вполне очевидно. И совершенно очевидно, что какой-то элемент должен быть изменен в самом конце. Таким образом, вы пишете код, но без начала цикла, условия конца и окончательного назначения.
Затем вы уходите от кода и выясняете, какой первый шаг необходимо выполнить. Вы изменяете начало цикла так, чтобы первый ход был правильным. Вы снова уходите от кода и выясняете, какой последний шаг нужно выполнить. Вы изменяете конечное условие так, чтобы последний ход был правильным. И, наконец, вы уходите от своего кода и выясняете, каким должно быть окончательное назначение, и соответственно исправляете код.
источник