dotzero

↑ ↑ ↓ ↓ ← → ← → B A Start

Имплементация LRU кэша на Go

LRU: Least Recently Used — алгоритм кэширования, при котором вытесняются значения, которые дольше всего не запрашивались. Алгоритмическая сложность O(1), а потому кеш работает очень быстро и используется в memcached.

Кеш имеет очередь фиксированного размера. Когда новый элемент попадает в кеш, то добавляется в начало очереди. При запросе элемента очередь выталкивает элемент в начало, а если нужно освободить место, то из вытесняется последний элемент.

Свой memcached на Go

Писать будем потоко-небезопасную реализацию LRU кэша с фиксированным количеством ячеек. В основе алгоритма двусвязный список и хеш-таблица. Двусвязный список будет очередью, а в хеш-таблицу запишем соответствия ключа и ссылки на значение.

import (
    "container/list"
)

type Item struct {
    Key   string
    Value interface{}
}

type LRU struct {
    capacity int
    items    map[string]*list.Element
    queue    *list.List
}

func NewLru(capacity int) *LRU {
    return &LRU{
        capacity: capacity,
        items:    make(map[string]*list.Element),
        queue:    list.New(),
    }
}

Структура LRU содержит поле с количеством ячеек, поле двусвязного списка *list.List и поле для хранения хеш-таблицы map[string]*list.Element. А Item содержит поля для хранения ключа и значения кэшируемого элемента. Функция конструктор NewLru инициализирует LRU и возвращает ссылку на экземпляр.

Сохраняем значение в кэше

При сохранении элемента в кеше, инициализируем новую структуру Item и добавляем ее в начало очереди c.queue.PushFront(item). Возвращенный очередью *Element добавляем в хеш-таблицу, где ключ это идентификатор записи, а значение это ссылка на элемент очереди.

func (c *LRU) Set(key string, value interface{}) bool {
    if element, exists := c.items[key]; exists == true {
        c.queue.MoveToFront(element)
        element.Value.(*Item).Value = value
        return true
    }

    if c.queue.Len() == c.capacity {
        c.purge()
    }

    item := &Item{
        Key:   key,
        Value: value,
    }

    element := c.queue.PushFront(item)
    c.items[item.Key] = element

    return true
}

Перед добавлением в очередь проверяем нет ли уже такого ключа в хеш-таблице и если есть, то заменяем значение на новое и двигаем в начало очереди c.queue.MoveToFront(element).

Если количество элементов очереди равно максимальному количеству ячеек, то пора выбросить последний элемент из очереди и ключ из хеш-таблицы вызвав функцию purge().

func (c *LRU) purge() {
    if element := c.queue.Back(); element != nil {
        item := c.queue.Remove(element).(*Item)
        delete(c.items, item.Key)
    }
}

Получаем значение из кэша

При запросе элемента из кеша, ищем соответствие ключа в хеш-таблице и при нахождении получаем значение элемента через каст значения на структуру element.Value.(*Item).Value. Перед возвращением перемещаем элемент в начало очереди.

func (c *LRU) Get(key string) interface{} {
    element, exists := c.items[key]
    if exists == false {
        return nil
    }
    c.queue.MoveToFront(element)
    return element.Value.(*Item).Value
}

Дальше можно добавить mutex и сделать функцию потоко-безопасной. А еще можно заменить количество ячеек на размер кеша по объему памяти хранимых сущностей.

Среднеквадратическое отклонение

Расскажу о среднеквадратическом отклонении на примере собак. Имея группу собак рост которых 600, 470, 170, 430 и 300 мм. Как узнать какие из этих собак большие, какие маленькие, а какие можно отнести к средним? Тут на помощь приходит среднеквадратическое отклонениеσ (греческая буква сигма).

Формула очень проста: это квадратный корень из дисперсии случайной величины. Что такое дисперсия? Это среднее арифметическое квадратов разностей от среднего арифметического.

А теперь конкретно на примере наших собак, все вычисления буду писать на python без использования numpy. Первым делом находим среднее арифметическое всех элементов:

dogs = [600, 470, 170, 430, 300]
average = sum(dogs) / len(dogs)
# 394

Теперь надо посчитать дисперсию, для этого из каждой высоты собаки вычитаем среднее арифметическое всех элементов, сумируем и делим на количество элементов:

variance = sum([(n-average)**2 for n in dogs]) / len(dogs)
# 21704

Последним шагом извлекаем квадратный корень из дисперсии:

standard_deviation = variance ** 0.5
# ~147

Таким образом имея среднеквадратическое отклонение (147) и среднее арифметическое (394) можно сказать, что верхний порог для средней собаки — 394 + 147 = 541, а значит собака ростом 600 мм — большая. Для маленьких собак этот порог — 394 - 147 = 247, а значит собака ростом 170 мм - маленькая.

Но что делать если собак очень много и их количество постоянно растет? Обычный подход к вычислению тут не подойдет. В таком случае необходимо заменить среднее арифметическое математическим ожиданием при вычислении дисперсии.

Если вернуться к нашим собакам и мы считаем, что эти 5 собак лишь кусок от большой популяции собак, то при вычислении дисперсии необходимо делить не на число элементов, а на число элементов минус 1.

variance = sum([(n-average)**2 for n in dogs]) / (len(dogs) - 1)
# 27130
standard_deviation = variance ** 0.5
# ~164

Как поменять местами значения в колонках таблицы

Условия задачи: есть MySQL таблица table1. Используя только язык SQL запросов необходимо поменять местами значения из колонок value1 и value2. Структура таблицы имеет следующий вид:

CREATE TABLE `table1` (
  `id` INT NOT NULL AUTO_INCREMENT ,
  `value1` VARCHAR(50) NOT NULL DEFAULT '' ,
  `value2` VARCHAR(50) NOT NULL DEFAULT '' ,
  PRIMARY KEY (`id`) )
ENGINE = MyISAM;

Решение «в лоб»

Самым простым способом является явное переименование колонок таблицы. Данное решение самое простое в реализации и самое быстрое по результатам моих тестов.

ALTER TABLE  `table1`
CHANGE `value1` `value2` VARCHAR(50) NOT NULL DEFAULT '' ,
CHANGE `value2` `value1` VARCHAR(50) NOT NULL DEFAULT '';

Решение с временной переменной

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

UPDATE `table1` SET `value1`=(@temp:=`value1`), `value1` = `value2`, `value2` = @temp;

Решение с подзапросом

Поскольку MySQL не даст сделать простой UPDATE с выборкой из этой же таблицы, поэтому будем извращаться с ON DUPLICATE KEY UPDATE. Самое медленное из предложенных решений, но данный синтаксис предоставляет определенные преимущества в некоторых ситуациях.

INSERT INTO `table1`
SELECT * FROM `table1` `t2` ON DUPLICATE
KEY UPDATE `value1` = `t2`.`value2`, `value2` = `t2`.`value1`;

Перевернуть строку на PHP

Самая популярная задача на собеседованиях это переворот строки без использования функции srtrev. Решил добавить свои 5 копеек, какой я вижу эту задачу.

Первое решение на знание других встроенных функций (никто ведь не запрещал использовать их).

$s = "123abc";

preg_match_all('/./u', $s, $a);
echo implode('', array_reverse($a[0]));

Второе решение с использованием операции конкатенации выглядит еще проще.

$s = "123abc";

for ($i = strlen($s); $i >= 0; $i--) {
    $s .= $s[$i];
    $s[$i] = '';
}

И напоследок решение которым можно удивить своего работодателя, если он слабо понимает булеву алгебру.

$s = "123abc";
$a = -1;
$b = strlen($b);

while (++$a < --$b) {
    $s[$a] = $s[$a] ^ $s[$b];
    $s[$b] = $s[$a] ^ $s[$b];
    $s[$a] = $s[$a] ^ $s[$b];
}

Простой алгоритм случайной выборки с учетом веса

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

В этой заметке я покажу вам два подхода к «взвешенному» случайному выбору - один подходит для небольших списков, а другой оптимизирован для большего числа элементов.

Простой алгоритм случайной выборки с учетом веса

В общем виде этот алгоритм можно описать так:

  1. Выбрать случайное число между единицей и суммой «весов» всех элементов
  2. Спускаться по списку элементов добавляя к счетчику вес текущего элемента
  3. Проверить, если счетчик (шаг №2) больше или равен случайному числу (шаг №1), то закончить цикл и вернуть текущий элемент. В противном случае перейдите к шагу №2.

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

/**
 * Выборка случайного элемента с учетом веса
 *
 * @param array $values индексный массив элементов
 * @param array $weights индексный массив соответствующих весов
 * @return mixed выбранный элемент
 */
function weighted_random_simple ( $values, $weights )
{
    $total = array_sum( $weights );
    $n = 0;

    $num = mt_rand( 1, $total );

    foreach ( $values as $i => $value )
    {
        $n += $weights[$i];

        if ( $n >= $num )
        {
            return $values[$i];
        }
    }
}

Вот пример скрипта который выведет либо A, B, C или с вероятностью 15%, 35% и 50% соответственно:

$values = array('A', 'B', 'C');
$weights = array(3, 7, 10);

echo weighted_random_simple($values, $weights);

Алгоритм случайной выборки из тысяч элементов

Описанный выше алгоритм может работать очень медленно, когда список элементов велик, и вам необходимо сделать несколько выборок. Это потому, что он должен пройтись по всему массиву каждый раз при обращении к функции.

Однако, алгоритм может быть расширен, чтобы сделать его значительно быстрее. Вместо вычисления общего веса (шаг №1) и счетчика (шаг №2) каждый раз, можно сделать это один раз и сохранить значения счетчиков в массиве. Тогда мы сможем использовать бинарный поиск, чтобы быстро выбрать правильный элемент. Ниже приведен модифицированный вариант функции:

/**
 * Случайно выбирает один из элементов на основе их веса.
 * Оптимизирован для большого числа элементов.
 *
 * @param array $values индексный массив элементов
 * @param array $weights индексный массив соответствующих весов
 * @param array $lookup отсортированный массив для поиска
 * @param int $total_weight сумма всех весов
 * @return mixed выбранный элемент
 */
function weighted_random($values, $weights, $lookup = null, $total_weight = null)
{
    if ($lookup == null OR $total_weight == null)
    {
        list($lookup, $total_weight) = calc_lookups($values, $weights);
    }

    $r = mt_rand(1, $total_weight);

    return $values[binary_search($r, $lookup)];
}

/**
 * Создание массива используемого в бинарном поиске
 *
 * @param array $values
 * @param array $weights
 * @return array
 */
function calc_lookups($values, $weights)
{
    $lookup = array();
    $total_weight = 0;

    for ($i=0; $i < count($weights); $i++)
    {
        $total_weight += $weights[$i];
        $lookup[$i] = $total_weight;
    }

    return array($lookup, $total_weight);
}

/**
 * Ищет в массиве элемент по номеру и возвращает элемент если он найден.
 * В противном случае возвращает позицию, где он должен быть вставлен,
 * или count($haystack)-1, если $needle больше чем любой элемент в массиве.
 *
 * @param int $needle
 * @param array $haystack
 * @return int
 */
function binary_search($needle, $haystack)
{
    $high = count($haystack) - 1;
    $low = 0;

    while ( $low < $high )
    {
        $probe = (int)(($high + $low) / 2);

        if ($haystack[$probe] < $needle)
        {
            $low = $probe + 1;
        }
        elseif ($haystack[$probe] > $needle)
        {
            $high = $probe - 1;
        }
        else
        {
            return $probe;
        }
    }

    if ( $low != $high )
    {
        return $probe;
    }
    else
    {
        return ($haystack[$low] >= $needle) ? $low : $low + 1;
    }
}

Описанный выше скрипт также содержит две новые функции - calc_lookups которая вычисляет массив для использования в бинарном поиске, и непосредственно функция binary_search которая осуществляет бинарный поиск. Пример использования скрипта:

// Рассчет массивов (1 раз)
list($lookup, $total_weight) = calc_lookups($values, $weights);
//....
// Каждый раз когда вам необходимо выбрать случайный элемент:
$val = weighted_random($values, $weights, $lookup, $total_weight);

В заключение

Чтобы дать вам представление о том, какова скорость этих алгоритмов: Для каждого из них я использовал массив включающий 10 000 элементов, 10 000 раз подряд. Первый алгоритм отработал за 13 секунд, а второй всего 0,09 секунд.