C #: алгоритм создания случайных равномерно распределенных потенциально перекрывающихся диапазонов

Question

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

Но когда дело доходит до генерации случайных вещей, я не очень хорош. Я создал что-то вроде этого:

    private static IEnumerable<Range<int>> GenerateRanges()
    {
        var r = new Random();
        var n = 10000;
        while(--n >= 0)
        {
            var start = r.Next(10000);
            var end = r.Next(10000);
            if (end < start)
                Swap(ref start, ref end);
            yield return Range.Create(start, end);
        }
    }

Конечно, это создает много диапазонов, но они не дают особенно интересных результатов, так как я всегда получаю только один диапазон после их свертывания. Как я могу создать более интересные диапазоны?

Answer 1

private static IEnumerable<Range<int>> GenerateRanges(int amount, int max, float density, int seed)
{
    var r = new Random(seed);
    var commonLength = max * density / amount; // edited
    var maxLength = commonLength * 2;
    while(--amount >= 0)
    {
        var length = r.Next(maxLength);
        var start = r.Next(max - length);
        var end = start + length;
        yield return Range.Create(start, end);
    }
}

Использование может быть: GenerateRanges(1000, 10000, 1.0, someTestSeed) или может быть: GenerateRanges(1000, 10000, .5, someTestSeed) для меньшего перекрытия

Answer 2

Если вы выберете начальную и конечную точки, диапазоны не будут распределены равномерно, а будут сосредоточены в центре. 50% диапазонов будут перекрывать центральную точку.

Сначала выберите размер для диапазона, затем поместите его где-нибудь между нижним и верхним пределами, то есть от 0 до 10000:

private static IEnumerable<Range<int>> GenerateRanges(int minSize, int maxSize) {
   Random r = new Random();
   for (int n = 0; n < 10000; n++) {
      int size = r.Next(minSize, maxSize);
      int start = r.Next(10000 - size);
      yield return Range.Create(start, start + size);
   }
}

Вы можете использовать разные значения для minSize и maxSize, чтобы управлять вероятностью получения перекрывающихся диапазонов.

Answer 3

Вы можете попробовать это:

• начните с меньших n - это даст вам в какой-то момент некоторые непересекающиеся регионы

• использовать фиксированное начальное число для случайных значений (для которых можно установить разные значения), чтобы получить воспроизводимые результаты

Другая идея заключается в использовании нескольких циклов для генерации, и каждый цикл имеет свой собственный набор минимальных и максимальных значений:

var start = r.Next(5000);
var end = start + r.Next(1000);

var start = 6500 + r.Next(1000);
var end = start + r.Next(1000);

Это всегда должно дать вам, по крайней мере, две непересекающиеся области (приблизительно 0-6000 и 6500-8500)

Answer 4

Убедитесь, что вы также добавили специальные тесты для угловых случаев, например:

• Пустой список диапазонов
• Два одинаковых диапазона
• Два диапазона, которые частично перекрываются
• Два диапазона, которые частично перекрываются, но указаны в обратном порядке (т. Е. Измените, какой из них добавляется в список первым)
• Два диапазона, которые не перекрываются, и проверьте оба пути
• Два диапазона, которые касаются (т. Е. 1-10 и 11-20) целочисленных значений, но, возможно, их не следует объединять

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