Генерация псевдослучайного дерева каталогов?

Question

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

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

edit: Или фрактальный алгоритм. Это звучит подозрительно, как фрактальный алгоритм.

---

edit 2: Неважно, думаю, я нашел очевидное решение, начнем с пустого дерева и просто используем последовательные выходы псевдослучайного генератора для детерминистского определения (на основе сгенерированного числа и состояния сгенерированного до сих пор дерева). ) выполнить одно из N действий, например создать новый подкаталог, добавить новый файл, переименовать файл, удалить файл и т. д.

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

Мне нужно сгенерировать не только одно фиксированное дерево, стратегия использования такова: немного увеличить древовидную структуру, оценить статистику производительности, еще немного увеличить древовидную структуру, оценить статистику производительности и т. Д.

Answer 1

Если это только для тестирования, что не так с некоторым простым, наивным алгоритмом генерации? Например, сгенерируйте случайное (1-10) количество подкаталогов, сгенерируйте для них имена, затем для каждого каталога рекурсивно сгенерируйте подкаталоги и некоторое количество файлов.

Это легко настраивается, и вы можете контролировать семена для rand. В зависимости от потребностей, распределение количества файлов / каталогов может быть нелинейным, но более подходящим для вас.

Звучит то, что можно за полчаса взбить и покончить с этим. Я не вижу необходимости в чем-то математическом или сложном. Если это не для развлечения, конечно: -)

Answer 2

Как вы упомянули во втором вашем редактировании, я бы, вероятно, реализовал все это как обход файлового дерева, когда PRNG решал «изменить каталог», «создать каталог», «перейти на один уровень вверх», «создать файл» , «удалить файл» и иметь другое значение, чтобы определить, какой файл удалить, какой каталог изменить, и сгенерировать имена для файлов и каталогов.

Я использовал аналогичный метод для стресс-тестирования сервера рабочих процессов, который я написал (хотя мне не нужно было отслеживать, где находятся рабочие элементы, просто нужно было случайно выбрать один для работы).

Answer 3

Это набор различных проблем, которые делают его веселой головоломкой.

Сначала у нас есть генератор псевдослучайных чисел. Есть много вещей, доступных. Я ожидаю только функцию, которая создает число в диапазоне 0..n-1.

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

randomsize() {
  int n = Random(0,10);
  if (n<10) return n;

  return Random(0,9) + 10 * random;
}

Эта функция производит небольшие числа. Большинство будет в диапазоне 0,9, но вершина практически бесконечна. Если вы хотите иметь большее число, вы также можете использовать больший порог

randomsize() {
  int n = Random(0,100);
  if (n<10) return n;

  return Random(0,9) + 10 * random;
}

Последняя проблема - как создать дерево. Это довольно просто. Но вы должны иметь в виду, что алгоритм должен закончиться. Так что вам нужно сделать одно из следующего:

• использовать максимальную глубину
• уменьшить сгенерированное число на основе уровня вложенности
• определяет количество листьев в процентах от общего числа подузлов. Этот процент должен увеличиваться на более высоких уровнях (10-50 на первом уровне, 20-60 на втором. 50-100 на пятом, 60-100 на шестом, до 90-100 на девятом и выше.

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