Lua: Cách tìm kiếm trong một bảng mà các phím là các bảng (hoặc các đối tượng)

Question

Tôi muốn lưu trữ một bảng lua nơi các phím là các bảng lua khác. Tôi biết rằng điều này là có thể NHƯNG tôi muốn có thể làm tra cứu trong bảng bằng cách sử dụng bản sao của những bảng đó. Cụ thể, tôi muốn để có thể làm:

t = {} 
key = { a = "a" } 
t[key] = 4 
key2 = { a = "a" } 

và sau đó tôi muốn để có thể nhìn lên:

t[key2] 

và nhận 4.

tôi biết rằng tôi có thể biến key thành một chuỗi và đặt nó vào bảng t. Tôi cũng đã nghĩ về việc viết một hàm băm tùy chỉnh hoặc làm điều này bằng cách lồng các bảng. Có cách nào tốt nhất để tôi có được loại chức năng này không? Tôi có những lựa chọn nào khác?

Answer 1

Trong Lua, hai bảng được tạo riêng được coi là "khác". Nhưng nếu bạn tạo một bảng một lần, bạn có thể gán nó cho bất kỳ biến nào bạn muốn, và khi bạn so sánh chúng, Lua sẽ cho bạn biết rằng chúng là như nhau. Nói cách khác:

t = {} 
key = { a = "a" } 
t[key] = 4 
key2 = key 
... 
t[key2] -- returns 4 

Vì vậy, đó là cách đơn giản, sạch sẽ để làm những gì bạn muốn.Lưu trữ key ở đâu đó, vì vậy bạn có thể truy xuất lại 4 bằng cách sử dụng nó. Điều này cũng rất nhanh.

Nếu bạn thực sự không muốn làm điều đó ... tốt, có một cách. Nhưng nó là loại không hiệu quả và xấu xí.

Phần đầu tiên là tạo một hàm so sánh hai bảng riêng biệt. Nó sẽ trả về true nếu hai bảng là "tương đương", và sai nếu chúng không. Hãy gọi nó là tương đương. Nó sẽ hoạt động như sau:

equivalent({a=1},{a=1})   -- true 
equivalent({a=1,b=2}, {a=1})  -- false 
equivalent({a={b=1}}, {a={b=2}}) -- false 

Hàm này phải đệ quy, để xử lý các bảng có chứa bảng. Nó cũng không được đánh lừa nếu một trong các bảng "chứa" khác, nhưng có nhiều yếu tố. Tôi đi ra với việc thực hiện này; có lẽ có những cái tốt hơn ngoài kia.

local function equivalent(a,b) 
    if type(a) ~= 'table' then return a == b end 

    local counta, countb = 0, 0 

    for k,va in pairs(a) do 
    if not equivalent(va, b[k]) then return false end 
    counta = counta + 1 
    end 

    for _,_ in pairs(b) do countb = countb + 1 end 

    return counta == countb 
end 

Tôi sẽ không giải thích chức năng ở đây. Tôi hy vọng nó là rõ ràng đủ những gì nó làm.

Phần khác của câu đố bao gồm việc tạo t sử dụng chức năng equivalent khi so sánh các phím. Điều này có thể được thực hiện với thao tác có thể chỉnh sửa cẩn thận và một bảng "lưu trữ" bổ sung.

Chúng tôi về cơ bản biến đổi t thành kẻ mạo danh. Khi mã của chúng ta bảo nó lưu trữ một giá trị dưới một khóa, nó không tự lưu nó; thay vào đó nó đưa nó vào bảng phụ (chúng tôi sẽ gọi là store). Khi mã yêu cầu t cho một giá trị, nó tìm kiếm nó trong store, nhưng sử dụng hàm equivalent để nhận được nó.

Đây là mã:

local function equivalent(a,b) 
... -- same code as before 
end 

local store = {} -- this is the table that stores the values 

t = setmetatable({}, { 
    __newindex = store, 
    __index = function(tbl, key) 
    for k,v in pairs(store) do 
     if equivalent(k,key) then return v end 
    end 
    end 
}) 

Cách sử dụng Ví dụ:

t[{a = 1}] = 4 

print(t[{a = 1}]) -- 4 
print(t[{a = 1, b = 2}]) -- nil 

Answer 2

Tôi không chắc chắn bạn có thể thực hiện việc này. Bạn có thể định nghĩa bình đẳng cho các bảng bằng cách sử dụng metatable, nhưng không có cách nào để định nghĩa hàm băm, và tôi nghi ngờ việc định nghĩa equality một mình sẽ làm những gì bạn cần. Bạn rõ ràng có thể xác định sự bình đẳng, sau đó lặp lại trên bảng bằng cách sử dụng pairs() và so sánh các khóa của chính bạn, nhưng điều đó sẽ biến những gì cần là O(1) tra cứu thành O(n).

Answer 3

Điều này không thể thực hiện được ở Lua. Nếu bạn sử dụng các bảng làm khóa, khóa là "cá thể" cụ thể của bảng. Ngay cả khi bạn tạo một bảng khác với cùng nội dung, cá thể khác nhau, do đó nó là một khóa khác.

Nếu bạn muốn làm điều gì đó như thế này, bạn có thể tạo một hàm băm, chạy ngang qua bảng để phục vụ như một khóa (thậm chí có thể đệ quy nếu cần) và xây dựng biểu diễn chuỗi nội dung bảng. Nó không cần phải là người có thể đọc được, miễn là nó khác với nội dung khác nhau và bằng nhau cho các bảng có cùng nội dung. Ngoài việc sử dụng pairs() để lướt qua bảng, bạn cũng cần phải chèn các phím vào bảng và sắp xếp chúng bằng cách sử dụng table.sort(), vì pairs() trả về chúng theo thứ tự tùy ý và bạn muốn có cùng một chuỗi cho các bảng "bằng nhau".

Một khi bạn đã xây dựng chuỗi như vậy, bạn có thể sử dụng nó như một chìa khóa:

function hash(t) ... end 
t = {} 
key1 = { a = "a", b = "b" } 
t[hash(key1)] = 4 
key2 = { a = "a", b = "b" } 
print(t[hash(key2)]) -- should print "4" if the hash function works correctly 

Theo tôi, tất cả điều này là quá phức tạp đối với các nhiệm vụ đơn giản của lập chỉ mục, và bạn có thể muốn suy nghĩ lại mong muốn của bạn để lập chỉ mục bằng cách sử dụng bản sao của bảng. Tại sao bạn lại muốn chức năng như vậy?

Cập nhật

Nếu bạn chỉ cần phải làm việc với các cụm từ, tôi nghĩ rằng concatenating chúng dễ dàng hơn tạo hàm băm chung chung như vậy. Nếu bạn cần nó cho chuỗi các cụm từ, bạn sẽ không thực sự cần phải lặp qua các bảng và sắp xếp các khóa, chỉ cần thu thập thông tin chính từ mỗi cụm từ. Bạn vẫn sẽ cần sử dụng chức năng trợ giúp, có thể tạo một khóa phù hợp cho bạn:

function pkey(...) 
    local n, args = select('#', ...), { ... } 
    for i=1,n do args[i] = args[i].value end -- extract your info here 
    return table.concat(args, ' ') -- space or other separator, such as ':'   
end 
tab[pkey(phrase1, phrase2, phrase3)] = "value" 

Answer 4

Tôi không biết nhiều về ngôn ngữ xử lý, và về mục tiêu bạn muốn tiếp cận với chương trình của bạn, nhưng về việc thu thập mã thông báo như thế này: sử dụng cấu trúc bảng lồng nhau như vậy chỉ có bảng chỉ mục lưu trữ các bảng được lập chỉ mục bởi mã thông báo cụm từ đầu tiên, sau đó mỗi mục con chứa giá trị được lập chỉ mục bởi mã thông báo cụm từ thứ hai ... v.v. , sẽ lập chỉ mục một giá trị số tương ứng với ce của cụm từ.

Có lẽ nó sẽ được rõ ràng hơn với một ví dụ, nếu bạn có hai cụm từ sau:

• Tôi thích chuối.
• Tôi thích gà nóng.

chỉ số của bạn sẽ có cấu trúc sau:

index["I"] = { 
    ["like"] = { 
     ["banana"] = 1, 
     ["hot"] = { 
      ["chick"] = 1 
     } 
    }  
} 

Bằng cách đó bạn có thể đếm frenquencies với một bước traversal duy nhất, và đếm lần xuất hiện cùng một lúc bạn lập chỉ mục, nhưng như tôi đã nói trước đây, nó phụ thuộc vào mục tiêu của bạn là gì, và nó sẽ ngụ ý phân chia lại cụm từ của bạn để tìm sự xuất hiện thông qua chỉ mục của bạn.câu trả lời

Answer 5

kikito là tốt, nhưng có một số sai sót:

• Nếu bạn thực hiện t[{a=1}] = true hai lần, store sẽ chứa hai bảng (rò rỉ bộ nhớ cho tuổi thọ của bảng băm)
• Sửa đổi giá trị một lần bạn đã lưu nó không hoạt động, bạn cũng không thể xóa nó. Cố gắng thay đổi nó sẽ dẫn đến việc thu hồi mạnh trả lại bất kỳ giá trị nào bạn đã gán cho khóa đó trong quá khứ.
• Hiệu suất truy cập là O (n) (n là số lượng mục được lưu trữ và giả định rằng truy xuất giá trị của lua từ một bảng là O (1)); kết hợp với điểm đầu tiên, hiệu suất của bảng băm này sẽ làm suy giảm với việc sử dụng

(Cũng lưu ý "tương đương" chức năng của kikito đó sẽ gây ra một vòng lặp vô hạn nếu bất kỳ bảng có một tham chiếu vòng tròn.)

Nếu bạn không bao giờ cần phải thay đổi/loại bỏ bất kỳ thông tin nào trong bảng, sau đó câu trả lời của kikito sẽ đủ khi nó đứng. Nếu không, metatable phải được thay đổi sao cho __newindex đảm bảo rằng bảng chưa tồn tại:

t = setmetatable({}, { 
    __newindex = function(tbl, key, value) 
     for k,v in pairs(store) do 
      if equivalent(k,key) then 
       tbl[k] = value 
       return 
      end 
     end 
     store[key] = value 
    end, 
    __index = function(tbl, key) 
     for k,v in pairs(store) do 
      if equivalent(k, key) then return v end 
     end 
    end 
}) 

Như bạn đã gợi ý, một lựa chọn hoàn toàn khác nhau là để viết một chức năng tùy chỉnh băm. Dưới đây là một Hashtable có thể tận dụng điều đó:

local function HashTable(Hash, Equals) 
    --Hash is an optional function that takes in any key and returns a key that lua can use (string or number). If you return false/nil, it will be assumed that you don't know how to hash that value. 
    -- If Hash is not provided, table-keys should have a GetHash function or a .Hash field 
    --Equals is an optional function that takes two keys and specify whether they are equal or not. This will be used when the same hash is returned from two keys. 
    -- If Equals is not provided, items should have a Equals function; items are in this case assumed to not be equal if they are different types. 
    local items = {} --Dict<hash, Dict<key, value>> 
    local function GetHash(item) 
     return Hash and Hash(item) or type(item) == "table" and (item.GetHash and item:GetHash() or item.Hash) or item 
    end 
    local function GetEquals(item1, item2) 
     if Equals then return Equals(item1, item2) end 
     local t1, t2 = type(item1), type(item2) 
     if t1 ~= t2 then return false end 
     if t1 == "table" and item1.Equals then 
      return item1:Equals(item2) 
     elseif t2 == "table" and item2.Equals then 
      return item2:Equals(item1) 
     end 
     return false 
    end 
    return setmetatable({}, { 
     __newindex = function(_, key, value) 
      local hash = GetHash(key) 
      local dict = items[hash] 
      if not dict then 
       if value ~= nil then --Only generate a table if it will be non-empty after assignment 
        items[hash] = {[key] = value} 
       end 
       return 
      end 
      for k, v in pairs(dict) do 
       if GetEquals(key, k) then --Found the entry; update it 
        dict[k] = value 
        if value == nil then --check to see if dict is empty 
         if next(dict) == nil then 
          items[hash] = nil 
         end 
        end 
        return 
       end 
      end 
      --This is a unique entry 
      dict[key] = value 
     end, 
     __index = function(_, key) 
      local hash = GetHash(key) 
      local dict = items[hash] 
      if not dict then return nil end 
      for k, v in pairs(dict) do 
       if GetEquals(key, k) then 
        return v 
       end 
      end 
     end 
    }) 
end 

Cách sử dụng Ví dụ:

local h = HashTable(
    function(t) return t.a or 0 end, --Hash 
    function(t1, t2) return t1.a == t2.a end) --Equals 
h[{a=1}] = 1 
print(h[{a=1}]) -- 1 
h[{a=1}] = 2 
print(h[{a=1}]) -- 2 
print(h[{a=1,b=2}]) -- 2 because Hash/Equals only look at 'a' 

Đương nhiên, bạn sẽ muốn có được Hash tốt hơn/Bằng chức năng.

Miễn là băm phím của bạn hiếm khi va chạm, hiệu suất này của lớp này phải là O (1).

(Lưu ý: Tôi muốn đã đặt nửa trên của câu trả lời này như một bình luận cho kikito, nhưng tôi không có danh tiếng vào thời điểm này để làm như vậy.)