Дж.Бентли "Жемчужины программирования" 2-е изд. - СПб.: Питер, 2002.
ISBN 5-318-00715-5

Автор замечаний к данному изданию - Аркадий Белоусов.
Его работы вы можете найти на alglib.dore.ru.
Они будут интересны для начинающих в области низкоуровнего
кодирования.

----------------------
- стр.29, задача 1: "если оперативная память ограничена парой сотен
килобайт"; стр.31: "лишь несколько сот байт оперативной памяти".

- стр.31: "Однако поле применения двоичного поиска не ограничивается быстрым
поиском в отсортированных массивах. Рой Вейл применил этот метод для
нахождения некорректной строки во входном файле, содержащем более 1000
строк. ... узнать о её наличии можно было, лишь обработав файл некоей
программой и получив некорректный ответ ... Попробуйте догадаться, как
удалось Вейлу найти ошибку за десять попыток?" - как тут применим
двоичный поиск?

- стр.34: "22 (!)" - должно быть "22!" (см. примечание на стр.104 про O(n!)).

- стр.242, задача 2: у меня подозрение, что здесь выпало решение - идут
ссылки на первый и другие варианты, но собственно решения нет.

- стр.243: "x[0..p-i]" - должно быть "x[0..p-i-1]".

- стр.36: о каких "временных файлах" идёт в задаче 4? Также, не понятно,
с чего говорится про двукратнаю разницу обмена и реверсирования. Алгоритм
реверсирования каждый элемент читает/пишет дважды, а алгоритм обмена это
делает однократно только в случае сдвига на n/2. Иначе количество обменов
больше: `br' меняется с `a', а потом он же меняется с `bl'. В случае
сдвига на единицу количество обменов растёт почти до 2n, хотя в среднем
это значение меньше. Как верно отметил сам Бентли, здесь та же
характеристика, что и у вычитательного (евклидовского) алгоритма НОД.

- стр.39, листинг 3.2: linenum следует переименовать в notstart, "linenum>0"
заменить на "notstart" и "linenum++" на "notstart=1", в противном случае
при количестве строк большем разрядности int (например, на 16-битной
платформе) в какой-то момент linenum опять станет равной 0.

* стр.58: "cantbe(m, n)" - должно быть "cantbe(m, n-1)".

- стр.61, задача 1: предлагается удостовериться, что программа не содержит
ошибок времени исполнения, но они там есть - в функции двоичного поиска
середина вычисляется как (l+u)/2, но это выражение даст переполнение
когда позиции искомого элемента > max(n)/2. Выражение, не подверженное
этой болезни - l+(u-l)/2 (ограничение: u должно быть >= l).

- стр.62, задача 5: не сказано, что предложенное рекуррентное соотношение
является функцией Аккермана.

- стр.62, задача 7: "y[i]+1" - должно быть "y[i+1]".

- стр.63, задача 9: "итеративная версия [вычисления n-й степени числа за
логарифмическое время] достаточно сложна" - это далеко не так.

- стр.71: "n=1..100 позволяет проверить случай с пустым массивом" - должно
быть "n=0..100".

- стр.72: ticks, а не clicks; умножить на 1e9, а не разделить; "344,5
наносекунд", а не "тиков".

- стр.72: "_Полное_ время выполнения _всех_ тестов" - должно быть "Среднее
время выполнения каждого теста".

- стр.90-91: "5000 дней" в таблицах (четыре раза) - должно быть "5000 год".

- стр.91: "Увеличение n на 1 увеличивает время выполнения на 12%" - с чего
увеличение на 1 должно увеличивать на 12% (в 1.12 раз)?

- стр.97: "Illiteracy and Ins Consequences" - наверное, "Its"?

- стр.102: "for(i = m; i >= l; i--)" - при беззнаковом i и l=0 будет ошибка.

- стр.105, рис.8.2: обратный порядок наименований (снизу вверх должны идти
"наносекунда", "микросекунда" и т.д., а не наоборот).

- стр.111: "В решении 2.3 ... содержащий ... % n" - нет там модуля, там уже
оператор if вместо модуля.

- стр.113: "Мы полагаем, что массив уже выделен, поэтому имеется возможность
временно затереть значение x[n]" - нужно не предполагать, а знать. Факт:
в тестовой программе search.c (где n идёт после x) при указании n=MAXN
второй и третий варианты последовательного поиска работают неправильно.

- стр.117: "Она учитывает возможность автоматической оптимизации,
обеспечиваемой при компиляции" - каким образом ручная оптимизация
(убирание лишних переменных и вынос общих операторов "за скобки")
учитывает "автоматическую оптимизацию"?

- стр.121, задача 10: "кэширование" - должно быть "хэширование".

- стр.253, задача 12: "i >= 0; i--" в заголовке цикла - то же замечание,
что и по стр.102. Так эта проблема обходится (без потери эффективности):

i = n;
while (i > 0) {
i--;
...

- стр.126: "используется массив из 200 указателей и 200 записей, каждая из
которых содержит целое и два указателя... указатели займут 800 байт" -
записей 2000, в них по 2 целых и 1 указателю; указатели займут 8000 байт
(4 байта*2000 записей). Либо следует сказать так: "массив из 200 указателей
(... займут 800 байт) и 2000 записей, каждая из которых содержит...".

- стр.126: "стрелки указывают на те элементы, индексы которых хранятся в
нижнем массиве" - не нижнем массиве (нижний - firstincol), а "в массиве
row". "Точки в столбце i" - должно быть либо "Номера строк и номера самих
точек из столбца i", либо "Точки из столбца i описываются в массивах...".

- стр.127: "в 1-байтовых беззнаковых целых (_char_)" - должно быть
"unsigned char".

- стр.127: "объём памяти до 6400 байт" - должно быть 6402=(2+1)*2000+2*201.

- стр.127: "Можно и вовсе избавиться от массива row, помещая соответствующую
координату точки в _её запись_ [должно быть в "структуру данных точки"]
... Это уменьшает занимаемый объём до 4400 байт" - перенос номеров строк
из отдельного массива в структуры занимаемой памяти не уменьшает. "могли
бы добавить в структуру данных точки обе её координаты и достигли бы
максимального уменьшения объёма" - опять же, общий "объём" не уменьшится,
а поиск усложнится, поэтому эти формулировки как минимум сбивают с толку.

- стр.127: "Даже если не добавлять в структуру точки эти поля, объём памяти
структуры можно уменьшить до 4000 байт" - должно быть "объём памяти
_индексирующей_ структуры".

- стр.127: "нет необходимости в массиве row, если есть массив col, потому
что к последнему мы обращаемся только через массив firstincol" - фраза
не понятна и к тоиу же массив col нигде не описан, не считая его
упоминания также на стр.129.

- стр.135, задача 5: "на каждый из элементов приходилось несколько битов
(_одна десятичная цифра_"; стр.253, решение: "функция позволяла получить
ответ приближённо, а недостающая точность достигалась прибавлением _одной
десятичной цифры, бравшейся из массива_" - где здесь сокращение памяти?

- стр.146: "более робастные" - использование малораспространённых терминов
ухудшает качество (читабельность, понимаемость) текста. Возможно, здесь
лучше использовать (вместо или вместе) слова типа "надёжные", "сильные".

* стр.148: "if u-l > cutoff" - должно быть "if u-l < cutoff".

- стр.149: "Функция qsort состоит из 15 строк быстрой сортировки и 5 строк
сортировки вставкой" - это описание qsort4 (а не сишной qsort).

- стр.150: "при получении статистических данных (минимум, максимум, среднее,
медиана и мода распределения)" - я знаю первые три функции и догадываюсь,
что такое "медиана" (либо половина суммы минимума и максимума, либо
средний элемент последовательности после сортировки); но что такое "мода
распределения"?

- стр.151: "стабильность (элементы с одинаковыми ключами должны оставаться в
исходном порядке" - в переводах Кнута и Вирта использовано слово
"устойчивость".

- стр.155: "вероятность ... становится нулевой, как только m чисел уже
набрано" - не "m", а "n"; не "нулевой", а "бесконечной"; больше набрать
нельзя не из-за вероятности, а потому-что не из чего будет выбирать.

- стр.156: "В этом алгоритме нет выделенных элементов" - это как?

- стр.157: "метод ... уменьшает время выполнения до O(m log m). ... К
сожалению, этот метод работает за время O(n)" - противоречие.

* стр.157: "Предположим, что n=10_000_000, а m=2^31" - перепутаны n и m.

- стр.256, задача 2: "m целых ... затем вернуть i, i+1, ... при
необходимости округляя их к нулю" - как можно "округлять" целые? И
возвращать нужно не "i, i+1 ...", а "i%n, (i+1)%n ...".

- стр.236, задача 12.4: "задача сборщика билетов" - на стр.257 использовано
название "задача коллекционера".

* стр.257, задача 7: нужно убрать "или выводить значение n+1-i, а не само i".

- стр.160, задача 11: "карты с ... точками, под которыми ... числа" -
наверное, лучше не "точки", а "позиции"?

- стр.169: "BITSPERWORD = 32" - это называется "плохой, непортабельный
стиль". Характеристики типа надо не предполагать, а вычислять. И хотя
C/C++ для этого неудобны, однако там есть заголовок limits.h и следует
использовать выражение "sizeof(int)*CHAR_BIT".

- стр.169: "1 + hi/BITSPERWORD" - опять неточное выражение (в случае hi
кратного BITSPERWORD это выражение на единицу больше точного). Должно
быть: "(hi+BITSPERWORD-1)/BITSPERWORD".

- стр.171: "1 + maxval/bins" - опять неточное выражение.

- стр.171: "Таблица 8.2" - должно быть "13.2".

- стр.173, задача 5: "решении задачи 9" - должно быть "2".

- стр.177: "Кучи" - heapsort обычно переводится как "пирамидальная
сортировка" и heap здесь - это пирамида, а не куча. Аналогично дальше -
"свойство формы" звучит несколько необычно.

- стр.179: "Избежать проблем в языке C проще всего, объявив массив x[n+1] и
забыв о нулевом элементе" - проблем нет и без потери места. Вот как
должны выглядеть при этом индексы:

root = 1-1 = 0
left(i) = 2*(i+1)-1 = 2*i+1
right(i) = 2*(i+1)+1-1 = 2*i+2 = 2*(i+1)
parent(i) = (i+1)/2-1 = (i-1)/2

- стр.184: "с помощью двоичного поиска за время O(n)" - наверное, O(log n)?
Также в этом абзаце неясно, о каком типе структур речь, но "двоичный
поиск" и "перемещение элементов", наверное, означают "упорядоченную
последовательность" (см. предыдущий абзац на предыдущей странице)?

- стр.185: "Функции insert и extractmin на куче ... за время O(n)" -
наверное, O(log n)?

- стр.186: "упорядоченную последовательность элементов, увеличивающуюся
слева направо" - слева направо последовательность будет _отсортирована_, а
_увеличивается_ она справа налево.

- стр.188: "Свойства формы и порядка ... форму инварианта - они являются
инвариантными свойствами" - это была попытка поиграть словами?

- стр.189, задача 2: "за время O(n)" - наверное, O(n log n)? [Должен ли я
напоминать о существовании доказательство того, что алгоритмы на базе
сравнений не могут быть лучше O(n log n)?]

- стр.261, задача 2: "maxheap()" - наверное, "heap()"? "строит кучу за
время O(n)" - наверное, O(n log n)?

- стр.192, табл.15.1: "unto", "thou" - в Библии используются такие "слова"
или где-то более длинные слова оказались обрезаны до четырёх знаков?

- стр.200: "добавим к нему k символов \0" - достаточно только 1 символ \0,
особенно с отдельной функцией skip() (см. ниже).

- стр.200: перепутаны word[6] и word[7] на рисунке.

- стр.201, листинг 15.11: "выбираем одну, на которую указывает p" - должно
быть "выбираем одну и запоминаем её адрес в p" (в первом варианте можно
решить, будто выбор происходит на основании значения p).

- стр.201, листинг 15.12: нигде не описана функция skip().

- стр.204, задача 9: "даны два _текста_" - должно быть "строки" (см. также
решение на стр.264).

- стр.264, задача 9: "при сканировании массива используйте исключающее ИЛИ"
- каким образом? "строка начинается до границы раздела" - какого раздела?

- стр.264, задача 14: "n-" - должно быть "n--".

* стр.264, задача 14: пропущено имя "p" в заголовке "hash(char *)".

- стр.212: "Схема алгоритма слияния набросана в задаче 14.4.4" - должно быть
"14.4.г".

- стр.214: "значения счётчика программы (задача 10.8)" - должно быть "10.7".

- стр.214: "В разделе 8.1 показано уменьшение времени выполнения программы
за счёт помещения ... в кэш" - в этом разделе про кэш ничего не говорится.

- стр.215: "В задаче 2.8 описана проблема выбора k-го минимума" - в этой
задаче не описана эта проблема.

- стр.215: "упоминаются в задачах ... 14.4.3" - должно быть "14.4.в".

- стр.215: "схема инициализации разреженных векторов ... применяется в
разделе 11.3" - этот раздел посвящён только qsort.

- стр.216: "В задаче 3.7 показана схема алгоритма оценки линейных
рекуррентных соотношенией" - нет там такого.

- стр.216: "в задачах 11.1 и 14.4.b" - должно быть "14.4.б".

- стр.217: "длина в ... милях", "вес ... в фунтах", "длина ... в футах" -
вообще-то мы живём в России и (обобщая) в Европе, в которых (не считая
старожилов Британии) принята метрическая система. Впрочем, в Америке она
тоже принята, хотя из-за... не будем уточнять чего амерканцев и не
заменила ещё имперскую систему. Я хочу сказать, что если в беллетристике
ещё допустимо использование авторских единиц в качестве экзотики и
колорита, что обычно не сильно влияет на художественную ценность
произвдения (хотя и жутко раздражает, что я не могу с ходу понять, что
скрывается за той или иной количественной харакеристикой персонажа или
объекта), то для технической литературы это обычно не допустимо. Не говоря
уже о неоднозначности: мили бывают разные, имперские и американские
единицы тоже отличаются... Позор.

- стр.220: "int thisp = (int)p" - должно быть "(ptrdiff_t)p" или хотя бы
"(long)p".

- стр.220: "с именем структуры в качестве первого аргумента и тем же именем
в кавычках" - во-первых, для этого достаточно использовать первый аргумент
с префиксом #, во-вторых, этот префикс уже использован в timemod.c.

- стр.221: "fi = i" - во-первых, эта инструкция должна быть частью только
тех инструкций, которые пользуются переменной fi; во-вторых, в этом коде
не выполняется "выравнивания" на границу тика перед началом теста, поэтому
измерение в M(op) с тем большей погрешностью, чем больше значение trials.

- стр.224: "В решении 10.6 сдвиг и логические операции заменены обращением к
таблице" - всё наоборот. Точнее, там арифметические операции заменены
обращением к таблице, которое уже заменено логическими операциями.

- стр.225: "В главе 13 маркеры применяются" - нет их там.

- стр.225: "В решении 14.4 маркер ставится" - должно быть "14.1".

- стр.225: "Дорогостояющую логическую операцию можно заменить на
эквивалентную её алгебраическую, которая будет вычисляться быстрее" -
полная "дичь". Всё наоборот - если сложение и вычитание ещё сравнимы с со
_всеми_ логическими операциями, то уж умножение и деление намного хуже. И
если на старых процессорах сдвиг на значение больше единицы был не самой
быстрой операцией, то уж во всяком случае быстрее умножений и делений.

- стр.226: "В решении 9.6 приведена схема проверок, порядок которых может
быть изменён" - там _нет_ схем проверок, порядок которых можно менять.

- стр.226: "В решении 9.6 описана реализация ... функции" - должно быть
"функций", во множественном числе.

- стр.231: см. моё замечание про BITSPERWORD на стр.169.

- стр.232: "// CHECK !" - похоже, забыли убрать служебную информацию.

Про звёздочки и палочки.
Я на 100% не уверен.
Но по-моему знаком "-" Аркадий пометил ошибки,
которые отрыл сам, а знаком "*" те которые уже
опубликованны на оригинальном (не нашего издания) сайте
книги. http://netlib.bell-labs.com/cm/cs/pearls/errata.html
Эти ошибки имееют тем не менее ценность и в данном
топике, поскольку страницы оригинального издания и русского
не совпадают. У Аркадия поставлены страницы где эти ошибки
встречаются именно в русском издании.

стр. 235
Глава 8
...
7. Сложение с плавающей точкой не всегда коммутативно.

Должно быть ... не всегда ассоциативно.

стр. 23. Постановка задачки по сортировке файла.
Цитата:

Если мы отведём под каждое число 7 байт,
в доступном мегабайте оперативной памяти поместится 143000 номеров.

Комментарий:
поместится на самом деле полными 149796 номеров.
далее цитата:

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

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