Попалась такая задача на C#.
Сейчас решение с сортировкой в случайно порядке, читай перемешиванием и брать первые N элементов. Выполняется за O(N logN).
Можно ли сделать как-то за O(N)?
public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}
Re: Получить M случайных и уникальных элементов из списка за O(N)
Здравствуйте, samius, Вы писали:
S>Здравствуйте, licedey, Вы писали:
L>>
L>>list.OrderBy(arg => Guid.NewGuid())
L>>
S>Вы уверены что так можно сортировать? Я — нет. Полагаю что ключи не кэшируются.
OrderBy — упорядочивает элементы используя делегат-в параметре как ключ для каждого элемента в перечислении. Это переупорядочивание отлично работает. Не понимаю о каком кэшировании идет речь.
Re[2]: Получить M случайных и уникальных элементов из списка за O(N)
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, licedey, Вы писали:
L>>Можно ли сделать как-то за O(N)? W>Можно: Reservoir sampling.
Меня волнует вопрос, как себя будет вести алгоритм, например при выборке 98 из 100 случайных элементах на последних итерациях. Ведь большая часть элементов
уже отобрана, алгоритм будет висеть пока не сгенерит 97 или 98 например. Или я ошибаюсь? Мы исключаем добавляемые элементы?
Re[3]: Получить M случайных и уникальных элементов из списка за O(N)
Здравствуйте, licedey, Вы писали:
L>Здравствуйте, samius, Вы писали:
S>>Вы уверены что так можно сортировать? Я — нет. Полагаю что ключи не кэшируются.
L>OrderBy — упорядочивает элементы используя делегат-в параметре как ключ для каждого элемента в перечислении. Это переупорядочивание отлично работает. Не понимаю о каком кэшировании идет речь.
Я подумал, что если реализация OrderBy вычисляет ключ для каждого элемента более одного раза? Тогда положение элемента может быть однозначно определено лишь при детерминированной функции вычисления ключа.
Посмотрел в код EnumerableSorter. Текущая реализация действительно использует специальный проход для того что бы закэшировать ключи для сравнения каждого элемента в массиве. При таком подходе все должно работать стабильно. Но где гарантия что это не изменится в будущем?
Re[4]: Получить M случайных и уникальных элементов из списка за O(N)
Здравствуйте, AK107, Вы писали:
S>>Но где гарантия что это не изменится в будущем?
AK>а не сломает ли это в таком случае совместимость linq с sql провайдерами, где (в sql) вполне себе норма писать так
Конечно. Засиделся я на компарерах объектов, к которым выдвигаются спецтребования. Потому и возбудился. Логично было бы предположить, что раз аналогичные требования не выдвигаются к функции получения ключа, то под капотом обязано быть нечто, что эти требования компенсирует.
Re[2]: Получить M случайных и уникальных элементов из списка за O(N)
Вроде эти алгоритмы гарантируют только случайность выборки, можете ткнуть где в них учитывается требование, чтобы в отобранных элементах не было дублей?
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Re[3]: Получить M случайных и уникальных элементов из списка за O(N)
Здравствуйте, ilvi, Вы писали:
I>Вроде эти алгоритмы гарантируют только случайность выборки, можете ткнуть где в них учитывается требование, чтобы в отобранных элементах не было дублей?
Если в исходной последовательности не было дублей, то на выходе дублей тоже не будет, потому что используется перемешивание.
Если же дубли там есть, то придется заполнять хешик и проверять его на каждом шаге и выкидывать дубли.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, ilvi, Вы писали:
I>Вроде эти алгоритмы гарантируют только случайность выборки, можете ткнуть где в них учитывается требование, чтобы в отобранных элементах не было дублей?
Опс, в исходном списке могут быть дубли?
Тогда Фишер-Ейтс точно не пойдёт, дальше зависит от данных. Если дублей много и нужны равные шансы вне зависимости от количества дублей, то проще сначала избавляться от дублей, затем отбирать. Если на равномерность наплевать, то ничего не мешает модифицировать алгоритм R, скидывая значения в хэш-таблицу и пропуская перестановки для дубликатов. Ещё лучше — перетащить топик в Алгоритмы, там местные гуру быстрее помогут.
