Тогда можно просто вставить ссылку на узел дерева прямо в саму ноту. Это гораздо эффективнее получится.
То есть, классически это решается так. Вы используете дерево для поиска по данным (интервалам времени) - возвращают эти поиски узлы (условно NoteNode). Далее операции удаления, обновления и прочего принимают напрямую эту NoteNode - в ней есть ссылки на узлы дерева. Поэтому у Вас пропадает операция поиска по объекту.
На моей практике, такой подход кратно упрощает реализацию.
На самом деле, замерить худший случай не так то и просто будет. Самая главная проблема - это нагрузка на аллокатор и сборщик мусора.
Например, при добавлении в связный список, у нас всегда аллоцируется узел списка. Чаще всего, это просто инкремент указателя в чистилище. Но, если окажется, что чистилище у нас занято - произойдёт малая сборка мусора. А это линейный проход по всему чистилищу (вероятно 16-256 MB на десктопе) - то есть довольно долго.
В случае же List, у нас либо хватает места и произойдёт простой инкремент индекса/указателя. Может не хватить места и произойдёт реаллок - это всего лишь копия элементов списка, а не целого чистилища. И крайний случай - может тоже не хватить памяти и произойдёт малая сборка мусора - тут тот же худший случай.
Поэтому наивный бенчмарк может померять не то (особено в языках с GC - у них большой фактор играет сборка мусора).
На практике, при длинах списка до 100 элементов, List работает быстрее LinkedList даже в худщем случае. Вся вот эта история с быстрыми точечными операциями становиться интересной когда у Вас миллионы элементов в списке - но там обычный LinkedList плохо работает, нужны интрузивные структуры данных.
Вообще, для таких задач часто подходят splay-деревья. Они не обладают гарантиями реального времени, но зато они очень хорошо оптимизируются под нагрузку.
Касательно работы с несколькими значениями для одного ключа, классически это решается курсора и:
Разрешаете дублирование ключей
Вместо операции search вводите операции lower_bound и upper_bound (ну или search_first и search_last)
При этом, результаты поиска возвращают не значения, а курсоры: специальные объекты, которые могут перемещаться вперёд-назад (и получать значения)
Справиться с линейным поиском по значениям без наложения ограничений на сами значения нельзя. Но я не очень понял зачем Вам искать по значениям (только как деталь реализации с координатами - но это решается курсорами).
Но зато можно делать дерево поиска по составному ключу. В качестве ключа мы используем пары (K1, K2). Порядок сравнения в них лексикографический. Тогда с одной стороны, у нас есть дерево поиска по (K1, K2) без повторяющихся ключей, а с другой стороны - дерево поиска по K1, но уже с повторяющимися ключами.
P. S. Имхо, делать обобщенные(в смысле дженериков) структуры данных не очень полезно. Гораздо важнее делать структуры данных под конкретные применения — там можно гораздо лучше использовать специфику задачи.
А потому всегда должен смотреть на худший случай тоже.
Это не всегда хорошая затея.
Фишка в том, что этот "худший" случай не может происходить слишком часто. Если выражаться формально, то там аммортизированное O(1).
Если вы не желаете структуры данных под реальное время, то вам стоит смотреть на суммарное время выполнения операций — а оно у списков кратно быстрее.
Прелесть нотации "O" большое в том, что мне даже не нужно бенчмарки запускать для понимания скорости
Вообще нет. Если бы это было бы так, мы бы все использовали фибоначеву кучу и галактические алгоритмы (спойлер: у них очень хорошее O, но на всех доступных сейчас объёмах данных, они очень медленные).
Ну, или с другой стороны: знали ли Вы, что современные реализации сортировок используют сортировку вставками, а не квиксорт в некоторых случаях — так быстрее.
Оно unsafe - это правда, но это не имеет отношения к синшному аби. Для сишного аби нужно использовать extern "C" а также использовать только типы со стабильным аби. Хотя данный конкретный пример настолько простой, что есть тупо нет альтернативных вариантов.
Впрочем, я перечитал с чего начался тред, и проблема в том, что раст умеет инлайнить функции из dylib (через split metadata, или через метадату прямо в dylib). И с недавних пор раст автоматически помечает простые функции как #[inline].
Чтобы этого избежать можно пометить функцию как #[inline(never)]. Или же увеличить тело функции, чтобы раст не инлайнил эту функцию.
В rustc есть постоянные замеры производительности. И те этапы, в которых могли бы задействоваться форвард декларации не встречаются в топе этих замеров.
Основное время сжирает либо трейт-солвинг, либо собственно кодген(то есть llvm) - в разный крестах по-разному.
Инкрементальная и параллельная сборка в rustc поддерживается при том на хорошем уровне. При этом, инкрементальная сборка не требует компромиссов вроде pimpl и подобного.
Не увидел противоречия Вашего определения и цитаты.
Почему так - не могу сказать
Потому что языковых средств не хватает. Например, вот хочу я обработать все ошибки бд в каком-то фильтре/мидлваре – я не могу как-то пометить свои хендлеры, что они кидают DbException, а мидлварь - что она его обрабатывает(чтобы на меня заругались, если вдруг я забыл добавить мидлварь). А большинство ошибок именно так и стоит обрабатывать в спринге... Выразительности физически не хватает.
Не очень понял, чем ваше решение лучше альтернатив (того же RA). Всё же, если и делать анонс, то хотя бы покажите это решение (showcase), чем оно хорошо. Пока выглядит как локальная либо для решения конкретно ваших проблем.
Например, беглый просмотр вызвал вопросы:
Зачем-то полезли в аутентификацию и прибили гвоздями к своей самописной либе. Более того, требуете хранить токен в localStorage (что как бы не очень затея)
Все также нет возможности кастомизировать ui (ну кроме css - но это везде)
Требуете запуск в корне приложения (что если я хочу админку как часть моего приложения)
По сути, требуете фиксированную структуру урл. Даже пример делаете на своём апи, а не на каком-то публичном.
И это я даже не начал смотреть на собственном основной функционал - уверен, там тоже полезут вопросы.
Золотое правило - не использовать криптографические примитивы. Стоит сразу брать библиотеки высокого уровня с пуленепробиваемыми апи: всякие tls и sodium.
AES, DH, RSA и прочие - слишком тяжело использовать без ошибок.
Структуры данных - это то как данные хранятся в памяти. И их всего две - массив и связный список.
Странное определение. "Как данные хранятся в памяти" - это что значит?
Например, можно взять модель машины указателей - там любая структура данных описывается при помощи набора записей; в каждой записи есть набор свойств (их количество ограничено глобально для структуры данных) - каждое из них хранит либо примитив, либо указатель, либо ничего не хранит. Но в такой модели есть гораздо больше структур данных, чем две (даже если забыть про инварианты).
Но вообще говоря, структура данных определяется набором операций (с их реализациями).
При том, на практике, все "интересные" структуры данных - интрузивны. То есть у нас нет отдельных деревьев, или списков - у нас каждый узел одновременно принадлежит нескольким деревьям, спискам, и пр. Поэтому утверждение что есть только "связанные списки и массивы" - странное.
И на основе этих структур можно реализовывать абстрактные типы данных - списки, очереди, стеки, деревья, etc.
Расскажите, как Вы реализуете, например, дерево поверх связного списка? Разумеется, чтобы операции были эффективными.
Я не очень понял, с чем Вы соглашаетесь, или что опровергаете :)
описанные уязвимости - математические
Прежде чем серьёзно говорить про "математические" уязвимости нужно строго (математически!) сформулировать, а что такое вообще уязвимость. А после этого математически доказать, что описанное в статье уязвимостями являются.
А статья будет полезна начинающим криптографам - к которым причисляю и себя
Нормальные вводные курсы по криптографии собственно начинаются со строгого определения, что такое вообще уязвимость. Выше я привёл упрощённое определение.
Потому что без определения, это просто махание руками, без какой либо математики. Так можно дойти и до того, что я объявлю функцию f(x), которая решает DLOG для заданной группы (просто предпосчитаю её например) - и у нас будет "математическая" уязвимость. И вот попробуйте мне доказать, что это не так? ;) (серьёзно - попробуйте опровергнуть этот тезис)
Статья у Вас в целом неплохая, но посыл чуть не тот. У Вас как раз очень хорошая иллюстрация, почему понятие "уязвимость" - довольно неоднозначное, и почему для него нужны строгие определения. Вот если Вы этими определниями(с разборами Ваших примеров по определениям) дополните статью - тогда действительно будет хороший материал для начинающих. А пока, она немного вводит в заблуждение неискушённого читателя.
Вам для понимания стоит сформулировать формально, что такое "уязвимость в криптосистеме DH". Тогда станет ясно, почему это не проблема.
Например, можно сформулировать так: это такой вероятностный алгоритм, что для случайного обмена публичных ключами, алгоритм даёт ответ с неисчезающей вероятностью. Неисчезающая вероятность означает, что если- вероятность угадать ответ при длине ключа в n бит, то
В такой постановке, Ваши примеры не являются уязвимостями.
Это работает только для независимых данных/запросов. Для зависимых запросов потребуется либо второй запрос, либо играться с пушами.
Само прогрессивное решение либо про медленную сеть, либо про много контента
Из тех реализации, которые я видел (для "прогрессивного" json/html), они были скорее про медленные запросы на сервере и про уменьшение задержки до контента (пока бек ходит в бд, мы уже отправили клиенту какую-то html-ку).
То есть требования к организации асинхронных объектов существенно выше,
Я видел фреймворки, в которых для использования такой прогрессивности не нужно делать ничего сложного. Можно даже не знать, о том, что используется прогрессивность.
Например, те же RSC или SolidJs/createAsync сами отслеживают использование "ассинхронных" частей и отказываются до ближайшего Suspense. Пользователю достаточно просто обернуть кусок интерфейса в Suspense, указать скелетон и в случае SolidJs обернуть асинхронную часть в createAsync.
Другое дело, что это решения сами в себе: они поддерживают только "прогрессивный" json, который сами же и сгенерили. Нельзя взять бекенд на условной Яве/Шарпах и получить от них прогрессивный json - стандарта не хватает. Вот для такого спека + пачка либ для тех самых "5%" очень бы помогли - остальные 95% за нас решили фреймворки.
вы можете использовать и просто батчи объектов
Попробуйте описать, как использовать "батчи" в кейсе, который я описал выше.
Пример кейса, зачем чём такая схема может быть интересна. Есть интерфейс с набором карточек. Каждая карточка состоит из заготовка и контента. При этом, на сервере зафетчить заголовок можно сильно быстрее, чем контент (например, если в контенте статистика). Поэтому мы хотим при загрузке страницы отображать только заголовки, а вместо контента скелет. Когда погрузиться контент - тогда уже отображаем контент.
Если делать на отдельными запросами, то будет условный запрос getTopK -> { id, header }[] и запрос getContentMulti(ids) -> { id, content }[]. Нам нужно будет запросить сначала заголовки, и только когда их получим, зависимым запросом запросить контент. При этом нужно будет ещё сматчить ответ с заголовками (что в целом не шибко сложно, но усложняет флоу).
Если же использовать прогрессивный json, то у нас будет один запрос getTopK -> { id, header, async content }[]. Сервер при получении запроса будет фетчить заголовки, отдавать их и сразу же начинать фетчить контент. В итоге это даст на один RTT меньше latency - что очень хорошо.
---
Мне кажется эта технология решает вполне понятную задачу: хочется чтобы при изменении требований "а теперь мы этот кусочек данных грузим ассинхронно", не нужно было всё переписывать, а нужно было в соответствующих местах вставить Suspense/useQuery/createAsync. Аналогичная история с серверами функциями.
Хотя именно эвристическая подход к прогрессивности лично меня смущает. Кажется, лучше чтобы разработчики явно помечал, какие поля могут быть ассинхронными. Но практика покажет.
Хотя я согласен с Вашим тезисы, конкретно эта статья подтверждает немного другой древний тезис: не пишите свою собственную криптографию, пусть это пишут профессионалы.
Впрочем, в определённом смысле, любой веб реализует какие-то проверки безопасности...
Хотя я видел и как синьёры пишут код подверженный path traversal attack и как его никто не замечает
Тогда можно просто вставить ссылку на узел дерева прямо в саму ноту. Это гораздо эффективнее получится.
То есть, классически это решается так. Вы используете дерево для поиска по данным (интервалам времени) - возвращают эти поиски узлы (условно NoteNode). Далее операции удаления, обновления и прочего принимают напрямую эту NoteNode - в ней есть ссылки на узлы дерева. Поэтому у Вас пропадает операция поиска по объекту.
На моей практике, такой подход кратно упрощает реализацию.
На самом деле, замерить худший случай не так то и просто будет. Самая главная проблема - это нагрузка на аллокатор и сборщик мусора.
Например, при добавлении в связный список, у нас всегда аллоцируется узел списка. Чаще всего, это просто инкремент указателя в чистилище. Но, если окажется, что чистилище у нас занято - произойдёт малая сборка мусора. А это линейный проход по всему чистилищу (вероятно 16-256 MB на десктопе) - то есть довольно долго.
В случае же List, у нас либо хватает места и произойдёт простой инкремент индекса/указателя. Может не хватить места и произойдёт реаллок - это всего лишь копия элементов списка, а не целого чистилища. И крайний случай - может тоже не хватить памяти и произойдёт малая сборка мусора - тут тот же худший случай.
Поэтому наивный бенчмарк может померять не то (особено в языках с GC - у них большой фактор играет сборка мусора).
На практике, при длинах списка до 100 элементов, List работает быстрее LinkedList даже в худщем случае. Вся вот эта история с быстрыми точечными операциями становиться интересной когда у Вас миллионы элементов в списке - но там обычный LinkedList плохо работает, нужны интрузивные структуры данных.
Вообще, для таких задач часто подходят splay-деревья. Они не обладают гарантиями реального времени, но зато они очень хорошо оптимизируются под нагрузку.
Касательно работы с несколькими значениями для одного ключа, классически это решается курсора и:
Разрешаете дублирование ключей
Вместо операции search вводите операции lower_bound и upper_bound (ну или search_first и search_last)
При этом, результаты поиска возвращают не значения, а курсоры: специальные объекты, которые могут перемещаться вперёд-назад (и получать значения)
Справиться с линейным поиском по значениям без наложения ограничений на сами значения нельзя. Но я не очень понял зачем Вам искать по значениям (только как деталь реализации с координатами - но это решается курсорами).
Но зато можно делать дерево поиска по составному ключу. В качестве ключа мы используем пары (K1, K2). Порядок сравнения в них лексикографический. Тогда с одной стороны, у нас есть дерево поиска по (K1, K2) без повторяющихся ключей, а с другой стороны - дерево поиска по K1, но уже с повторяющимися ключами.
P. S. Имхо, делать обобщенные(в смысле дженериков) структуры данных не очень полезно. Гораздо важнее делать структуры данных под конкретные применения — там можно гораздо лучше использовать специфику задачи.
Это не всегда хорошая затея.
Фишка в том, что этот "худший" случай не может происходить слишком часто. Если выражаться формально, то там аммортизированное O(1).
Если вы не желаете структуры данных под реальное время, то вам стоит смотреть на суммарное время выполнения операций — а оно у списков кратно быстрее.
Вообще нет. Если бы это было бы так, мы бы все использовали фибоначеву кучу и галактические алгоритмы (спойлер: у них очень хорошее O, но на всех доступных сейчас объёмах данных, они очень медленные).
Ну, или с другой стороны: знали ли Вы, что современные реализации сортировок используют сортировку вставками, а не квиксорт в некоторых случаях — так быстрее.
Оно unsafe - это правда, но это не имеет отношения к синшному аби. Для сишного аби нужно использовать extern "C" а также использовать только типы со стабильным аби. Хотя данный конкретный пример настолько простой, что есть тупо нет альтернативных вариантов.
Впрочем, я перечитал с чего начался тред, и проблема в том, что раст умеет инлайнить функции из dylib (через split metadata, или через метадату прямо в dylib). И с недавних пор раст автоматически помечает простые функции как #[inline].
Чтобы этого избежать можно пометить функцию как #[inline(never)]. Или же увеличить тело функции, чтобы раст не инлайнил эту функцию.
А, они так и не реализовали used для функций. Тогда только no_mangle
Потому что раст считает по умолчанию, функции недоступными для внешней линковки и потому он просто убирает мёртвый код.
Чтобы он не убирал функцию, необходимо либо пометить её как #[used], либо как no_mangle (в любом случае, как Вы планируете линковаться к ней…)
Лично мне понятие аффинного вектора тоже незнакомо. Я лишь обращал внимание, что Вы его путаете с другими векторами.
Судя по всему, понятие аффиного вектора родственно понятию связанного вектора - просто упорядоченная пара точек аффинного пространства.
Плюс, похоже товарищ @dmagin знает какую-то алгебру поверх этих векторов. Пока что выглядит как во многом формальные комбинации векторов.
Вы здесь путаете аффинные векторы со свободными векторами. Это всё так сильно разные штуки.
В rustc есть постоянные замеры производительности. И те этапы, в которых могли бы задействоваться форвард декларации не встречаются в топе этих замеров.
Основное время сжирает либо трейт-солвинг, либо собственно кодген(то есть llvm) - в разный крестах по-разному.
Инкрементальная и параллельная сборка в rustc поддерживается при том на хорошем уровне. При этом, инкрементальная сборка не требует компромиссов вроде pimpl и подобного.
Не увидел противоречия Вашего определения и цитаты.
Потому что языковых средств не хватает. Например, вот хочу я обработать все ошибки бд в каком-то фильтре/мидлваре – я не могу как-то пометить свои хендлеры, что они кидают DbException, а мидлварь - что она его обрабатывает(чтобы на меня заругались, если вдруг я забыл добавить мидлварь). А большинство ошибок именно так и стоит обрабатывать в спринге... Выразительности физически не хватает.
Не очень понял, чем ваше решение лучше альтернатив (того же RA). Всё же, если и делать анонс, то хотя бы покажите это решение (showcase), чем оно хорошо. Пока выглядит как локальная либо для решения конкретно ваших проблем.
Например, беглый просмотр вызвал вопросы:
Зачем-то полезли в аутентификацию и прибили гвоздями к своей самописной либе. Более того, требуете хранить токен в localStorage (что как бы не очень затея)
Все также нет возможности кастомизировать ui (ну кроме css - но это везде)
Требуете запуск в корне приложения (что если я хочу админку как часть моего приложения)
По сути, требуете фиксированную структуру урл. Даже пример делаете на своём апи, а не на каком-то публичном.
И это я даже не начал смотреть на собственном основной функционал - уверен, там тоже полезут вопросы.
Короче, выглядит как банальный NIH
Золотое правило - не использовать криптографические примитивы. Стоит сразу брать библиотеки высокого уровня с пуленепробиваемыми апи: всякие tls и sodium.
AES, DH, RSA и прочие - слишком тяжело использовать без ошибок.
Странное определение. "Как данные хранятся в памяти" - это что значит?
Например, можно взять модель машины указателей - там любая структура данных описывается при помощи набора записей; в каждой записи есть набор свойств (их количество ограничено глобально для структуры данных) - каждое из них хранит либо примитив, либо указатель, либо ничего не хранит. Но в такой модели есть гораздо больше структур данных, чем две (даже если забыть про инварианты).
Но вообще говоря, структура данных определяется набором операций (с их реализациями).
При том, на практике, все "интересные" структуры данных - интрузивны. То есть у нас нет отдельных деревьев, или списков - у нас каждый узел одновременно принадлежит нескольким деревьям, спискам, и пр. Поэтому утверждение что есть только "связанные списки и массивы" - странное.
Расскажите, как Вы реализуете, например, дерево поверх связного списка? Разумеется, чтобы операции были эффективными.
Я не очень понял, с чем Вы соглашаетесь, или что опровергаете :)
Прежде чем серьёзно говорить про "математические" уязвимости нужно строго (математически!) сформулировать, а что такое вообще уязвимость. А после этого математически доказать, что описанное в статье уязвимостями являются.
Нормальные вводные курсы по криптографии собственно начинаются со строгого определения, что такое вообще уязвимость. Выше я привёл упрощённое определение.
Потому что без определения, это просто махание руками, без какой либо математики. Так можно дойти и до того, что я объявлю функцию f(x), которая решает DLOG для заданной группы (просто предпосчитаю её например) - и у нас будет "математическая" уязвимость. И вот попробуйте мне доказать, что это не так? ;) (серьёзно - попробуйте опровергнуть этот тезис)
Статья у Вас в целом неплохая, но посыл чуть не тот. У Вас как раз очень хорошая иллюстрация, почему понятие "уязвимость" - довольно неоднозначное, и почему для него нужны строгие определения. Вот если Вы этими определниями(с разборами Ваших примеров по определениям) дополните статью - тогда действительно будет хороший материал для начинающих. А пока, она немного вводит в заблуждение неискушённого читателя.
Вам для понимания стоит сформулировать формально, что такое "уязвимость в криптосистеме DH". Тогда станет ясно, почему это не проблема.
Например, можно сформулировать так: это такой вероятностный алгоритм, что для случайного обмена публичных ключами, алгоритм даёт ответ с неисчезающей вероятностью. Неисчезающая вероятность означает, что если
- вероятность угадать ответ при длине ключа в n бит, то
В такой постановке, Ваши примеры не являются уязвимостями.
Это работает только для независимых данных/запросов. Для зависимых запросов потребуется либо второй запрос, либо играться с пушами.
Из тех реализации, которые я видел (для "прогрессивного" json/html), они были скорее про медленные запросы на сервере и про уменьшение задержки до контента (пока бек ходит в бд, мы уже отправили клиенту какую-то html-ку).
Я видел фреймворки, в которых для использования такой прогрессивности не нужно делать ничего сложного. Можно даже не знать, о том, что используется прогрессивность.
Например, те же RSC или SolidJs/createAsync сами отслеживают использование "ассинхронных" частей и отказываются до ближайшего Suspense. Пользователю достаточно просто обернуть кусок интерфейса в Suspense, указать скелетон и в случае SolidJs обернуть асинхронную часть в createAsync.
Другое дело, что это решения сами в себе: они поддерживают только "прогрессивный" json, который сами же и сгенерили. Нельзя взять бекенд на условной Яве/Шарпах и получить от них прогрессивный json - стандарта не хватает. Вот для такого спека + пачка либ для тех самых "5%" очень бы помогли - остальные 95% за нас решили фреймворки.
Попробуйте описать, как использовать "батчи" в кейсе, который я описал выше.
Няп, это противоречит идеологии rest как таковой. Тут уж просто какой-то rpc с json via hotpot получается.
Пример кейса, зачем чём такая схема может быть интересна. Есть интерфейс с набором карточек. Каждая карточка состоит из заготовка и контента. При этом, на сервере зафетчить заголовок можно сильно быстрее, чем контент (например, если в контенте статистика). Поэтому мы хотим при загрузке страницы отображать только заголовки, а вместо контента скелет. Когда погрузиться контент - тогда уже отображаем контент.
Если делать на отдельными запросами, то будет условный запрос getTopK -> { id, header }[] и запрос getContentMulti(ids) -> { id, content }[]. Нам нужно будет запросить сначала заголовки, и только когда их получим, зависимым запросом запросить контент. При этом нужно будет ещё сматчить ответ с заголовками (что в целом не шибко сложно, но усложняет флоу).
Если же использовать прогрессивный json, то у нас будет один запрос getTopK -> { id, header, async content }[]. Сервер при получении запроса будет фетчить заголовки, отдавать их и сразу же начинать фетчить контент. В итоге это даст на один RTT меньше latency - что очень хорошо.
---
Мне кажется эта технология решает вполне понятную задачу: хочется чтобы при изменении требований "а теперь мы этот кусочек данных грузим ассинхронно", не нужно было всё переписывать, а нужно было в соответствующих местах вставить Suspense/useQuery/createAsync. Аналогичная история с серверами функциями.
Хотя именно эвристическая подход к прогрессивности лично меня смущает. Кажется, лучше чтобы разработчики явно помечал, какие поля могут быть ассинхронными. Но практика покажет.
Хотя я согласен с Вашим тезисы, конкретно эта статья подтверждает немного другой древний тезис: не пишите свою собственную криптографию, пусть это пишут профессионалы.
Впрочем, в определённом смысле, любой веб реализует какие-то проверки безопасности...
Хотя я видел и как синьёры пишут код подверженный path traversal attack и как его никто не замечает