Как эффективно генерировать случайные подмножества строк из матрицы

Question

У меня есть большая матрица M, реализованная как vector<vector<double> с m строками, то есть матрица является вектором из m векторов из n элементов столбца.

Мне нужно создать два подмножества строк этой матрицы, то есть A содержит k строк, а B - остальные m-k строк. Строки должны быть выбраны случайным образом.

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

Два подхода, которые я рассмотрел:

1. генерирует std :: random_shuffle индексов строк, копирует строки, указанные первыми k индексами, в A, а строки, указанные другими m-k, в B
2. сделать из std :: random_shuffle M. скопировать k строк в A и m-k строк в B

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

Спасибо!

Answer 1

Если вам не нужно, чтобы B находился в случайном порядке, то random_shuffle выполняет больше работы, чем вам нужно.

Если под "STL" вы подразумеваете STL SGI, тогда используйте random_sample .

Если под "STL" вы подразумеваете стандартные библиотеки C ++, то у вас нет random_sample. Возможно, вы захотите скопировать реализацию, кроме остановки после первых шагов n. Это сократит время.

Обратите внимание, что они оба изменяют последовательность на месте. В зависимости от того, где вы на самом деле хотите, чтобы A и B заканчивались, и от того, кому принадлежит оригинал, это может означать, что вы в конечном итоге делаете 2 копии каждой строки - один раз, чтобы поместить его в изменяемый контейнер для перемешивания, затем снова, чтобы получить его конечный пункт назначения. Это больше памяти и времени обработки, чем требуется. Чтобы исправить это, вы можете swap строк из временного контейнера и в A и B. Или скопировать алгоритм, но приспособить его к:

• Составить список индексов первого вектора
• Частично перетасовать список индексов
• Скопируйте строки, соответствующие первым n индексам, в A, а остальные в B.

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

Стандарт для random_shuffle говорит, что он выполняет "свопы". Я надеюсь, что это означает, что он эффективен для векторов, но вы можете проверить, что он на самом деле использует оптимизированный swap, не копируя. Я думаю, что это должно означать это, тем более что естественная реализация такая же, как у Фишера-Йейтса, но я не уверен, следует ли использовать язык в стандарте, чтобы гарантировать это. Если это копирование, то ваш второй подход будет очень медленным. Если он использует swap, то они примерно сопоставимы. swap для вектора будет немного медленнее, чем swap для индекса, но в нем не так уж много. Замена вектора или индекса происходит очень быстро по сравнению с копированием строки, и для каждой операции существует M, поэтому я сомневаюсь, что это сильно изменит общее время выполнения.

[Редактировать: Алекс Мартелли недавно жаловался на неправильное использование термина "STL" для обозначения стандартных библиотек C ++. В этом случае это имеет значение: -)]

Answer 2

Я думаю, что random_shuffle индексов имеет смысл.

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

Answer 3

Самый простой способ: использовать генератор случайных целых чисел и поставить в очередь смещения каждой строки в отдельном контейнере (при условии, что строка имеет одинаковое смещение в каждом векторе столбца). Используемый вами контейнер будет больше зависеть от его возможного использования. (Не забудьте позаботиться об ограничении size_t и привязке жизни смещенного контейнера к самой Матрице).

Редактировать: замена указателей на смещения - имеет больше смысла и безопаснее.

Orig: Быстрый Q: каждый (внутренний) вектор является строкой или столбцом?

т.е. такое M вектор столбцов или вектор строк?