Требует ли qsort последовательных сравнений или я могу использовать его для перемешивания? - PullRequest
1 голос
/ 26 апреля 2009

Обновление : Пожалуйста, подайте это под плохие идеи. Вы ничего не получаете бесплатно в жизни, и это, безусловно, доказательство. Простая идея испортилась. Это, безусловно, есть чему поучиться.

Задача ленивого программирования. Если я передам функцию, которая 50-50 возвращает значение true или false для функции сравнения qsort, я думаю, что смогу эффективно отсортировать массив структур, записывающих 3 строки кода.

int main ( int argc, char **argv)
{
    srand( time(NULL) );  /* 1 */
    ...
    /* qsort(....) */     /* 2 */
}

...

int comp_nums(const int *num1, const int *num2)
{
    float frand = 
          (float) (rand()) / ((float) (RAND_MAX+1.0));  /* 3 */

    if (frand >= 0.5f)
         return GREATER_THAN;
    return LESS_THAN;
}

Какие подводные камни мне нужно искать? Это возможно в меньшем количестве строк через обмен или это самый чистый, который я получаю для 3 нетривиальных линий?

Ответы [ 6 ]

13 голосов
/ 26 апреля 2009

Плохая идея. Я имею в виду очень плохо.

Ваше решение дает непредсказуемый результат, а не случайный результат, и существует большая разница. Вы не имеете реального представления о том, что будет делать ксорт со случайным сравнением и одинаково ли вероятны все комбинации. Это самый важный критерий для перемешивания: все комбинации должны быть одинаково вероятными. Смещенные результаты означают большие проблемы. Там нет никакого способа доказать это в вашем примере.

Вы должны реализовать тасование Фишера-Йейтса (также известное как тасование Кнута).

6 голосов
/ 26 апреля 2009

В дополнение к другим ответам, это хуже, чем простое перемешивание Фишера-Йейтса, потому что это слишком медленно. Алгоритм qsort равен O (n * log (n)), число Фишера-Йейтса равно O (n).

В Википедии имеется более подробная информация о том, почему этот тип "случайного воспроизведения" обычно не работает так же хорошо, как метод Фишера-Йейтса :

Сравнение с другими тасовками Алгоритмы

Суета Фишера-Йейтса довольно эффективный; действительно, его асимптотическое время и сложность пространства являются оптимальными. В сочетании с качественным объективным источник случайных чисел, это также гарантированно производить непредвзято Результаты. По сравнению с некоторыми другими решения, оно также имеет преимущество что, если только часть полученного нужна перестановка, может быть остановился на полпути, или даже остановился и перезапустился несколько раз, генерируя перестановку по мере необходимости. На высоком уровне языки программирования с быстрым встроенный алгоритм сортировки, альтернативный метод, где каждый элемент из набора, который нужно перетасовать, назначается случайное число и набор тогда отсортировано по этим номерам, май быть быстрее на практике необходимо], несмотря на то, что хуже асимптотическая сложность времени (O (n log n) против O (n)). Как Фишер-Йейтс в случайном порядке, этот метод также даст объективные результаты, если правильно реализовано, и может быть более терпимым определенных видов смещения в случайном номера. Тем не менее, необходимо соблюдать осторожность чтобы убедиться, что назначенный случайный числа никогда не дублируются, так как алгоритмы сортировки вообще не будут элементы порядка случайным образом в случае галстук. Вариант вышеуказанного метода который видел некоторое использование в языках которые поддерживают сортировку с пользовательские функции сравнения перемешать список, отсортировав его функция сравнения, которая возвращает случайные значения. Однако это не всегда работать: с рядом используемые алгоритмы сортировки, результаты в конечном итоге смещен из-за внутреннего асимметрия в сортировке осуществление. [7]

Ссылка на здесь :

еще одна вещь, когда писал это статья, которую я экспериментировал с различными версии методов и обнаружены еще один недостаток в оригинальной версии (переименован мной в shuffle_sort). я был неправильно, когда я сказал «это хорошо возвращается перетасованный массив каждый раз, когда это называется.»

Результаты не очень хорошо перемешаны все. Они предвзяты. Плохо. Тот означает, что некоторые перестановки (т.е. упорядочения) элементов более вероятны чем другие. Вот еще один фрагмент код, чтобы доказать это, снова заимствовано из обсуждение группы новостей:

N = 100000
A = %w(a b c)
Score = Hash.new { |h, k| h[k] = 0 }
N.times do
  sorted = A.shuffle  
  Score[sorted.join("")] += 1
end

Score.keys.sort.each do |key|
  puts "#{key}: #{Score[key]}"
end

Этот код перемешивает 100000 раз массив из трех элементы: a, b, c и записи, сколько раз каждый возможный результат был достигнуты. В этом случае есть только шесть возможных заказов, и мы должны получил каждый около 16666,66 раз. Если мы попробуем непредвзятую версию shuffle (shuffle или shuffle_sort_by), результат, как и ожидалось:

 
 abc: 16517
 acb: 16893
 bac: 16584
 bca: 16568
 cab: 16476
 cba: 16962

Конечно, Есть некоторые отклонения, но они не должен превышать нескольких процентов ожидаемое значение, и они должны быть разные каждый раз, когда мы запускаем этот код. Можно сказать, что распределение даже.

Хорошо, что произойдет, если мы используем метод shuffle_sort?

 abc: 44278 
 acb: 7462
 bac: 7538
 bca: 3710
 cab: 3698
 cba: 33314

Это не равномерное распределение на всех. Опять?

Он показывает, как метод сортировки является предвзятым, и подробно объясняет, почему это так. В конце концов он ссылается на Coding Horror :

Давайте посмотрим на правильный Алгоритм Кнута-Фишера-Йейтса.

for (int i = cards.Length - 1; i > 0; i--)
{
  int n = rand.Next(i + 1);
  Swap(ref cards[i], ref cards[n]);
}

Вы видите разницу? Я пропустил это первый раз. Сравните свопы для колоды из 3 карт:

 
Naïve shuffle   Knuth-Fisher-Yates shuffle
rand.Next(3);    rand.Next(3);
rand.Next(3);    rand.Next(2);
rand.Next(3); 

Наивное перемешивание в результате получается 3 ^ 3 (27) возможных колод комбинации. Это странно, потому что mathemатики говорят нам, что есть действительно только 3! или 6 возможных комбинации из трех карточных колод. в KFY shuffle, мы начинаем с начальной ордер, своп с третьей позиции с любой из трех карт, затем поменяйте местами снова со второй позиции с оставшиеся две карты.

2 голосов
/ 26 апреля 2009

Нет, это не будет правильно перетасовывать массив, оно будет лишь перемещать элементы вокруг их первоначального расположения с экспоненциальным распределением.

1 голос
/ 09 мая 2009

Старое новое берет это

Я думаю, что основная идея случайного рекурсивного разбиения набора на пути вниз и объединения результатов на пути вверх будет работать (это будет усреднять O (n * log n) двоичных решений, и это чертовски близко к log2 (факт (n)) но q-sort не обязательно сделает это со случайным предикатом.

Кстати, я думаю, что тот же аргумент и проблемы могут быть сказаны для любой стратегии сортировки O (n * log n).

1 голос
/ 26 апреля 2009

Функция сравнения не должна возвращать логический тип, она должна возвращать отрицательное число, положительное число или ноль, которые qsort() использует, чтобы определить, какой аргумент больше другого.

0 голосов
/ 26 апреля 2009

Рэнд не самая случайная вещь ... Если вы хотите перетасовать карты или что-то в этом роде, это не самое лучшее. Кроме того, перемешивание Кнута было бы быстрее, но ваше решение в порядке, если оно не зацикливается вечно

...