#performance #hashset
#Производительность #набор хэшей
Вопрос:
У меня есть два больших списка, например, с 10^7 и 10^5 элементами. Ожидается, что их пересечение будет содержать, скажем, 10^3 элемента. Мне не нужен сам набор пересечений, а только один случайный его элемент. Мне приходится делать это часто, каждый раз для новых наборов, поэтому производительность очень важна.
Наборы содержат целые числа. Они разрежены и неравномерно заселены различными распределениями. Я бы знал максимальное значение (обычно 10^9) или другие «нормальные» статические свойства бесплатно. (Также хэш-наборы этих списков могут быть предоставлены бесплатно)
Я хочу нарисовать общий элемент из обоих равномерно распределенных списков. (каждый из 10^3 с одинаковым шансом).
Есть ли быстрый способ сделать это? Быстрее, чем вычислять пересечение, и быстрее, чем рисовать случайным образом из одного и проверять, содержится ли оно в другом.
Комментарии:
1. Отсортируйте оба списка, затем следуйте логике объединения двух отсортированных списков, это даст вам наименьшую запись, которая появляется в обоих.
2. @MarkLavin спасибо за комментарии. Два списка могут быть отсортированы бесплатно. Однако мне нужен равномерно выбранный случайный элемент, а не самый маленький. Любая дальнейшая идея будет оценена по достоинству. Я обдумываю идею сделать вашу точку зрения с помощью скремблированной версии списков, разве я не совсем понимаю, как это сделать.
3. Затем (поскольку оба списка отсортированы) просто начните не с самого маленького элемента, а со случайной позиции
4. Здесь проблема будет заключаться в том, что списки должны быть заполнены неравномерно. Он гораздо чаще выбирал бы элемент «после разрыва».