Thực hành: kiểm tra 1024 mẫu dừng

Giữ giá trị và thứ tự khi dừng

Tạo thủ công elastic-model.mjs, lưu mã sau rồi chạy node elastic-model.mjs. Nguồn đưa ra bốn phần tử có thứ tự và chỉ tiến khi được chấp nhận. Bit 0 của mẫu điều khiển cạnh 0, bit 1 điều khiển cạnh 1, v.v. Duyệt hết 1024 mẫu ready mười bit, rồi giữ đích sẵn sàng để tháo hết công việc đang chờ.

Chuyển giao từ ô cũ trước khi quyết định phần tử thay thế. Ô trống chấp nhận một phần tử ngay cả khi đích dừng. Ô đầy đang dừng không thể làm nguồn tiến. Tăng next mỗi cạnh sẽ loại phần tử chưa được chấp nhận và làm nguồn thử nghiệm sai ngay cả khi bộ đệm đúng.

import assert from 'node:assert/strict';
const values = [0, 9, 255, 12];
let deliveries = 0;
for (let pattern = 0; pattern < 1024; pattern++) {
  let slot = null, next = 0;
  const seen = [];
  for (let edge = 0; edge < 20; edge++) {
    const ready = edge >= 10 || ((pattern >>> edge) & 1) === 1;
    const old = slot;
    const inReady = old === null || ready;
    if (old !== null && ready) seen.push(old);
    if (inReady) {
      slot = next < values.length ? { tag: next, y: values[next] } : null;
      if (slot !== null) next++;
    } else {
      assert.deepEqual(slot, old);
    }
    assert.equal(next - seen.length, Number(slot !== null));
  }
  assert.deepEqual(seen, values.map((y, tag) => ({ tag, y })));
  assert.equal(slot, null);
  deliveries += seen.length;
}
console.log(`ELASTIC PASS: 1024 patterns, ${deliveries} deliveries`);

Với mẫu 0, đích dừng trong mười cạnh đầu tiên. Tag0,y0 vào ô trống tại cạnh 0 và ở đó đến cạnh 9. Cạnh 10 chuyển giao nó và lưu tag1,y9. Các thẻ 1,2,3 sau đó truyền tại cạnh 11,12,13. Không được nhầm giá trị 0 hợp lệ với null. Thành công báo 1024 mẫu và 4096 lần chuyển giao.

Số đã chấp nhận trừ số đã chuyển giao bằng số ô đang chiếm sau mỗi cạnh. Đối soát cục bộ này khoanh vùng lỗi sớm hơn việc chỉ so đầu ra cuối. Kiểm tra giữ bao quát bảo toàn tải, nhưng so với triển khai thực cần quan sát đầu ra thực của nó thay vì chỉ biến không đổi trong mô hình. Duyệt hết mẫu mười chu kỳ là kiểm tra có giới hạn, không chứng minh mọi độ dài dừng có thể xảy ra. Hoàn thành về sau còn giả định đích cuối cùng sẽ sẵn sàng; áp lực ngược vô hạn đòi hỏi bảo toàn, không bảo đảm chuyển giao.