Tạo ID duy nhất trong C++

Question

Cách tốt nhất để tạo ID duy nhất từ ​​hai (hoặc nhiều) ngắn ints trong C++ là gì? Tôi đang cố gắng xác định duy nhất các đỉnh trong biểu đồ. Các đỉnh chứa hai đến bốn ints ngắn làm dữ liệu, và lý tưởng là ID sẽ là một loại băm của chúng. Ưu tiên tính di động và tính độc đáo trên tốc độ hoặc dễ dàng.

Có rất nhiều câu trả lời tuyệt vời ở đây, tôi sẽ cố gắng hết sức tối nay để xem điều gì phù hợp nhất với vấn đề của tôi. Một vài từ nữa về những gì tôi đang làm.

Biểu đồ là tập hợp các mẫu từ tệp âm thanh. Tôi sử dụng biểu đồ dưới dạng Chuỗi Markov để tạo tệp âm thanh mới từ tệp cũ. Vì mỗi đỉnh lưu trữ một vài mẫu và các điểm vào một mẫu khác, và các mẫu đều là các int ngắn, có vẻ như tự nhiên để tạo một ID từ dữ liệu. Kết hợp chúng thành một âm thanh dài dài tốt, nhưng có thể một cái gì đó đơn giản như chỉ là là tất cả những gì tôi cần. không chắc chắn bao nhiêu không gian là cần thiết để đảm bảo tính duy nhất, nếu mỗi đỉnh lưu trữ 2 mẫu 16 bit, có 2^32 kết hợp có thể đúng không? và vì vậy nếu mỗi đỉnh lưu trữ 4 mẫu, có 2^64 kết hợp có thể?

Giải pháp cụ thể về nền tảng và thư viện không thực sự liên quan đến câu hỏi này. Tôi không muốn bất kỳ ai khác có thể biên dịch chương trình của tôi để tải xuống các thư viện bổ sung hoặc thay đổi mã cho phù hợp với hệ điều hành của họ.

Answer 1

Một giải pháp đơn giản là sử dụng số nguyên 64 bit trong đó 16 bit thấp hơn là tọa độ đỉnh đầu tiên, 16 bit tiếp theo là số thứ hai, v.v. Điều này sẽ là duy nhất cho tất cả các đỉnh của bạn, mặc dù không phải là rất nhỏ gọn.

Vì vậy, đây là một số mã được hỗ trợ một nửa để thực hiện việc này. Hy vọng rằng tôi đã nhận được các quyền.

uint64_t generateId(uint16_t v1, uint16_t v2, uint16_t v3, uint16_t v4) 
{ 
    uint64_t id; 
    id = v1 | (((uint64_t)v2) << 16) | (((uint64_t)v3) << 32) | (((uint64_t)v4) << 48); 
    return id; 
} 

Tùy chọn này có thể được thực hiện với công đoàn (ý tưởng tuyệt vời từ Leon Timmermans, xem nhận xét).Rất sạch sẽ theo cách này:

struct vertex 
{ 
    uint16_t v1; 
    uint16_t v2; 
    uint16_t v3; 
    uint16_t v4; 
}; 

union vertexWithId 
{ 
    vertex v; 
    uint64_t id; 
}; 

int main() 
{ 
    vertexWithId vWithId; 
    // Setup your vertices 
    vWithId.v.v1 = 2; 
    vWithId.v.v2 = 5; 

    // Your id is automatically setup for you! 
    std::cout << "Id is " << vWithId.id << std::endl; 
    return 0; 
} 

Answer 2

Vâng cách duy nhất để đảm bảo ID là duy nhất, là làm cho có nhiều sự kết hợp id hơn những gì gettings id của bạn từ

ví dụ cho 2 quần short (giả sử 16bit), bạn nên sử dụng một 32bit int

int ID = ((int)short1 << 16) | short2; 

và 4 quần short bạn sẽ cần một int 64bit, vv ...

với cơ bản va chạm bất cứ thứ gì (nhiều điều có thể nhận được id giống nhau) được khá nhiều đảm bảo.

Tuy nhiên một cách tiếp cận khác nhau (mà tôi nghĩ rằng sẽ tốt hơn) để có được id sẽ được trao chúng ra như đỉnh được chèn:

unsigned LastId = 0;//global 

unsigned GetNewId(){return ++LastId;} 

này cũng có tác dụng cho phép bạn thêm/khác nhau dữ liệu cho mỗi đỉnh. Tuy nhiên, nếu bạn mong muốn tạo hơn 2^32 đỉnh mà không cần đặt lại thì đây có lẽ không phải là phương pháp tốt nhất.

Answer 3

sử dụng lâu dài, do đó bạn có thể lưu trữ tất cả 4 khả năng, sau đó bitshift mỗi ngắn:

((lâu dài) shortNumberX) < < 0, 4, 8, hoặc 12

chắc chắn rằng bạn đúc trước khi dịch chuyển hoặc dữ liệu của bạn có thể bị mất kết thúc.

Chỉnh sửa: quên thêm, bạn nên HOẶC chúng lại với nhau.

Answer 4

Đôi khi những điều đơn giản nhất hoạt động tốt nhất.

Bạn có thể thêm trường id vào đối tượng Vertex và gán cho nó một số theo thứ tự xây dựng không?

static int sNextId = 0; 
int getNextId() { return ++sNextId; } 

Answer 5

off the cuff tôi muốn nói sử dụng số nguyên tố,

id = 3 * value1 + 5 * value2 + .... + somePrime * valueN 

Hãy chắc chắn rằng bạn không tràn không gian id của bạn (lâu? Lâu dài?). Vì bạn đã có một số lượng cố định các giá trị, chỉ cần crap một số số nguyên tố ngẫu nhiên. Đừng bận tâm tạo ra chúng, có đủ sẵn trong danh sách để giúp bạn đi một lúc.

Tôi là một chút sơ sài về bằng chứng mặc dù, có thể một người nào đó thêm mathmatical có thể móc tôi lên. Có lẽ có một cái gì đó để làm với yếu tố chính duy nhất của một số.

Answer 6

Nếu bạn thích tính di động, sau đó boost::tuple là đẹp:

Bạn sẽ muốn có một tuple của 4 hạng mục:

typedef boost::tuple<uint16,uint16,uint16,uint16> VertexID; 

Bạn có thể gán như thế này:

VertexID id = boost::make_tuple(1,2,3,4); 

Việc tăng tuple đã có hỗ trợ để so sánh, bình đẳng, vv, vì vậy nó rất dễ sử dụng trong các thùng chứa và các thuật toán.

Answer 7

Định nghĩa về "ID" trong câu hỏi không thực sự rõ ràng: bạn có cần sử dụng nó làm khóa để tra cứu nhanh Vertex không? Bạn có thể xác định một bộ so sánh cho std::map (xem bên dưới để biết ví dụ)

Bạn có cần phân biệt giữa hai đối tượng Vertex với cùng tọa độ (nhưng khác với một trường khác) không? Xác định một số 'nhà máy id' (cfr. Mẫu đơn) tạo ra ví dụ: một chuỗi các int, không liên quan đến các giá trị của các đối tượng Vertex. - Phần lớn theo cách mà Fire Lancer gợi ý (nhưng hãy cẩn thận về các vấn đề an toàn theo chủ đề!)

Theo ý kiến ​​của tôi, hai đỉnh có toạ độ giống hệt hệt nhau. Vậy tại sao bạn lại cần thêm một ID?

Ngay sau khi bạn xác định 'strict weak ordering' trên loại này, bạn có thể sử dụng nó làm khóa trong ví dụ: một std::map,

struct Vertex { 
    typedef short int Value; 
    Value v1, v2; 

    bool operator<(const Vertex& other) const { 
    return v1 < other.v1 || (v1 == other.v1 && v2 < other.v2) ; 
}; 

Vertex x1 = { 1, 2 }; 
Vertex x2 = { 1, 3 }; 
Vertex y1 = { 1, 2 }; // too! 

typedef std::set<Vertex> t_vertices; 

t_vertices vertices; 
vertices.insert(x1); 
vertices.insert(x2); 
vertices.insert(y1); // won't do a thing since { 1, 2 } is already in the set. 

typedef std::map<Vertex, int> t_vertex_to_counter; 
t_vertex_to_counter count; 
count[ x1 ]++; 
assert(count[x1] == 1); 
assert(count[y1] == 1); 
count[ x2 ]++; 
count[ y1 ]++; 
assert(count[x1] == 2); 
assert(count[y1] == 2); 

Answer 8

Nếu bạn đang trên Windows, bạn có thể sử dụng CoCreateGUID API, trên Linux, bạn có thể sử dụng/proc/sys/kernel/ngẫu nhiên/uuid, bạn cũng có thể nhìn vào 'libuuid'.

Answer 9

Nếu bạn đang xây dựng một bảng băm trong đó để lưu trữ các đỉnh của bạn, tôi có thể nghĩ đến một vài cách để tránh va chạm:

1. Tạo ID trực tiếp từ dữ liệu đầu vào mà không ném bất kỳ bit đi, và sử dụng bảng băm đủ lớn để chứa tất cả các ID có thể. Với các ID 64 bit, ID sau sẽ cực kỳ có vấn đề: bạn sẽ phải sử dụng một bảng nhỏ hơn phạm vi ID của bạn, do đó bạn sẽ phải đối phó với các xung đột. Ngay cả với các ID 32 bit, bạn cũng sẽ cần hơn 4GB RAM để rút ra mà không có xung đột.
2. Tạo ID liên tiếp khi bạn đọc trong các đỉnh. Thật không may, điều này làm cho nó rất tốn kém để tìm kiếm các đỉnh đọc trước đó để cập nhật xác suất của chúng, vì một trình tạo ID tuần tự không phải là hàm băm. Nếu lượng dữ liệu được sử dụng để xây dựng chuỗi Markov nhỏ hơn đáng kể so với lượng dữ liệu mà chuỗi Markov được sử dụng để tạo ra (hoặc nếu cả hai đều nhỏ), thì đây có thể không phải là vấn đề.

Ngoài ra, bạn có thể sử dụng một cài đặt bảng băm để xử lý các va chạm cho bạn (chẳng hạn như unordered_map/hash_map), và tập trung vào phần còn lại của ứng dụng của bạn.