Я получил от Кнута чек на 0x$3,00

[TimsTims]

А может вы сами укажете автору найденные ошибки (тем более это проще простого через ctrl+enter), а автор вам тоже несколько шестнадцатеричных долларов вышлет?

[saloid]

Слово sometime тоже существует — «когда-то». Это оба наречия и они, в принципе, оба синтаксически могут быть на этом месте предложения. Оно неправильно лишь в контексте («После неудачного поиска когда-то желательно ввести...»). Такую ошибку может разве-что какая-то нейронка найти, а не ворд.

[Si010ver]

Если это и не ворд, это еще не значит что такого нет. Последние 2-3 года пользуюсь grammarly, и грамматические, и стилистические ошибки находит в большинстве случаев.

[ef_end_y]

ну скормите ей этот текст. найдет ошибку?

[Si010ver]

Нашло, вот вам пруф; еще говорит, там запятой не хватает, но это я уже не ручаюсь.

[andreymal]

Картинкохостинг, который не отображает встроенную в комментарий картинку, пока на сайте не пройдена CloudFlare-капча. Прекрасно.

[vk_0x5D]

Легко!

[Ctacfs]

Тут сложный вопрос, спеллчекер распознал ошибку или это ошибка спеллчекера в незнании этого наречия.

[tyomitch]

Пусть Si010ver или vk_0x5D проверят на тексте, где это наречие употреблено правильно.

[vk_0x5D]

Прошу,

[third112]

Я также хотел бы найти баг в первом томе «Фундаментальные алгоритмы». Может, и нашёл бы, но в местной библиотеке по какой-то причине имеются только тома 2, 3 и 4A.

ИМХО автору нужно купить у Кнута 1й том в электронном виде за свои шестнадцатеричные доллары ;)

[alan008]

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

[third112]

потом оказывается, что этот кусок кода в рантайме вообще никогда не вызывается.

Что само по себе ИМХО уже является ошибкой («мертвый код») ;)

[speshuric]

Код может не вызываться в runtime по разным причинам. Например, это может быть обработка исключительной ситуации, которая не происходит, но может произойти. Для анализатора это не «мертвый код».

[third112]

Ok. Если «может произойти», то неверное утверждение:

этот кусок кода в рантайме вообще никогда не вызывается.

:)))

[speshuric]

Ну нет же противоречия. «Никогда не вызывается» — как факт эксплуатации системы и «не может быть вызван» (плюс, говоря про стат. анализ, надо добавить «и это можно определить статическим анализом») — как характеристика кода. Два разных утверждения. Из второго следует первое, из первого второе — нет.

[third112]

Не понял.
Пример 1:

read (n);
if n<>0 then
 x:=y/n
else
 write ('Error: invalid input');

Пример 2:

n := 3.14314;
if n<>0 then
 x:=y/n
else
 write ('Error: invalid input');

В примере 1 при внимательном пользователе код write ('Error: invalid input') не вызывается, но м.б. вызван, если пользователь промажет по клавише или нарочно введет ноль. В примере 2 код write ('Error: invalid input') не м.б. вызван.
Поэтому он мертвый и должен быть удален:

n := 3.14314;
x:=y/n

[Jesting]

Оператор <> (!=) вполне себе может быть переопределён таким образом что 3.14 == 0 (Для военных например). Так что пример 2 корректен 100%

[assembled]

Что-то вспомнился баян:

#define true false

Видимо, тоже военными придуман ;D

[third112]

Оператор <> (!=) вполне себе может быть переопределён

В стандартном Паскале, на котором пример, не может)

[assembled]

Ну во FreePascal это возможно, но только вроде как для пользовательских типов.

[third112]

Речь о первых стандартах ISO 7185:1983, ANSI/IEEE 770X3.97:1983. ИМХО по контексту понятно, что в этих моих примерах не предполагалось никакого переопределения.

[YuryZakharov]

Хороший анализатор должен показать, что этот кусок кода не вызывается, а не ошибки в нём искать. Иначе зачем такой анализатор нужен?

[speshuric]

Позвольте не согласиться. Тут важен контекст.
Кнут, судя по текстам и интервью, перфекционист и дотошный зануда (это не оскорбление, а комплимент), причем с высокой самооценкой с определённым высокомерным снобизмом (оправданно). При всём перфекционизме он умудрился написать 4,5 тома, причем по полноте охвата темы аналогов нет. В качестве учебного пособия я могу этот четырёхтомник сравнить только с монументальным Ландау-Лившицем, но он не настолько пропитан занудством и перфекционизмом. Кнут, понимая, что он перфекционист и дотошный зануда пишет труд, который заведомо его переживёт. Несмотря на как бы "стремительное развитие" CS, он выделил тот слой, который будет устаревать очень-очень долго.
Предложение о поиске опечаток, мне кажется, несёт 3 идеи:

1. Обещание, что ошибок немного.
2. Шлифовка текста до состояния "оставить потомкам". Здесь есть добрая доля здорового тщеславия, но если капелька тщеславия помогла написать "Искусство программирования", то это оправданная цена.
3. Ещё тема про опечатки — она не совсем про деньги, и, даже, возможно, не совсем про ошибки. Понимая, что книга не простая для чтения, но требует внимательного чтения Д. Кнут добавил элемент геймификации — ачивку за внимательность.

[ZEvS_Poisk]

Кажется я старый…
Из этой статьи (автору спасибо), я узнал, что Дональд Кнут написал 4,5 тома.
Я всегда, называл сей труд «трехтомник Кнута», и у меня на полке 3 тома стоят :)

[speshuric]

Написаны 1,2,3 и 4А. За «полтома» можно считать «Volume 1, Fascicle 1» (в русском переводе Том 1 выпуск 1) и 2 первые части того, что войдёт в 4B (если Д.К. успеет): «Volume 4, Fascicle 5» и «Volume 4, Fascicle 6» (русских переводов не видел).
И, да, когда я его первый раз читал, то он тоже был трёхтомник, а в книге «Язык программирования C++» Страуструпа шаблоны еще считались свежей фичей («Однако, шаблоны типа и обработка особых ситуаций относятся к самым последним расширениям языка, и возможно, что ваш транслятор их не содержит.»)

[A1exXx]

Согласен, это спорный момент. Что считать отправной точкой: Дату которую назвал автор, когда он придумал алгоритм, или дату когда алгоритм был опубликован.

[tyomitch]

Кнуту ничего не мешало именно так и написать — «Алгоритм был придуман в 1960 и опубликован в 1962».

[tyomitch]

Там Кнут пишет: «Любопытно, что эту идею обнаружили только в 1962 году»

[dimm_ddr]

При особенной степени занудства можно и тут прочитать так, чтобы было верно. Ведь пока идея живет только в голове ее автора для мира этой идеи не существует. Поэтому вполне можно сказать что идею обнаружили тогда, когда она была представлена миру.

[Balling]

Ну надо же. Я совсем недавно читал про быстрое умножение:
habr.com/ru/post/451860

[Habivax]

извините, ошибся, удалил.

[Naves]

Кстати, не совсем понятно, как вот так просто можно взять и «Прикрепите нужный элемент к концу массива»
А если в памяти, сразу за искомым массивом начинается новый блок данных, который кем-то используется.

[Wesha]

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

1. Проверьте последний элемент массива. Запомните результат проверки.
2. Запомните последний элемент массива. Замените последний элемент массива на искомый.
3. Проверьте, является ли текущий элемент искомым. Если так,
   3a. если указатель находится на последнем элементе массива, восстанавливаем последний элемент массива из запомненного и возвращаем запомненный на шаге 1 результат
   3b. если указатель находится не на последнем элементе массива, восстанавливаем последний элемент массива из запомненного и возвращаем ответ
4. Увеличьте указатель и продолжайте.

[Wesha]

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

[Teodot2463]

Прикрепите нужный элемент к концу массива, затем запустите указатель в начале массива и выполните следующие действия в цикле:

1. Проверьте, является ли текущий элемент желаемым. Если так, возвращаем ответ, если указатель находится в пределах массива, или ошибку, если это не так. В противном случае
2. Увеличьте указатель и продолжайте.

Если массив не содержит искомого элемента, алгоритм вернет добавленный нами элемент. Наверное должно быть «возвращаем ответ, если указатель находится в пределах массива и не указывает на последний (добавленный нами) элемент».

Поскольку, чем больше ошибок, тем больше вероятность рассмотрения, предлагаю объединить усилия и поделить награду:)

[Naves]

Скорее всего в оригинале все правильно сформулировано с вложенным if. Просто в дословном переводе получилось, подъезжая к станции с меня слетела шляпа.

[questor]

А как Кнут решает ситуации, что одну и ту же ошибку зарепортят несколько человек? Ведь речь идёт о бумажной книге, кто-то найдёт ошибку — он должен вероятно зайти на сайт автора, поискать нет ли этой опечатки в списке «в следующем тираже будет исправлено» и только потом репортить.

[tyomitch]

Совершенно верно: www-cs-faculty.stanford.edu/~knuth/taocp.html#errata

[dMac]

Вот сам себя обманул. Из заголовка решил, что дедушка Дональд прислал автору ноль раз по три доллара, заинтересовался. Зашел почитать, как это так. А это, оказывается, про шестнадцатиричные доллары.

[0x9d8e]

Это вот сейчас обидно было (минус не мой) :)

[assembled]

Я вообще подумал, что он прислал ему пустой вектор.

Заголовок спойлера

Шутка для J-программистов. Суффикс «x» у числа означает произвольную точность, $ конструирует массив, левый аргумент — размеры массива, правый — элементы.

[Legomegger]

Надеюсь он что-то предпринимает для того, чтобы все его планы были осуществлены. Не хотелось бы чтобы его знания ушли вместе с ним

[vokzamag]

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

В качестве теоретического упражнения — интересная мысль.
На практике- так себе оптимизация. Добавление элемента чревато тем, что придётся просить ещё памяти у ОС (системный вызов — очень дорогая штука) и, скорей всего, копировать старый массив в новый за O(n). На избавлении от проверки границы много не сэкономить — процессор неплохо умеет предсказывать ветвления.

[Rupper]

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

Так надо только для элемента выделять память, или для примитивных типов обойтись регистрами вообще.

[assembled]

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

[assembled]

Ах да, в многопоточном приложении могут быть ещё проблемы. Короче, алгоритм может и быстрый, но годится не везде и использовать надо с осторожностью.

[Rupper]

поскольку мы упарываемся за каждый такт и байт, то команда сравнения с нулем занимает минимум на 1 байт меньше, чем с каким-то значением :)

[dimm_ddr]

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

[zaiats_2k]

1. Проверьте, является ли текущий элемент желаемым. Если так, возвращаем его; в противном случае
2. Проверьте, находится ли указатель за границей массива. Если так, возвращаем ошибку; в противном случае
3. Увеличьте указатель и продолжайте.

Что-то не верится что у Кнута может быть такой детский 0-дейчик.
1. Сначала мы лезем по адресу, а потом внезапно спохватываемся и
2. Проверяем не лазили ли мы, случайно, за границу…

Вот нет у нас искомого в массиве, просканировали мы его весь, ничего не нашли
3. Увеличили указатель (вылезли за границу), продолжаем
1. Ээээ, что-что мы сейчас собираемся проверить? Что именно нам бог послал за границей массива?