1 //QuickAccess.h 2 3 #pragma once 4 5 #include <map> 6 7 struct QANode 8 { 9 QANode(int _key, int _value) 10 : key(_key) 11 , value(_value) 12 , next(nullptr) 13 , prev(nullptr) 14 {} 15 QANode* next; 16 QANode* prev; 17 int key; 18 int value; 19 }; 20 21 class QuickAccess 22 { 23 public: 24 QuickAccess(); 25 26 QuickAccess(int size); 27 28 ~QuickAccess(); 29 30 int Access(int id); 31 32 double GetHitRate(); 33 34 void PrintItems(); 35 36 private: 37 void MoveToHead(QANode* hitNode); 38 39 void InsertNode(QANode* newNode); 40 41 int Search(int id); 42 43 private: 44 int m_nCapacity; 45 int m_nSize = 0; 46 std::map<int, void*> m_map; 47 QANode* m_pRoot; 48 49 int m_nAccessCount = 0; 50 int m_nHitCount = 0; 51 };
1 //QuickAccess.cpp 2 3 #include "QuickAccess.h" 4 #include <cstdlib> 5 #include <ctime> 6 7 QuickAccess::QuickAccess() 8 : m_nCapacity(10) 9 { 10 QuickAccess(m_nCapacity); 11 } 12 13 QuickAccess::QuickAccess(int nCapacity) 14 : m_nCapacity(nCapacity) 15 { 16 srand(time(0)); 17 m_pRoot = new QANode(0, 0); 18 m_pRoot->prev = m_pRoot; 19 m_pRoot->next = m_pRoot; 20 } 21 22 QuickAccess::~QuickAccess() 23 { 24 QANode* currentNode = m_pRoot->next; 25 QANode* deleteNode = currentNode; 26 while (currentNode != m_pRoot) { 27 currentNode = currentNode->next; 28 delete deleteNode; 29 deleteNode = currentNode; 30 } 31 delete m_pRoot; 32 m_pRoot = nullptr; 33 } 34 35 int QuickAccess::Access(int key) 36 { 37 m_nAccessCount++; 38 auto it = m_map.find(key); 39 if (it == m_map.end()) {//未命中 40 int value = Search(key); 41 InsertNode(new QANode(key, value)); 42 } 43 else {//命中 44 m_nHitCount++; 45 MoveToHead((QANode*)m_map[key]); 46 } 47 return ((QANode*)m_map[key])->value; 48 } 49 50 //1,2,3,4,5 51 void QuickAccess::MoveToHead(QANode* hitNode) 52 { 53 hitNode->prev->next = hitNode->next; 54 hitNode->next->prev = hitNode->prev; 55 56 hitNode->next = m_pRoot->next; 57 m_pRoot->next->prev = hitNode; 58 59 hitNode->prev = m_pRoot; 60 m_pRoot->next = hitNode; 61 } 62 63 void QuickAccess::InsertNode(QANode* newNode) 64 { 65 //insert new item to head 66 newNode->next = m_pRoot->next; 67 m_pRoot->next->prev = newNode; 68 m_pRoot->next = newNode; 69 newNode->prev = m_pRoot; 70 m_map[newNode->key] = newNode; 71 if (m_nSize == m_nCapacity) {//full 72 //delete last item 73 QANode* lastSecondItem = m_pRoot->prev->prev; 74 m_map.erase(lastSecondItem->next->key); 75 delete lastSecondItem->next; 76 lastSecondItem->next = m_pRoot; 77 m_pRoot->prev = lastSecondItem; 78 } 79 else { 80 m_nSize++; 81 } 82 } 83 84 int QuickAccess::Search(int id) 85 { 86 int reverse = 0; 87 while (id) { 88 reverse = (reverse * 10) + (id % 10); 89 id /= 10; 90 } 91 return reverse; 92 } 93 94 double QuickAccess::GetHitRate() 95 { 96 return (m_nHitCount * 1.0) / m_nAccessCount; 97 } 98 99 void QuickAccess::PrintItems() 100 { 101 QANode* currentNode = m_pRoot->next; 102 int alignCnt = 1; 103 printf("\n******************************PrintItems*************************************\n"); 104 while (currentNode != m_pRoot) { 105 printf("%d[%d] ", currentNode->key, currentNode->value); 106 if (alignCnt % 10 == 0) { 107 printf("\n"); 108 alignCnt = 0; 109 } 110 alignCnt++; 111 currentNode = currentNode->next; 112 } 113 printf("\n"); 114 }
// ConsoleApplication1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include <iostream> #include <random> #include "QuickAccess.h" void QuickAccessTest(); int main() { QuickAccessTest(); return 0; } void QuickAccessTest() { srand(time(0)); int cacheSize = 0; int searchRange = 0; while (1) { printf("input cache size and search range: "); if (scanf_s("%d,%d", &cacheSize, &searchRange) != 2) { return; } QuickAccess qa(cacheSize); for (int i = 0; i < 100000; i++) { int randValue = rand() % searchRange; qa.Access(randValue); } qa.PrintItems(); printf("\nhitRate = %lf\n", qa.GetHitRate()); } printf("\n\n"); }