이 도전은 정말 간단하다 (그리고 더 어려운 도전의 선구자!).
자원 액세스 배열 (음이 아닌 정수로 간단히 표시됨)과 매개 변수가 주어지면 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
- 주황색 : 현재 캐시 창
- 노란색 : 만료 된 캐시 값
자바 스크립트 (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)
되는지 테스트 하는 데 사용 합니다. 이 테스트가 실패 할 때마다 ~ [ x 를 a []에 추가 하고 미스 수 k를 증가시킵니다 .
예
아래는이 방법을 사용하는 위와 동일한 예제에 대한 다른 단계입니다. 캐시 값은 단순히 배열의 끝에 추가되기 때문에 명시적인 캐시 포인터가 없습니다.
답변
하스켈 , 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의 크기는이 목록이 비어 있음을 의미합니다.