Tại sao tôi không thể lưu trữ các khóa chuỗi trong một mảng liên kết?

Question

Tôi mới sử dụng ngôn ngữ lập trình D, chỉ mới bắt đầu đọc cuốn sách Ngôn ngữ lập trình D.

Tôi chạy vào báo lỗi khi cố gắng một mảng kết hợp mã ví dụ

#!/usr/bin/rdmd 
import std.stdio, std.string; 

void main() { 
    uint[string] dict; 
    foreach (line; stdin.byLine()) { 
     foreach (word; splitter(strip(line))) { 
      if (word in dict) continue; 
      auto newId = dict.length; 
      dict[word] = newId; 
      writeln(newId, '\t', word); 
     } 
    } 
} 

DMD lãm này Thông báo lỗi:

./vocab.d(11): Error: associative arrays can only be assigned values with immutable keys, not char[]

Tôi đang sử dụng DMD biên dịch 2,051

Tôi đã đoán các quy tắc cho mảng kết hợp đã thay đổi kể từ sách TDPL.

Tôi nên sử dụng mảng Kết hợp với khóa chuỗi như thế nào?

Cảm ơn.

Cập nhật:

Tôi đã tìm thấy giải pháp trong phần sau của cuốn sách.

sử dụng string.idup để tạo một giá trị bất biến trùng lặp trước khi đưa vào mảng.

nên

dict[word.idup] = newId; 

sẽ thực hiện công việc.

Nhưng điều đó có hiệu quả không?

Answer 1

Các mảng liên kết yêu cầu khóa của chúng không thay đổi được. Nó có ý nghĩa khi bạn nghĩ về một thực tế rằng nếu nó không phải là bất biến, thì nó có thể thay đổi, có nghĩa là băm của nó thay đổi, có nghĩa là khi bạn đi lấy lại giá trị, máy tính sẽ không tìm thấy nó. Và nếu bạn đi thay thế nó, bạn sẽ kết thúc với một giá trị khác được thêm vào mảng kết hợp (vì vậy, bạn sẽ có một giá trị với hàm băm chính xác và một với một hàm băm không chính xác). Tuy nhiên, nếu khóa là bất biến, nó không thể thay đổi, và do đó không có vấn đề như vậy.

Trước dmd 2.051, ví dụ đã hoạt động (là bug). Nó đã được sửa chữa mặc dù vậy, ví dụ trong TDPL không còn đúng nữa. Tuy nhiên, nó không phải là quá nhiều trường hợp rằng các quy tắc cho mảng kết hợp đã thay đổi vì có một lỗi trong đó mà không bị bắt. Ví dụ được biên soạn khi nó không nên có, và Andrei đã bỏ lỡ nó. Nó được liệt kê trong official errata for TDPL và phải được khắc phục trong các bản in sau này.

Mã đã sửa cần sử dụng dictionary[word.idup] hoặc dictionary[to!string(word)]. word.idup tạo bản sao của word không thay đổi. Mặt khác, to!string(word) chuyển đổi word thành string theo cách thích hợp nhất.Dưới dạng word là char[] trong trường hợp này, có thể là sử dụng idup. Tuy nhiên, nếu word đã là string, thì nó sẽ chỉ trả lại giá trị đã được chuyển vào và không cần sao chép nó. Vì vậy, trong trường hợp chung, to!string(word) là sự lựa chọn tốt hơn (đặc biệt là trong các chức năng templated), nhưng trong trường hợp này, hoặc chỉ hoạt động tốt (to!() là trong std.conv).

Về mặt kỹ thuật, có thể đúc char[] thành string, nhưng thường là một ý tưởng tồi. Nếu bạn biết rằng char[] sẽ không bao giờ thay đổi, thì bạn có thể thoát khỏi nó, nhưng trong trường hợp chung, bạn đang gặp rủi ro, vì trình biên dịch sẽ giả định rằng kết quả string không bao giờ có thể thay đổi được mã không đúng. Nó thậm chí có thể segfault. Vì vậy, đừng làm điều đó trừ khi hồ sơ cho thấy bạn thực sự cần hiệu quả tránh né bản sao, bạn không thể tránh được bản sao bằng cách thực hiện một cái gì đó như chỉ sử dụng một số string (vì vậy không cần chuyển đổi) và bạn biết rằng string sẽ không bao giờ bị thay đổi.

Nói chung, tôi sẽ không lo lắng quá nhiều về hiệu quả của việc sao chép chuỗi. Nói chung, bạn nên sử dụng string thay vì char[] để bạn có thể sao chép chúng xung quanh (ví dụ: str1 = str2;) thay vì sao chép toàn bộ nội dung của chúng như dup và idup do) mà không lo lắng về điều đó đặc biệt không hiệu quả. Vấn đề với ví dụ là stdin.byLine() trả về một char[] thay vì một số string (có lẽ là để tránh sao chép dữ liệu nếu không cần thiết). Vì vậy, splitter() trả về một số char[] và do đó word là char[] thay vì string. Bây giờ, bạn có thể làm splitter(strip(line.idup)) hoặc splitter(strip(line).idup) thay vì idup nhập khóa. Bằng cách đó, splitter() sẽ trả lại một string thay vì char[], nhưng đó có thể cơ bản hiệu quả như idup ing word. Bất kể, vì văn bản đến từ đâu ban đầu, đó là char[] thay vì string, buộc bạn phải idup nó ở đâu đó dọc theo dòng nếu bạn dự định sử dụng nó làm khóa trong mảng kết hợp. Tuy nhiên, trong trường hợp chung, tốt hơn hết là chỉ sử dụng string chứ không phải char[]. Sau đó, bạn không cần phải idup bất cứ điều gì.

EDIT:
Trên thực tế, ngay cả khi bạn tìm thấy một tình huống mà đúc char[]-string dường như cả hai an toàn và cần thiết, xem xét sử dụng std.exception.assumeUnique() (documentation). Về cơ bản, đó là cách ưu tiên để chuyển đổi một mảng có thể thay đổi thành một mảng bất biến khi bạn cần và biết rằng bạn có thể. Nó thường sẽ được thực hiện trong trường hợp bạn đã xây dựng một mảng mà bạn không thể làm cho bất biến bởi vì bạn phải làm nó thành nhiều mảnh nhưng không có tham chiếu khác và bạn không muốn tạo bản sao sâu của nó. Nó sẽ không hữu ích trong các tình huống như ví dụ mà bạn đang hỏi về, vì bạn thực sự cần phải sao chép mảng.

Answer 2

Không, nó không hiệu quả vì nó rõ ràng là trùng lặp chuỗi. Nếu bạn có thể bảo đảm rằng chuỗi bạn tạo sẽ không bao giờ được sửa đổi trong bộ nhớ, vui lòng sử dụng rõ ràng một dàn diễn viên cast(immutable)str trên đó, thay vì sao chép chuỗi đó.

(Mặc dù, tôi đã nhận thấy rằng trình thu gom rác hoạt động tốt, vì vậy tôi khuyên bạn không thực sự thử điều đó trừ khi bạn thấy nút cổ chai, vì bạn có thể quyết định thay đổi chuỗi sau đó. để giúp bạn tìm thấy nút cổ chai sau này, nếu nó tồn tại.)