Spotify에서 노래를 검색할 때 최근 검색은 모두'최근 검색'아래에 저장됩니다.유사한 기능을 어떻게 구축하는지 봅시다.

요구 사항 파악

Spotify의 최근 검색 구성 요소의 모든 기능을 살펴보겠습니다.
1>노래 검색:

노래를 검색할 때 이 노래는'최근 검색'아래에 열거됩니다. 목록이 비어 있기 때문에 먼저 Coldplay를 추가합니다.
2> 더 많은 노래 검색:

더 많은 노래를 검색할 때, 목록이 증가하고, 노래는 목록으로 밀려난다.
명세서를 작성합시다.

관찰: 우리가 어떤 물건을 검색할 때, 그것은 목록 앞에 추가됩니다.
3> 목록이 가득 차면 노래를 검색합니다.

우리가 검색하고 목록이 가득 찼을 때, 목록 끝에 전파된 첫 번째 노래 i Coldplay는 목록에서 삭제됩니다.
여기서 LRU 캐시를 처음 봤습니다.
LRU = 최근에 가장 적게 사용됩니다.처음에 Coldplay를 검색했지만 다시 검색하지 않았기 때문에 목록 뒤로 전파되어 가장 적게 사용되는 구성 요소가 되었습니다. 따라서 목록에서 삭제합니다.
우리의 전진에 따라 이 개념은 명확해질 것이다.
4> 목록에서 제거:

여기서 우리는 목록에서 솜사탕을 삭제했지만 상대적인 순서를 유지했다.
5> 목록에 있는 노래 검색 중:

여기서, 앨런 워커가 명단에 있었지만, 우리가 그것을 수색했기 때문에, 앨런 워커카는 앞으로 옮겨졌다.
LRU가 뭐예요? 왜 쓸모가 있어요?
우선 캐시는 무엇입니까?
캐시는 기본적으로 고속 읽기와 쓰기에 편리한 메모리이다.
캐시 메커니즘은 무엇입니까?
캐시 메커니즘은 고속 읽기와 쓰기에 편리한 조작이다.캐시 크기가 제한되어 있기 때문에 최적 캐시 메커니즘을 사용하여 제한된 캐시를 충분히 활용하고 데이터를 효율적으로 저장해야 한다.
당신은 이것에 대해 잘 알고 있을 것입니다.

LRU가 뭐야? 왜 LRU야?

LRU는 다음과 같은 작업을 수행하는 캐시 메커니즘입니다.
1> 캐시가 가득 차면 최소한의 항목을 사용하여 캐시를 이동합니다.
2> 항목에 자주 액세스하는 경우 빠른 읽기 및 쓰기 속도를 위해 전면으로 이동합니다.
3 > 항목에 대한 삭제 및 업데이트 작업을 수행합니다.
주요 구속조건은 O(1) 시간 내에 모든 작업을 수행하는 것입니다.
Spotify의 예가 좀 혼란스러울 것 같아서 이런 상황을 고려해 보겠습니다.
당신의 미련이 곧 다가올 것입니다. 당신은 그녀에게 깊은 인상을 남기고 싶어서 당신의 요리 기교로 그녀에게 깊은 인상을 남기고 피자를 구워주기로 결정했습니다.그래서 피자 조미료와 아침 계란과 우유를 사러 시장에 가기로 했어요.
우리는 쇼핑카를 5개의 물품을 수용할 수 있는 우리의 캐시로 여길 것이다.
새 탭에서 이미지를 열고 다른 LRU 작업을 확대 및 실행하는 작업을 살펴보겠습니다.

이제 당신은 LRU가 무엇인지, 왜 그것을 사용하는지, 응용 프로그램이 무엇인지 알고 있습니다. 코드를 작성합시다!

요구 사항: 다음 기능을 수행하는 구성 요소/LRU를 설계합니다.

1> O(1)에 항목을 추가합니다.
2> O(1)에서 넘칠 때 항목을 제거합니다.
3 > O(1)의 항목을 삭제합니다.
4> O(1)의 항목을 가져옵니다.
5> O(1)의 항목을 업데이트합니다.

데이터 구조

해시표는 좋은 선택인 것 같지만, 목록이 아니며, 항목 사이의 순서를 유지할 수 없다.
💡 두 가지 데이터 구조를 통합하는 것은 어떻습니까?
해시표의 유일한 문제는 정렬이다. 따라서 우리는 데이터 구조와 해시표를 결합시켜 우리의 목적을 달성하자.

짐작한 바와 같이, 창고/대기열/트리와 해시 테이블의 조합이 좋지 않습니다.
우리의 생활을 더욱 가볍게 하기 위해서, 우리는 단일 체인 시계가 아니라 이중 체인 시계를 사용할 것이다.따라서 삭제 작업이 훨씬 빠릅니다.
1> 이중 링크 목록을 작성합니다.

class DLL {
      int key;        // stores the key which we will use to reference the item
      int val;        // stores the actual information
      DLL prev;       // Points towards previous item
      DLL next;       // points towards next item
}

2> 캐시를 구성하는 방법:

Map<Integer,DLL> cache = new HashMap<>();

키 -> 노드 맵을 만들 것입니다.
이것은 우리가 사용자 정의한 이중 링크 목록이기 때문에, 우리는 두 개의 노드, 머리와 꼬리를 만들 것이다.이 두 노드는 우리가 항목을 추가하고 팝업하는 데 도움을 줄 것이다.
3>우리로 하여금 우리의 행동을 조직하게 한다.
작업:
movetohead는 다음과 같은 경우에 흔합니다.
add(): 노드를 생성하고 머리로 이동합니다.
get (): 해시 테이블을 사용하여 주어진 키가 존재하는지 확인하고 head로 이동합니다
삭제는 다음과 같은 경우에 흔합니다.
delete (): 노드를 위치에서 제거하고 버립니다.
popTail(): 끝 노드를 제거하고 버립니다.
불만 사항:
업데이트 (): 노드를 업데이트할 때,
1> 목록에서 삭제합니다.
2> 머리로 이동합니다.

시각화 비트:

(품질이 좋지 않아서 죄송하지만 GIF를 만들기 위해 좋은 사이트를 추천해 주세요)
우선, 우리는 함수를 인코딩하고, 이 함수를 통해 캐시와 상호작용을 할 것이다.

// add a new item
public void add(int key,int value){
  DLL node = new DLL();
  node.key = key;
  node.val = value;
  this.moveToHead(node);
 }

// get a item
public int get(int key){
  DLL node = cache.get(key);
  if(node == null){
      return -1;
   }else{
    this.moveToHead(node);
    return node.val;
   }
}

// delete a item
public boolean delete(int key){
  DLL node = cache.get(key);
  if(node == null) return false;
  this.deleteNode(node);
  return true;
 }

//pop from tail
public void popTail(){
  DLL nodeToBeRemove = tail.prev;
  DLL newTail = nodeToBeRemove.prev;
  newTail.next = tail;
  tail.prev = newTail;
 }

//update an item
public boolean update(int key,int value){
  DLL node = cache.get(key);
  if(node == null){
      return false;
  }else{
    node.val = value;
    this.deleteNode(node);
    this.moveToHead(node);
    return true;
  }
}

이제 캐시를 처리하는 데 도움이 될 함수를 작성합시다.

public void deleteNode(DLL node){
  DLL next = node.next;
  DLL prev = node.prev;
  next.prev = prev;
  prev.next = next;
 }

public void moveToHead(DLL node){
  DLL next = head.next;
  head.next = node;
  node.prev = head;
  node.next = next;
  next.prev = node;
 }

이제 필요한 모든 함수를 갖추었으므로 모든 내용을 하나로 묶을 수 있습니다.

class LRUCache {
    class DLL{
        int val;
        int key;
        DLL next;
        DLL prev;
    }

    public void moveToHead(DLL node){
        DLL next = head.next;
        head.next = node;
        node.next = next;
        next.prev = node;
        node.prev = head;
    }

    public void deleteNode(DLL node){
        DLL prev = node.prev;
        DLL next = node.next;
        prev.next = next;
        next.prev = prev;
    }

    DLL head;
    DLL tail;
    Map<Integer,DLL> map;
    int count;
    int capacity;
    public LRUCache(int capacity) {
        map = new HashMap<>();
        this.count = 0;
        this.capacity = capacity;
        head = new DLL();
        tail = new DLL();
        head.prev = null;
        head.next = tail;
        tail.prev = head;
        tail.next = null;
    }

    public int get(int key) {
        DLL node = map.get(key);
        if(node == null) return -1;
        this.moveToHead(node);
        return node.val;
    }

    public void add(int key,int value){
      DLL node = cache.get(key);
      if(node != null){
          this.update(key,value);
      }else{
          node = new DLL();
          node.key = key;
          node.val = value;
          this.moveToHead(node);
    }

    public boolean delete(int key){
      DLL node = cache.get(key);
      if(node == null) return false;
      this.deleteNode(node);
      cache.remove(key);
      return true;
    }

    public void popTail(){
      DLL nodeToBeRemove = tail.prev;
      DLL newTail = nodeToBeRemove.prev;
      newTail.next = tail;
      tail.prev = newTail;
      cache.remove(nodeToBeRemove.key);
    }   

    public boolean update(int key,int value){
      DLL node = cache.get(key);
      if(node == null){
          return false;
      }else{
        node.val = value;
        this.deleteNode(node);
        this.moveToHead(node);
        return true;
      }
    }
}

그렇습니다!이것이 바로 LRU 전체의 실현이다.우리의 버전은 모듈식이어서 필요하지 않으면 쉽게 기능을 삭제할 수 있다.
Spotify의 최근 검색 구성 요소는 추가, 삭제, 팝업 검색만 가능합니다.완전성을 위해서 우리는 나머지 부분을 실현했다.
나는 네가 이 해석을 좋아하길 바란다.만약 네가 이곳에 올 수 있다면, 나는 매우 고마워.
만약 내가 어떤 잘못이 있거나 당신에게 어떤 의문이 있다면, 평론을 발표해 주십시오.