So sánh số có nhanh hơn so sánh chuỗi không?

Question

Tôi nghe nói rằng băm (tức là chuyển đổi một chuỗi hoặc một đối tượng thành một số) được sử dụng cho các chuỗi và vì vậy dễ so sánh các số hơn so với chuỗi. Nếu đúng, lý do cho điều này là gì?

Answer 1

này không nhất thiết phải như vậy, nhưng có lẽ là trường hợp hầu hết thời gian.

Xem xét tình huống sau:

Tôi muốn so sánh chuỗi "quả táo" với "cam". Nếu tôi chỉ muốn xác định "quả táo" == "cam", tôi chỉ cần so sánh ký tự đầu tiên của mỗi chuỗi: 'a'! = 'O' => "táo"! = "Cam". Nếu tôi băm chuỗi và sau đó làm so sánh, nó là chậm hơn đáng kể khi tôi phải phân tích cả hai chuỗi và đưa chúng vào một thuật toán băm trước khi so sánh các số nguyên kết quả.

Nếu, tuy nhiên, tôi cần thực hiện so sánh này nhiều lần và có lẽ tôi đang so sánh "cam" với "đười ươi", sau đó nếu tôi băm tất cả các chuỗi một lần và thực hiện so sánh các số nguyên nhiều lần, nó sẽ làm việc nhanh hơn. Đây là nguyên tắc mà một bản đồ băm được dựa trên. Tuy nhiên, chú ý rằng băm chuỗi là hữu ích cho việc so sánh trực tiếp, nó không thể xác định xem các chuỗi có lớn hơn hay nhỏ hơn nhau hay không, và vì vậy không thể đặt chuỗi thông qua phương thức băm. (Đây là lý do tại sao HashMap trong Java là không có thứ tự).

Answer 2

Có, nhưng điều đó không liên quan gì đến băm.

So sánh các số liên quan đến các hướng dẫn phần cứng đơn giản so sánh bit. So sánh các chuỗi liên quan đến (a) lặp qua cả hai chuỗi cho đến khi bạn tìm các ký tự khác nhau (không giống như số, kích thước cố định) và (b) rất nhiều ma thuật Unicode (các chuỗi khác nhau có độ dài khác nhau thực sự có thể bằng nhau và khác nhau ký tự trong các khối mã khác nhau so sánh khác nhau).

---

Việc băm thường được sử dụng để chuyển đổi chuỗi thành chỉ mục mảng.

Answer 3

So sánh các số nguyên thủy chắc chắn nhanh hơn so với so sánh các chuỗi vì đó chỉ là một hướng dẫn máy tính trong khi so sánh các chuỗi trong Java là một phương thức. Nhưng băm trong Java được sử dụng vì một lý do khác, Object.hashCode() được sử dụng trong các bảng băm để tìm kiếm nhanh trong các bộ sưu tập.

Answer 4

So sánh hai số là magnitudes nhanh hơn so sánh hai chuỗi (đại diện cho cùng một số). So sánh hai số chỉ đơn giản là yêu cầu so sánh từng bit và có thể được thực hiện siêu nhanh bằng cách sử dụng bất kỳ bổ sung AND, XOR, 2, v.v.

So sánh hai chuỗi rất chậm và tốn kém. Hầu hết các thuật toán yêu cầu lặp qua toàn bộ chuỗi và khớp với từng ký tự.

Ví dụ: giả sử chúng tôi muốn so sánh 9 với 12 (sai). Để so sánh số, giả sử thuật toán so sánh từng bit riêng lẻ. 9 = 1001 12 = 1100

Đây, thuật toán trường hợp xấu nhất sẽ so sánh 4 bit.

Bây giờ nếu chúng ta đại diện cho "9" và "12" làm chuỗi, chúng sẽ được lưu trữ trong bộ nhớ dưới dạng 16 bit (Nhớ lại: Java sử dụng UTF-16 để biểu diễn chuỗi trong bộ nhớ) và phải được chuyển đến một chuỗi thuật toán so sánh. Thực tế, hàm so sánh String thực tế của Java là dưới đây:

public boolean equals(Object anObject) { 
    if (this == anObject) { 
     return true; 
    } 
    if (anObject instanceof String) { 
     String anotherString = (String)anObject; 
     int n = count; 
     if (n == anotherString.count) { 
      char v1[] = value; 
      char v2[] = anotherString.value; 
      int i = offset; 
      int j = anotherString.offset; 
      while (n-- != 0) { 
       if (v1[i++] != v2[j++]) 
        return false; 
      } 
      return true; 
     } 
    } 
    return false; 
} 

Như bạn có thể thấy, có rất nhiều thứ khác để so sánh chuỗi.

Answer 5

Nói chung, hầu hết các máy tính có một hướng dẫn đơn để so sánh các số nguyên, số liệu, vv và sẽ thực hiện tối đa một vài chu kỳ lệnh. Các chuỗi thường được so sánh bởi một hàm/phương thức tiện ích (có thể có ngoại lệ lẻ đối với quy tắc này).

trong Java ví dụ một String được về cơ bản thể hiện dưới dạng

 /** The value is used for character storage. */ 
    private final char value[]; 

    /** The offset is the first index of the storage that is used. */ 
    private final int offset; 

    /** The count is the number of characters in the String. */ 
    private final int count; 

Và bằng phương pháp là

if (this == anObject) { 
    return true; 
} 
if (anObject instanceof String) { 
    String anotherString = (String)anObject; 
    int n = count; 
    if (n == anotherString.count) { 
     char v1[] = value; 
     char v2[] = anotherString.value; 
     int i = offset; 
     int j = anotherString.offset; 
     while (n-- != 0) { 
      if (v1[i++] != v2[j++]) 
       return false; 
     } 
     return true; 
    } 
} 
return false; 

Các bằng phương pháp hiện cả hai này == anObject và n == anotherString .count, cả về cơ bản so sánh số nguyên, ngay cả trước khi nó bắt đầu so sánh các ký tự.Nó sẽ mất rất nhiều thời gian hơn một chỉ dẫn duy nhất mà một số nguyên so sánh mất

---

Chuỗi C so sánh là đơn giản hơn/nhanh hơn so với Java tương đương nhưng nó sẽ chứa một số loại vòng lặp và nhiều hướng dẫn cho mỗi lượt đi qua vòng lặp.

này sẽ mất nhiều thời gian hơn so với một hướng dẫn rằng một Integer Hãy so sánh đòi hỏi