Jak sprawdzić, czy tabela zawiera element w Lua?

98

Czy istnieje metoda sprawdzania, czy tabela zawiera wartość? Mam swoją (naiwną) funkcję, ale zastanawiałem się, czy istnieje do tego coś „oficjalnego”? Albo coś bardziej wydajnego ...

function table.contains(table, element)
  for _, value in pairs(table) do
    if value == element then
      return true
    end
  end
  return false
end

Nawiasem mówiąc, głównym powodem, dla którego używam tej funkcji, jest używanie tabel jako zestawów, tj. Bez zduplikowanych elementów. Czy jest coś innego, czego mógłbym użyć?

Wookai
źródło
3
co oznacza _, notacja?
Martin
24
Jest to po prostu zmienna „śmieci” o nazwie _. pairs()zwraca key, value, ale w tym przykładzie potrzebuję tylko wartości. Jest to rodzaj konwencji (przyjętej w książce „Programming in Lua” lua.org/pil/index.html ), aby używać tej _zmiennej do przechowywania rzeczy, których nie potrzebujesz.
Wookai,
Widziałem konwencję nazywania zmiennych "śmieciowych" _używaną również w Pythonie i JavaScript.
iono

Odpowiedzi:

117

Możesz umieścić wartości jako klucze tabeli. Na przykład:

function addToSet(set, key)
    set[key] = true
end

function removeFromSet(set, key)
    set[key] = nil
end

function setContains(set, key)
    return set[key] ~= nil
end

Jest bardziej pełni funkcjonalny przykład tutaj .

interjay
źródło
13
Anonimowy użytkownik zaproponował następującą poprawkę do twojego kodu: Jeśli wartość w zestawie z określonym kluczem to FALSE, funkcja setContains () zwraca fałsz, mimo że w tabeli znajduje się element o określonym kluczu. wiersz „return set [key] ~ = nil” naprawia ten błąd.
oferuje
Być może takżefunction keysOfSet(set) local ret={} for k,_ in pairs(set) do ret[#ret+1]=k end return ret end
Jesse Chisholm
24

Biorąc pod uwagę Twoją reprezentację, Twoja funkcja jest tak wydajna, jak to tylko możliwe. Oczywiście, jak zauważyli inni (i jak jest to praktykowane w językach starszych niż Lua), rozwiązaniem twojego prawdziwego problemu jest zmiana reprezentacji. Jeśli masz tabele i chcesz zestawy, zamieniasz tabele w zestawy, używając elementu set jako klucza i truejako wartości. +1 do interjay.

Norman Ramsey
źródło
2

Nie mogę wymyślić innego sposobu porównywania wartości, ale jeśli użyjesz elementu zestawu jako klucza, możesz ustawić wartość na cokolwiek innego niż zero. Dzięki temu uzyskujesz szybkie wyszukiwania bez konieczności przeszukiwania całej tabeli.

Joel
źródło
2

Wiem, że to stary post, ale chciałem dodać coś dla potomności. Prostym sposobem rozwiązania problemu, który masz, jest utworzenie innej tabeli o wartości do klucza.

to znaczy. masz 2 tabele o tej samej wartości, jedna wskazuje w jednym kierunku, a druga w drugą.

function addValue(key, value)
    if (value == nil) then
        removeKey(key)
        return
    end
    _primaryTable[key] = value
    _secodaryTable[value] = key
end

function removeKey(key)
    local value = _primaryTable[key]
    if (value == nil) then
        return
    end
    _primaryTable[key] = nil
    _secondaryTable[value] = nil
end

function getValue(key)
    return _primaryTable[key]
end

function containsValue(value)
    return _secondaryTable[value] ~= nil
end

Następnie możesz wysłać zapytanie do nowej tabeli, aby sprawdzić, czy zawiera kluczowy „element”. Zapobiega to konieczności iteracji przez każdą wartość w drugiej tabeli.

Jeśli okaże się, że w rzeczywistości nie możesz użyć `` elementu '' jako klucza, ponieważ nie jest to na przykład łańcuch, dodaj sumę kontrolną lub tostringna przykład do niej, a następnie użyj tego jako klucza.

Dlaczego chcesz to zrobić? Jeśli twoje tabele są bardzo duże, ilość czasu na iterację przez każdy element będzie znacząca, uniemożliwiając ci wykonywanie tego bardzo często. Dodatkowy narzut pamięci będzie stosunkowo niewielki, ponieważ będzie przechowywać 2 wskaźniki do tego samego obiektu, a nie 2 kopie tego samego obiektu. Jeśli twoje tabele są bardzo małe, będzie to miało znacznie mniejsze znaczenie, w rzeczywistości iteracja może być nawet szybsza niż ponowne wyszukiwanie mapy.

Sformułowanie pytania jednak silnie sugeruje, że masz do czynienia z dużą liczbą spraw.

James
źródło
Dobre wyjaśnienie, ale tak naprawdę nic nie wnosi do dyskusji. Prawdopodobnie lepszym pomysłem byłaby edycja odpowiedzi interjaya.
bcdan
1
Ponadto „.key” należy zastąpić „[key]” wszędzie w tym kodzie (to samo z „value”)
Njol