ФБ, конечно, хороши тем, что они мягко предлагают хранить всю историю переписки в "типа" защищённых облаках гугла и эппла. Уверен, большинство пользователей, не читая, кликают "согласен" с тем, что их переписка будет бэкапиться на подконткольные США сервера. По факту, и гугл, и эппл сливают всю переписку спецслужбам по первому требованию, и ФБ об этом знает, конечно. Пока они не предложат делать бэкап на яндекс.диске или других стораджах вне юрисдикции Штатов, их e2e-шифрование ничего не стоит.
Так что да, Телеграм не идеален в плане защиты. Но и ватсапп не идеален тоже. Хочется приватности, есть Сигнал и другие менее распиаренные альтернативы.
Я не про баллы или очки, а про слово «сюжет». Вы выше писали про «пользовательские истории» из джиры (опять же, не понятно, зачем добавлять «пользовательские» к «историям»?). А термин “story points” родился именно для оценки историй. Так при чем здесь сюжет?
Даже если допустить, что в русском айти должна использоваться русская терминология (с чем я абсолютно не согласен), перевод "сюжетные баллы" или "сюжетные точки" просто отвратителен. Где сюжет? Мы кино снимаем или театральную постановку? Раз уж так хотите использовать русский язык, придумайте нормальный термин. Не обязательно переводить дословно.
Можно использовать любой S3-совместимый storage или другой тип CDN с нормальным API и нет проблемы с нагрузкой на ФС, заодно и быстрее работать будет, т.к. грузиться будет с ближайшего сервера.
Да просто кто-то из топов гугла запилил свой pet-проект на Svelte, и другие топы такие: ого, круто! Ты, оказывается, умеешь кодить! Вот тебе два ляма на пиар. Не забудь про Хабр.
Да, тут всё плохо :) Для даты 2001-01-01 ваш алгоритм сразу находит единицу, поэтому работает быстро. Моему приходится искать в дереве, и единица будет самым глубоким левым нодом, поэтому ищется долго.
Пока у меня вот такой результат получается. В некоторых тестах дерево работает медленнее, даже чем в FindNextOld, но зато в сложных случаях показывает 15х производительность.
P.S. Я пока сделал только поиск вперед. Все тесты проходятся нормально.
Так двоичное дерево легко представляется в виде массива, где корневой элемент под индексом 0, два дочерних под индексами 1 и 2, следующие 4 дочерних под индексами 3-6 и т.д. Таким образом, у элемента T[i] дочерние будут T[i*2 + 1] и T[i*2 + 2].
Надо будет проверять только пересекающиеся интервалы. В случае с большим количеством значений через запятую будет просто много нодов в дереве, но в результате поиск вернёт только один интервал за O(logN).
Пока что я не готов написать рабочий код из-за отсутствия времени. Может, на выходных доберусь, если тема будет ещё актуальна :)
Зачем делать 283 итерации, если можно сделать один поиск в дереве, содержащем один элемент?
Хотя, конечно, без понимания, в каких условиях будет использоваться код, и без проведения перформанс-тестов, невозможно сказать, что будет эффективнее - массивы или деревья. Если в шаблоне будет указано, например, 990 значений миллисекунд через запятую, то поиск значения в дереве в среднем займёт ~5 итераций (при глубине дерева log2(990) ~ 10), а поиск в массиве ~1 (т.к. почти все ячейки будут true).
Ок, для таких случаев должны возвращаться оба интервала. Step работает уже на следующем уровне: когда мы получили интервал, определяем, попадает ли искомая компонента даты под шаг. Если попадает, возвращаем её. Если нет, возвращаем ближайшее число, удовлетворяющее шагу и направлению поиска.
Тем не менее, если бинарный поиск не подходит, то линейный поиск подходящей миллисекунды в среднем обойдётся в 500 итераций цикла для случая, когда в шаблоне указано единственное конкретное значение. В случае с деревом сложность будет O(1).
Учитывая, что количество лет потенциально неограниченно, мне кажется, дерево всё же предпочтительнее :)
Ну и не совсем понятно, как вы организуете бинарный поиск в случаях интервалов с шагом: например, 0-999/2.
Предположим, я передал дату 2000-01-01 00:00:00:001.
Очевидно, она не подпадает под шаблон. В каком диапазоне делать поиск? [2;999]? Среднее значение будет 500. Оно подпадает под шаблон, но по сути неверное, т.к. следующее верное значение - 2.
1) Для каждого сегмента шаблона (год, месяц, день, час, минута, секунда, миллисекунда) завёл бы segment tree с таким интерфейсом:
enum SearchDirection
{
Forward,
Backward,
}
class SegmentTree
{
public void AddSegment(int from, int to, ISegment segment) {...}
// Возвращает сегмент, в который попадает number.
// Если number не попадает ни в один сегмент, возвращает ближайший с учётом searchDirection.
public ISegment GetSegment(int number, SearchDirection searchDirection) { ... }
}
interface ISegment
{
int? GetFirstMatch(int number, SearchDirection searchDirection);
}
// Класс, представляющий интервал годов/месяцев/дней/часов/минут/секунд/миллисекунд. Интервал может быть представлен единственным числом.
class Interval : ISegment
{
// from == to для случая, когда значение указано без диапазона
Interval(int from, int to) {...}
int? GetFirstMatch(int number, SearchDirection searchDirection)
{
return number;
}
}
// Класс, представляющий интервал годов/месяцев/дней/часов/минут/секунд/миллисекунд с учётом шага
class IntervalWithStep : ISegment
{
IntervalWithStep(int from, int to, int step) {...}
int? GetFirstMatch(int number, SearchDirection searchDirection)
{
var offset = number - this.from;
if (offset % this.step == 0)
{
// Если попали в шаг, возвращаем number
return number;
}
// Если не попали в шаг, возвращаем ближайшее подходящее значение с округлением. Если это значение выходит за пределы интервала, возвращаем null.
var increment = searchDirection == SearchDirection.Forward ? 1 : -1;
var result = this.from + (offset / this.step + increment) * this.step;
return result < this.from || result > this.to ? null : result;
}
}
2) При конструировании дерева наполнял бы его разными типами нодов: для простых констант и интервалов - Interval, для интервалов с шагом - IntervalWithStep.
То есть, для случая "*.*.* * *:*:*.*/2" все деревья, кроме дерева миллисекунд, содержали бы по одному ноду Interval, у которого from=0, to=int.MaxValue.
Дерево для миллисов содержало бы один нод IntervalWithStep (from=0, to=int.MaxValue, step=2).
3) Поиск похож на ваш: сначала ищем интервал для года, вызываем у него GetFirstMatch(date.Year), дальше делаем то же самое для месяца, дня и т.д. Если на каком-то из этапов GetFirstMatch возвращает null (т.е. вышли за пределы интервала), то берем следующий сегмент. Где-то мог ошибиться в логике, но вроде бы должно работать.
Таких пропоузлов насчитал штук десять на гитхабе. Большинство закрыто с резолюшном: не будем делать, потому что это тот же самый goto. В данном случае использование goto не является зашкваром.
ФБ, конечно, хороши тем, что они мягко предлагают хранить всю историю переписки в "типа" защищённых облаках гугла и эппла. Уверен, большинство пользователей, не читая, кликают "согласен" с тем, что их переписка будет бэкапиться на подконткольные США сервера. По факту, и гугл, и эппл сливают всю переписку спецслужбам по первому требованию, и ФБ об этом знает, конечно. Пока они не предложат делать бэкап на яндекс.диске или других стораджах вне юрисдикции Штатов, их e2e-шифрование ничего не стоит.
Так что да, Телеграм не идеален в плане защиты. Но и ватсапп не идеален тоже. Хочется приватности, есть Сигнал и другие менее распиаренные альтернативы.
Может быть, всё же опрос проводился не среди «россиян», а среди «пользователей соцсетей из России»?
Я не про баллы или очки, а про слово «сюжет». Вы выше писали про «пользовательские истории» из джиры (опять же, не понятно, зачем добавлять «пользовательские» к «историям»?). А термин “story points” родился именно для оценки историй. Так при чем здесь сюжет?
Даже если допустить, что в русском айти должна использоваться русская терминология (с чем я абсолютно не согласен), перевод "сюжетные баллы" или "сюжетные точки" просто отвратителен. Где сюжет? Мы кино снимаем или театральную постановку? Раз уж так хотите использовать русский язык, придумайте нормальный термин. Не обязательно переводить дословно.
Можно использовать любой S3-совместимый storage или другой тип CDN с нормальным API и нет проблемы с нагрузкой на ФС, заодно и быстрее работать будет, т.к. грузиться будет с ближайшего сервера.
Да просто кто-то из топов гугла запилил свой pet-проект на Svelte, и другие топы такие: ого, круто! Ты, оказывается, умеешь кодить! Вот тебе два ляма на пиар. Не забудь про Хабр.
Так я конкретный случай рассматриваю, когда в дереве 1 нод.
Поиск в массиве - O(N).
Да, тут всё плохо :) Для даты 2001-01-01 ваш алгоритм сразу находит единицу, поэтому работает быстро. Моему приходится искать в дереве, и единица будет самым глубоким левым нодом, поэтому ищется долго.
Шаблон был таким:
*.1,3,6,8,11.1,3,6,8,11,13,16,18 1,3,6,8,11,13,16,18:1,3,6,8,11,13,16,18:1,3,6,8,11,13,16,18Пока у меня вот такой результат получается. В некоторых тестах дерево работает медленнее, даже чем в FindNextOld, но зато в сложных случаях показывает 15х производительность.
P.S. Я пока сделал только поиск вперед. Все тесты проходятся нормально.
Так двоичное дерево легко представляется в виде массива, где корневой элемент под индексом 0, два дочерних под индексами 1 и 2, следующие 4 дочерних под индексами 3-6 и т.д. Таким образом, у элемента T[i] дочерние будут T[i*2 + 1] и T[i*2 + 2].
Вполне себе кэш-френдли.
Надо будет проверять только пересекающиеся интервалы. В случае с большим количеством значений через запятую будет просто много нодов в дереве, но в результате поиск вернёт только один интервал за O(logN).
Пока что я не готов написать рабочий код из-за отсутствия времени. Может, на выходных доберусь, если тема будет ещё актуальна :)
Зачем делать 283 итерации, если можно сделать один поиск в дереве, содержащем один элемент?
Хотя, конечно, без понимания, в каких условиях будет использоваться код, и без проведения перформанс-тестов, невозможно сказать, что будет эффективнее - массивы или деревья. Если в шаблоне будет указано, например, 990 значений миллисекунд через запятую, то поиск значения в дереве в среднем займёт ~5 итераций (при глубине дерева log2(990) ~ 10), а поиск в массиве ~1 (т.к. почти все ячейки будут true).
Ок, для таких случаев должны возвращаться оба интервала. Step работает уже на следующем уровне: когда мы получили интервал, определяем, попадает ли искомая компонента даты под шаг. Если попадает, возвращаем её. Если нет, возвращаем ближайшее число, удовлетворяющее шагу и направлению поиска.
Это будет не одно дерево, а 8 деревьев, в каждом по одному ноду IntervalWithStep (from=0, to=int.MaxValue, step=4).
Точно, не заметил ограничения в задаче.
Тем не менее, если бинарный поиск не подходит, то линейный поиск подходящей миллисекунды в среднем обойдётся в 500 итераций цикла для случая, когда в шаблоне указано единственное конкретное значение. В случае с деревом сложность будет O(1).
Учитывая, что количество лет потенциально неограниченно, мне кажется, дерево всё же предпочтительнее :)
Ну и не совсем понятно, как вы организуете бинарный поиск в случаях интервалов с шагом: например, 0-999/2.
Предположим, я передал дату 2000-01-01 00:00:00:001.
Очевидно, она не подпадает под шаблон. В каком диапазоне делать поиск? [2;999]? Среднее значение будет 500. Оно подпадает под шаблон, но по сути неверное, т.к. следующее верное значение - 2.
Я бы сделал так:
1) Для каждого сегмента шаблона (год, месяц, день, час, минута, секунда, миллисекунда) завёл бы segment tree с таким интерфейсом:
2) При конструировании дерева наполнял бы его разными типами нодов: для простых констант и интервалов - Interval, для интервалов с шагом - IntervalWithStep.
То есть, для случая "*.*.* * *:*:*.*/2" все деревья, кроме дерева миллисекунд, содержали бы по одному ноду Interval, у которого from=0, to=int.MaxValue.
Дерево для миллисов содержало бы один нод IntervalWithStep (from=0, to=int.MaxValue, step=2).
3) Поиск похож на ваш: сначала ищем интервал для года, вызываем у него GetFirstMatch(date.Year), дальше делаем то же самое для месяца, дня и т.д. Если на каком-то из этапов GetFirstMatch возвращает null (т.е. вышли за пределы интервала), то берем следующий сегмент. Где-то мог ошибиться в логике, но вроде бы должно работать.
Таких пропоузлов насчитал штук десять на гитхабе. Большинство закрыто с резолюшном: не будем делать, потому что это тот же самый goto. В данном случае использование goto не является зашкваром.
Ммм, не уверен, что понял. Звёздочка должна быть представлена одним интервалом в дереве: [0 ; int.MaxValue].