Haber akışı için cache hit oranı
Görev tanımı
Problem
Bir haber akışı (news feed) servisi son görüntülenen gönderileri veritabanının önündeki bir LRU cache'te (önbellek) tutuyor. Okuyucuların istediği gönderi id'lerinin dizisi ve gönderi cinsinden cache kapasitesi verildiğinde istekleri yeniden oynat: cache'teki bir gönderi için istek bir hit'tir ve onu en son kullanılan yapar; bir miss gönderiyi cache'e yükler, cache kapasiteyi aşıyorsa en az yakın zamanda kullanılan gönderiyi çıkarır. Hit oranını 1 ondalığa yuvarlanmış bir yüzde olarak döndür. Her ek slot'un ne kazandırdığını görmek için birkaç kapasiteyle çağır. En fazla 1.000.000 istek var.
Örnekler
Input: feed = ["p1", "p2", "p1", "p3", "p1", "p2", "p4", "p1", "p5", "p2", "p1", "p3"],
capacities 1, 2, 3 and 4
Output: [0.0, 16.7, 41.7, 50.0]
Neden: en çok üçüncü slot katkı yapar, çünkü iki sıcak gönderiyi, p1 ve p2'yi tutmaya yeter
Input: feed = ["a", "b", "c", "a", "b", "c"], capacity = 2
Output: 0.0
Neden: cache'ten bir gönderi fazla olan bir döngü, her gönderiyi tekrar gerekmesinden hemen önce çıkarır
Input: feed = ["x", "x", "x"], capacity = 1
Output: 66.7
Neden: edge case: yalnız bir gönderi için ilk istek miss olabilir
İpuçları
0 / 3
Bir LRU cache'in iki işlemin hızlı olmasına ihtiyacı var: bir gönderiyi aramak ve çıkarılacak en az yakın zamanda kullanılanı bulmak.
Python'un OrderedDict'i ekleme sırasını korur ve bir anahtarı sona taşıyabilir. Sonu en son kullanılan, önü de bir sonraki çıkarılacak olarak düşün.
Bir hit'te say ve gönderiyi sona taşı. Bir miss'te ekle ve cache artık kapasiteyi aşıyorsa ilk öğeyi pop et. Sonda hit'leri isteklere böl.
- Hedef zaman
- O(n)
- Hedef alan
- O(c)
Kısıtlar
- at most 10⁶ requests
Çözüm
Akış trafiği çarpıktır, birkaç gönderi görüntülemelerin çoğunu alır ve küçük bir cache'i değerli kılan bu çarpıklıktır. Simülasyon bir OrderedDict üzerinde bir LRU cache'tir: bir hit gönderiyi en son kullanılan uca taşır, bir miss de onu ekler ve cache taştığında diğer uçtan çıkarır. Aynı izi birkaç kapasiteye karşı çalıştırmak, bir mülakat cevabının üzerine düşünmesi gereken hit oranı eğrisini verir: ilk örnek cache iki sıcak gönderiyi tutabildiği anda sıçrar, sonra düzleşir. İkinci örnek LRU'nun bilinen zayıf noktasıdır: cache'ten biraz büyük döngüsel bir tarama, burada hit oranı sıfıra düşer. Her istek O(1)'dir; kapasite başına zaman O(n), c cache'lenmiş gönderi için alan O(c).
from collections import OrderedDict
def hit_ratio(requests, capacity):
cache, hits = OrderedDict(), 0 # front = least recently used
for post in requests:
if post in cache:
hits += 1
cache.move_to_end(post) # now the most recently used
else:
cache[post] = True
if len(cache) > capacity:
cache.popitem(last=False) # evict the least recently used
return round(100 * hits / len(requests), 1)
feed = ["p1", "p2", "p1", "p3", "p1", "p2", "p4", "p1", "p5", "p2", "p1", "p3"]
print([hit_ratio(feed, c) for c in (1, 2, 3, 4)]) # -> [0.0, 16.7, 41.7, 50.0]
print(hit_ratio(["a", "b", "c", "a", "b", "c"], 2)) # -> 0.0
print(hit_ratio(["x", "x", "x"], 1)) # -> 66.7Kodda değil de fikirde mi takıldın? Dağıtık cache tasarla bunu anlatıyor.