В сообществе разработчиков линукса и около него очень лояльное отношение к goto. Недавно было на ютубе видео "every goto in the Linux kernel", там приводятся цитаты Линуса и других по этому поводу (ну и заводная музыка фоном под это)
Если только распределение уклонения не экспоненциально - в этом случае распределение инвариантно относительно точки начала измерения: вероятность уклонения в ближайшие t часов от текущего момента такая же, как была вероятность уклонения в первые t часов от первой мысли о написании статьи.
Под словом "оценка" в математике обычно (но не всегда) имеют в виду оценку сверху или снизу, т.е. неравенство, а не равенство. Чебышев дает оценку сверху на вероятность, и в данной задаче эта оценка оказалось очень грубой, но все же верной.
Первая строка вводит в заблуждение: статья опубликована в nature machine intelligence и это совсем не то же, что nature, хоть и принадлежит тому же издателю. Более того, судя по всему журнал очень средней руки и в нем публикуются, в том числе, чтобы как раз можно было сказать "у нас статья в nature machine intelligence", а люди (как автор например) услышали бы "у нас статья в nature".
В довольно широком смысле из-за алгоритма Риша вычисление интегралов, понимаемое как вычисление первообразной, это тоже техника. Алгоритм сложный, поэтому его не преподают. Но есть разные нюансы в алгоритме Риша и в понимании того, что значит найти первообразную (в элементарных функциях или еще в каких-то функциях), и есть, конечно, интегралы с переменными пределами, вычисление которых, видимо, до сих пор искусство.
Можно косвенно влиять на предсказатель. Это не точная наука, но кое на что можно полагаться. Например, что предсказатель считает дальние условные переходы менее вероятными (именно такой скорее всего будет переход на abort) и что условные ближние переходы назад более вероятны. Понятно, что предсказатель это непростая штука и есть много условий, в том числе история выполнения кода. Но можно немного на него влиять. Думаю, что автор это и имел ввиду под подсказками предсказателю.
Это же и будет алгоритм Дейкстры. По крайней мере тот же вариант, который описан в статье в коде (в текстовом описании алгоритм в статье немного отличается от варианта в коде). Есть еще два варианта Дейкстры: 1 не помещать повторно в кучу то, что там уже находится, а просто выполнять heapifyUp для такого узла из кучи (минусы: куча с heapifyUp есть не в каждой библиотеке и ее придется реализовать самому; поддерживать указатели на узлы из кучи не так просто и ресурсозатратно; плюсы: используем О(n) памяти под кучу, а не О(m)), и 2 вообще изначально положить в кучу все узлы (минусы и плюсы в таком варианте те же)
Бегло прошёлся по бенчмаркам в интернете и, судя по всему, LZMA и его производные даже против deflate (это LZ77 с Хаффманов) дают в 1.5 - 2 раза лучшее сжатие. А против LZW они будут ещё лучше (LZW проигрывает deflate по сжатию, но не так драматически). По-моему это не "сравнимая" степень сжатия. Зависит от сжимаемых данных, конечно, но эти бенчмарки часто довольно репрезентативны. Недавно, кстати, на хабре была хорошая статья на близкую тему: https://habr.com/ru/post/570694/ (там же есть ссылка на один хороший бенчмарк; ещё можно посмотреть http://www.mattmahoney.net/dc/text.html). Много раз уже сталкивался с похожим мнением, что сжатие не важно и важнее скорость. Согласен, есть такие приложения, где это так. Но даже в таком случае LZW далеко не лучший выбор и методы на основе LZ77 (не обязательно LZMA) работаю лучше. Например, zstd с флагом "level 2" (или около того), судя по бенчмаркам, так же эффективен по степени сжатия, как deflate с наилучшим сжатием, но раз в 5 быстрее декодирует. Я уверен, что LZW с Хаффманом/арифметиком декодирует медленнее, чем deflate (LZW для декодирования использует более сложного вида словарь, а deflate просто копирует уже декодированные куски); в интернете пишут, что LZW в 2 раза медленнее декодирует, чем deflate, в некоторых реализациях. Без Хаффмана LZW точно по-быстрее будет, но тоже не факт, что быстрее чем deflate. Так что zstd явно гораздо лучше в этом отношении и чем LZW, и чем deflate.
Я думаю, что это сделано для простоты реализации. LZW - очень простой но при этом эффективный алгоритм, который каждый может реализовать без мудрствований. Но если продолжать вашу мысль и довести её до идеала, то оптимально было бы применять для каждой фразы LZW адаптивное интервальное кодирование или что-то в этом духе. Тогда вся последовательность из z фраз LZW будет занимать всего log2(256) + log2(257) + ... + log2(255 + z) + 1 битов, ну или log2(256) + log2(257) + ... + log2(d) + log2(d) + ... + log2(d) + 1 битов, если размер словаря ограничен d фразами (например, d = 2^16, как обычно полагают). В стандартных реализациях LZW (типа LZC) тоже есть механизмы уменьшения размера кодов для первых фраз (хоть и не такие оптимальные): обычно первые фразы занимают последовательно 9, 10, ..., 16 битов, а потом словарь перестаёт расти. Вполне возможно, что на реальных датасетах этот простой трюк не намного хуже более хитрого оптимального кодирования. Вообще, если нужно сжатие по-лучше, то лучше сразу обращаться к LZMA, а не пытаться тюнить LZW.
Точно помню, что видел либо на хабре, либо на гиктаймс статью с подробным расследованием этой атаки от какой-то чешской или словакской фирмы, занимающейся ИБ (может avast, но не уверен). Всё обшарил, пытался загуглить разными запросами, но так и не смог найти. Может быть кто-нибудь помнит, как называлась та статья? Хочется вспомнить аргументы «стороны обвинения».
Вспомнился обширный интересный комментарийkraidiky о невероятной разумности компилятора фортран. Правда, он не стал, как автор, раздувать из комментария статью (может, всё таки, зря).
О том, что у человека при просмотре такого выступления может возникнуть ощущение, что для выправления собственной речи не обязательно избавляться от слов-паразитов и рваных фраз, что это всё мелочи. Однако, по своему опыту сужу, что речь многих докладчиков, не обладающих той же харизмой, чувством юмора и чувством аудитории, как докладчик на видео выше, страдает именно и главным образом от рваных фраз, слов-паразитов и ненамеренно высокомерных реплик (как в списке в статье). Вот от таких ошибок статья и предостерегает (и справедливо, судя по количеству совершающих эти ошибки), но при этом честно упоминает, что хорошие докладчики иногда нарушают все эти правила и начинающего это может ввести в заблуждение, что типа так и надо. Имхо, не у всех достаточно харизмы/уверенности в себе/ещё чего-то, чтобы превратить свои недостатки в достоинства, как на видео выше.
Однако отдельные личности с критическим мышлением предостерегают нас от ошибки при выборе примеров для подражания. Далеко не всё, что говорят даже самые лучшие спикеры, положительно воспринимается аудиторией.
Так что очень даже в тему это видео. Что позволено Юпитеру…
То что вы ищете называется cache-oblivious model: https://en.wikipedia.org/wiki/Cache-oblivious_algorithm
Эта модель, придуманная ещё в середине девяностых, несколько более сложна, чем традиционная RAM, поэтому под неё разработано меньше алгоритмов. Так получается, я полагаю, потому что при решении ещё нерешённой задачи люди сначала предпочитают всесторонне рассмотреть её в близкой (и часто практической), но более простой обычной RAM, а уже потом смотрят на кэш/внешнюю память/параллелизм.
Более логичным выглядит предположение, что популярность этого алгоритма вытекает из его простоты.
Скорее всего вы правы, но всё таки есть немало программистов, которые краем уха где-то слышали об оптимальности LRU при каких-то условиях, что частично оправдывает его использование (смотрите мой комментарий выше).
Вы совсем как-то заклеймили LRU. Верю, что, вероятно, на многих реальных паттернах использования кэша LRU проигрывает некоторым другим кэшам. Но есть у LRU одна особенность: в худшем случае его поведение в некотором смысле наилучшее по отношению к «ясновидящему» оптимальному алгоритму. Это доказано Слейтором и Тарьяном в статье Amortized efficiency of list update and paging rules (раздел 4). Немного огрублённо их результат можно сформулировать так:
Для любой константы c>1 и для любой последовательности s обращений к кэшируемым элементам (кэшируемые элементы имеют одинаковый размер) выполняется F_LRU(s) <= c F_OPT(s), где F_LRU(s) и F_OPT(s) — это число непопаданий в кэш на последовательности s для, соответственно, алгоритма LRU с размером кэша n и ясновидящего алгоритма OPT с размером кэша (1 — 1/c)n.
И обратно: для любого алгоритма кэширования A найдётся сколь угодно длинная последовательность s обращений к кэшируемым элементам, такая что F_A(s) >= c F_OPT(s), где F_A(s) — это число непопаданий в кэш на последовательности s для алгоритма A с размером кэша n, а у OPT опять размер кэша (1 — 1/c)n.
Если вы рассматриваете строку, в которой последний символ отличается от всех остальных символов (как в примере), то для строки длины N количество вершин в суффиксном дереве всегда будет больше N (корень + по листу на каждый суффикс). Но, естественно, вершин может быть больше, чем N+1. Тем не менее, количество вершин всегда не больше 2N+1. Чтобы в этом убедиться достаточно последовательно вставлять в дерево каждый суффикс: когда вы вставляете суффикс появляется одна или две вершины (лист + вершина, к которой этот лист крепится, если её ещё нет).
В случае произвольной строки ситуация несколько иная: вершин также не больше 2N+1, но может быть и меньше, чем N (например, для строки aaaaaaaaaaa суффиксное дерево содержит всего две вершины).
В тексте я неявно опирался на тот факт, что в дереве с n листьями, в котором у каждой нелистовой вершины есть как минимум два потомка, всегда O(n) вершин. Я не учёл, что это, вообще-то, не очень очевидно.
В сообществе разработчиков линукса и около него очень лояльное отношение к goto. Недавно было на ютубе видео "every goto in the Linux kernel", там приводятся цитаты Линуса и других по этому поводу (ну и заводная музыка фоном под это)
Если только распределение уклонения не экспоненциально - в этом случае распределение инвариантно относительно точки начала измерения: вероятность уклонения в ближайшие t часов от текущего момента такая же, как была вероятность уклонения в первые t часов от первой мысли о написании статьи.
"Я долго уклонялся от написания этой статьи..." лучше бы и дальше уклонялись, чем писать вот это
Под словом "оценка" в математике обычно (но не всегда) имеют в виду оценку сверху или снизу, т.е. неравенство, а не равенство. Чебышев дает оценку сверху на вероятность, и в данной задаче эта оценка оказалось очень грубой, но все же верной.
Первая строка вводит в заблуждение: статья опубликована в nature machine intelligence и это совсем не то же, что nature, хоть и принадлежит тому же издателю. Более того, судя по всему журнал очень средней руки и в нем публикуются, в том числе, чтобы как раз можно было сказать "у нас статья в nature machine intelligence", а люди (как автор например) услышали бы "у нас статья в nature".
(Не туда ответил, извините)
Статья переводная. В некоторых странах в школах обязательно изучают секансы, поэтому и в универе там берут от них интегралы и это там всем знакомо
В довольно широком смысле из-за алгоритма Риша вычисление интегралов, понимаемое как вычисление первообразной, это тоже техника. Алгоритм сложный, поэтому его не преподают. Но есть разные нюансы в алгоритме Риша и в понимании того, что значит найти первообразную (в элементарных функциях или еще в каких-то функциях), и есть, конечно, интегралы с переменными пределами, вычисление которых, видимо, до сих пор искусство.
Можно косвенно влиять на предсказатель. Это не точная наука, но кое на что можно полагаться. Например, что предсказатель считает дальние условные переходы менее вероятными (именно такой скорее всего будет переход на abort) и что условные ближние переходы назад более вероятны. Понятно, что предсказатель это непростая штука и есть много условий, в том числе история выполнения кода. Но можно немного на него влиять. Думаю, что автор это и имел ввиду под подсказками предсказателю.
Это же и будет алгоритм Дейкстры. По крайней мере тот же вариант, который описан в статье в коде (в текстовом описании алгоритм в статье немного отличается от варианта в коде). Есть еще два варианта Дейкстры: 1 не помещать повторно в кучу то, что там уже находится, а просто выполнять heapifyUp для такого узла из кучи (минусы: куча с heapifyUp есть не в каждой библиотеке и ее придется реализовать самому; поддерживать указатели на узлы из кучи не так просто и ресурсозатратно; плюсы: используем О(n) памяти под кучу, а не О(m)), и 2 вообще изначально положить в кучу все узлы (минусы и плюсы в таком варианте те же)
Бегло прошёлся по бенчмаркам в интернете и, судя по всему, LZMA и его производные даже против deflate (это LZ77 с Хаффманов) дают в 1.5 - 2 раза лучшее сжатие. А против LZW они будут ещё лучше (LZW проигрывает deflate по сжатию, но не так драматически). По-моему это не "сравнимая" степень сжатия. Зависит от сжимаемых данных, конечно, но эти бенчмарки часто довольно репрезентативны. Недавно, кстати, на хабре была хорошая статья на близкую тему: https://habr.com/ru/post/570694/ (там же есть ссылка на один хороший бенчмарк; ещё можно посмотреть http://www.mattmahoney.net/dc/text.html). Много раз уже сталкивался с похожим мнением, что сжатие не важно и важнее скорость. Согласен, есть такие приложения, где это так. Но даже в таком случае LZW далеко не лучший выбор и методы на основе LZ77 (не обязательно LZMA) работаю лучше. Например, zstd с флагом "level 2" (или около того), судя по бенчмаркам, так же эффективен по степени сжатия, как deflate с наилучшим сжатием, но раз в 5 быстрее декодирует. Я уверен, что LZW с Хаффманом/арифметиком декодирует медленнее, чем deflate (LZW для декодирования использует более сложного вида словарь, а deflate просто копирует уже декодированные куски); в интернете пишут, что LZW в 2 раза медленнее декодирует, чем deflate, в некоторых реализациях. Без Хаффмана LZW точно по-быстрее будет, но тоже не факт, что быстрее чем deflate. Так что zstd явно гораздо лучше в этом отношении и чем LZW, и чем deflate.
Я думаю, что это сделано для простоты реализации. LZW - очень простой но при этом эффективный алгоритм, который каждый может реализовать без мудрствований. Но если продолжать вашу мысль и довести её до идеала, то оптимально было бы применять для каждой фразы LZW адаптивное интервальное кодирование или что-то в этом духе. Тогда вся последовательность из z фраз LZW будет занимать всего log2(256) + log2(257) + ... + log2(255 + z) + 1 битов, ну или log2(256) + log2(257) + ... + log2(d) + log2(d) + ... + log2(d) + 1 битов, если размер словаря ограничен d фразами (например, d = 2^16, как обычно полагают). В стандартных реализациях LZW (типа LZC) тоже есть механизмы уменьшения размера кодов для первых фраз (хоть и не такие оптимальные): обычно первые фразы занимают последовательно 9, 10, ..., 16 битов, а потом словарь перестаёт расти. Вполне возможно, что на реальных датасетах этот простой трюк не намного хуже более хитрого оптимального кодирования. Вообще, если нужно сжатие по-лучше, то лучше сразу обращаться к LZMA, а не пытаться тюнить LZW.
Так что очень даже в тему это видео. Что позволено Юпитеру…
Эта модель, придуманная ещё в середине девяностых, несколько более сложна, чем традиционная RAM, поэтому под неё разработано меньше алгоритмов. Так получается, я полагаю, потому что при решении ещё нерешённой задачи люди сначала предпочитают всесторонне рассмотреть её в близкой (и часто практической), но более простой обычной RAM, а уже потом смотрят на кэш/внешнюю память/параллелизм.
Скорее всего вы правы, но всё таки есть немало программистов, которые краем уха где-то слышали об оптимальности LRU при каких-то условиях, что частично оправдывает его использование (смотрите мой комментарий выше).
Для любой константы c>1 и для любой последовательности s обращений к кэшируемым элементам (кэшируемые элементы имеют одинаковый размер) выполняется F_LRU(s) <= c F_OPT(s), где F_LRU(s) и F_OPT(s) — это число непопаданий в кэш на последовательности s для, соответственно, алгоритма LRU с размером кэша n и ясновидящего алгоритма OPT с размером кэша (1 — 1/c)n.
И обратно: для любого алгоритма кэширования A найдётся сколь угодно длинная последовательность s обращений к кэшируемым элементам, такая что F_A(s) >= c F_OPT(s), где F_A(s) — это число непопаданий в кэш на последовательности s для алгоритма A с размером кэша n, а у OPT опять размер кэша (1 — 1/c)n.
В случае произвольной строки ситуация несколько иная: вершин также не больше 2N+1, но может быть и меньше, чем N (например, для строки aaaaaaaaaaa суффиксное дерево содержит всего две вершины).
В тексте я неявно опирался на тот факт, что в дереве с n листьями, в котором у каждой нелистовой вершины есть как минимум два потомка, всегда O(n) вершин. Я не учёл, что это, вообще-то, не очень очевидно.
Надеюсь я смог ответить на ваш вопрос.