В свое время много вопросов вызвала дискуссия: надо ли проверять массив на упорядоченность (предусловие) при бинарном поиске. Надо? :)
Поразмышляю на эту тему ;)
Начну с того, что еще раз обращу внимание на то, что в теории никто не говорит о том, что в действительности надо делать с предусловием, постусловием и инвариантами. Они есть и все ;)
Теперь обратимся к разуму :) На сколько мне известно, бинарный поиск имеет сложность Q(log(n)) (по умолчанию у программистов логарифм двоичный ;), а вот проверка массива на упорядоченность, по всей видимости, Q(n) (по крайней мере я не знаю способа сделать это быстрее ;) Т.е. получается, что сама по себе проверка сводит на нет все преимущества бинарного поиска... К тому же, стоит сказать, что выигрыш в бинарном поиске обычно происходит при неоднократном обращении (имеется в виду, что если нам надо найти элемент в не упорядоченном массиве один раз, то лучше просто пройтись по нему, чем отсортировать его, а потом искать в нем бинарным поиском). При рассмотрении проблемы с этого ракурса, кажется логичным не включать проверку массива на упорядоченность в бинарный поиск ;)
Теперь стоит ответить на вопрос - что же тогда делать с наши предусловием? Оно же имеет место быть (по логике вещей). На самом деле, скорее всего это тот класс (имеется в виду не класс в программировании, а... социальный класс ;) предусловий, который может использовать в своей работе разработчик. Т.е. другими словами, у программиста есть метод бинарного поиска, который ему необходимо реализовать, причем при этом ему сказано - "не заморачивайся по поводу не упорядоченности элементов в массиве". Такие предусловия не должны попадать в код в виде непосредственных проверок. В принципе, можно сделать их автоматическое добавление в xml документацию ;)
Ну и напоследок, рассмотрим несколько примеров предусловий для бинарного поиска, которые можно было бы и включить в код.
Итак, начнем с упорядоченности элементов в массиве. Вроде мы можем быть абсолютно уверены в том, что элементы в массиве упорядочены, но не совсем ;) Ведь нам еще важно - в каком направлении они упорядочены :) Так что проверяем, что, первый элемент <= последнему. В принципе, от данной проверки можно отказаться, если написать такой бинарный поиск, который просто анализирует, в каком направлении отсортирован массив. Вторая проверка больше подойдет для Generic коллекций. Если я ничего не путаю, то, скорее всего, в алгоритме бинарного поиска придется что то сравнивать ;) А это означает, что элементы массива должны реализовывать интерфейс IComparable (ну если мы говорим про .NET ;).
Кстати говоря, наверное еще желательно, что бы все элементы были одного типа (точнее говоря приводились к типу, который мы ищем). Но это уже попахивает очередной проверкой всех элементов ;)
Ну вот на этом я, пожалуй, и закончу ;)
Теперь обратимся к разуму :) На сколько мне известно, бинарный поиск имеет сложность Q(log(n)) (по умолчанию у программистов логарифм двоичный ;), а вот проверка массива на упорядоченность, по всей видимости, Q(n) (по крайней мере я не знаю способа сделать это быстрее ;) Т.е. получается, что сама по себе проверка сводит на нет все преимущества бинарного поиска... К тому же, стоит сказать, что выигрыш в бинарном поиске обычно происходит при неоднократном обращении (имеется в виду, что если нам надо найти элемент в не упорядоченном массиве один раз, то лучше просто пройтись по нему, чем отсортировать его, а потом искать в нем бинарным поиском). При рассмотрении проблемы с этого ракурса, кажется логичным не включать проверку массива на упорядоченность в бинарный поиск ;)
Теперь стоит ответить на вопрос - что же тогда делать с наши предусловием? Оно же имеет место быть (по логике вещей). На самом деле, скорее всего это тот класс (имеется в виду не класс в программировании, а... социальный класс ;) предусловий, который может использовать в своей работе разработчик. Т.е. другими словами, у программиста есть метод бинарного поиска, который ему необходимо реализовать, причем при этом ему сказано - "не заморачивайся по поводу не упорядоченности элементов в массиве". Такие предусловия не должны попадать в код в виде непосредственных проверок. В принципе, можно сделать их автоматическое добавление в xml документацию ;)
Ну и напоследок, рассмотрим несколько примеров предусловий для бинарного поиска, которые можно было бы и включить в код.
Итак, начнем с упорядоченности элементов в массиве. Вроде мы можем быть абсолютно уверены в том, что элементы в массиве упорядочены, но не совсем ;) Ведь нам еще важно - в каком направлении они упорядочены :) Так что проверяем, что, первый элемент <= последнему. В принципе, от данной проверки можно отказаться, если написать такой бинарный поиск, который просто анализирует, в каком направлении отсортирован массив. Вторая проверка больше подойдет для Generic коллекций. Если я ничего не путаю, то, скорее всего, в алгоритме бинарного поиска придется что то сравнивать ;) А это означает, что элементы массива должны реализовывать интерфейс IComparable (ну если мы говорим про .NET ;).
Кстати говоря, наверное еще желательно, что бы все элементы были одного типа (точнее говоря приводились к типу, который мы ищем). Но это уже попахивает очередной проверкой всех элементов ;)
Ну вот на этом я, пожалуй, и закончу ;)
В принципе тема раскрыта, только проблема в том, что 90% ошибок при бинарном поиске появляются, когда массив неотсортирован. ;)
ОтветитьУдалитьА вот представляешь - есть описание предусловия, что массив должен быть отсортирован, и это предусловие проверяется во время компиляции (а не во время работы приложения). Вот это я понимаю - проектирование по контракту ;)
ОтветитьУдалить