тут опять же не буду спорить т.к. эти соображения зависят от пары вещей:
вариант 2 ввиду амортизации неприменим на практике
это разумеется зависит от размера кэша и времени обращения к нижележащему хранилищу - если речь о кэшировании веб-страниц, условно, то флаш кэша занимающий 5мс очевидно ничтожен по сравнению с запросами в интернет занимающими в десятки и сотни раз больше; но конечно в задачах где нам нужен гарантированно быстрый отклик это действительно неудобно (впрочем в таких задачах и LRU-стратегия под вопросом - как пишет википедия, кэш в процессорах ARM вообще на рандомную стратегию переделали ради простоты и скорости - и норм)
Ну и использование итерации по мапе в качестве семплирования — не очень хорошо.
всё правильно, тут всё таки демонстрационная реализация :) к сожалению устройство и возможности мэпы конкретно в Go делают её особенно неудобной для любого "продвинутого" применения так что для реального кэша, так что в идеале нужна самодельная реализация
Спасибо за комментарий :) приятно что тема, несмотря на "туманность" действительно даёт повод повыдумывать дополнительные варианты!
Минимальное и максимальное значение храним в отдельных переменных.
Да, это вполне неплохой вариант у которого однако есть нюанс - он будет давать хорошие варианты если элементы используются более-менее равномерно.
Мы же счетчик увеличиваем как на Put-ах так и на Get-ах - и вот представим если к какому-то элементу (или нескольким, небольшому числу) внезапно возникла пиковая нагрузка - за счет него счётчик увеличится, скажем, на несколько тысяч очень быстро. И когда мы попытаемся выбрать 20% от разницы между минимумом и максимумом - то в удаляемые попадут внезапно все элементы кроме этого опрошенного тысячу раз.
Ну, это необязательно катастрофа, просто нужно иметь в виду такую возможность.
Т.е. ваш вариант это тоже некая "эвристика" имеющая право на существование :)
Значение счетчика используем по модулю равному максимальному размеру словаря.
или просто проходя кэш при операции очередного удаления уменьшаем все счетчики на фиксированную величину (например, min).
Честно было бы при сравнении давать последнему, "упрощенному" варианту меньше размер
тут я спорить не собираюсь т.к. с точки зрения данных внутри всё зависит от конкретного случая, конкретных данных. в классическом варианте две коллекции ключей а значений только одна, так выходит. в кэшах где значения "массивны" - ваше замечание абсолютно справедливо.
Еще непонятно, почему второй вариант быстрее первого. Не верю, что работа со списками настолько медлнее O(N) удаления.
тут кажется недопонимание :) удаление во втором варианте не O(N) а O(1) амортизированное - мы ведь договорились удалять группами - т.е. редко. это ещё в тестовом примере группа небольшая (треть что ли данных)
работа со списками не медленная сама по себе - нам всего лишь нужно переставить несколько указателей
проблема в том что это приходится делать на каждый Get - поэтому многие варианты оптимизации этого варианта связаны с тем чтобы этого всё-таки не делать так часто (правда это фактически делает кэш не строго LRU)
В целом же тесты и сравнение сделаны не для того чтобы показать что "это быстрее того" а просто продемонстрировать что они более-менее близки. Всё-таки разница не так велика чтобы из неё делать далеко идущие выводы. Много зависит от реализации мэпы например внутри языка...
а на процессорах не было не то что вентиляторов, но даже радиаторов
...
Это примерно как 486DX2 66 MHz.
нас не проведёшь :) радиатор был точно, хотя пропеллер более-менее опционально
а по существу - нам-то стар...рам вспомнить мило (и даже со слезой взглянуть в собственную папочку-копилку с подобными экспериментами) - но в современной реальности по-моему слово "ротозумер" и то проассоциируют с чем-то другим :)
с другой стороны такое ощущение немножко, знаете, машина голдберга для стрельбы из пушки по воробьям. (ну или для собственного развлечения программиста, что неплохо)
читатель пробегая текст "по диагонали" не будет особо разбираться как именно закругляли уголки. а уж если текст будет разбирать LLM как сейчас модно, чтобы представить "выжимку" то тем более :)
особенно прекрасно в исполнении эйчаров от яндекса, уж извиняюсь за прямоту
которым уже три раза сказано "не пишите мне, тем более не лезьте в телеграм который вообще не указан в контактах" - и спустя несколько месяцев всё то же :)
я это к чему. забавная статья, которая имела бы смысл лет 15-20 назад
но сейчас рекрутинг настолько в странную сторону поменялся, что писать в духе "кандидаты глупые, а HR-ы пушистые" - это прям скажем небезопасно
У меня ещё 800 непросмотренных, а сегодня нужно закрыть три позиции.
вот именно. здесь проблема. сейчас рекрутинговый аппарат в конторах настроили на идею "возьмём количеством а не качеством". ну или проблема в том что теперь жалуются, плачут, жрут кактус но упорно не хотят что-то менять. даже углубляют. выделили низшую касту рекрутёров в "сорсеров" и какой-то магии от этого ждут
не в курсе, где он нашумел и кто это такой, но было бы здорово если бы автор не переводил всю эту огромную портянку а выжал бы обычную для таких случаев воду и представил бы мысль по существу. в принципе вполне можно ещё это сделать и добавить вверху статьи как "abstract"
Ну вот реально:
Если вы ещё не знаете То прочтя эту статью узнаете Я это узнал потому что не знал а теперь знаю Скоро узнаете и вы Другие не знали но потом узнают и будут рыдать Моя семья, я пишу это для них (а зачем мы читаем?) ИИ, мы не знали, но знание одухотворяет И тррррррррррррррррр...
Задачи забавные, хотя кажется что на собеседовании такое встретить можно только в какой-то фантасмагорической конторе. Да, припоминаю, в Biocad мне показывали задачку которая хитроумным образом сводится к перемножению с помощью БПФ или что-то в этом духе - но представляется что процент задач и соискателей такого класса очень невелик :)
В любом случае спасибо за статью. Наверное аккуратнее было бы назвать эту штуку "принципом" или "идеей" нежели "структурой данных" (т.к. данные она эффективно профукивает по большей части, она не для хранения строго говоря) - но в качестве "очертить общий подход" - это очень хорошо!
Ну и конечно использование реального стека в вашем коде не выглядит супер-эффективным - вместо этого поштучного "попанья" надо использовать обычный массив с указателем на "верхушку" и двоичным поиском находить куда вставляется очередной элемент и "переключается" указатель.
Спасибо за столь подробный обзор... но если честно
Go 1.26 стал релизом, в котором сошлись результаты нескольких лет работы над разными направлениями. Это не просто набор отдельных улучшений, а согласованное развитие языка,
вот реально выглядит что набор мелких второстепенных улучшений. ничего такого чтобы сказать "вах". ничего такого ради чего чувствовалось бы обоснованное желание скорее обновляться :)
без претензий, к автору, но кажется что разработчики языка отчаянно стагнируют, возможно у них все время уходит на отклонение запросов типа "сделайте наконец тернарный оператор" в гитхабе :)
Не серчайте, но кажется было бы хорошо если бы из первой пары абзацев можно было понять что собой представляет приложение "Заметки" и что за редактор из него рождали.
Статья взяв "с места в карьер" как бы подразумевает что читатель должен быть в курсе что такое KvadraOS, почему нужно делать приложение с нуля а нельзя взять какое-то готовое (написано же - Android-разработчик - и что, под андроид не нашли ничего? - подумает читатель) - а тут где-то ближе к середине становится ясно что вроде редактор заметок должен быть со стилями (зачем? я не знаю).
Иными словами автор немножко на своей волне, он знает свою задачу, знает проделанную работу и настолько спешит поделиться что предполагает что как минимум половина из этого уже известна и читателю. Вполне возможно такие читатели есть, но я бы не стал делать ставку на то что их много :)
Откуда информация про "под капотом передается указатель"?
в статье ссылка на исходник реализации функции отправки - посмотрите пожалуйста внимательно. она указатель принимает.
ниже в комментариях есть и дизассемблированный код.
мы выполняем функцию, которая замкнула переменную i и изменяет ее внутри тела
в ваших размышлениях отсутствует какое-либо логическое объяснение того почему переменная либо "замыкается" либо нет в зависимости от того прибавляется к ней ноль или нет.
замкнула переменную i и изменяет ее внутри тела
какая функция "замкнула" переменную и "изменяет" её? вы о чём? внешняя её изменяет но не замыкает (т.к. переменная глобальная) а внутренняя замыкает но не изменяет
Не серчайте, но озадачивает идея статьи. Rust - язык с довольно уникальным способом обращения с памятью. В то же время Go использует максимально широко распространённый способ (с небольшими нюансами). Если цель была показать чем интересен и хорош Rust, это лучше было писать "Rust vs All" (подразумевая все прочие языки с автоматическим управлением памятью или как это лучше сказать). А так если придёт почитать человек с бэкграундом в Java или C++ то по этой статье он вынужден будет 60% времени погружаться в детали организации памяти в Go и пытаться понять нужны ему эти детали или нет.
А так написано в достаточно технически подробно, конечно.
нет, как раз копия значения не уходит. канал оперирует ссылками, именно поэтому в примере без прибавления нуля в канал уходит значение взятое по указателю (фактически переданному в канале) - то есть значение на момент вычитывания а не на момент отправки
в том что отправляемое выражение вычисляется в разные моменты в зависимости от того что в этом выражении написано - либо до инструкции <- либо уже при вычитывании (и тут даже буфер не при чем)
Вы абсолютно правы, по крайней мере с "формальной" кочки зрения :)
Но с точки зрения практической получается такая шляпа: Go сейчас занял нишу языка на который "несложно быстро мигрировать" например с Java или C++ (и получить от этого некоторые преимущества). Это влечёт за собой стремление сделать язык достаточно предсказуемым для новичков и "защищённым от дураков". Во многих отношениях эта "политика" действительно прослеживается. Например Go Memory Model настойчиво просит чтобы записи чисел и указателей влезающих в машинное слово были атомарны, и дата рейс на них никогда не приводил бы к проблемам (если бы не это, количество багов в существующем go-шном коде было бы на порядки больше).
С этой точки зрения проектировать язык так чтобы он работал ожидаемо только в расчете на очень грамотного и внимательного программиста - явное отступление от этой стратегии. Тем более здесь фикс возможен тривиальный (как коллеги упомянули выше).
тут опять же не буду спорить т.к. эти соображения зависят от пары вещей:
это разумеется зависит от размера кэша и времени обращения к нижележащему хранилищу - если речь о кэшировании веб-страниц, условно, то флаш кэша занимающий 5мс очевидно ничтожен по сравнению с запросами в интернет занимающими в десятки и сотни раз больше; но конечно в задачах где нам нужен гарантированно быстрый отклик это действительно неудобно (впрочем в таких задачах и LRU-стратегия под вопросом - как пишет википедия, кэш в процессорах ARM вообще на рандомную стратегию переделали ради простоты и скорости - и норм)
всё правильно, тут всё таки демонстрационная реализация :) к сожалению устройство и возможности мэпы конкретно в Go делают её особенно неудобной для любого "продвинутого" применения так что для реального кэша, так что в идеале нужна самодельная реализация
Спасибо за комментарий :) приятно что тема, несмотря на "туманность" действительно даёт повод повыдумывать дополнительные варианты!
Да, это вполне неплохой вариант у которого однако есть нюанс - он будет давать хорошие варианты если элементы используются более-менее равномерно.
Мы же счетчик увеличиваем как на Put-ах так и на Get-ах - и вот представим если к какому-то элементу (или нескольким, небольшому числу) внезапно возникла пиковая нагрузка - за счет него счётчик увеличится, скажем, на несколько тысяч очень быстро. И когда мы попытаемся выбрать 20% от разницы между минимумом и максимумом - то в удаляемые попадут внезапно все элементы кроме этого опрошенного тысячу раз.
Ну, это необязательно катастрофа, просто нужно иметь в виду такую возможность.
Т.е. ваш вариант это тоже некая "эвристика" имеющая право на существование :)
или просто проходя кэш при операции очередного удаления уменьшаем все счетчики на фиксированную величину (например, min).
тут я спорить не собираюсь т.к. с точки зрения данных внутри всё зависит от конкретного случая, конкретных данных. в классическом варианте две коллекции ключей а значений только одна, так выходит. в кэшах где значения "массивны" - ваше замечание абсолютно справедливо.
тут кажется недопонимание :) удаление во втором варианте не O(N) а O(1) амортизированное - мы ведь договорились удалять группами - т.е. редко. это ещё в тестовом примере группа небольшая (треть что ли данных)
работа со списками не медленная сама по себе - нам всего лишь нужно переставить несколько указателей
проблема в том что это приходится делать на каждый Get - поэтому многие варианты оптимизации этого варианта связаны с тем чтобы этого всё-таки не делать так часто (правда это фактически делает кэш не строго LRU)
В целом же тесты и сравнение сделаны не для того чтобы показать что "это быстрее того" а просто продемонстрировать что они более-менее близки. Всё-таки разница не так велика чтобы из неё делать далеко идущие выводы. Много зависит от реализации мэпы например внутри языка...
нас не проведёшь :) радиатор был точно, хотя пропеллер более-менее опционально
а по существу - нам-то стар...рам вспомнить мило (и даже со слезой взглянуть в собственную папочку-копилку с подобными экспериментами) - но в современной реальности по-моему слово "ротозумер" и то проассоциируют с чем-то другим :)
тот случай когда анализируемое короче анализатора, не серчайте пожалуйста :)
С одной стороны - круто, плюсую :)
с другой стороны такое ощущение немножко, знаете, машина голдберга для стрельбы из пушки по воробьям. (ну или для собственного развлечения программиста, что неплохо)
читатель пробегая текст "по диагонали" не будет особо разбираться как именно закругляли уголки. а уж если текст будет разбирать LLM как сейчас модно, чтобы представить "выжимку" то тем более :)
Об использовании LLM для чтения бесполезных текстов написанных другими LLM :)
ну, резонно, от характера данных зависит
но кстати отсюда может получиться интересный кейс иллюстрирующий пример что бинарный поиск вовсе необязательно должен делить ровно пополам :)
особенно прекрасно в исполнении эйчаров от яндекса, уж извиняюсь за прямоту
которым уже три раза сказано "не пишите мне, тем более не лезьте в телеграм который вообще не указан в контактах" - и спустя несколько месяцев всё то же :)
я это к чему. забавная статья, которая имела бы смысл лет 15-20 назад
но сейчас рекрутинг настолько в странную сторону поменялся, что писать в духе "кандидаты глупые, а HR-ы пушистые" - это прям скажем небезопасно
вот именно. здесь проблема. сейчас рекрутинговый аппарат в конторах настроили на идею "возьмём количеством а не качеством". ну или проблема в том что теперь жалуются, плачут, жрут кактус но упорно не хотят что-то менять. даже углубляют. выделили низшую касту рекрутёров в "сорсеров" и какой-то магии от этого ждут
попробуйте оценивать статьи по содержанию а не по просмотрам
для примера, если 77 миллионов американцев проголосовали за престарелого идиота, то он от этого не перестаёт быть престарелым идиотом
(не экстраполируя этот пример на вашего автора)
не в курсе, где он нашумел и кто это такой, но было бы здорово если бы автор не переводил всю эту огромную портянку а выжал бы обычную для таких случаев воду и представил бы мысль по существу. в принципе вполне можно ещё это сделать и добавить вверху статьи как "abstract"
Ну вот реально:
Если вы ещё не знаете
То прочтя эту статью узнаете
Я это узнал потому что не знал а теперь знаю
Скоро узнаете и вы
Другие не знали но потом узнают и будут рыдать
Моя семья, я пишу это для них (а зачем мы читаем?)
ИИ, мы не знали, но знание одухотворяет
И тррррррррррррррррр...
Задачи забавные, хотя кажется что на собеседовании такое встретить можно только в какой-то фантасмагорической конторе. Да, припоминаю, в Biocad мне показывали задачку которая хитроумным образом сводится к перемножению с помощью БПФ или что-то в этом духе - но представляется что процент задач и соискателей такого класса очень невелик :)
В любом случае спасибо за статью. Наверное аккуратнее было бы назвать эту штуку "принципом" или "идеей" нежели "структурой данных" (т.к. данные она эффективно профукивает по большей части, она не для хранения строго говоря) - но в качестве "очертить общий подход" - это очень хорошо!
Ну и конечно использование реального стека в вашем коде не выглядит супер-эффективным - вместо этого поштучного "попанья" надо использовать обычный массив с указателем на "верхушку" и двоичным поиском находить куда вставляется очередной элемент и "переключается" указатель.
Спасибо за столь подробный обзор... но если честно
вот реально выглядит что набор мелких второстепенных улучшений. ничего такого чтобы сказать "вах". ничего такого ради чего чувствовалось бы обоснованное желание скорее обновляться :)
без претензий, к автору, но кажется что разработчики языка отчаянно стагнируют, возможно у них все время уходит на отклонение запросов типа "сделайте наконец тернарный оператор" в гитхабе :)
Не серчайте, но кажется было бы хорошо если бы из первой пары абзацев можно было понять что собой представляет приложение "Заметки" и что за редактор из него рождали.
Статья взяв "с места в карьер" как бы подразумевает что читатель должен быть в курсе что такое KvadraOS, почему нужно делать приложение с нуля а нельзя взять какое-то готовое (написано же - Android-разработчик - и что, под андроид не нашли ничего? - подумает читатель) - а тут где-то ближе к середине становится ясно что вроде редактор заметок должен быть со стилями (зачем? я не знаю).
Иными словами автор немножко на своей волне, он знает свою задачу, знает проделанную работу и настолько спешит поделиться что предполагает что как минимум половина из этого уже известна и читателю. Вполне возможно такие читатели есть, но я бы не стал делать ставку на то что их много :)
в статье ссылка на исходник реализации функции отправки - посмотрите пожалуйста внимательно. она указатель принимает.
ниже в комментариях есть и дизассемблированный код.
в ваших размышлениях отсутствует какое-либо логическое объяснение того почему переменная либо "замыкается" либо нет в зависимости от того прибавляется к ней ноль или нет.
какая функция "замкнула" переменную и "изменяет" её? вы о чём? внешняя её изменяет но не замыкает (т.к. переменная глобальная) а внутренняя замыкает но не изменяет
вы то ли не прочли статью, то ли прочли как-то не так. непонятно что случилось, простите :)
Не серчайте, но озадачивает идея статьи. Rust - язык с довольно уникальным способом обращения с памятью. В то же время Go использует максимально широко распространённый способ (с небольшими нюансами). Если цель была показать чем интересен и хорош Rust, это лучше было писать "Rust vs All" (подразумевая все прочие языки с автоматическим управлением памятью или как это лучше сказать). А так если придёт почитать человек с бэкграундом в Java или C++ то по этой статье он вынужден будет 60% времени погружаться в детали организации памяти в Go и пытаться понять нужны ему эти детали или нет.
А так написано в достаточно технически подробно, конечно.
нет, как раз копия значения не уходит. канал оперирует ссылками, именно поэтому в примере без прибавления нуля в канал уходит значение взятое по указателю (фактически переданному в канале) - то есть значение на момент вычитывания а не на момент отправки
в том что отправляемое выражение вычисляется в разные моменты в зависимости от того что в этом выражении написано - либо до инструкции
<-либо уже при вычитывании (и тут даже буфер не при чем)Вы абсолютно правы, по крайней мере с "формальной" кочки зрения :)
Но с точки зрения практической получается такая шляпа: Go сейчас занял нишу языка на который "несложно быстро мигрировать" например с Java или C++ (и получить от этого некоторые преимущества). Это влечёт за собой стремление сделать язык достаточно предсказуемым для новичков и "защищённым от дураков". Во многих отношениях эта "политика" действительно прослеживается. Например Go Memory Model настойчиво просит чтобы записи чисел и указателей влезающих в машинное слово были атомарны, и дата рейс на них никогда не приводил бы к проблемам (если бы не это, количество багов в существующем go-шном коде было бы на порядки больше).
С этой точки зрения проектировать язык так чтобы он работал ожидаемо только в расчете на очень грамотного и внимательного программиста - явное отступление от этой стратегии. Тем более здесь фикс возможен тривиальный (как коллеги упомянули выше).