Случайно сгенерированные отсортированные массивы: сравнение производительности поиска
Я делаю программу, которая тестирует и сравнивает статистику Последовательный ключ поиск и интерполирование бинарный поиск. Я прошу совета:
Каков наилучший способ отсортировать случайно сгенерированный массив целых чисел или даже сгенерировать его как отсортированный (если это имеет смысл) в данном контексте?
Я изучал некоторые методы сортировки, но, если учесть, что акцент на поиск (не сортировка) спектакль, Все расширенные сортировки кажутся довольно сложными для использования только в одном служебном методе. Учитывая, что массив должен быть больше 106 (для целей тестирования), варианты Modified / Bubble, Selection или Insertion не являются опцией.
Дополнительным ограничением является то, что все члены массива должны быть уникальный.
Сейчас, моя первоначальная идея должен был разделить интервал [INT_MIN, INT_MAX] в N интервалы (N длина массива), а затем добавить случайное целое число из, 0 в 232/ п (округляется в меньшую сторону) до начала каждого интервала.
Проблема в том:
Я предполагаю, что, как N поднимается ближе к 232, Как и у меня, поиск по интерполяции начинает давать лучшие и лучшие результаты, так как интерполяция становится более точной.
Тем не мение:
Если я полагаюсь исключительно на генераторы псевдослучайных чисел (лайк rand();), их дисперсионные характеристики диктуют ту же тенденцию для генерируемой тогда отсортировано массив, то есть — интерполяция становится лучше при точном определении наиболее вероятного местоположения, когда размер становится ближе к int предел. Характеристики однородности / дисперсии теряются как N поднимается к INT_MAX, таким образом, из-за установленных ограничений интерполяция, кажется, всегда выигрывает.
Не стесняйтесь обсуждать, критиковать и разъяснять этот вопрос по своему усмотрению, но я довольно отчаянно нуждаюсь в ответе, потому что тест в любом случае сфальсифицирован в пользу Интерполяции, и я хочу проанализировать их справедливо. Короче говоря: я хочу убедиться, что моя первоначальная идея не склоняет чашу весов в пользу Интерполяции, и я хочу использовать ее, потому что она На).
Решение
Итак, вы хотите создать «массив», который имеет N уникальных случайных чисел, и они должны быть в отсортированном порядке? Это звучит как идеальное использование для std::set. При вставке элементов в set они сортируются для нас автоматически, и набор может содержать только уникальные элементы, поэтому он проверяет, было ли уже сгенерировано случайное число.
std::set random_numbers;
std::random_device rd;
std::mt19937 mt(rd());
while (random_numbers.size() < number_of_random_numbers_needed)
{
random_numbers.insert(mt());
}
Затем вы можете преобразовать набор в что-то еще, как std::vector или же std::array если вы не хотите хранить его как набор.
Другие решения
Вот метод для генерации упорядоченной случайной последовательности. Это использует Алгоритм Кнута S и взято из книги Программирование Жемчуг.
Для этого требуется функция, которая возвращает случайный дубль в диапазоне [0,1). я включен my_rand() В качестве примера. Я также изменил его, чтобы взять выходной итератор для назначения.
namespace
{
std::random_device rd;
std::mt19937 eng{ rd() };
std::uniform_real_distribution<> dist; // [0,1)
double my_rand() { return dist(eng); }
}
// Programming Pearls column 11.2
// Knuth's algorithm S (3.4.2)
// output M integers (in order) in range 1..N
template <typename OutIt>
void knuth_s(int M, int N, OutIt dest)
{
double select = M, remaining = N;
for (int i = 1; i <= N; ++i) {
if (my_rand() < select / remaining) {
*dest++ = i;
--select;
}
--remaining;
}
}
int main()
{
std::vector<int> data;
knuth_s(20, 200, back_inserter(data)); // 20 values in [1,200]
}
Хорошо, это я решил перенести ответственность на встроенный PRNG и выполнить следующее:
добавлять N rand() результаты в двоичный дерево и заполните массив, пройдя его по порядку (от крайнего левого листа).
Как насчет генерации отсортированного массива из статистических свойств?
Это, вероятно, требует некоторого рытья, но вы должны быть в состоянии генерировать целые числа по порядку, добавляя случайную разницу, среднее значение которой является стандартным отклонением вашей общей выборки.
Это создает некоторую проблему на границах диапазона, но, учитывая размер вашей выборки, вы, вероятно, можете ее игнорировать.