В голову пришла мысль, что врачи могут всё писать на бумаге, чтобы было быстро, а потом эти бумаги уносят синкаться в базу.
Выйгрыш в том, что вбивальщики просто сидят на конвеере, не отвлекаются на врача с пациентом и не сбивают ритм. И главное, их нужно гораздо меньше, чем в каждый кабинет.
С чуваками ещё оставлять на смене какого-нибудь врача, чтобы он если что помогал.
Основная разновидность — линейные массивы, или одноразмерные.
Их размер статичен, то есть при объявлении линейного массива задаётся фиксированный размер.
Неясно, почему линейные массивы противопоставляются динамическим. Подразумевались, очевидно, статические массивы.
Действительно, вставка в динамический массив происходит за O(n), но эта информация не очень полезна без того факта, что в силу мультипликативной стратегии реаллокации амортизиованная сложность вставки получается O(1), то есть последовательная вставка n элементов произойдёт не за O(n^2), как можно было бы подумать, а за O(n).
Данные хранятся в узлах, указывающих на другие узлы.
Узел содержит один элемент данных и одну ссылку (на другой узел).
Связный список соединяет узлы друг с другом с помощью ссылок от одного узла к другому.
Под определение, которое дано в статье подходит всякая ересь, например:
Оптимизированный поиск: связный список — O(n).
Неясно, что такое оптимизированный поиск в связном списке.
(оффтоп: чутка развив идею списка можно делать на нём аналог двоичного поиска, гуглить skip list).
Этот процесс называется хэшированием: однозначным сопоставлением друг другу входных и выходных данных.
Вот это жесть, конечно. Конечно, хэширование не занимается однозначным сопоставлением, потому что значений хэшей должно быть меньше, чем значений хэшируемых объектов, чтобы это имело хоть какой-то смысл.
Хэш-коллизиями называются ситуации, когда для двух разных входных данных функция возвращает одинаковые выходные данные.
Эта проблема свойственна всем хэш-функциям.
Часто она решается с помощью увеличения хэш-таблиц до огромного размера.
Решается она не так, конечно, а с помощью использования стратегий разрешения коллизий. Гуглить цепочки, линейное разрешение, двойное хэширование, хэширование кукушки.
Двоичное дерево — это такая структура данных, в которой каждый узел имеет максимум два дочерних элемента.
Дочерние элементы бывают левым и правым.
При этом у каждой вершины не больше одного левого сына и не больше одного правого.
Все эти операции работают за O(высота дерева). Если дерево сбалансированное, то тогда это действительно O(log N), но само по себе дерево сбалансированным навряд ли станет.
Существуют хитрые двоичные деревья, которые всегда остаются сбалансированными. Гуглить, например, красно-чёрное дерево, AVL-дерево, splay-дерево.
Поиск в ширину оптимален для поиска по дереву, чья ширина превышает глубину.
Это почему вдруг? С точки зрения времени алгоритм всегда обработает каждую вершину 1 раз, а каждое ребро – 2 или 1 раз (в зависимости от того, ориентированный граф или нет). Если же хочется пооптимизировать память, то поиск в ширину наоборот тратит меньше памяти на очередь на «глубоких узких» графах (потому что слои получаются маленькие).
В связи с использованием очереди такой метод поиска потребляет больше памяти, чем поиск в глубину.
Ну неясно. Поиск в глубину же стек поддерживает пока ходит (неявно, через рекурсию). Те же самые O(V) памяти.
E — количество рёбер (граней?).
Рёбер. Грань – область, ограниченная рёбрами в плоском графе и не содержащая внутри себя вершин и рёбер графа.
[Поиск в глубину] Алгоритм оптимален для поиска по дереву, чья глубина превышает ширину.
Аналогично, с точки зрения времени всё то же самое, а с точки зрения памяти всё ровно наоборот.
Сравнение поисков в ширину и в глубину
Выбирайте тип поиска в соответствии с размером и формой дерева.
Для широких, мелких деревьев используйте поиск в ширину.
Для глубоких, узких деревьев используйте поиск в глубину.
Если уж заморачиваться, то ровно наоборот.
Вообще, поиск в ширину и поиск в глубину – это базовые алгоритмы, из которых потом растут свои ответвления, например:
с помощью поиска в ширину можно искать кратчайшие пути в невзвешенном графе
с помощью поиска в глубину можно искать мосты и точки сочленения.
Сравнение данных с помощью алгоритма сортировки:
Весь набор данных делится минимум на две группы.
Пары значений сравниваются между собой, наименьшее перемещается влево.
После сортировки внутри всех пар, сравниваются левые значения двух левых пар. Таким образом, создаётся группа из четырёх значений: два наименьшие — слева, наибольшие — справа.
Процесс повторяется до тех пор, пока не останется только один набор.
Каша, мёд, говно и пчёлы. Сначала, я так понял, автор начал описывать рекурсивную реализацию, а потом описал итеративную.
«Весь набор данных делится минимум на две группы» – первый шаг рекурсивного алгоритма. Затем каждая часть рекурсивно сортируется и сливается.
Наилучший вариант сортировки: сортировка слиянием — O(n).
Средний вариант сортировки: сортировка слиянием — O(n log n).
Худший вариант сортировки: сортировка слиянием — O(n log n).
Сортировка слиянием всегда работает ровно за O(n log n).
Жадные алгоритмы используются для поиска оптимального решения данной проблемы.
Все алгоритмы в идеале используются для поиска оптимального решения конкретной проблемы. Специфика жадных алгоритмов в том, что их наоборот часто используют для поиска хоть каких-то решений в задачах, в которых искать оптимальное решение не представляется возможным.
Псевдокод жадного алгоритма для поиска самой большой разницы между двумя числами в массиве
Псевдокод жадного алгоритма для поиска самой большой разницы между двумя соседними числами в массиве.
Так можно и поматчить их как .*?, а чё, все правильные email адреса сматчатся, а на false-positive плевать. На практике, конечно, я согласен с тем, что матчить email адреса нужно по наличию ровно одного @ (ваш регэкс, кстати, сматчит и a@b@c), а затем просто слать email, если хочется удостовериться, что email валидный (и, более того, скорее всего настоящий).
1. Пожалуйста, больше никогда не вываливайте набор символов вроде #([A-Fa-f0-9]{6}|[A-Fa-f0-9]{3})
в немоноширинной гарнитуре, это призыв к насилию и вообще экстремизм
2. Электронные адреса не соответствуют никакой регулярной грамматике, а потому и нельзя проверить их никаким регулярным выражением ¯\_(ツ)_/¯
3. То, что должно матчить HTML-теги сматчит не только HTML-теги.
В Португалии занимаемся чартерной авиацией (http://jetway.to), нужно серверов восемь-десять для просчёта логистики.
Забрать могу прямо из Утрехта во второй половине июля.
mingalev@jetway.to
Пользователи, которые не верифицировались, денег не получат, но их доля также просчитывается, и автоматически отправляется владельцам сайтов, которые сами эти пользователи посещают чаще других.
Делаешь ферму неверифицированных кликеров, которые сидят на твоём сайте
Про сценарии различные согласен, разумеется.
Вообще интересны какие-нибудь исследования про долю ошибок в поле емейла, которые отсекаются чем-то сложнее проверкой наличия коммерческого at и точки, отделяющей TLD.
Разве что внутри одного суперрегиона (или даже региона), и то с натяжкой.
Выйгрыш в том, что вбивальщики просто сидят на конвеере, не отвлекаются на врача с пациентом и не сбивают ритм. И главное, их нужно гораздо меньше, чем в каждый кабинет.
С чуваками ещё оставлять на смене какого-нибудь врача, чтобы он если что помогал.
Роберт Шекли, "Мой двойник — робот".
Неясно, почему линейные массивы противопоставляются динамическим. Подразумевались, очевидно, статические массивы.
Действительно, вставка в динамический массив происходит за O(n), но эта информация не очень полезна без того факта, что в силу мультипликативной стратегии реаллокации амортизиованная сложность вставки получается O(1), то есть последовательная вставка n элементов произойдёт не за O(n^2), как можно было бы подумать, а за O(n).
Под определение, которое дано в статье подходит всякая ересь, например:
Неясно, что такое оптимизированный поиск в связном списке.
(оффтоп: чутка развив идею списка можно делать на нём аналог двоичного поиска, гуглить skip list).
Вот это жесть, конечно. Конечно, хэширование не занимается однозначным сопоставлением, потому что значений хэшей должно быть меньше, чем значений хэшируемых объектов, чтобы это имело хоть какой-то смысл.
Решается она не так, конечно, а с помощью использования стратегий разрешения коллизий. Гуглить цепочки, линейное разрешение, двойное хэширование, хэширование кукушки.
При этом у каждой вершины не больше одного левого сына и не больше одного правого.
Все эти операции работают за O(высота дерева). Если дерево сбалансированное, то тогда это действительно O(log N), но само по себе дерево сбалансированным навряд ли станет.
Существуют хитрые двоичные деревья, которые всегда остаются сбалансированными. Гуглить, например, красно-чёрное дерево, AVL-дерево, splay-дерево.
Ну неясно. Поиск в глубину же стек поддерживает пока ходит (неявно, через рекурсию). Те же самые O(V) памяти.
Рёбер. Грань – область, ограниченная рёбрами в плоском графе и не содержащая внутри себя вершин и рёбер графа.
Аналогично, с точки зрения времени всё то же самое, а с точки зрения памяти всё ровно наоборот.
Если уж заморачиваться, то ровно наоборот.
Вообще, поиск в ширину и поиск в глубину – это базовые алгоритмы, из которых потом растут свои ответвления, например:
Каша, мёд, говно и пчёлы.Сначала, я так понял, автор начал описывать рекурсивную реализацию, а потом описал итеративную.«Весь набор данных делится минимум на две группы» – первый шаг рекурсивного алгоритма. Затем каждая часть рекурсивно сортируется и сливается.
Сортировка слиянием всегда работает ровно за O(n log n).
Все алгоритмы в идеале используются для поиска оптимального решения конкретной проблемы. Специфика жадных алгоритмов в том, что их наоборот часто используют для поиска хоть каких-то решений в задачах, в которых искать оптимальное решение не представляется возможным.
Псевдокод жадного алгоритма для поиска самой большой разницы между двумя соседними числами в массиве.
:(
SUM(a, b) * SUM(c, d) == a + b*c + d.*?, а чё, все правильные email адреса сматчатся, а на false-positive плевать. На практике, конечно, я согласен с тем, что матчить email адреса нужно по наличию ровно одного @ (ваш регэкс, кстати, сматчит иa@b@c), а затем просто слать email, если хочется удостовериться, что email валидный (и, более того, скорее всего настоящий).#([A-Fa-f0-9]{6}|[A-Fa-f0-9]{3})в немоноширинной гарнитуре, это призыв к насилию и вообще экстремизм
2. Электронные адреса не соответствуют никакой регулярной грамматике, а потому и нельзя проверить их никаким регулярным выражением ¯\_(ツ)_/¯
3. То, что должно матчить HTML-теги сматчит не только HTML-теги.
// Столлман мод
Забрать могу прямо из Утрехта во второй половине июля.
mingalev@jetway.to
Contest?
https://toster.ru/user/splastunov/answers
Посмотрел оригинальную работу. Откуда взялась диаграмма выше так и не понял, а в самой статье лежит куда более интересная.
Делаешь ферму неверифицированных кликеров, которые сидят на твоём сайте
Вообще интересны какие-нибудь исследования про долю ошибок в поле емейла, которые отсекаются чем-то сложнее проверкой наличия коммерческого at и точки, отделяющей TLD.