Количество уникальных пользователей, если пользователь посещает n раз - PullRequest
Новая
       42

Количество уникальных пользователей, если пользователь посещает n раз

1 голос
/ 25 мая 2019

Я хочу реализовать FreqCapping в рекламной сети. Я хочу обслуживать кампанию для уникальных пользователей только n раз в день. Если n = 1, я мог бы реализовать это с BloomFilter в redis, но обычно n больше 1. Существует ли какая-либо структура данных (даже вероятностная структура данных), которая нацелена на эту проблему? И это реализовано в Redis?

Ответы [ 2 ]

3 голосов
/ 27 мая 2019

Звучит так, как будто вы описываете Количество минутных набросков , и хотя в ядре Redis его нет, RedisBloom делает:)

1 голос
/ 25 мая 2019

Если n мало, просто используйте фильтр Блума на '1x' + user, '2x' + user, ..., n + 'x' + 'user'.Как подробно, проверьте их в случайном порядке.Это означает, что, когда пользователь был просмотрен только небольшую часть времени, у вас будет меньше поисков.

Если n большой, рассмотрите возможность делать только фиксированное количество случайных поисков.Это меняет производительность, когда вы приближаетесь к своему пределу, иногда выбирая не заполнять, когда вы приближаетесь к своему пределу.Например, с максимум 4 поисками, на 50% пути к пределу вы делаете правильный выбор более 90% времени, а на 80% пути к пределу вы все равно делаете правильный выбор около 60% времени.время.И если n=20, вы экономите лот времени, когда вы достигнете предела.

Я уверен, что есть какой-то специальный фильтр Блума, который достигает аналогичных пределовгде вы проверяете / устанавливаете случайное подмножество хеш-функций каждый раз (проверяете больше, чем вы бы установили).Но вы не найдете эту специальную структуру, уже встроенную в Redis.

Я предлагаю следующую вероятностную версию: 

def is_available(user, k=4, n=20):
    tried = []
    for 1..k:
        i = rand(n)
        while i in tried:
            i = rand(n)
        id = user + ":" + str(i)
        if bloomfilter.lookup(id):
            tried.append(i)
        else:
            bloomfilter.add(id)
            return True
    return False

Точка рандомизации заключается вуменьшить количество поисков вам нужно.Если вы идете в том же порядке каждый раз, то при 10-м посещении у вас будет 9 поисков, прежде чем вы обнаружите, что они не превышают квоту.Но если n равно 20, а вы работаете в случайном порядке, то половины времени первого поиска будет достаточно.Это уменьшает количество поездок в оба конца, что повышает производительность, что очень важно для adtech.

...