Một số phương pháp tốt để thay thế tên chuỗi bằng băm số

Question

Thông thường, các thực thể và thành phần hoặc các phần khác của mã trò chơi trong thiết kế theo hướng dữ liệu sẽ có tên được kiểm tra nếu bạn muốn tìm đối tượng nào bạn đang xử lý với chính xác.

void Player::Interact(Entity *myEntity) 
{ 
    if(myEntity->isNearEnough(this) && myEntity->GetFamilyName() == "guard") 
    { 
     static_cast<Guard*>(myEntity)->Say("No mention of arrows and knees here"); 
    } 
} 

Nếu bạn bỏ qua khả năng này có thể tối ưu hóa quá sớm, nó khá rõ ràng rằng nhìn lên các đơn vị sẽ nhanh hơn rất nhiều nếu "tên" của họ là một giá trị 32 bit đơn giản thay vì một chuỗi thực tế.

Tính toán băm ra khỏi tên chuỗi là một tùy chọn có thể. Tôi đã không thực sự thử nó, nhưng với một loạt các 32bit và một hàm băm tốt nguy cơ va chạm nên được tối thiểu.

Câu hỏi là: Rõ ràng chúng ta cần một số cách để chuyển đổi trong mã (hoặc trong một số loại tệp bên ngoài) chuỗi thành các số nguyên, vì người làm việc trên các đối tượng được đặt tên này sẽ vẫn muốn tham chiếu đến đối tượng là "guard" thay vì "0x2315f21a".

Giả sử chúng tôi đang sử dụng C++ và muốn thay thế tất cả các chuỗi xuất hiện trong mã, điều này thậm chí có thể đạt được với các tính năng được xây dựng bằng ngôn ngữ hoặc chúng tôi phải xây dựng một công cụ bên ngoài xem thủ công tất cả các tệp và trao đổi giá trị?

Answer 1

Jason Gregory viết này trên his book:

Tại Naughty Dog, chúng tôi sử dụng một biến thể của thuật toán CRC-32 để băm chuỗi của chúng tôi, và chúng tôi đã không gặp phải một vụ va chạm nào trong hơn hai năm phát triển trên Uncharted: Drake's Fortune.

Vì vậy, bạn có thể muốn xem xét điều đó.

Và về bước xây dựng bạn đã đề cập, anh ấy cũng đã nói về nó. Về cơ bản, chúng đóng gói các chuỗi cần được băm nhỏ thành một cái gì đó như:

_ID("string literal") 

Và sử dụng công cụ bên ngoài tại thời gian xây dựng để băm tất cả các lần xuất hiện. Bằng cách này bạn tránh mọi chi phí thời gian chạy.

Answer 2

Đây là những gì enums dành cho. Tôi sẽ không dám quyết định tài nguyên là tốt nhất cho chủ đề này, nhưng có rất nhiều để lựa chọn: https://www.google.com/search?q=c%2B%2B+enum

Answer 3

Tôi muốn nói đi với enums!

Nhưng nếu bạn đã có nhiều mã đã sử dụng chuỗi, thì hãy giữ nó theo cách đó (đơn giản và thường đủ nhanh trên PC) hoặc băm bằng cách sử dụng một số loại CRC hoặc MD5 thành số nguyên.

Answer 4

Điều này về cơ bản được giải quyết bằng cách thêm một hướng dẫn trên bản đồ băm.

Giả sử bạn muốn chuyển đổi xâu kí tự sang số nguyên:

• Viết một lớp bọc cả một mảng và một hashmap. Tôi gọi những lớp từ điển này.
• Mảng chứa các chuỗi.
• Khóa của bản đồ băm là chuỗi (các con trỏ được chia sẻ hoặc các mảng ổn định nơi con trỏ thô cũng an toàn)
• Giá trị của bản đồ băm là chỉ mục trong mảng mà chuỗi được đặt, cũng là phần tử xử lý nó trở về mã gọi.
• Khi thêm chuỗi mới vào hệ thống, nó được tìm kiếm đã tồn tại trong hashmap, trả về xử lý nếu có.
• Nếu không có tay cầm, hãy thêm chuỗi vào mảng, chỉ mục là tay cầm.
• Đặt chuỗi và tay cầm trên bản đồ và trả lại tay cầm.

Notes/Hãy cẩn thận:

• Chiến lược này làm cho nhận được chuỗi lại từ xử lý chạy trong thời gian không đổi (nó chỉ đơn thuần là một sự tôn kính mảng).
• xử lý số nhận dạng trước hết được phân phát trước, nhưng nếu bạn tuần tự hóa chuỗi thay vì giá trị thì sẽ không thành vấn đề.
• Toán tử [] quá tải cho cả khóa và giá trị khá đơn giản (đăng ký chuỗi mới hoặc lấy lại chuỗi), nhưng gói tay cầm với lớp do người dùng xác định (bao gồm số nguyên) bổ sung rất nhiều loại an toàn, và cũng tránh sự mơ hồ nếu bạn muốn khóa và các giá trị cùng loại (quá tải không biên dịch và vv)
• Bạn phải lưu các chuỗi trong RAM, đây có thể là vấn đề.