Выборка случайной взвешенной записи из БД

Задача

Имеется таблица с некоторыми записями (пусть это будут баннеры, к примеру). Нужно выбрать из этой таблицы случайную запись.

И всё бы хорошо, но каждая запись имеет свой вес (weight) выраженный целым числом от 0 до 100. Чем больше этот вес, тем больше должна быть вероятность выборки данной записи. Случай weight=0 означает, что запись вообще не должна попадать в выборку.

Решение

Представим каждую запись из таблицы как отрезок длины weight. Положим их на одной прямой начиная с 0 друг за другом.

В таблице заведём дополнительные поля left и right. left будет соответствовать левой координате отрезка на прямой, а right - соответственно правой. Пусть max равно максимальному значению right. Тогда мы можем взять случайную координату rand из промежутка [0,max). Отрезок который содержит в себе эту координату и будет искомым. При попадании rand на границу отрезка, правый отрезок отбрасывается.

Реализация

Я не буду расписывать по шагам как это сделать, а просто выкладываю работающие функции в том виде, в котором они лежат у меня в проекте. Знающие люди найдут в них всё, что надо.

Сохранение/изменение записи

$params - ассоциативный массив с сохраняемыми данными

function save($params){
 $id_bg = empty($params['id_bg']) ? 0 : intval($params['id_bg']);
 
 $params['bg_weight'] = (empty($params['bg_weight']) || $params['bg_weight']<0) ?
    0 : ($params['bg_weight']>100 ? 100 : $params['bg_weight']);
 // Проверим существование редактируемой записи
 if(!empty($id_bg) && isset($params['bg_weight'])){
   $res = mysql_query('SELECT bg_left,bg_weight FROM '.$this->bg_table.
     ' WHERE id_bg="'.$id_bg.'" LIMIT 1',$this->db->conn) or $this->db->Error();
   if($res){
     $sheet = mysql_fetch_assoc($res);
     mysql_free_result($res);
     $sheet['shift'] = intval($params['bg_weight'])-intval($sheet['bg_weight']);
     $params['bg_right'] = $sheet['bg_left']+$params['bg_weight'];
   }else{
     $id_bg = 0;
   }
 }
 
 // Если добавляем запись
 if(empty($id_bg)){
   $res = mysql_query('SELECT max(bg_right) FROM '.$this->bg_table,$this->db->conn)
      or $this->db->Error();
   if($res){
     $max = array_shift(mysql_fetch_assoc($res));
     mysql_free_result($res);
   }else{
     $max = 0;
   }
   $params['bg_left'] = $max;
   $params['bg_right'] = $max+intval($params['bg_weight']);
 }
 
 unset($params['id_bg']);
 $id_bg = $this->db->updateRecord($id_bg,'id_bg',$this->bg_table,$this->bg_params,$params);
 if(!empty($id_bg) && !empty($sheet['shift'])) 
   mysql_query('UPDATE '.$this->bg_table.' SET bg_left=bg_left+'.$sheet['shift'].
   ',bg_right=bg_right+'.$sheet['shift'].' WHERE bg_left>'.$sheet['bg_left'].
   ' OR (bg_left='.$sheet['bg_left'].' AND bg_right>bg_left AND id_bg<>'.$id_bg.')'
   ,$this->db->conn) or $this->db->Error();
 return $id_bg;
}

Удаление записи по id

function delete_by_id($id){
 if(empty($id) || !is_numeric($id)) return false;
 // Проверим существование удаляемой записи
 $res = mysql_query('SELECT bg_left,bg_weight FROM '.$this->bg_table.' WHERE id_bg="'.
           $id.'" LIMIT 1',$this->db->conn) or $this->db->Error();
 if(!$res) return false;
 $sheet = mysql_fetch_assoc($res);
 mysql_free_result($res);
 $shift = intval($sheet['bg_weight']);
 mysql_query('UPDATE '.$this->bg_table.' SET bg_left=bg_left-'.$shift.',bg_right=bg_right-'.
  $shift.' WHERE bg_left>'.$sheet['bg_left'],$this->db->conn) or $this->db->Error();
 return $this->db->Query('DELETE FROM '.$this->bg_table.' WHERE id_bg="'.$id.'"');
}

Выборка случайной записи

function get_random(){
 $res = mysql_query('SELECT max(bg_right) FROM '.$this->bg_table,$this->db->conn) 
     or $this->db->Error();
 if($res){
   $max = array_shift(mysql_fetch_assoc($res));
   mysql_free_result($res);
 }else{
   return false;
 }
 if($max==0) return false;
 $rand = rand(0,$max-1);
 return array_shift($this->db->Query('SELECT * FROM '.$this->bg_table.
            ' WHERE bg_left<='.$rand.' AND bg_right>'.$rand.' LIMIT 1'));
}

В функциях используются следующие не описанные в этой статье методы:

$this->db->UpdateRecord($id, $key_name, $table, $params, $values ) - обновление/создание записей в таблице.

$this->db->Query($query) - SQL запрос к БД. В случае SELECT возвращает массив со значениями.

Тэги: mysql, random

Комментарии:

Добавление комментария

Как вас зовут: E-mail:

или

Яндекс Мой Круг Yahoo! Google Livejournal OpenId

Комментарии перед публикацией просматриваются и одобряются (или не одобряются), спасибо за понимание.