FIFO 캐시 누락 수 1, 2, 3] 0 =

이 도전은 정말 간단하다 (그리고 더 어려운 도전의 선구자!).

자원 액세스 배열 (음이 아닌 정수로 간단히 표시됨)과 매개 변수가 주어지면 n캐시에 용량이 있다고 가정하고 캐시 n가 가득 찼을 때 FIFO (First-In-First-Out) 배출 체계를 사용 한다고 가정 할 때 캐시 누락 수를 리턴하십시오. .

예:

4, [0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 0, 1, 2, 3]
0 = not in cache (miss), insert, cache is now [0]
1 = not in cache (miss), insert, cache is now [0, 1]
2 = not in cache (miss), insert, cache is now [0, 1, 2]
3 = not in cache (miss), insert, cache is now [0, 1, 2, 3]
0 = in cache (hit), cache unchanged
1 = in cache (hit), cache unchanged
2 = in cache (hit), cache unchanged
3 = in cache (hit), cache unchanged
4 = not in cache (miss), insert and eject oldest, cache is now [1, 2, 3, 4]
0 = not in cache (miss), insert and eject oldest, cache is now [2, 3, 4, 0]
0 = in cache (hit), cache unchanged
1 = not in cache (miss), insert and eject oldest, cache is now [3, 4, 0, 1]
2 = not in cache (miss), insert and eject oldest, cache is now [4, 0, 1, 2]
3 = not in cache (miss), insert and eject oldest, cache is now [0, 1, 2, 3]

이 예에서는 9 번의 누락이있었습니다. 코드 예제가 더 잘 설명하는 데 도움이 될 수 있습니다. 파이썬에서 :

def num_misses(n, arr):
    misses = 0
    cache = []
    for access in arr:
        if access not in cache:
            misses += 1
            cache.append(access)
            if len(cache) > n:
                cache.pop(0)
    return misses

몇 가지 추가 테스트 사례 (다음 도전에 대한 힌트가 포함되어 있습니다. 궁금한 점이 있습니까?) :

0, [] -> 0
0, [1, 2, 3, 4, 1, 2, 3, 4] -> 8
2, [0, 0, 0, 0, 0, 0, 0] -> 1
3, [3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4] -> 9
4, [3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4] -> 10

바이트 단위의 최단 코드가 이깁니다.



답변

자바 스크립트 (ES6), 55 바이트

방법 # 1 : 캐시가 입력을 덮어 씁니다.

카레 구문으로 입력을 (cache_size)(list)받습니다.

n=>a=>a.map(x=>a[a.indexOf(x,k>n&&k-n)<k||k++]=x,k=0)|k

온라인으로 사용해보십시오!

어떻게?

0으로 초기화 된 별도의 포인터 k를 사용하여 입력 배열 a [] 를 캐시로 덮어 씁니다 .

x 가 캐시에 a.indexOf(x, k > n && k - n) < k있는지 여부를 테스트 하는 데 사용 합니다.

캐시는 원래 배열을 수행하는 것보다 빠르게 커질 수 없으므로 캐시 창 안 또는 밖에서 각 값을 찾을 수 있습니다 (즉, -1을indexOf() 반환하지 않음 ).

max (0, k-n)k-1 (두 범위 포함) 사이의 인덱스에서 발견되면 값은 캐시 에 있으며,이 경우 a [true] = x 입니다. 이것은 a [] 뒤에 있는 기본 객체의 속성에만 영향을 미치지 만 배열 a []는 변경하지 않습니다 . 그렇지 않으면, 우리는 a [k ++] = x 합니다.

다음은 [1, 1, 2, 3, 3, 2, 1, 4]캐시 크기가 2 인 입력의 다른 단계입니다 .

  • 굵은 테두리 : map () 포인터
  • 괄호 : 캐시 포인터 k
  • 주황색 : 현재 캐시 창
  • 노란색 : 만료 된 캐시 값

방법 # 1


자바 스크립트 (ES6), 57 바이트

방법 # 2 : 입력 끝에 캐시가 추가됨

카레 구문으로 입력을 (cache_size)(list)받습니다.

n=>a=>a.map(x=>n*~a.indexOf(~x,-n)||a.push(~x)&k++,k=0)|k

온라인으로 사용해보십시오!

어떻게?

입력 배열 a [] 는 음이 아닌 정수를 포함하도록 보장되므로 각 값 x 의 1-complement ~ x 를 사용하여 a [] 끝에 캐시를 안전하게 추가 할 수 있습니다 .

마지막 n 값 중에서 ~ x 가 발견 n * ~a.indexOf(~x, -n)되는지 테스트 하는 데 사용 합니다. 이 테스트가 실패 할 때마다 ~ [ xa []에 추가 하고 미스 수 k를 증가시킵니다 .

아래는이 방법을 사용하는 위와 동일한 예제에 대한 다른 단계입니다. 캐시 값은 단순히 배열의 끝에 추가되기 때문에 명시적인 캐시 포인터가 없습니다.

방법 # 2


답변

하스켈 , 50 바이트

f n=length.foldl(\r x->[x|all(/=x)$take n r]++r)[]

온라인으로 사용해보십시오!

전체 캐시 기록을 저장하고 길이를 가져 오는 Lynn의 방법 을 기반으로 합니다. 단항 출력 은 약간 짧습니다.

하스켈 , 47 바이트

n?l=1<$foldl(\r x->[x|all(/=x)$take n r]++r)[]l

온라인으로 사용해보십시오!


답변

파이썬 2 , 58 바이트

lambda n,a:len(reduce(lambda c,i:[i][i in c[:n]:]+c,a,[]))

온라인으로 사용해보십시오!

3 바이트에 대한 ovs와 3 개에 대한 xnor 덕분입니다.


답변

R , 69 64 62 바이트

function(n,A,K={}){for(i in A)K=c(i[!i%in%K[0:n]],K);sum(K|1)}

온라인으로 사용해보십시오!

개선 사항을 제안한 JayCe와 다른 커플을위한 DigEmAll에 감사드립니다!


답변

하스켈, 61 58 바이트

n!a|let(a:b)#c|elem a c=b#c|1<2=1+b#take n(a:c);_#_=0=a#[]

온라인으로 사용해보십시오!

n!a|      =a#[]     -- take input 'n' and a list 'a'
                    -- and call # with the initial list and an empty cache
 let                -- bind function '#':
  (a:b)#c           -- if there's at least one element 'a' left in the list
     |elem a c=b#c  --  and it's in the cache, go on with the same cache
                    --  and the remainder of the list
     |1<2=          -- else (i.e. cache miss)
          1+        --  add one to the recursive call of
       b#           --  the remainder of the list and
       take n(a:c)  --  the first n elements of 'a' prepended to the cach
 _#_=0              -- if there's no element in the list, return 0

편집 : @Lynn 덕분에 -3 바이트.


답변

05AB1E , 17 16 바이트

)svDyå_i¼y¸ìI£]¾

온라인으로 사용해보십시오!

설명

)                   # wrap the stack in a list
 sv                 # for each item y in input list
   D                # duplicate current list
    yå_i            # if y is not contained in the current list
        ¼           # increment counter
         y¸ì        # prepend y to the current list
            I£      # keep the first input elements
              ]¾    # end loop and push counter


답변

코 틀린 , 82 69 바이트

{a,n->a.fold(List(0){0}){c,v->if(v!in c.takeLast(n))c+v else c}.size}

int로서 입력을 받아 IntArray, 하지 전형적인 List<Int>(문제가 안되는). 이것은 “캐시 히스토리를 구축하고, 그 길이를 계산”의 방법을 사용한다.

온라인으로 사용해보십시오!

설명

{ a, n ->                         // lambda where a is accesses and n is cache size
    a.fold(List(0){0}) { c, v ->  // fold on empty list
        if(v !in c.takeLast(n))   // if resource is not in last n cache inserts
            c + v                 // insert to cache list
        else
            c                     // return cache as is
    }.size                        // length of cache list is number of inserts
}

빈 목록 만들기

Kotlin에는 컬렉션 리터럴이 없지만 새 컬렉션을 만드는 기능이 있습니다.

빈을 만드는 올바른 방법 List<Int>은 다음과 같습니다.

List<Int>()

그러나 크기와 이니셜 라이저 인수를 남용하면이 작업이 더 짧습니다.

List(0){0}
List(0)       // List of size 0
       { 0 }  // with generator returning 0

생성기 람다는 0을 반환하므로 Kotlin은이 목록의 유형을로 추정하고 List<Int>0의 크기는이 목록이 비어 있음을 의미합니다.