số nguyên duy nhất/dài băm thế hệ then chốt trong chuỗi cho compairson nhanh

Question

tôi tò mò như thế nào những người khác đã giải quyết vấn đề này, và những vấn đề có thể ẩn nấp đằng sau những giải pháp ngây thơ:

tôi có một hệ thống xử lý dữ liệu mà thị trường chứng khoán. Có hàng chục nghìn biểu tượng, với giá/kích cỡ liên quan, chảy vào hệ thống với tốc độ vài nghìn mili giây.

Một trong những thao tác cơ bản cần thực hiện trên mỗi lần đánh dấu là so sánh chuỗi để xem liệu kết quả khớp có khớp với biểu tượng mà chúng ta quan tâm hay không. của toàn bộ hệ thống.

Tôi đang nghĩ đến việc tạo băm của chuỗi ký hiệu và lưu trữ nó bằng bản ghi. Để so sánh tiếp theo, hệ thống nên sử dụng băm này (là một int hoặc một thời gian dài, so sánh phải là một hoạt động đơn lẻ, thay vì lặp qua từng ký tự của chuỗi cho đến khi tìm thấy sự không phù hợp).

Hãy bỏ qua chi phí tạo bản thân hàm băm (trong thực tế, thực tế có thể bị cấm). Vấn đề duy nhất tôi có thể thấy là với một số lượng lớn các ký hiệu duy nhất, một va chạm băm (hai biểu tượng riêng biệt tạo ra cùng một băm) sẽ bị tàn phá. Có một thuật toán băm đảm bảo rằng các chuỗi khớp với các ràng buộc nhất định (chẳng hạn như giới hạn về số ký tự) là duy nhất không?

EDIT: Tôi sẽ viết mã này bằng Java. Không chắc chắn về chất lượng (va chạm) của hashCode hoặc tốc độ mà nó được tính toán.

Answer 1

Có thể hàm băm không phải là cách tiếp cận tốt nhất ở đây. Nếu bạn đang nhận được một biểu tượng ticker (và không phải là băm của biểu tượng ticker), bạn sẽ phải tính toán băm cho nó mỗi lần nó đi qua. Nếu thuật toán băm của nó không có xung đột, bạn sẽ cần phải nhìn vào mọi ký tự của ký hiệu. Vì vậy, bạn cũng có thể so sánh trực tiếp các nhân vật.

Tôi đề xuất xây dựng cấu trúc dữ liệu Trie của tất cả các mã bạn quan tâm. (Xem http://en.wikipedia.org/wiki/Trie). Đi qua cây cho mỗi biểu tượng và nếu bạn đạt đến cuối của ticker mà không tìm thấy một trận đấu, sau đó nó không phải là một ticker thú vị.

Với băm, bạn sẽ phải thực hiện việc truyền tải này trong tập hợp tất cả giá trị băm của các mã thú vị.

Answer 2

Nếu bạn sử dụng String.intern() hoặc nhóm chuỗi của riêng bạn, bạn có thể sử dụng == thay vì .equals() - Tôi đã thực hiện điều này trong mã quan trọng tương tự và nó đã tạo ra sự khác biệt lớn. Chuỗi mặc định đã có hàm hashCode() hoạt động khá hiệu quả.

Tôi vừa nhận ra đây không phải là câu hỏi Java, nhưng cũng áp dụng như vậy. Có, băm và sau đó sử dụng kiểm tra nhận dạng có thể tiết kiệm thời gian. Thuật toán băm java sử dụng:

 
    s[0] * 31^(n-1) + s[1] * 31^(n-2) + ... + s[n-1] 

Answer 3

hàm băm mật mã thông dụng như SHA-1 đầu ra 20 byte (160 bit). Biểu tượng cổ phiếu của bạn dài bao lâu? Nếu chúng ta đang nói về ticker symbols như "WMT" (Walmart), "KO" (Coca-Cola), v.v ... thì chúng dường như chỉ dài vài byte - vì vậy sẽ nhanh hơn để so sánh chúng trực tiếp thay vì đối phó với một băm 20 byte. Bạn đề cập đến va chạm băm - Tôi sẽ không lo lắng về chúng, đặc biệt là không khi đầu vào nhỏ hơn nhiều so với đầu ra băm.

Bạn có thể truyền các byte thành int hoặc long tùy thuộc vào ngôn ngữ lập trình và nền tảng và sau đó thực hiện so sánh giữa các "số" này trong một hướng dẫn CPU. (Tôi không biết nếu trình biên dịch hiện đại có thể so sánh một loạt các byte không kém phần nhanh chóng với một cuộc gọi đến memcmp?)

Answer 4

Bạn nên xem xét sử dụng một Perfect hash function, tôi nghĩ rằng nó phù hợp với yêu cầu của bạn

Answer 5

Bạn có thể tạo ra băm bằng cách xử lý chuỗi như là một số Base-27 (giả sử các ký hiệu chỉ chứa các chữ cái). Điều này sẽ tạo ra sự độc đáo mà bạn đang tìm kiếm. Ví dụ:

(không có chữ cái) = 0, A = 1, B = 2, ...Z = 26

AA = (1 x 27) + (1 x 27) = 28

AAA = (1 x 27) + (1 x) + (1 x 27) = 757

BBB = (2 x 27) + (2 x) + (2 x 27) = 1514

GOOG = (7 x 27) + (15 x 27) + (15 x 27) + (7 x 27) = 149128

Điều này sẽ hoạt động tốt đến 6 ký tự trong một số32 bit.

Answer 6

Bất kỳ hàm băm nào cũng xử lý tốt xung đột. Về cơ bản, nếu băm kết quả trong một lần truy cập mà nhiều câu trả lời tồn tại, có một danh sách liên kết các giải pháp tiềm năng trong nhóm đó và sự cần thiết, mọi thứ sẽ chậm lại khi tìm câu trả lời chính xác (nếu có).

Nhưng đừng viết hàm băm của riêng bạn, hãy sử dụng hàm băm trên đó.

Ồ, và tạo băm chỉ được thực hiện một lần, tôi nghĩ vậy. Bởi vì bạn có một bảng tra cứu những thứ bạn đang theo dõi, và bảng băm chỉ nên thay đổi khi bạn thêm một thứ "thú vị" mới để quét.

Answer 7

Chỉnh sửa: Nhận xét tốt hơn so với bình luận của riêng tôi đã được ném vào (và trước đó), làm cho tôi dư thừa ở mức tốt nhất.

Answer 8

Điều bạn muốn là hàm băm nhanh có sức mạnh phân biệt đối xử tốt. Đối với mỗi chuỗi, tính hàm băm liên quan và lưu nó bằng chuỗi. Sau đó, để so sánh, mã: if (Hash (s1) == Hash (s2) & & s1 == s2) sau đó {...} Chuỗi thực tế so sánh sẽ không xảy ra trừ khi băm phù hợp, mà trong thực tế chỉ khi các chuỗi phù hợp.

Một số người sẽ cho bạn biết để triển khai băm hoàn hảo.Bạn chỉ có thể thực hiện khi tập hợp các chuỗi bạn muốn băm có kích thước giới hạn, thường là chỉ 10-1000. Bạn không thể làm điều đó cho một từ vựng lớn tùy ý của chuỗi. Vì bạn không thể làm điều đó, bạn thực sự phải so sánh các chuỗi để xác định sự bình đẳng.

băm mật mã có sức mạnh phân biệt đối xử lớn nhưng không được thiết kế để nhanh. Nói chung là rất nhanh và có phân biệt đối xử tốt, quyền hạn là các hàm CRC, và hầu hết các langauges dễ dàng tìm thấy các thư viện tính toán nhanh chóng (sử dụng kỹ thuật tra cứu bảng trên byte). Chúng tôi sử dụng CRC-32 và nó rất hiệu quả cho điều này (về cơ bản 1 cơ hội trong 2^32 rằng một va chạm băm sẽ xảy ra, khi các chuỗi không khớp). Bạn có thể sử dụng CRC-64, nhưng sức mạnh phân biệt đối xử bổ sung nó cung cấp sẽ không thực sự thêm bất kỳ chức năng thực sự nào.

Answer 9

Tôi thứ hai đề xuất ở trên về cấu trúc Trie là cách tiếp cận tốt nhất cho trường hợp này. Tính toán tương đương với một băm hoàn hảo, nhưng khái niệm đẹp hơn nhiều. Đây là giả định ký hiệu của bạn bị giới hạn về độ dài.

Answer 10

FWIW, trên dự án khối lượng dữ liệu cao cuối cùng tôi đã bật, chúng tôi đã tìm thấy dữ liệu lọc, tổng hợp và phân loại trước bằng cách sử dụng một số mã C được điều chỉnh chặt chẽ là chìa khóa. Tất cả các nguồn cấp dữ liệu của chúng tôi đã đi vào bộ xử lý trước này và nó đã xử lý việc làm sạch dữ liệu đơn giản trước khi chuyển phần lớn dữ liệu đến hệ thống dựa trên Java của chúng tôi để xử lý. Về cơ bản, bộ xử lý trước chỉ làm những gì bạn đang yêu cầu: xác định các hồ sơ quan tâm, xác minh chúng đã hoàn thành và loại bỏ các dups và trống. Trong thời gian cao điểm, bộ xử lý trước có thể loại bỏ tới 20% của 8 triệu bản ghi chúng tôi nhận được mỗi giờ (có thể không hoàn toàn là khối lượng tôi tưởng tượng bạn nhận được từ nguồn cấp dữ liệu thị trường chứng khoán). Phiên bản Java ban đầu của chúng tôi rất may mắn để nhận được một nửa (nhưng nó "thanh lịch", ít nhất!)

Answer 11

Nếu bạn nhận được ký hiệu mã 4 chữ cái, thì mỗi chữ cái phải được thể hiện dưới dạng một byte. Đóng gói tất cả 4 với nhau thành một int 32-bit, và thì đấy, bạn có "băm" của bạn. Bây giờ bạn có thể so sánh điều này với tham chiếu bằng cách sử dụng một lệnh máy đơn.

Nếu bạn không sử dụng Java, tức là.

Tôi thực sự sẽ không đề xuất sử dụng Java cho bất kỳ thứ gì có tốc độ quan trọng, đặc biệt không phải hàng nghìn so sánh chuỗi trên mỗi mili giây.

chỉnh sửa: Nếu bạn muốn sử dụng mã 64 bit, bạn có thể đóng gói tối đa 8 chữ cái trên mỗi int dài và sau đó so sánh trong 1 lệnh.

Answer 12

Vì giá trị của nó. Tôi đã giải quyết vấn đề này đặc trưng cho mã vạch CMS (NYSE) và CQS (NASDAQ). Các ký tự gốc sẽ dài tối đa 6 ký tự và sẽ là chữ hoa. Yêu cầu của tôi là như sau:

• dữ liệu sẽ đến cho biết biểu tượng
• Khi nhận được dữ liệu tính toán một giá trị băm được sử dụng để so sánh
• Tính giá trị một lần, lưu trữ các giá trị trong một bản đồ để so sánh tương lai
• So sánh giá trị sẽ là bình đẳng
• So sánh giá trị sẽ nằm trong phạm vi.

Ví dụ: Nếu dữ liệu cho GOOG đến, cần xử lý và phân phối cho các quy trình trong phạm vi biểu tượng [F-HAA]. (F < = GOOG < = HAA). Tôi đã sử dụng một lớp phạm vi có giá trị thấp (F) và một giá trị cao (HAA).Khái niệm hàm băm của tôi tương tự như việc đóng gói các ký tự thành các byte nhưng đối với các mục đích ghi nhật ký, mạng và cuối cùng, tôi đã chọn unsigned long long làm kiểu lưu trữ của mình. Trước khi gọi chức năng này, các biểu tượng được đệm bằng ký tự '@'. (IBM @@@)

unsigned long long SymbolToVal(std::string& str) 
{ 
size_t maxlen = 6; // Symbology constraint 
if (str.length() != maxlen) return 0; 
unsigned long long val; 
unsigned long long retval=0; 
int expon = maxlen*2; // ASCII val range (65-90) 
double factor = std::pow(10.0,expon); 
expon-=2; 
for (size_t i = 0; i < maxlen; i++) 
{ 
    val = (unsigned long long)factor * str[i]; 
    retval += val; 
    factor = (unsigned long long) std::pow(10.0,expon); 
    expon-=2; 
    } 
    return retval; 
} 

Một phương pháp brute force sẽ được tính toán tất cả những biểu tượng có thể sắp xếp chúng đúng cách và gán cho họ một số nguyên sau đó lưu trữ chúng trong một bản đồ. Có thể quá mức cần thiết nếu dữ liệu đến chỉ bao gồm một phần nhỏ trong tổng số miền (đó là trường hợp bình thường).