#Введение#
Решал задачки на LeetCode и вот небольшой переводик небольшой статьи про небольшой алгоритм.
Алгоритм голосования Бойера-Мура является одним из самых популярных и оптимальных алгоритмов, который используется для поиска преобладающего элемента среди заданных, который имеет более N / 2 вхождений. Алгоритм выполняет 2 обхода по заданным элементам, что работает при O (N) временной сложности и O (1) пространственной сложности.
Числа — совершенно особенная категория текстовых объектов. Они могут быть представлены разными способами: от зачастую многословного и не всегда согласованного между собой ряда убывающих числительных до записи арабскими или римскими цифрами, с разбивкой запятыми или точками, с пробелами или без них.
Не проще обстоят дела и с программным представлением таких объектов.
Представьте на секунду, что вы очень азартный игрок, который только что попал в казино и не может выбрать, за какой игровой автомат ему сесть. Или один муравей из колонии, выбирающий по какому пути ему пойти на поиски пищи. Или даже вы – это целый маркетплейс, который думает, какую же цену, ему поставить на тот или иной товар!
На первый взгляд может показаться, что все эти странные ситуации никак не связаны. Но это только на первый взгляд. Если откинуть все необычность ситуации, то перед нами дилемма исследования-использования. Посудите сами: как азартный игрок, вы хотите найти автомат, дающий больше всего денег – это использование, но вы не знаете, какой это автомат и ищите его, дергая ручки и сравнивая выигрыши – это исследование. Как часто вам нужно подходить к игровому автомату, который, по вашему мнению самый прибыльный, а как часто нужно сомневаться в этом и пробовать другие? Как часто муравью нужно идти по тому пути, где товарищи-муравьи уже протоптали тропинку, а как часто стоит рискнуть и пойти своей дорогой? Как часто нужно менять цену, чтобы поспевать за инфляцией и спросом пользователей, а еще при этом максимизировать прибыль?
Одним днем возникла необходимость добавить в проект генерацию коротких css классов и id элементов в html верстке. Основные причины были следующие:
* Усложнить жизнь парсерам и блокировщикам рекламы (они зачастую на имена классов опираются).
* Уменьшить размер html страниц
* И чтобы все было как у Google, шутка ?
Очевидно, что минификация классов и id полностью не защитит от парсеров, как говорится, лучшая защита от парсинга – удалить страницу из интернета. Но данный подход может отбить охоту у вчерашних студентов с фриланс биржи зарабатывать на парсинге, или защитить от универсальных ботов-парсеров.
У вас бывало, что открываешь поиск, ищешь что-то по программированию и не находишь ответ? Тогда эта история для вас.
Меня зовут Алексей Степанов, я руковожу службой исследований машинного обучения поиска Яндекса. Сегодня я расскажу непростую историю. Она про проблему, до решения которой у нас слишком долго не доходили руки. Из поста вы узнаете, почему стандартная метрика качества поиска не учитывала интересы разработчиков и как мы её улучшили. Расскажу про новую нейросеть CS YATI, обученную понимать таких же айтишников, как и мы. Ну и про грабли на нашем пути тоже расскажу, куда без них.
Этот пост основан на моём докладе с Data Fest 2022, но не во всём (мой коллега Максим Хурсанов @Maxim2207 существенно расширил историю).
Всем доброго времни суток, для начинающего программиста (коим я и являюсь) реализация базовых структур данный, по типу бинарных деревьев и связных списков, довольно легка. Чего не скажешь о хэш картах.
В данной статье рассматриваются алгоритмы абстрактного мышления и механизм побуждения разума к действию. Это мышление - главная загадка современности и есть мнение, что компьютер не в силах ее решить, что только душа человека на это способна. Что сначала будет создана урезанная версия ИИ, а только потом будет создан сильный ИИ похожий на человеческий.
Основываясь на том, что:
• мышление основано на картах реальности, см статья теория алгоритма лежащего в основе фантазирования реальностью в мозге.
• мышление основано на сценах, которые предполагают варианты действий разуму в реальности, пример ниже.
• мышление основано на словах, и слова несут информацию.
• смысл слов существующих в реальности (люди, предметы) описан в статье теория алгоритма, дающего смысл словам.
• есть закономерность, что в биологии эволюция идет через создание копий генов с небольшим изменением их функций и гены несут в себе алгоритмы мышления.
• что алгоритм распознавания в визуальной информации стилей и текстур очень многогранен (см. статья теория групп слов, на базе которых работает мышление) и участвует в мышлении, имея разный смысл у различных групп слов.
• мышление рекурсивное, т.е. думая мы повторяем одно и тоже действие (мысль) и что то придумываем.
• есть гипотезы, что за всей работой мозга стоит несложный алгоритм, например фрактал. Хотя считается, что за всем стоят нейросети с еще неопределенными параметрами.
Абстрактное мышление это умение с помощью переноса сознания в абстрактный мир и исследуя вопрос или проблему с разных вариантов в этом мире, правильно либо ее описать, либо решить. Упрощенно мышление с реальными объектами в данной теории (см. рис. 1)
"По классике" FIFO-очередь для обработки некоторого потока задач обычно реализуется в виде связанного списка элементов. Но для JavaScript такой подход нехорош - он требует либо создания "обвязки" над элементом очереди в виде дополнительного объекта, содержащего ссылки на сам элемент и указатель на следующий, либо превращения элемента в объект и расширения его таким же указателем.
В таких нагруженных системах, как коллектор нашего сервиса мониторинга PostgreSQL-серверов, создание и последующая подчистка Garbage Collector'ом подобных избыточных объектов и полей - непозволительная роскошь.
Но если внимательно посмотреть на эту схему, то можно заметить, что сами элементы очереди A, B, C линейно упорядочены. Так нельзя ли использовать в качестве очереди обычный массив с его .push() и .shift()?..
Насколько это будет эффективно, какие грабли встретятся на этом пути, и как их можно обойти - сегодня об этом.
С тех пор как мир возник во мгле
Нет ничего на свете более интересного лично для
Исследователя и одновременно полезного для
Человечества, чем позна́ние окружающего Мира.
Валерий Баканов. Крым, Щёлкино/Казантип, август 2022.
Данная публикация предназначена для Исследователей, которым не жаль с пользой употребить своё время для практического количественного углу́бленного понимания свойств внутреннего (скрытого) параллелизма в алгоритмах и его, на́йденного параллелизма, рационального использования в вычислительных практиках. Рациональное использование имеющегося в алгоритмах параллелизма определяется набором приёмов, позволяющих получить наиболее приемлемый (по разумным параметрам) план (расписание) выполнения рассматриваемого алгоритма (программы) на заданном поле параллельных вычислителей. Т.к. конечная (реализуемая в процессе собственно вычислений) последовательность выполнения команд неминуемо я́вится всё же несколько иной относительно разработанного на данном этап ие плана вычислений, логично назвать результат данного анализа каркасом плана (расписания) параллельных вычислений.
Алгоритм является результатом разумной деятельности человечества и отражает в себе (в опосредованном виде, конечно) наиболее глуби́нные, фундаментальные законы развития Природы. Одно это является вполне обоснованной необходимостью исследования характеристик алгоритмов.
Ряд лет интересом пользовалось изучение параметров вычислительной трудоёмкости (фактически зависимости числа вычислительных операций от размерности обрабатываемых данных) для различных алгоритмов. Параметры параллелизма в алгоритмах – очередная сторона многогранной сущности “алгоритм”. В современной ситуации отечественным разработчикам придётся самостоятельно исследовать и решать все связанные с автоматизированной обработкой данных вопросы – время “неограниченной халявы” (когда можно было десятилетиями бездумно копировать западные разработки в области архитектуры и готовых решений аппаратной и программной частей) закончилось.
Ещё никто на всей земле
Не предава́лся сожаленью
О том, что о́тдал жизнь ученью.
Абу Абдалла́х Рудаки́, Бухара, около 860÷941.
Всем ведь приходилось заниматься улучшением производительности? Для игр особенно актуально, ну может какая-то три-в-ряд не страдает этим. Как обычно серебряной пули нет, начинаем со структур данных, алгоритмов, спускаемся ниже если не помогает, придумываем SoA, AoS шаблоны. Если проблема не решается, подтягиваем профайлеры и предметно разбираем узкие места, но все чтобы мы не делали зачастую таким узким местом всегда будет "железо". Можно сколько угодно оптимизировать другие места, но CPU c его гигагерцами будет простаивать 90% времени если его неправильно "кормить" данными. Одной (только одной из проблем) проблемой организации эффективной работы с данными будет меньше, если знать и уметь работать с кэшами разных уровней. Тут на вики описано, как "на пальцах" быстренько убить перф на обходе массива, простого и общего решения для такого обхода нет. Можно и дальше увеличивать размер кэша, что собственно и делают (гдето здесь на хабре была новость, что Интел при переходе на L1 кэш размером 32кб, заново спроектировал блок доступа к нему, сорян не нашел ссылку), но это дорого, неэффективно на масштабах современных процов, и всегда найдутся данные, которые этот кэш отравят, опять. Интересно как починить? го под кат...
Обучение с самоконтролем позволяет нейронной сети самостоятельно выяснить, что имеет значение. Этот процесс может быть тем, что делает наш собственный мозг таким успешным.
Вот уже десять лет многие из самых впечатляющих систем искусственного интеллекта обучаются с использованием огромного количества размеченных данных. Изображение может быть помечено как «полосатый кот» или «тигр», например, чтобы «обучить» искусственную нейронную сеть правильно отличать полосатого кота от тигра. Стратегия оказалась одновременно впечатляюще успешной и прискорбно несовершенной.
Немного о генерации случайных чисел в рамках программирования. Для новичков.
Это мой первый серьёзный пост на подобную тему. В первую очередь я хочу очертить суть данной статьи. Тут я не буду разбирать полностью тему о генерации случайных чисел самим компьютером, за исключением одного термина для понимания разницы между Генерацией истинно случайных чисел(ГСЧ) и генерацией псевдослучайных чисел (ГПСЧ). Тут мы больше поговорим об алгоритмах которые используют языки программирования для генерации случайных чисел, и о том, почему они не случайны и не могут быть таковыми. Эта статья предназначена для тех программистов, которые минимум уже освоили функцию генерирующую случайные числа в своем языке, и хотят понять глубже эту тему. Я считаю эта тема одна из самых важных и в какой то степени сложной. Случайные числа очень полезны в различного рода алгоритмах, и понимание того, как они работают, возможно в будущем помогут вам сделать, что-то невероятное или просто полезное. А в конце я покажу свою псевдо-удачную попытку изобрести свой генератор псевдослучайных чисел.
Как я уже писал ранее, на FPS в Flame в основном влияют операции, производимые на CPU. Если в вашей игре достаточно много взаимодействующих объектов, то одной из самых дорогих операций будет определение столкновений. Настолько дорогой, что на экране performance-метрики она закроет собой любые другие неоптимизированные участки.
Сами авторы Flame отлично осознают, что их алгоритм – не идеальный, а просто «дающий достаточную производительность». Достаточна она, видимо, для случаев, когда у вас всего объектов 10, не более. Если же у вас что-то более сложное – тогда приятного чтения!
Нашел я недавно в закромах старый оптический диск (CD). Открыл его в проводнике и не могу зайти ни в одну папку. Протёр диск. Попробовал снова - та же оказия. Царапины на диске конечно есть, но не много и не сильные. Решил воспользоваться специальным софтом BadCopy. Половина мелких файлов восстановилась, половина нет. Большие файлы восстановились не полностью. В итоге в двух повреждённых архивах (повреждено 2% и 10%) я обнаружил один и тот же файл. При попытке его извлечь вылезала ошибка CRC. Но если в WinRAR при извлечении установить галочку "Keep broken files", то извлекается как есть. Так как мой файл был дорог мне как воспоминание и был небольшим - всего 640 КБ, я решил заморочиться. Там же в WinRAR, кстати, можно узнать оригинальный размер файла и его CRC32.
Итак, у нас есть две повреждённые версии файла, его длина и даже его CRC32, нужно восстановить оригинал. Что может быть проще?
В один прекрасный день, стреляя по NPC в космосе, мне стало интересно, а смогу ли я этот рутинный процесс немного автоматизировать.
Выводить в консоль «Привет, мир!» я уже умел.
Теоретическое представление, что нужно делать, так же имелось.
Оставалось дело за малым - реализовать задумку.
Изначальная цель была простой - определять, что дронов в космосе атакуют и собирать их в ангар, после чего выкидывать обратно в космос.
Продолжаем решать задачу описанную в предыдущей статье: Есть n стандартных игральных костей (6-ти гранных кубиков) со стандартным обозначением всех граней от 1 до 6. Бросаем все n кубики разом. Нужно найти вероятность выпадения числа k, а именно суммы всех значений, выпавших на этих кубиках. Доходим до 1000 кубиков.
Существуют ограниченное число алгоритмов в нашем разуме, но их почему то, не удается выделить по отдельности и понять. Дело в том, что один и тот же алгоритм проявляет себя по разному в разных группах слов. Эта статья продолжает рассматривает идеи из статьи теория алгоритма, лежащего в основе разума.
Исходя из того, что слова делятся на группы по смыслу и для каждой из них есть свои правила (Статья про семантические карты мозга). Трудность понимания моделирования в человеческой психике в том, что все разделено на группы, и в анализируемом предложении могут быть слова из разных групп со своими законами и с разными правилами взаимодействия между словами различных групп. Например, в книге написано про общение людей в замке, и описаны окружающие людей предметы, и указано, что люди видят. В итоге, в модели присутствует слишком много различных правил для разных групп слов, что бы их можно было обобщить.
В мозге есть карта реальности и есть общий план действий (см. рис. 1). По плану надо перейти через переход. Человек стоит перед переходом и мозг ищет в памяти сцены ко всему, что на карте. Потенциальных сцен много, но учитывая план, что надо перейти через дорогу, мозг находит сцену с переходом, светофором (они есть на карте местности) и с результатом действия, который подходит к плану. Сцена это кусочек карты, но например, на карте светофор имеет свое место, а на сцене он находится в какой то зоне (это понято на основе опыта).
Наверняка многие бекенд программисты сталкивались с задачей ограничением запросов к некоторому источнику данных. Существует множество решений этой проблемы:
1) хранить историю во внешнем источнике данных, как redis. Для вычисления возможности отправить запрос, нужно каждый раз ходить в этот источник данных, что может быть непозволительно в некоторых сферах (так как существенно увеличивается время обработки запроса)
2) не париться с limiter и анализировать ответ от внешнего источника данных и на основе его ответов, принимать решение когда и сколько запросов можно отправить (но такие ответы есть не у каждого сервиса и существует вероятность, что будут отправлены лишние запросы, что может привести к бану)
3) хранить историю запросов локально, но использовать алгоритм leaked bucket, но это не позволяет накидать несколько запросов и ждать
4) хранить историю запросов локально, но использовать алгоритм sliding window, можно накидать запросов и ждать какое-то известное время
О реализации sliding window для java пойдет речь в этой статье.
Всем привет! Меня зовут Хусрав, я бэкенд разработчик в компании Bimeister.
В этой статье я бы хотел бы поговорить о способе поиска родительских и дочерних элементов структуры посредством PostgreSQL Materialized Path.
Статья является вводной и рассчитана на людей, незнакомых с темой.
