Действительно ли Quicksort является потенциальной угрозой безопасности?
В целом, и это ни в коем случае не "правило", которому нужно слепо следовать, самое гибкое расположение:
interface
abstract class
concrete class 1
concrete class 2
интерфейс там по нескольким причинам:
- существующий класс, который уже расширяет что-то, может реализовать интерфейс (предположение, что Вы управляете кодом для существующего класса)
- , существующий класс может быть подклассами, и подкласс может реализовать интерфейс (предположение, что существующий класс является подподдающимся классификации)
, Это означает, что можно посещать существующие ранее уроки (или просто классы, которые ДОЛЖНЫ расшириться от чего-то еще), и сделайте, чтобы они работали с кодом.
абстрактный класс там для обеспечения всех общих битов для реальных классов. Абстрактный класс расширяется от того, когда Вы пишете новые классы или изменяете классы, что Вы хотите расширить его (предположение, что они расширяются от java.lang. Объект).
Вы всегда должны (если у Вас нет действительно серьезного основания не к), объявляют переменные (экземпляр, класс, локальный, и параметры метода) как интерфейс.
6 ответов
Да, это угроза безопасности, точнее DoS, которую тривиально можно уменьшить, добавив проверку глубины рекурсии в вашу быструю сортировку , и вместо этого переключиться на что-то другое, если будет достигнута определенная глубина. Если вы переключитесь на динамическую сортировку, вы получите интросорт , который фактически используется во многих реализациях STL.
В качестве альтернативы вы просто случайным образом выбираете сводный элемент.
Многие реализации быстрой сортировки выполняются с использованием рандомизированная версия алгоритма . Это означает, что DoS-атака со специально созданными входными данными невозможна.
Кроме того, даже без этого, большинство наборов данных слишком малы, чтобы иметь значение O (nlog) против O (n ^ 2). . Размер сортируемого набора должен быть достаточно большим, чтобы оказывать влияние. Даже с несколькими миллионами элементов разница во времени, вероятно, будет не очень большой.
В целом, любое данное веб-приложение, использующее быструю сортировку, с гораздо большей вероятностью будет иметь другие проблемы безопасности .
Взгляните на этот вопрос (и отмеченный ответ), в котором обсуждаются способы уменьшения наихудшего случая QuickSort:
Если производительность - это то, что имеет значение, тогда QuickSort может показаться плохим выбором в большинстве случаев, независимо от соображений безопасности. Есть ли что-то, что заставляет вас уклоняться от таких алгоритмов, как Heapsort или Mergesort?
Это так, но только в очень, очень маловероятных случаях, которых легко избежать правильно разработанному алгоритму.
Но если вы хотите быть сверхбезопасным, вы можете использовать что-то вроде Introsort , которое начинается как QuickSort, но переключается на Heap Sort, если по глубине рекурсии обнаруживает, что алгоритм
Edit: Я вижу, что Павел победил меня в Introsort.
В ответ на отредактированный вопрос: Я лично не тестировал каждую библиотеку Quicksort, но уверен, что почти все они имеют проверки, чтобы избежать худшего случая.
Я думаю, что это в значительной степени вопрос о том, где вы на самом деле используете быструю сортировку. Использование алгоритмов O (n ^ 2) отлично подходит, например, при работе с массивами из 5 элементов. С другой стороны, когда есть вероятность, что данные могут быть значительно большими, опасение, что DoS-атака - не первая проблема, с которой вы столкнетесь - первой проблемой будет снижение производительности до того, как вы столкнетесь с реальной проблемой. Учитывая большое количество других доступных алгоритмов,