Смысл цитирования Гейтса в данной статье был не в самом Билле, а в книге о важности сна. Билл в данном контексте — это просто один из символов технологий, указанный, так как сама тема статьи о технологиях и жизни человека рядом с ними.
Можно вечно искать у всех богатых людей грязные миллионы, но не «тяните» это к статье, которая совсем о другом.
Так а почему нельзя использовать персистентное декартово дерево для обычного редактора без коллаборации?
В вершинах хранить блоки по x символов. При приближении размера блока к x / 2 или 2 * x мёрджить или сплитить вершины.
Для того, чтобы искать конкретную строку, можно поддерживать статистику в вершине о кол-ве переносов строк в поддереве и делать спуск по дереву.
Все операции за O(log n), и всё одной структурой. Правда, перс. ДД звучит не намного проще splay tree. Но если, у нас нет тысячи плагинов, code inspection и т.д., то от персистентности можно отказаться.
Ещё вариант без персистентности, использовать дерево отрезков или корневую декомпозицию, чтобы ещё проще писать. Опять же храним блоки по x, и при приближении блока к каким-то границам k * x и x / k перестраивать всю структуру. Амортизированно можно добиться O(log n), O(sqrt(n)). Правда, при перестроении редактор будет зависать, но это можно делать в фоне, пока на экране всё будет дальше обновляться.
Хмм, действительно отличное решение. И ошибка будет меньше. Как-то я просто при виде задачи сразу подумал над быстрым поиском пути в дереве, а до DSU не догадался.
Можно ещё быстрее за O(log n) с помощью Heavy-Light Decomposition.
Представим всё в виде дерева (леса). По факту между каждой парой вершин есть два ориентированных ребра. В одну сторону мы делим, а в другую сторону умножаем на одну и ту же величину. Поэтому можно мысленно представить неориентированный граф и найти в нём любое остовное дерево. Выберем в качестве корня центроид для лучшей константы. И снова мысленно направим рёбра в сторону от корня к листам. Назначим, каждому ребру коэффициент так, чтобы в сторону от корня к листу умножать, а в обратную делить. Теперь можно сделать HLD — разбить дерево на log путей. Затем на каждом пути сделать структуру, позволяющую быстро считать произведение. Мы можно использовать ту же идею, что и в частичных суммах: посчитаем произведения на префиксах. Ответ: pref[r] / pref[l — 1]. Всё построение выполняется за O(V + E), т. к. используются только обходы в глубину.
Теперь как искать ответ. Коэффициент между двумя единицами измерения — произведение/отношение коэффициентов на пути. Простой путь в дереве между любой парой вершин единственнен; — это путь a -> lca(a, b) -> b. Ответ: f(lca(a, b) -> b) / f(a -> lca(a, b)). Он ищется за O(log n) — не более log путей на запрос, в каждом из которых операция за O(1)
Лично мне в мобильном приложении очень не хватает фичи разделения лучших статей на лучшие за всё время, неделю и день, как в веб-версии. «Интересных» статей слишком много, а лучшие есть только за всё время — я их давненько все прочитал. Тратится слишком много времени просто на поиск хотя бы чего-то, что почитать вечерком.
Судя по поставленным в исследовании критериям, broadcast-сообщения по сети не приветствуются. Тогда несколько вопросов к экспертам. Чем же они так плохи? Можно ли реализовать их использование безопасно? И какие есть другие способы искать друг друга в локальной сети, если у нас DHCP?
На самом деле, самый важный момент в статье — что Телеграм не отобразил в списке сессий еще один левый сеанс. Это явная недоработка и уязвимость протокола.
Как вроде бы описано в статье, копирование всей папки телеграма привело к тому, что и файлы хранящие активные ключи сессии были скопированы. Зачастую, эти ключи самодостаточны и содержат информацию о клиенте, в том числе и мета-информацию о устройстве. Соответственно, сервер не нашёл отличий между подключениями, т.к., видимо, информация о сессии не хранится в объекте подключения, а в этих ключах. Хотя, судя по статье, сервер через какое-то время заметил несовпадения при копи-пасте, но не сделал этого при бэкапе. Здесь явно где-то баг.
Очень интересно. Я тоже занимаюсь разработкой игр. Тяну на своей горбатой спине сложный и непосильный проект, а именно action survival от первого лица. Есть товарищ, с которым мы все и затеяли, но толку от него ноль. Он как напридумает, а мне все делать. Если его о чем-нибудь попросить, внести вклад в проект, то фиг с маслом через месяц… Вобщем, классный пост. Если бы мог, то плюсанул и пост и карму
Интересно, довольно классно и игровая логика просчитана, но для такого проще будет написать целый движок с компилятором и программатором для Arduino. К тому же, я хочу сделать, в качестве следующего проекта, умные часы или голосовую систему управления.
Я смотрел вывод через VGA, но у меня возникло много вопросов, а еще, по-моему, телевизионная игровая приставка теряет часть от своего названия, именно, что она ТВ, а не VGA или «мониторная». К тому же, я хочу сделать, в качестве следующего проекта, умные часы или голосовую систему управления.
На обложке используется габаритная фотка с одной макеткой вместо геймпадов. Я их попросту не присоедил. Подумываю сделать ракетки с акселлерометрами в качестве контроллеров
Можно вечно искать у всех богатых людей грязные миллионы, но не «тяните» это к статье, которая совсем о другом.
В вершинах хранить блоки по x символов. При приближении размера блока к x / 2 или 2 * x мёрджить или сплитить вершины.
Для того, чтобы искать конкретную строку, можно поддерживать статистику в вершине о кол-ве переносов строк в поддереве и делать спуск по дереву.
Все операции за O(log n), и всё одной структурой. Правда, перс. ДД звучит не намного проще splay tree. Но если, у нас нет тысячи плагинов, code inspection и т.д., то от персистентности можно отказаться.
Ещё вариант без персистентности, использовать дерево отрезков или корневую декомпозицию, чтобы ещё проще писать. Опять же храним блоки по x, и при приближении блока к каким-то границам k * x и x / k перестраивать всю структуру. Амортизированно можно добиться O(log n), O(sqrt(n)). Правда, при перестроении редактор будет зависать, но это можно делать в фоне, пока на экране всё будет дальше обновляться.
Тогда непонятно, почему автор всю статью разбирал такое простое решение, если у неё существуют гораздо более эффективные, но не сильно более сложные.
Хмм, действительно отличное решение. И ошибка будет меньше. Как-то я просто при виде задачи сразу подумал над быстрым поиском пути в дереве, а до DSU не догадался.
Можно ещё быстрее за O(log n) с помощью Heavy-Light Decomposition.
Представим всё в виде дерева (леса). По факту между каждой парой вершин есть два ориентированных ребра. В одну сторону мы делим, а в другую сторону умножаем на одну и ту же величину. Поэтому можно мысленно представить неориентированный граф и найти в нём любое остовное дерево. Выберем в качестве корня центроид для лучшей константы. И снова мысленно направим рёбра в сторону от корня к листам. Назначим, каждому ребру коэффициент так, чтобы в сторону от корня к листу умножать, а в обратную делить. Теперь можно сделать HLD — разбить дерево на log путей. Затем на каждом пути сделать структуру, позволяющую быстро считать произведение. Мы можно использовать ту же идею, что и в частичных суммах: посчитаем произведения на префиксах. Ответ: pref[r] / pref[l — 1]. Всё построение выполняется за O(V + E), т. к. используются только обходы в глубину.
Теперь как искать ответ. Коэффициент между двумя единицами измерения — произведение/отношение коэффициентов на пути. Простой путь в дереве между любой парой вершин единственнен; — это путь a -> lca(a, b) -> b. Ответ: f(lca(a, b) -> b) / f(a -> lca(a, b)). Он ищется за O(log n) — не более log путей на запрос, в каждом из которых операция за O(1)