21.05.2019 15:20
m1rko 52 45000 Источник
Дональд Кнут — учёный в области информатики, который настолько заботится о правильности своих книг, что предлагает один шестнадцатеричный доллар ($2,56, 0x$1,00) за любую найденную «ошибку», где ошибкой считается всё, что «технически, исторически, типографически или политически неправильно». Я очень хотел получить чек от Кнута, поэтому решил поискать ошибки в его выдающемся труде «Искусство программирования» (TAOCP). Удалось найти три. Верный слову, Кнут прислал чек на 0x$3,00.



Как видите, это не настоящий чек. Раньше Кнут отправлял реальные чеки, но прекратил в 2008 году из-за безудержного мошенничества. Теперь он рассылает «личные депозитные сертификаты» в банке Сан-Серрифф (BoSS). Он говорит, что готов выслать реальные деньги в случае необходимости, но, похоже, это слишком хлопотно.

Я нашёл две опечатки и одну историческую ошибку. Перечислю их в порядке уменьшения тривиальности.

Опечатка №1


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

Конечно, в такой ошибке нет ничего удивительного. Только в этой статье обязательно найдётся несколько опечаток (никаких наград за их нахождение). Что на самом деле удивительно, так это то, что её так долго не замечали. Страница 392 не зарыта глубоко в раздел с математикой, это самая первая страница шестой главы «Поиск»! Возможно, один из самых читаемых разделов книги. По идее, там должно быть меньше всего опечаток, но нет.

Кстати, если вы когда-нибудь думали почитать TAOCP, попробуйте. Многие скажут, что это справочник, не предназначенный для прямого чтения, но это неправда. У автора есть чёткая точка зрения и своеобразный стиль. Единственное, что препятствует читаемости, — это сложность математики. Однако есть простое решение: читайте, пока не дойдёте до математики, которую вы не понимаете, пропустите её и откройте следующий раздел, который можете понять. Читая таким образом, я пропускаю по крайней мере 80% книги, но остальные 20% великолепны!

Также говорят, что TAOCP нерелевантна, устарела или иным образом неприменима к «реальному программированию». Это тоже неправда. Например, в первом разделе после введения рассматривается поиск элемента в несортированном массиве. Самый простой алгоритм знаком всем программистам. Запустите указатель в начале массива, затем выполните следующие действия в цикле:

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

Теперь рассмотрим: сколько проверок границ требует этот алгоритм, в среднем? В худшем случае, когда массив не содержит элемента, для каждого элемента в списке потребуется одна проверка, и в среднем это будет что-то вроде $N/2$. Более умный алгоритм поиска может обойтись всего одной проверкой границ. Прикрепите нужный элемент к концу массива, затем запустите указатель в начале массива и выполните следующие действия в цикле:

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

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

«Поиск, поиск
Так долго
Поиск, поиск
Я просто хотел танцевать»
— Лютер Вандросс, «Поиск» (1980)

Опечатка №2


Вторая опечатка — в томе 4A, «Комбинаторные алгоритмы», часть 1. На странице 60 описана задача с планированием выступлений комиков в различных казино. В качестве примера приводятся несколько реальных комиков, в том числе Лили Томлин, Странный Эл Янкович и Робин Уильямс, который был ещё жив, когда вышла книга. Кнут всегда приводит в указателе полные имена, поэтому Уильямс упоминается на странице 882 как «Уильямс, Робин Мак-Лорим». Но его второе имя заканчивается на «н», а не на «м», то есть Мак-Лорин.

Мак-Лорин — девичья фамилия его матери. Она была правнучкой Ансельма Джозефа Мак-Лорина, 34-го губернатора Миссисипи. Его правление, видимо, не запомнилось ничем хорошим. Из книги «Миссисипи: история»:

«Самым важным событием во время администрации Мак-Лорина стало объявление Соединёнными Штатами войны Испании весной 1898 года… К сожалению, война, возможно, дала некоторым государственным чиновникам возможность практиковать взяточничество. Мак-Лорина обвинили в различных сомнительных практиках, включая кумовство и чрезмерное использование полномочий по помилованию. В эпоху движения за трезвость критики обвинили губернатора в пьянстве, что он публично признал».

Историческая ошибка


Рассмотрим традиционный алгоритм умножения из школьной программы. Сколько он требует одноразрядных операций умножения? Предположим, вы умножаете $m$-разрядное число $x$ на $n$-разрядное $y$. Сначала умножаете первую цифру $x$ на каждую цифру $y$ по очереди. Затем умножаете вторую цифру $x$ на каждую цифру $y$ по очереди и так далее, пока не пройдёте все цифры $x$. Таким образом, традиционное умножение требует $mn$ примитивных умножений. В частности, перемножение двух чисел по $n$ разрядов требует $n^2$ одноразрядных умножений.

Это плохо, но можно оптимизировать процесс с помощью метода, разработанного советским математиком Анатолием Алексеевичем Карацубой. Предположим, что $x$ и $y$ — двузначные десятичные числа; то есть существуют числа $a$, $b$, $c$, $d$ такие, что $x = (ab)_{10}$ и $y = (cd)_{10}$ (обобщение этого алгоритма на большие цифры требует определённых манипуляций; хотя это не слишком сложно, но чтобы не ошибиться в деталях, я лучше буду придерживаться простого примера). Тогда $x = 10a + b$, $y = 10c + d$, $xy = (10a + b)(10c + d)$. Умножение двучленов даёт $xy = 100ac + 10ad + 10bc + bd$. На данный момент у нас по-прежнему $n^2 = 4$ одноразрядных умножения: $ac$, $ad$, $bc$, $bd$. Теперь сложим и вычтем $10ac + 10bc$. После нескольких перестановок, которые я оставлю в качестве упражнения для читателя, получается $xy = 110ac + 11bd + 10(a - b)(d - c)$ — всего три одноразрядных умножения! (Есть некоторые постоянные коэффициенты, но их можно вычислить только сложением и сдвигом разрядов).

Не просите доказательства, но алгоритм Карацубы (рекурсивно обобщённый из приведённого выше примера) улучшает традиционный метод умножения с $O(n^2)$ операций до $O(n^{(lg 3)})$. Обратите внимание, что это реальное улучшение алгоритма, а не оптимизация для расчётов в уме. Действительно, алгоритм не подходит для счёта в уме, так как требует больших накладных расходов на рекурсивные операции. Кроме того, эффект проявится не в полной мере, пока цифры не станут достаточно большими (к счастью, вместо алгоритма Карацубы пришли ещё более быстрые методы: в марте 2019 года был опубликован алгоритм, требующий всего n log n умножений; ускорение применимо только к невообразимо большим числам).

Этот алгоритм описан на странице 295 второго тома «Получисленные алгоритмы». Там Кнут пишет: «Любопытно, что эту идею обнаружили только в 1962 году», когда была опубликована статья, описывающая алгоритм Карацубы. Но! В 1995 году Карацуба опубликовал статью «Сложность вычислений», в которой говорит несколько вещей: 1) около 1956 года Колмогоров предположил, что умножение нельзя произвести менее чем в $O(n^2)$ шагов; 2) в 1960 году Карацуба присутствовал на семинаре, где Колмогоров изложил свою гипотезу n?. 3) «Ровно за неделю» Карацуба разработал алгоритм «разделяй и властвуй»; 4) в 1962 году Колмогоров написал и опубликовал статью от имени Карацубы с описанием алгоритма. «Я узнал об этой статье только после того, как её перепечатали».

Таким образом, ошибка заключается в том, что вместо 1962 должен быть указан 1960 год. Вот и всё.

Анализ


Поиск ошибок не требовал особого мастерства.

  1. Первая ошибка была настолько банальной, насколько это возможно, и находилась в относительно видном месте (начало главы). Любой идиот нашёл бы её; просто я оказался тем идиотом.
  2. Поиск второй опечатки требовал удачи и усердия, но не умения. Индекс для «Уильямса» находится на предпоследней странице тома, довольно заметная часть книги. Я как раз листал индексный указатель (это не так жалко, как кажется, потому что в указателях Кнута спрятаны пасхальные яйца. Например, там есть записи на арабском и иврите, и обе указывают на страницу 66. Но на этой странице не упоминается ни один из языков; вместо этого там упоминаются «языки, которые читаются справа налево»). И моё внимание привлекло второе имя. Поскольку я обычно читаю Википедию, то проверил Робина Уильямса и заметил несоответствие.
  3. Хотел бы я сказать, что я провёл серьёзное исследование, чтобы найти историческую ошибку, но на самом деле просто посмотрел страницу Википедии об алгоритме Карацубы. В первых же строках написано: «Алгоритм Карацубы — это алгоритм быстрого умножения. Открыт Анатолием Карацубой в 1960 году и опубликован в 1962 году». После этого оставалось лишь сложить дважды два.

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

Финансовые факты:

  • В общей сложности, мой вклад в TAOCP состоит всего из трёх символов: одном добавлении s, замене m на n и 2 на 0. По цене $2,56 это довольно прибыльные символы; если бы вам платили такие деньги, то статья из 1000 слов (в среднем, по четыре символа) принесла бы вам десять штук.
  • С тремя шестнадцатеричными долларами я вместе с 29-ю другими гражданами делю 69-е место в списке самых богатых вкладчиков банка Сан-Серрифф (по состоянию на 1 мая 2019 года).


Другие обсуждения чеков от Кнута


  • Как получить чек от Кнута

    Общие рекомендации по поиску ошибок в книгах Кнута. В основном касаются технических ошибок, которых у меня нет. Там есть одно предложение, которое я принял всерьёз:

    Лучше подождать, пока вы не соберёте набор ошибок для отправки. Объединив нескольких реальных, но не очень ценных ошибок, вы повысите вероятность того, что одну из них действительно расценят как ошибку или совет. Если отправлять ошибки по одной, каждую по отдельности могут отклонить.

    Я не хотел посылать просто ерундовые опечатки, а послушался совета и отправил письмо только когда нашёл историческую ошибку, которая показалась достаточно серьёзной.
  • Чеки Ашутоша Мехры

    Ашутош Мехра — третий по богатству вкладчик в Сан-Серрифф с колоссальным состоянием 0x$207,f0 в BoSS.
  • Чек за некоторые нефункциональные ошибки в реальном коде TeX
  • Разное: #1 #2 #3 #4 #5 #6

Комментарии (52)


  1. Peter03
    21.05.2019 20:30
    #20182102
    -3

    Загрузить всё в MS Word, включить проверку орфографии — профит?


    1. TimsTims
      22.05.2019 00:55
      #20182898

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


      1. Peter03
        22.05.2019 00:57
        #20182912

        Вообще то я имел в виду

        После неудачного поиска иногда (sometime) желательно ввести в таблицу новую запись, содержащую K; метод, который делает это, называется алгоритмом поиска и вставки. Ошибка в том, что вместо sometime должно быть sometimes
        проверка орфографии должна найти простые случаи типа sometime vs sometimes


        1. saloid
          22.05.2019 06:27
          #20183192

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


          1. Si010ver
            22.05.2019 09:46
            #20183660

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


            1. ef_end_y
              22.05.2019 11:50
              #20184308
              +1

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


              1. Si010ver
                22.05.2019 13:01
                #20184714
                -1

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


                1. andreymal
                  22.05.2019 13:16
                  #20184796
                  +1

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


              1. vk_0x5D
                22.05.2019 13:21
                #20184830
                +2

                Легко!
                image


                1. Ctacfs
                  22.05.2019 15:46
                  #20185648

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


                  1. tyomitch
                    22.05.2019 15:52
                    #20185678

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


                    1. vk_0x5D
                      22.05.2019 16:54
                      #20186052

                      Прошу, image


  1. third112
    21.05.2019 21:49
    #20182358
    +1

    Я также хотел бы найти баг в первом томе «Фундаментальные алгоритмы». Может, и нашёл бы, но в местной библиотеке по какой-то причине имеются только тома 2, 3 и 4A.
    ИМХО автору нужно купить у Кнута 1й том в электронном виде за свои шестнадцатеричные доллары ;)


  1. alan008
    21.05.2019 21:55
    #20182382

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


    1. third112
      21.05.2019 22:22
      #20182500
      +2

      потом оказывается, что этот кусок кода в рантайме вообще никогда не вызывается.
      Что само по себе ИМХО уже является ошибкой («мертвый код») ;)


      1. speshuric
        21.05.2019 23:25
        #20182706

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


        1. third112
          21.05.2019 23:29
          #20182714
          +1

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

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

          :)))


          1. speshuric
            21.05.2019 23:35
            #20182740

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


            1. third112
              21.05.2019 23:47
              #20182766

              Не понял.
              Пример 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


              1. Jesting
                22.05.2019 08:35
                #20183432

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


                1. assembled
                  22.05.2019 15:45
                  #20185642

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

                  #define true false

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


                1. third112
                  23.05.2019 08:11
                  #20188356

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


                  1. assembled
                    23.05.2019 10:11
                    #20188926

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


                    1. third112
                      23.05.2019 11:03
                      #20189300

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


    1. YuryZakharov
      21.05.2019 22:55
      #20182638

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


    1. speshuric
      21.05.2019 23:17
      #20182694
      +5

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


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


  1. ZEvS_Poisk
    22.05.2019 01:14
    #20182946

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


    1. speshuric
      22.05.2019 02:22
      #20183024

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


  1. mwambanatanga
    22.05.2019 04:46
    #20183104

    По третьему пункту Кнут прав (или, как минимум, не неправ) — в 1960-ом году об алгоритме стало известно одному человеку (создателю/открывателю), а миру он стал известен лишь в 1962 г.


    1. A1exXx
      22.05.2019 10:45
      #20183914

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


      1. tyomitch
        22.05.2019 11:10
        #20184068

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


    1. tyomitch
      22.05.2019 11:07
      #20184040

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


      1. dimm_ddr
        23.05.2019 12:43
        #20189952

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


  1. Balling
    22.05.2019 06:26
    #20183188

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


  1. HEKOT
    22.05.2019 10:27
    #20183832

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

    Out of range!
    С Вас двоичный доллар! :)


    1. Habivax
      22.05.2019 18:12
      #20186466

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


    1. Naves
      22.05.2019 20:25
      #20187016

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


    1. Teodot2463
      22.05.2019 23:32
      #20187620

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

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

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

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


      1. Naves
        22.05.2019 23:45
        #20187652

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


  1. questor
    22.05.2019 11:42
    #20184268

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


    1. tyomitch
      22.05.2019 11:50
      #20184306

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


  1. dMac
    22.05.2019 12:32
    #20184542

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


    1. 0x9d8e
      22.05.2019 18:07
      #20186442

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


    1. assembled
      23.05.2019 10:19
      #20188966
      +1

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

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


  1. Legomegger
    22.05.2019 14:06
    #20185074

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


  1. random1st
    22.05.2019 17:28
    #20186242

    У Вас в тексте квадратный доллар получается) Не в личку, потому что хотелось поделиться, вдруг это не баг а фича)


  1. vokzamag
    23.05.2019 02:13
    #20187964

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

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


    1. Rupper
      23.05.2019 08:54
      #20188516

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

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


      1. assembled
        23.05.2019 10:27
        #20189008

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


        1. assembled
          23.05.2019 10:34
          #20189044

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


        1. Rupper
          23.05.2019 10:45
          #20189138

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


    1. dimm_ddr
      23.05.2019 12:47
      #20189976
      +1

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