Alrond's technoblog

Для задачи хранения состояний множества элементов иногда используются битовые маски. Например, о прочтении комментариев к статьям для каждого пользователя. И хотя в этом случае лучше хранить время последнего захода в конкретную тему, но могут возникнуть и другие задачи, в которых необходимо запоминать бинарные данные для элементов, не содержащих дату.

Можно использовать M2M связь между User и объектом. Главный недостаток - это большие издержки на индекс и количество записей, если пользователей и объектов наблюдения очень много. Но можно использовать битовые маски, лишенные этого недостатка.

Идея такова, что для каждого пользователя существует только одна запись в базе, а номер байта в этой записи и номер бита в этом байте определяют состояние определенного элемента. В стандартной поставке django нет модели, поддерживающей blob-элементы в базах (битовые данные), поэтому я использовал обычное текстовое поле, один символ которого определяет состояние для четырех элементов. То есть запись в 250 байт дает нам данные о состоянии для 1000 элементов.

Например, имеем 10.000 анекдотов (чтобы этот метод был правомочен, их должно быть много, значит скорее всего статьи мелкие :)
И имеем 100.000 пользователей. Тогда модель связей будет выглядеть примерно так:

class Readed(models.Model):
  user = models.ForeignKey(User, related_name='readed')
  readed_flags = models.TextField(blank=True)

Количество записей равно количеству пользователей, то есть 100.000
А размер readed_flags максимум до 2500 байт. (10.000/4)
С данным решением можно хранить не все 2500 байт, а только до самого большого прочтенного ID, деленного на 4.

Флаг прочитанности и его установка происходит с помощью двух функций внутри модели: is_readed(id) и set_readed(id)
Только после set_readed() надо не забыть записать в базу через save()
Я специально не сделал запись внутри функции, чтобы можно было безболезненно для скорости устанавливать флаги для большого количества анекдотов и потом одним махом (запросом в базу) сохранять.

Вот полный код модели:

READED_FLAG = [1,2,4,8,0]
class Readed(models.Model):
  user = models.ForeignKey(User, related_name='readed')
  readed_flags = models.TextField(blank=True)

  def dec2hex(self,n):
    return "%X" % n
  
  def hex2dec(self,s):
    return int(s, 16)
  
  def is_readed(self,num):
    if num < 1:
      raise ValueError("Must be positiv and not null")
    byte_position, bit_position = divmod(num-1,4)
    notpresent = byte_position + 1 - len(self.readed_flags)
    if notpresent:
      return False
    four_status = self.hex2dec(self.readed_flags[byte_position])
    return (four_status & READED_FLAG[bit_position]) != READED_FLAG[4]
  
  def set_readed(self,num):
    if num < 1:
      raise ValueError("Must be positiv and not null")
    byte_position, bit_position = divmod(num-1,4)
    notpresent = byte_position + 1 - len(self.readed_flags)
    for i in xrange(notpresent):
      self.readed_flags += "0"
    if notpresent:
      four_status = 0
    else:
      four_status = self.hex2dec(self.readed_flags[byte_position])
    four_status_new = self.dec2hex(four_status|READED_FLAG[bit_position])
    readed_flags_new = self.readed_flags[:byte_position]+ \
                    four_status_new+self.readed_flags[byte_position+1:]
    self.readed_flags = readed_flags_new

Применение этого метода шире, чем просто замена M2M поля, у кого насколько хватит фантазии ;)

Top Posts:

• Результаты тестирования шести ведущих фреймворков на производительность
• Дополнение к тесту MVC-фреймворков
• Ну и где купить ноутбук с Linux? Ответы 13 фирм-производителей.