Cấu trúc dữ liệu thích hợp cho khóa hai chiều <-> bảng tra cứu val

Question

Tôi có một nhóm khóa (ký tự) < -> liên kết băm (số nguyên) trong R. Tôi muốn lưu trữ các liên kết này trong một cấu trúc duy nhất cho phép tôi để tham khảo một cặp khóa/băm bằng khóa, và cũng bằng băm.

Vì vậy, một cái gì đó giống như

"hello" <-> 1234 

trong biến db.

Và truy cập nó với (ish; không phải là cú pháp truy cập chính xác này):

db["hello"] -> 1234 
db[1234] -> "hello" 

tôi đã cố gắng sử dụng một khung dữ liệu, và đặt tên cho các rownames các phím. Nhưng sau đó tôi không thể tham chiếu một hàng bằng số nguyên băm. Nếu tôi sử dụng số nguyên băm làm tên miền, thì tôi không thể tham chiếu bằng tên khóa, v.v.

Giải pháp hiện tại của tôi là giữ hai dbs dưới dạng hai khung dữ liệu. Một cái có băm tên là rownames, cái còn lại có các phím như rownames. Điều này làm việc, nhưng có vẻ hơi khó xử và lặp đi lặp lại để giữ khoảng hai khung dữ liệu giống hệt nhau (khác với tên của họ).

Tôi muốn nó siêu nhanh ở cả hai hướng :). Tôi nghĩ rằng điều này có nghĩa là O (log (n)) cho hướng ký tự, và O (1) cho hướng số nguyên, nhưng tôi không phải là một chuyên gia về cấu trúc/thuật toán dữ liệu. O (log (n)) theo hướng số nguyên có lẽ là OK, nhưng tôi nghĩ O (n) (cần phải đi qua toàn bộ giải pháp db) theo một trong hai hướng sẽ cân nhắc mọi thứ xuống quá nhiều.

db cũng là tính từ. Tức là, mỗi khóa ánh xạ chính xác một giá trị và mỗi giá trị ánh xạ chính xác đến một khóa.

EDIT: Cảm ơn bài viết cho đến nay:

Chạy một vài xét nghiệm, kỹ thuật trận đấu chắc chắn là chậm hơn so với một data.table có khóa. Như Martin đã chỉ ra, điều này là do thời gian cần thiết cho trận đấu để tạo ra bàn phím. Đó là, cả hai trận đấu và một data.table keyed thực hiện một tìm kiếm nhị phân để tìm giá trị. Nhưng bất kể, trận đấu quá chậm so với nhu cầu của tôi khi trả về một giá trị duy nhất. Vì vậy, tôi sẽ mã hóa một giải pháp data.table và đăng bài.

> system.time(match(1,x)) 
    user system elapsed 
    0.742 0.054 0.792 
> system.time(match(1,x)) 
    user system elapsed 
    0.748 0.064 0.806 
> system.time(match(1e7,x)) 
    user system elapsed 
    0.747 0.067 0.808 
> system.time(x.table[1]) 
    user system elapsed 
     0  0  0 
> system.time(x.table[1e7]) 
    user system elapsed 
    0.001 0.001 0.000 
> system.time(x.table[1e7]) 
    user system elapsed 
    0.005 0.000 0.005 
> system.time(x.table[1]) 
    user system elapsed 
    0.001 0.000 0.000 
> system.time(x.table[1]) 
    user system elapsed 
    0.020 0.001 0.038 

EDIT2:

tôi đã đi với các giải pháp fmatch và một vector được đặt tên. Tôi thích sự đơn giản của cách tiếp cận trận đấu, nhưng tôi đang thực hiện các lần tra cứu lặp lại trên db, do đó, hiệu suất truy cập của việc tạo lại bảng băm trên mỗi cuộc gọi để phù hợp là quá lớn.

fmatch có giao diện tương tự như đối sánh, hoạt động trên cùng một kiểu dữ liệu vectơ, v.v. Nó chỉ lưu trữ/ghi nhớ bảng băm được tạo để các cuộc gọi tiếp theo trên vectơ có tên chỉ thực hiện tra cứu băm. Tất cả điều này là trừu tượng từ người gọi, vì vậy fmatch chỉ đơn giản là một dropin cho phù hợp.

Simple mã wrapper cho việc tra cứu hai chiều:

cách tiếp cận

getChunkHashes = function(chunks, db) { 
     return(db[fmatch(chunks, names(db))]) 
} 

getChunks = function(chunkHashes, db) { 
     return(names(db[fmatch(chunkHashes, db)])) 
} 

Answer 1

Given:

Các db cũng là song ánh. Tức là, mỗi khóa ánh xạ chính xác một giá trị và mỗi giá trị ánh xạ chính xác đến một khóa.

Sau đó, tôi muốn đề nghị giải pháp băm (ví dụ các hash package), các fastmatch package, hoặc data.table::chmatch. Tham gia có khóa trong data.table được dự định nhiều hơn cho đã đặt hàng các khóa nhiều cột và/hoặc dữ liệu được nhóm, mà thực sự không phải là vấn đề của bạn.

Answer 2

Một cơ sở là sử dụng một vector tên:

db <- c(hello = 1234, hi = 123, hey = 321) 

Để đi từ chìa khóa (s) giá trị (s), sử dụng [:

db[c("hello", "hey")] 
# hello hey 
# 1234 321 

để đi từ giá trị (s) để chìa khóa (s) là một phức tạp hơn chút:

names(db)[match(c(321, 123), db)] 
# [1] "hey" "hi" 

(Lưu ý rằng match(x, y) trả về chỉ số của trận đấu đầu tiên của x trong y, vì vậy phương pháp này chỉ hoạt động tốt nếu bản đồ của bạn là đơn ánh, một cái gì đó bạn không làm rõ trong câu hỏi của bạn.)

Nếu bạn thấy rằng sử dụng cuối cùng một chút quá "nặng", bạn chắc chắn có thể viết chức năng của riêng bạn.

Lưu ý: như đã chỉ ra, phương pháp này có khả năng làm chậm theo hướng giá trị-tới-khóa, vì vậy nó có thể không lý tưởng cho việc truy cập hai chiều lặp đi lặp lại của bản đồ lớn. Để bảo vệ nó, nó là dễ thực hiện, không yêu cầu bất kỳ gói nào khác ngoài base, và sẽ làm một công việc rất phong nha cho 99% nhu cầu của mọi người. Nếu không có gì, nó có thể được sử dụng ở đây như một điểm chuẩn so với các lựa chọn thay thế nhanh hơn.

Answer 3

Thêm chi tiết về sự lo ngại của @claytonstanley về phản hồi của @flodel. match làm cho một băm của một trong những đối số của nó sau đó tìm kiếm các đối số khác. Chi phí là trong việc tạo ra các hash chứ không phải là tra cứu

> n = 1e7; x = seq_len(n) 
> system.time(match(1, x)) 
    user system elapsed 
    1.156 0.064 1.222 
> system.time(match(n, x)) 
    user system elapsed 
    1.152 0.068 1.221 

và nó phân bổ dần cho số look-up thực hiện

> y = sample(x) 
> system.time(match(y, x)) 
    user system elapsed 
    2.112 0.052 2.167 

vì vậy bạn có chắc chắn muốn tra cứu được 'vectorized '.