Быстрое среднее число без подразделения
Выведенные по типу константы могут быть только скалярными значениями, то есть такими вещами, как целые числа, числа с двойными числами и т. Д. Для этих типов констант компилятор действительно заменяет символ константы значением константы всякий раз, когда он встречает их в выражениях.
Типизированные константы, с другой стороны, могут быть структурированными значениями - массивами и записями. Этим ребятам нужно фактическое хранилище в исполняемом файле, то есть им нужно выделить для них хранилище, чтобы при загрузке ОС ОС значение типизированной константы физически находилось в некотором месте в памяти.
Чтобы объяснить, почему, исторически, типизированные константы в раннем Delphi и его предшественнике, Turbo Pascal, доступны для записи (и, таким образом, по сути инициализировали глобальные переменные), нам нужно вернуться к временам DOS.
DOS работает в реальном режиме в терминах x86. Это означает, что программы имеют прямой доступ к физической памяти без какого-либо MMU , выполняющего виртуально-физические отображения. Когда программы имеют прямой доступ к памяти, защита памяти не действует. Другими словами, если по какому-либо адресу есть память, она доступна как для чтения, так и для записи в реальном режиме.
Таким образом, в программе Turbo Pascal для DOS с типизированной константой, значение которой распределяется по адресу в памяти во время выполнения, эта типизированная константа будет доступна для записи. Нет никакого аппаратного MMU, мешающего и мешающего программе записать в него. Точно так же, поскольку Паскаль не имеет понятия «константности», которое есть в C ++, в системе типов нет ничего, что могло бы вас остановить. Многие люди воспользовались этим, поскольку Turbo Pascal и Delphi в то время еще не инициализировали глобальные переменные как функцию.
Переходя к Windows, существует слой между адресами памяти и физическими адресами: блок управления памятью. Этот чип берет индекс страницы (сдвинутую маску) адреса памяти, к которому вы пытаетесь обратиться, и ищет атрибуты этой страницы в своей таблице страниц . Эти атрибуты включают в себя читаемые, записываемые и для современных чипов x86 неисполняемые флаги. Благодаря этой поддержке можно помечать разделы .EXE или .DLL такими атрибутами, чтобы при загрузке Windows загрузчик выполнил образ в память, он назначал соответствующие атрибуты страниц для страниц памяти, которые отображаются на страницы дисков в этих разделах.
Когда появилась 32-битная версия компилятора Delphi для Windows, имело смысл сделать const-подобные вещи действительно const, поскольку ОС также имеет эту функцию.
4 ответа
int mid = (low + high) >>> 1;
Имейте в виду, что использование "(low + high) / 2" для вычислений средней точки не будет работать правильно , когда целочисленное переполнение становится проблемой.
Вы можете использовать сдвиг битов, а также преодолеть возможную проблему переполнения:
low + ((high-low) >> 1)
Однако я должен признать, что ожидаю, что современные компиляторы и интерпретаторы будут выполнять деление на 2 (или деление на любую другую постоянную степень 2) как сдвиг битов, поэтому не уверен, что это действительно поможет - попробуйте.
Вот битовая версия среднего, не страдающая от проблемы переполнения:
unsigned int average (unsigned int x, unsigned int y)
{
return (x&y)+((x^y)>>1);
}
Если я правильно помню, в некоторых случаях использование точной середины массива может быть медленнее. Решение состоит в том, чтобы рандомизировать выбор индекса, по которому вы делите массив пополам. То же верно и для алгоритма определения медианы массива.
Я не могу вспомнить точных деталей, но я помню, как слышал лекцию 6 из серии алгоритмов MIT на iTunes.