Chương trình học Bài 27 trên tổng số 148 · Dùng AI để hiểu
Dùng AI để hiểu

Bài sinh đôi tắt AI: vòng băm

Vì sao điều này quan trọng Nhật ký vòng trong Mắc kẹt vào chính mình có một ý tưởng ở lõi. Nó lại ở đây, trong một hệ thống bạn có thể thật sự xây, khi người hướng dẫn bị tắt.

Người hướng dẫn bị tắt cho bài toán này. Hãy tự tìm ra lời giải.

Một cụm bộ đệm phân bố khóa qua các máy chủ bằng băm nhất quán (consistent hashing). Mỗi máy chủ sở hữu một vài vị trí trên một vòng các số nguyên từ 0 tới khoảng hai tỉ. Một khóa được băm thành một con số, và nó thuộc về vị trí nút đầu tiên bằng hoặc sau con số đó, đi quanh vòng: vượt qua vị trí lớn nhất, nó quay về vị trí nhỏ nhất.

Các vị trí nút được lưu đã sắp xếp trong một bảng dùng chung, nhưng bảng là một bộ đệm vòng: nó bắt đầu ở bất cứ đâu người ghi cuối cùng đã dừng. Mỗi lần đọc bảng là một chuyến đi khứ hồi qua mạng, nên các lần đọc được đếm.

Dữ liệu

from creative.budget import Tape
ring = Tape([700, 900, 100, 300])   # sorted positions 100, 300, 700, 900, stored from 700
hashes = [250, 950]
# owners(ring, hashes) -> [300, 100]
Đến lượt bạn

Viết owners(ring, hashes). ring là một Tape các vị trí nút phân biệt đã sắp xếp nhưng có thể bị xoay (được lưu từ bất kỳ điểm bắt đầu nào, có thể là 0). Nó giữ ít nhất một nút. Với mỗi giá trị băm h, trả về vị trí nhỏ nhất >= h; nếu không có, trả về vị trí nhỏ nhất trong tất cả. Ngân sách: với 100.000 nút và 200 giá trị băm bạn được đọc nhiều nhất 20.000 giá trị. len(ring) là miễn phí.

Tắt AI: không có gia sư, gợi ý hoặc lời giải mẫu cho bài này. Chỉ dùng tư duy của riêng bạn.

Bạn thấy vấn đề gì trong bài học này? Hãy báo cáo nó · Hỏi về bài học này

Bài tập này sẽ sớm mở.

Hoàn thành bài học trước đó để mở khóa bài này. Toàn bộ khóa học là miễn phí, không cần tài khoản, và bạn có thể đọc bài học này ngay bây giờ.