Каковы эффективность и качество этого алгоритма перестановки?
Мне удалось обойти эту проблему, когда я переписал «inspect.exe» в свой файл решения вместо отдельного проекта!
8 ответов
Я не эксперт по внутренностям Perl, таким образом, я не знаю, как "вид" будет работать здесь. Однако большинство функций вида ожидает непротиворечивость в своих сравнениях, и я ожидал бы, что они будут работать непредсказуемо, если функция самостоятельно случайна. К сожалению, непредсказуемость не является тем же как случайностью, и таким образом, у меня не было бы уверенности в Вашем переставленном массиве. Это может иметь тенденцию помещать элементы в своего рода порядок, так же, как торопливо созданное и сложное рекуррентное соотношение не может быть случайным.
Вместо того, чтобы анализировать функцию вида, я предложил бы идти с Фишером-Йетсом.
Как сказанный Knuth, случайность слишком важна, чтобы быть оставленной случиться.
$ perldoc List::Util
⋮
shuffle LIST
Returns the elements of LIST in a random order
@cards = shuffle 0..51 # 0..51 in a random order
⋮
Это было бы моим предложением.
Я на самом деле немного удивлен, что Ваша предложенная перестановка работает. В реализации Perl sort функция, это пытается получить элементы массива в порядок по возрастанию в зависимости от значения Вашей функции сравнения. Проблема, Ваша функция сравнения не дает последовательные ответы! Иногда это могло бы сказать "foo" lt "bar", в то время как другие времена это могло бы сказать "bar" lt "foo". Это имеет возможность путания алгоритма сортировки до такой степени, когда, это никогда не завершается или завершается с фатальной ошибкой или некоторым другим катастрофическим отказом.
Документация жемчуга относительно sort говорит это
Функция сравнения требуется, чтобы вести себя. Если это возвращает непоследовательные результаты (иногда говоря, что $x [1] является меньше, чем $x [2] и иногда высказывание противоположного, например), результаты не четко определены.
Таким образом, это - плохая идея сделать это.
ETA: Я просто сделал сравнительный тест. На 100 000 массивов элемента, с помощью ПЕРЕСТАНОВКИ ФИНАНСОВОГО ГОДА больше чем в 10 раз быстрее также.
Это - просто интуиция, но я думаю, что использование вида как это произведет набор, порядок которого до некоторой степени зависит от порядка исходного набора. Результаты действительно случайного вида не должны зависеть вообще от порядка исходного набора. Я не могу объяснить, почему/как, возможно, кто-то еще может (или показывать, что это на самом деле случайно)?
Относительно того, насколько эффективный это, я не уверен, но это, вероятно, не намного менее эффективно, чем какое-либо другое использование вида sort, начиная с AFAIK rand() является относительно дешевым. Я мог быть неправым там, все же.
С одной стороны, Вы знаете, что, неважно, компаратор, Вы используете вид () не может возможно быть быстрее, чем O (n, регистрируют n). Таким образом, даже если перестановка, которую это выполняет, будет справедлива, то ее производительность будет хуже.
Таким образом, действительно ли перестановка справедлива? Это, очевидно, не справедливо для некоторых (легкий проанализировать) сортировка алгоритмов. Полагайте, что простая пузырьковая сортировка - для элемента перемещается от одного конца до другого, функция сравнения должна оценить положительный для n последующих вызовов - 1 в 2^n вероятность для того, что должно быть 1 в n событии. Для быстрой сортировки трудно проанализировать, и возможно, что заканчивает тем, что был справедлив. Но если важно, чтобы это было правильно, сделайте это правильный путь.
Существует лучшая функция перестановки Фишера-Йетса, которая не использует sort встроенный в perlfaq4: Как я переставляю массив случайным образом?.
Если HelperMethod требуется вторая попытка, в этом нет ничего плохого, но ваш код в catch пытается сделать слишком много,