Эффективный выбор набора случайных элементов из связанного списка
Как правило, ответ на ваш вопрос - нет.
Однако в некоторых случаях может быть возможно отобразить часть страницы ASP.net, а затем поместить результат на страницу ASP.
Я экспериментировал с этим немного на прошлой неделе с использованием AJAX.
Вот что вы можете сделать.
Предположим, что у вас есть страница ASP.net с формы в нем, которую вы хотите отобразить на странице ASP.
1) Создайте страницу ASP.net с формой и оберните ее в ASP: Panel - дайте ей идентификатор: pnlForm 2 ) В коде ASP.net введите следующий код в Page_Load: pnlForm.RenderControl().
System.IO.StringWriter stringWriter = new System.IO.StringWriter();
HtmlTextWriter htmlWriter = new HtmlTextWriter(stringWriter);
pnlReport.RenderControl(htmlWriter);
Response.Write(stringWriter.ToString());
3) Добавьте следующий фрагмент кода в конец кода:
// This snippet is neccessary to get ASP.net to render the report outsisde the page to write to an Excel spreadsheet.
public override void VerifyRenderingInServerForm(Control control)
{
return;
}
4) Создайте пустую div на вашей классической странице ASP - дайте ей ID formDiv.
5) На классической странице ASP используйте jQuery.ajax для извлечения формы и поместите его на классическую страницу ASP:
$.ajax({
type: "GET",
url: "myASPdotNetpage.aspx",
success: function(response) { $('#formDiv').html(response); }
});
Как вы можете себе представить, это не совсем то, как предполагается использовать фреймворк, но если вам действительно нужно отобразить некоторые ASP.net и поставить это немного e else (например, на странице ASP или даже в электронной таблице), вы можете по крайней мере захватить HTML.
5 ответов
Это называют Водохранилище, Выбирающее проблема. Простое решение должно присвоить случайный номер каждому элементу списка, поскольку Вы видите его, затем сохраните вершину (или нижняя часть) k элементами, как заказано случайным числом.
Если Вы не знаете длину списка, то необходимо будет пересечь его завершенный для обеспечения случайных выборов. Метод, который я использовал в этом случае, является тем, описанным Tom Hawtin ( 54070 ). При пересечении списка Вы сохраняете k элементы, которые формируют Ваш случайный выбор к той точке. (Первоначально Вы просто добавляете первое k элементы, с которыми Вы встречаетесь.) Затем с вероятностью k/i, Вы заменяете случайный элемент от своего выбора с i th элемент списка (т.е. элемент, который Вы в, в тот момент).
легко показать, что это дает случайный выбор. После наблюдения m элементы (m > k), у нас есть это каждый из первых m, элементы списка являются частью Вас случайный выбор с вероятностью k/m. То, что это первоначально хранения тривиально. Тогда для каждого элемента m+1, Вы помещаете его в свой выбор (заменяющий случайный элемент) с вероятностью k/(m+1). Теперь необходимо показать, что все другие элементы также имеют вероятность k/(m+1) из того, чтобы быть выбранным. У нас есть это, вероятность k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1))) (т.е. вероятность, что элемент был во времена списка вероятность, что это все еще там). С исчислением можно прямо показать, что это равно [1 112].
Почему Вы не можете просто сделать чего-то как
List GetKRandomFromList(List input, int k)
List ret = new List();
for(i=0;i<k;i++)
ret.Add(input[Math.Rand(0,input.Length)]);
return ret;
, я уверен, что Вы не имеете в виду что-то, что простой, таким образом, можно определить далее?
Я предложил бы: Сначала найдите свои k случайные числа. Отсортируйте их. Тогда пересеките и связанный список и Ваши случайные числа однажды.
, Если Вы так или иначе не знаете длину своего связанного списка (как?), тогда Вы могли захватить первый k в массив, затем для узла r, генерировать случайное число в [0, r), и если это - меньше, чем k, замените rth объект массива. (Не полностью убежденный, который не смещает...)
Кроме этого: "На вашем месте я не запустил бы отсюда". Вы - верный связанный список, является правильным для Вашей проблемы? Есть ли не лучшая структура данных, такая как старый добрый список плоской антенной решетки.
Ну, действительно необходимо знать то, что N во времени выполнения, по крайней мере, даже если это включает выполнение дополнительной передачи по списку для подсчета их. Самый простой алгоритм, чтобы сделать это должно просто выбрать случайное число в N и удалить тот объект, повторные k времена. Или, если допустимо возвратить повторные числа, не удаляйте объект.
, Если у Вас нет ОЧЕНЬ большого N и очень строгих требований к производительности, этот алгоритм выполнения с O(N*k) сложность, которая должна быть приемлемой.
Редактирование: Nevermind, метод Tom Hawtin является путем лучше. Выберите случайные числа сначала, затем пересеките список однажды. Та же теоретическая сложность, я думаю, но намного лучше ожидаемое время выполнения.