Неточные инструменты тоже бывают полезными. Всякими фильтрами блума, или hyperloglog-ом вполне себе успешно пользуются. Ну и в целом, что ssd/had, что ram — штуки не шибко точные. Но ничего, пользуемся.
До релиза раст детектировал такие паники и выдавал именно что ошибку. Перед реализовать это превратили в линт, который к тому же был выключен. Видимо некоторое время назад этот линт сделали deny by default.
Но линт, на то и линт, что он распознает эти паники эвристиками. Поэтому иногда не очень хорошо срабатывает (например)
Вопрос не в том, чтобы убедиться что нет конкретной лазейки. Вопрос в том, что доказать отсутствие бэкдоров внешними методами — крайне проблематично.
А пока у меня маленький вопрос - а зачем это мне?
Не знаю. Если Вы хотите, чтобы Вашим приложением пользовались в качестве "приватного мессенджера" — то открыть прийдётся. Если же Ваша ЦА — обычные пользователи, которым просто нужен мессенжер (удобный, красивый, etc), то можете не открывать.
Если что, открытие исходников не означает отсутствие заработка. Можете рассмотреть разные модели монетизации.
Вопрос именно в том, что открытые исходники есть необходимый пререквизит к приватному мессенжеру. Если мы о реальной приватности, а не о маркетинге, конечно
Есть механизмы стеганографии по встраиванию бэкдора в криптографию. Например, можно к каждому шифрованному офферу прилагать метаинформацию, зашифрованную публичным ключом злоумышленика. Или в самом p2p соединении оставлять шифрованный блок.
Дальше продать эту информацию провайдерам/точкам обмена трафиком и профит. Ну или мониторить офферы и собирать информацию.
Или в другую сторону: а сколько по времени нужно производить эксперимент по мониторингу? Что если приложение выходит на связь только раз в сутки, в глубокую ночь?;)
И напомню, что всю процедуру проверки необходимо повторять после каждого обновления. С нуля, т.к. неизвестно что поменялось.
Короче говоря, нет. Закрытые исходники — это крест на доверии/приватности.
А стоит ли? Кажется такое усложнение может устранить преимущество этой структуры данных. Всё же это такая, весьма специфичная структура данных. Поэтому эджкейсы в ней норм, если их документировать.
Но вообще, хотелось бы понять, границы её применимости, где она лучше альтернатив работает. Может сделаете статью о конкретных её юзкейсах и сравнению с альтернативами (именно на этих юзкейсах). Тогда, кажется, будет меньше странных вопросов.
На самом деле, я не очень понял, почему Вы подаёте ниуникальность ключей, как какую-то особенность структуры. Ведь деревъя с неуникальными ключами точно также несложно делаются.
Если постараться, можно даже сделать хешмап с неуникальными ключами. С ним уже сложнее и нужно аккуратно быть. Но если не нужен порядок, то хешмап должен быть гораздо быстрее.
Тогда это нужно явно говорить (типа "сложность поиска в худшем случае O(n), но при ряде условий). Потому что пока это не очевидно и создаётся ошибочное представление.
Понятное дело, что бывают ситуации, когда удаления редкие события. Но также есть много алгоритмов, которые активно добавляют и удаляют элементы. И для таких алгоритмов нарваться на подобную патологию довольно просто.
Вот тут пожалуйста по-подробнее, у меня покрыты тестами этот и другой случаи. Буду признателен за конкретный пример, на котором код работает некорректно. Про деградацию по производительности - такая же просьба.
Перечитал тот код, конкретно там вроде ок. Но комментарии помогли бы.
С одинаковыми ключами сложность например в том, что в них могут быть разные элементы (значения). В таком случае, нужно уметь указывать, а какой именно из них хочется удалить.
Также, есть обратная сторона медали: если мне нужны только уникальные элементы(а этом, согласитесь, более частый кейс), то приходится делать Search||Insert - а это бъёт по перфу.
Ассимптотическую деградацию я, наверное, сейчас не приведу. Вроде о простых проблемах Вам уже wataru рассказал (и возможно Вы их уже и так обрабатывали).
Это не сильно важно. Суть в том, что пусть у нас есть последовательность поисковых запросов Search(x1), Search(x2), ..., Search(xm). Каждый из этих запросов найдёт элемент по индексу Index(x1), Index(x2), ..., Index(xm). Вопрос в том, из какого распределения берутся x1, .., xm.
Автор, в этой теореме, предполагает, что x1, ..., xm берутся из такого распределения, что Index(xk) распределены равномерно на U[1, .., n] (где n - количество элементов в массиве). Это вообще говоря, очень нетривиальное условие. Мало того, что из этого условия не очень понятно, как должны быть распределены сами x1, .., xm (оно зависит от распределения вставок!), так ещё распределение запросов редко кто готов предсказать. Но, допустим, для простоты, что нам достаточно того, чтобы x1, ..., xm были распределены равномерно.
На практике, равномерные распределения редко встречаются. Вообще, распределение запросов в реальных задачах - вопрос очень сложный и неоднозначный. Но если пытаться на него ответить, то я бы сказал, что для статических задач поиска (где сначала все insert-ы, а потом все search-и), есть некоторая доля ключейна которые приходятся почти все запросы - так называемые "горячие данные". И вот если Вам не повезёт, и эти горячие данные попадут в малые сегменты, то поиски будут систематически медленными. Поэтому и говорю, что на практике та теорема малоприменима.
Верно. Так как это случай был критичен для моего случая практического использования - оптимизировал его хранением позиций первого и последнего неудалённого элемента в массиве. Но со вторым элементом с конца всё будет так как вы написали.
Но там же пересчёт за линейное время. При удалении минимального элемента, нужно линейное время, чтобы найти следующий после него.
Если в качестве value - int64, как в бенчмарке, будет чувствительно
Кажется такой бенчмарк не очень репрезентативен. Не до конца понятна целевая ниша этой структуры данных, но обычно всё же у нас есть ещё какое-то (сравнительно большое) значение. И на фоне значения уже не так критично.
Также стоит понимать, что использовать деревья просто как ассоциативные контейнеры чаще всего затея не самая удачная. Банальный хешмап на порядок быстрее деревьев или вот этих вот bwa. Деревья обычно берут чтобы на них строить всякие интересные статистики и прочее. Поэтому опять же вес узла там не так значителен.
Про время поиска нужно аккуратно формулировать. Из статьи:
Theorem 5 (Search Time (Hit)). For a BWA with up to n = 2^m values, the amortized time of a hit search is O(log n) , provided that the values are uniformly distributed.
Значения поисков редко распределены равномерно. Вообще распределение входных ключей может быть сильно разным. И есть основания полагать, что достаточно часто оно сильно перекошено (всякие правила Парето и прочее). Поэтому на практике результатами этой теоремы воспользоваться нельзя.
Реальная ассимптотика поиска будет как раз, что весьма неприятно. Даже на каком-то миллионе элементов константа вырастет в 20 раз.
Ну и отдельный вопрос к формулировке. Не очень понятно, почему автор здесь говорит про аммортизированное время, если доказал он только среднее время (матожидание). Это, как никак, сильно разные понятия.
И в целом, там амортизация внятно не доказана. Там только какие-то очень простые кейсы для последовательностей одинаковых операций.
P.S. Будьте аккуратнее с обработкой "одинаковых ключей", как Вы заявили. Потому что там очень легко все ассимптотики могут стать. Хотя глядя на код поиска, кажется он некорректен в присутствии одинаковых элементов.
Нет, там наибольшее влияние оказал лисп (поэтому что это изначально и был лисп). Ну а передача по ссылке была почти во всех языках с гц того времени, поэтому от явы тут ничего нет.
Неточные инструменты тоже бывают полезными. Всякими фильтрами блума, или hyperloglog-ом вполне себе успешно пользуются. Ну и в целом, что ssd/had, что ram — штуки не шибко точные. Но ничего, пользуемся.
А, уже теперь...
До релиза раст детектировал такие паники и выдавал именно что ошибку. Перед реализовать это превратили в линт, который к тому же был выключен. Видимо некоторое время назад этот линт сделали deny by default.
Но линт, на то и линт, что он распознает эти паники эвристиками. Поэтому иногда не очень хорошо срабатывает (например)
Это Вы откуда-то из 2014 пришли. Сейчас это уже рантайм паника.
Вопрос не в том, чтобы убедиться что нет конкретной лазейки. Вопрос в том, что доказать отсутствие бэкдоров внешними методами — крайне проблематично.
Не знаю. Если Вы хотите, чтобы Вашим приложением пользовались в качестве "приватного мессенджера" — то открыть прийдётся. Если же Ваша ЦА — обычные пользователи, которым просто нужен мессенжер (удобный, красивый, etc), то можете не открывать.
Если что, открытие исходников не означает отсутствие заработка. Можете рассмотреть разные модели монетизации.
Вопрос именно в том, что открытые исходники есть необходимый пререквизит к приватному мессенжеру. Если мы о реальной приватности, а не о маркетинге, конечно
Я регулярно сталкиваюсь с виндовыми системами, которые разваливались от такого подхода (и становились неработоспособными).
Анализ сложности этой структуры весьма нетривиальный. Если Вы, конечно, хотите оценки с логарифмами получить, а не с
на каждую операцию.
Тогда разделите статью на две. Иначе в обсуждениях каша из мнений.
Есть механизмы стеганографии по встраиванию бэкдора в криптографию. Например, можно к каждому шифрованному офферу прилагать метаинформацию, зашифрованную публичным ключом злоумышленика. Или в самом p2p соединении оставлять шифрованный блок.
Дальше продать эту информацию провайдерам/точкам обмена трафиком и профит. Ну или мониторить офферы и собирать информацию.
Или в другую сторону: а сколько по времени нужно производить эксперимент по мониторингу? Что если приложение выходит на связь только раз в сутки, в глубокую ночь?;)
И напомню, что всю процедуру проверки необходимо повторять после каждого обновления. С нуля, т.к. неизвестно что поменялось.
Короче говоря, нет. Закрытые исходники — это крест на доверии/приватности.
А стоит ли? Кажется такое усложнение может устранить преимущество этой структуры данных. Всё же это такая, весьма специфичная структура данных. Поэтому эджкейсы в ней норм, если их документировать.
Но вообще, хотелось бы понять, границы её применимости, где она лучше альтернатив работает. Может сделаете статью о конкретных её юзкейсах и сравнению с альтернативами (именно на этих юзкейсах). Тогда, кажется, будет меньше странных вопросов.
Хранить деревья отрезков вместо сегментов. По идее должно быть достаточно быстро.
На самом деле, я не очень понял, почему Вы подаёте ниуникальность ключей, как какую-то особенность структуры. Ведь деревъя с неуникальными ключами точно также несложно делаются.
Если постараться, можно даже сделать хешмап с неуникальными ключами. С ним уже сложнее и нужно аккуратно быть. Но если не нужен порядок, то хешмап должен быть гораздо быстрее.
Тогда это нужно явно говорить (типа "сложность поиска в худшем случае O(n), но при ряде условий
). Потому что пока это не очевидно и создаётся ошибочное представление.
Понятное дело, что бывают ситуации, когда удаления редкие события. Но также есть много алгоритмов, которые активно добавляют и удаляют элементы. И для таких алгоритмов нарваться на подобную патологию довольно просто.
Перечитал тот код, конкретно там вроде ок. Но комментарии помогли бы.
С одинаковыми ключами сложность например в том, что в них могут быть разные элементы (значения). В таком случае, нужно уметь указывать, а какой именно из них хочется удалить.
Также, есть обратная сторона медали: если мне нужны только уникальные элементы(а этом, согласитесь, более частый кейс), то приходится делать Search||Insert - а это бъёт по перфу.
Ассимптотическую деградацию я, наверное, сейчас не приведу. Вроде о простых проблемах Вам уже wataru рассказал (и возможно Вы их уже и так обрабатывали).
Это не сильно важно. Суть в том, что пусть у нас есть последовательность поисковых запросов Search(x1), Search(x2), ..., Search(xm). Каждый из этих запросов найдёт элемент по индексу Index(x1), Index(x2), ..., Index(xm). Вопрос в том, из какого распределения берутся x1, .., xm.
Автор, в этой теореме, предполагает, что x1, ..., xm берутся из такого распределения, что Index(xk) распределены равномерно на U[1, .., n] (где n - количество элементов в массиве). Это вообще говоря, очень нетривиальное условие. Мало того, что из этого условия не очень понятно, как должны быть распределены сами x1, .., xm (оно зависит от распределения вставок!), так ещё распределение запросов редко кто готов предсказать. Но, допустим, для простоты, что нам достаточно того, чтобы x1, ..., xm были распределены равномерно.
На практике, равномерные распределения редко встречаются. Вообще, распределение запросов в реальных задачах - вопрос очень сложный и неоднозначный. Но если пытаться на него ответить, то я бы сказал, что для статических задач поиска (где сначала все insert-ы, а потом все search-и), есть некоторая доля ключей
на которые приходятся почти все запросы - так называемые "горячие данные". И вот если Вам не повезёт, и эти горячие данные попадут в малые сегменты, то поиски будут систематически медленными. Поэтому и говорю, что на практике та теорема малоприменима.
Не, я говорил про всякие деревья отрезков, или более хитрые структуры. Вам wataru выше об этом тоже написал.
Но там же пересчёт за линейное время. При удалении минимального элемента, нужно линейное время, чтобы найти следующий после него.
Кажется такой бенчмарк не очень репрезентативен. Не до конца понятна целевая ниша этой структуры данных, но обычно всё же у нас есть ещё какое-то (сравнительно большое) значение. И на фоне значения уже не так критично.
Также стоит понимать, что использовать деревья просто как ассоциативные контейнеры чаще всего затея не самая удачная. Банальный хешмап на порядок быстрее деревьев или вот этих вот bwa. Деревья обычно берут чтобы на них строить всякие интересные статистики и прочее. Поэтому опять же вес узла там не так значителен.
Про время поиска нужно аккуратно формулировать. Из статьи:
Значения поисков редко распределены равномерно. Вообще распределение входных ключей может быть сильно разным. И есть основания полагать, что достаточно часто оно сильно перекошено (всякие правила Парето и прочее). Поэтому на практике результатами этой теоремы воспользоваться нельзя.
Реальная ассимптотика поиска будет как раз
, что весьма неприятно. Даже на каком-то миллионе элементов константа вырастет в 20 раз.
Ну и отдельный вопрос к формулировке. Не очень понятно, почему автор здесь говорит про аммортизированное время, если доказал он только среднее время (матожидание). Это, как никак, сильно разные понятия.
И в целом, там амортизация внятно не доказана. Там только какие-то очень простые кейсы для последовательностей одинаковых операций.
P.S. Будьте аккуратнее с обработкой "одинаковых ключей", как Вы заявили. Потому что там очень легко все ассимптотики могут стать
. Хотя глядя на код поиска, кажется он некорректен в присутствии одинаковых элементов.
Использовать backtrace? :)
Нет, там наибольшее влияние оказал лисп (поэтому что это изначально и был лисп). Ну а передача по ссылке была почти во всех языках с гц того времени, поэтому от явы тут ничего нет.