VPF::Алгоритм кэширования LRU - Форум программистов

Sveta7

Дата 9.5.2012, 12:08 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 16.5.2010

Репутация: нет
Всего: нет

Добрый день!

Помогите пожалуйста с такой проблемой... необходимо реализовать кэширование с алгоритмом вытеснения lru.
Нашла в сети подходящую не сильно замудренную реализацию на Java. Пытаюсь переделать на C++, но как-то не очень получается. Может кто-то сможет помочь?
Спасибо.

Код


/**
 * 
 */
package solution.misc;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import junit.framework.Assert;

import org.junit.Test;

import com.google.inject.internal.Lists;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 */
public class CacheStrategies {

        public interface CacheStrategy<K, T> {
                /**
                 * get the data by key.
                 * 
                 * @param key
                 * @return
                 */
                T get(K key);

                /**
                 * put <key, data> pair
                 * 
                 * @param key
                 * @param data
                 */
                void put(K key, T data);

                /**
                 * helper function
                 * 
                 * @return
                 */
                List<K> toAry();
        }

        class CacheStrategyLRU<K, T> implements CacheStrategy<K, T> {
                class Node {
                        T data;
                        K key;
                        Node next;
                        Node prev;

                        public Node(K key, T data) {
                                this.data = data;
                                this.key = key;
                        }
                }

                Node head;

                Map<K, Node> map;

                int maxsize;
                Node tail;

                public CacheStrategyLRU(int maxsize) {
                        this.maxsize = maxsize;
                        map = new HashMap<K, Node>();
                        // hook up the head and tail nodes
                        head = new Node(null, null);
                        tail = new Node(null, null);
                        head.next = tail;
                        tail.prev = head;
                }

                private void attach(Node head, Node node) {
                        // add note behind the head.
                        node.prev = head;
                        node.next = head.next;
                        node.next.prev = node;
                        node.prev.next = node;
                }

                private void detach(Node node) {
                        // detach it from the queue
                        node.prev.next = node.next;
                        node.next.prev = node.prev;
                }

                /**
                 * get data
                 */
                @Override
                public T get(K key) {
                        Node node = map.get(key);
                        if (node == null)
                                return null;

                        if (map.size() == 1)
                                return node.data;

                        // refresh
                        // - detach it from the queue
                        detach(node);
                        // - attach it to head
                        attach(head, node);
                        return node.data;
                }

                /**
                 * put <key,data> into cache.
                 */
                @Override
                public void put(K key, T data) {
                        if (maxsize <= 0)
                                return;

                        Node node = map.get(key);
                        if (node != null) {
                                // hit, just update data
                                detach(node);
                                attach(head, node);
                                node.data = data;
                        } else {
                                // miss, create new data
                                node = new Node(key, data);
                                map.put(key, node);
                                attach(head, node);
                                if (map.size() > maxsize) {
                                        // overflow, remove the tail
                                        detach(tail.prev);
                                        map.remove(tail.prev.key);
                                }
                        }
                }

                /**
                 * helper function
                 */
                @Override
                public List<K> toAry() {
                        List<K> ary = new ArrayList<K>();
                        Node head = this.head.next;
                        while (head != tail) {
                                ary.add(head.key);
                                head = head.next;
                        }
                        return ary;
                }
        }

        @Test
        public void test() {
                CacheStrategy<Integer, Integer> cs = new CacheStrategyLRU<Integer, Integer>(
                                3);
                Integer[][] data = new Integer[][] { //
                // {0:put, 1:get}, {result}
                                { 0, 1 }, { 1 }, // put 1 - add
                                { 0, 2 }, { 2, 1 },// put 2 - add
                                { 0, 3 }, { 3, 2, 1 },// put 3 - add
                                { 0, 2 }, { 2, 3, 1 },// put 2 - refresh, data changed
                                { 1, 1 }, { 1, 2, 3 },// get 1 - get
                                { 0, 3 }, { 3, 1, 2 },// put 3 - refresh, data changed
                                { 1, 4 }, { 3, 1, 2 },// get 4 - miss
                                { 0, 4 }, { 4, 3, 1 },// put 4 - 2 is gone
                                { 0, 0 }, { 0, 4, 3 },// put 0 - 1 is gone
                };

                for (int i = 0; i < data.length; i += 2) {
                        int act = data[i][0];
                        int d = data[i][1];
                        if (act == 1) { // get
                                cs.get(d);
                        } else { // put
                                cs.put(d, d);
                        }
                        Assert.assertEquals(cs.toAry(), Lists.newArrayList(data[i + 1]));
                }
        }
}

sergioK1

Дата 9.5.2012, 13:06 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 417
Регистрация: 30.1.2011

Репутация: нет
Всего: нет

Цитата(Sveta7 @ 9.5.2012, 11:08)

Нашла в сети подходящую не сильно замудренную реализацию на Java. Пытаюсь переделать на C++, но как-то не очень получается.

что конкретно как-то не очень получается?

volatile

Дата 9.5.2012, 23:41 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Sveta7, К чорту джаву.
в бусте есть пример MRU-списка. http://www.boost.org/doc/libs/1_41_0/libs/...rialization.cpp
По сути это и есть кэширование с алгоритмом вытеснения lru.
В списке остаются только N последних используемых, давно неиспользуемые вытесняются.

Sveta7

Дата 11.5.2012, 21:50 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 16.5.2010

Репутация: нет
Всего: нет

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

volatile, большое спасибо за информацию. Но так как я профан в C++, то не могли бы вы привести пример, как использовать boost в рамках моей задачи?

volatile

Дата 11.5.2012, 23:41 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Цитата(Sveta7 @ 11.5.2012, 21:50

)

Но так как я профан в C++, то не могли бы вы привести пример, как использовать boost в рамках моей задачи?

По ссылке что я привел выше, готовый пример.
Если оттуда удалить сериализацию, и пользовательский ввод/вывод, то останется то что нужно.
В принципе там останется несколько строчек. Так как вся логика реализована в boost::multi_index
Предполагаю что это учебный проект, и там нужно все запрограммировать вручную, в таком случае это вам не подойдет.

зы:а вообще, не вижу попыток что-то сделать самостоятельно.

sergioK1

Дата 13.5.2012, 09:31 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 417
Регистрация: 30.1.2011

Репутация: нет
Всего: нет

Цитата(Sveta7 @ 11.5.2012, 20:50)

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

ну хоть какие то усилия сделайте ,
какого этого ? на форумах где читают мысли Я не бываю smile

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »