Как выбрать случайное (маленькое) демонстрационное использование данных, Отображают/Уменьшают?
Я хочу записать отобразить/уменьшить задание для выбора многих случайных выборок из большого набора данных на основе условия уровня строки. Я хочу минимизировать количество промежуточных ключей.
Псевдокод:
for each row
if row matches condition
put the row.id in the bucket if the bucket is not already large enough
Вы сделали что-то вроде этого? Есть ли какой-либо известный алгоритм?
Демонстрационное, содержащее последовательные строки, также достаточно хорошо.
Спасибо.
2 ответа
Подход Карла отлично работает, но мы можем значительно уменьшить объем данных, производимых картографами.
Пусть K желаемое количество отсчетов. Мы предполагаем, что он достаточно мал, чтобы хранить его в памяти на одном из ваших узлов. Мы присвоим случайное значение каждой совпадающей строке, а затем воспользуемся модификацией алгоритма выбора , чтобы найти K наименьших значений.
На этапе настройки каждого преобразователя создайте приоритетную очередь ; Куча Фибоначчи - хороший выбор для этого. Мы будем использовать числа с плавающей запятой в качестве приоритета; если у вас огромный объем данных, может быть более уместным дублирование, чтобы избежать связей. Для каждой строки, соответствующей вашему условию, вставьте эту строку в очередь приоритета со случайно выбранным числом с плавающей запятой между 0 и 1 в качестве приоритета. Если у вас в очереди более K вещей, удалите самый ценный элемент (это противоположно терминологии стандартной кучи Фибоначчи).
Наконец, в конце сопоставителя выдайте все, что есть в вашей очереди. Для каждого генерируемого вами элемента используйте в качестве ключа приоритет как FloatWritable и некоторое представление соответствующей строки в качестве значения (идентификатор строки или, возможно, все содержимое строки). Вы будете выдавать только K значений для каждого преобразователя (или меньше, если в этом преобразователе было меньше K совпадающих строк).
В вашем единственном редукторе Hadoop автоматически просматривает ключи в порядке от самого низкого до самого высокого.Выведите строки, соответствующие первым видимым клавишам K (самый низкий K ), затем выйдите.
Это работает, потому что каждая совпадающая строка имеет одинаковую вероятность наличия одного из K наименьших значений с плавающей запятой. Мы отслеживаем K наименьших чисел с плавающей запятой для каждого преобразователя, чтобы убедиться, что мы не пропустили ни одного, а затем отправляем их редуктору, чтобы найти K наименьшее в целом.
Mappers: Выведите все подходящие значения, каждое со случайным целочисленным ключом.
Один редуктор: вывести первые N значений, отбрасывая ключи.
Сортировщик случайным образом изменит порядок вывода картографа. Вы не знаете, сколько квалифицирующих значений найдет преобразователь, поэтому каждый преобразователь должен вывести все подходящие значения из своего раздела.
В общем, мне нравится создавать простые инструменты отображения / сокращения, подобные этому, которые используют как можно больше механизмов Hadoop; В конечном итоге я снова использую их в разных задачах.