Uzyskaj indeks elementu tablicy szybciej niż O (n)

Biorąc pod uwagę, że mam OGROMNĄ tablicę i wartość z niej. Chcę uzyskać indeks wartości w tablicy. Czy jest inny sposób, zamiast zadzwonić Array#indexpo to? Problem wynika z potrzeby utrzymywania naprawdę dużej tablicy i wywoływania Array#indexogromną liczbę razy.

Po kilku próbach odkryłem, że buforowanie indeksów wewnątrz elementów poprzez przechowywanie struktur z (value, index)polami zamiast samej wartości daje ogromny skok wydajności (20x wygrana).

Nadal zastanawiam się, czy istnieje wygodniejszy sposób na znalezienie indeksu elementu en bez buforowania (lub jest dobra technika buforowania, która zwiększy wydajność).

Przekonwertuj tablicę na skrót. Następnie poszukaj klucza.

array = ['a', 'b', 'c']
hash = Hash[array.map.with_index.to_a]    # => {"a"=>0, "b"=>1, "c"=>2}
hash['b'] # => 1

Dlaczego nie użyć indeksu lub rindeksu?

array = %w( a b c d e)
# get FIRST index of element searched
puts array.index('a')
# get LAST index of element searched
puts array.rindex('a')

indeks: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-index

rindex: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-rindex

Inne odpowiedzi nie uwzględniają możliwości wielokrotnego wpisu w tablicy. To zwróci skrót, w którym każdy klucz jest unikalnym obiektem w tablicy, a każda wartość jest tablicą indeksów, która odpowiada miejscu, w którym obiekt żyje:

a = [1, 2, 3, 1, 2, 3, 4]
=> [1, 2, 3, 1, 2, 3, 4]

indices = a.each_with_index.inject(Hash.new { Array.new }) do |hash, (obj, i)| 
    hash[obj] += [i]
    hash
end
=> { 1 => [0, 3], 2 => [1, 4], 3 => [2, 5], 4 => [6] }

Pozwala to na szybkie wyszukiwanie zduplikowanych wpisów:

indices.select { |k, v| v.size > 1 }
=> { 1 => [0, 3], 2 => [1, 4], 3 => [2, 5] }

Czy istnieje dobry powód, aby nie używać skrótu? Odnośniki są O(1)a O(n)dla tablicy.

Jeśli jest to posortowana tablica, możesz użyć algorytmu wyszukiwania binarnego ( O(log n)). Na przykład rozszerzenie klasy Array o tę funkcjonalność:

class Array
  def b_search(e, l = 0, u = length - 1)
    return if lower_index > upper_index

    midpoint_index = (lower_index + upper_index) / 2
    return midpoint_index if self[midpoint_index] == value

    if value < self[midpoint_index]
      b_search(value, lower_index, upper_index - 1)
    else
      b_search(value, lower_index + 1, upper_index)
    end
  end
end

Biorąc pod uwagę odpowiedź @ sawy i komentarz tam wymieniony, można zaimplementować indeks „quick” i rindex w klasie tablicy.

class Array
  def quick_index el
    hash = Hash[self.map.with_index.to_a]
    hash[el]
  end

  def quick_rindex el
    hash = Hash[self.reverse.map.with_index.to_a]
    array.length - 1 - hash[el]
  end
end

Jeśli twoja tablica ma naturalną kolejność, użyj wyszukiwania binarnego.

Użyj wyszukiwania binarnego.

Wyszukiwanie binarne ma O(log n)czas dostępu.

Oto kroki, jak korzystać z wyszukiwania binarnego,

• Jaka jest kolejność twojej tablicy? Na przykład, czy jest posortowane według nazwy?
• Służy bsearchdo znajdowania elementów lub indeksów

Przykład kodu

# assume array is sorted by name!

array.bsearch { |each| "Jamie" <=> each.name } # returns element
(0..array.size).bsearch { |n| "Jamie" <=> array[n].name } # returns index

Nadal zastanawiam się, czy istnieje wygodniejszy sposób na znalezienie indeksu elementu en bez buforowania (lub jest dobra technika buforowania, która zwiększy wydajność).

Możesz użyć wyszukiwania binarnego (jeśli twoja tablica jest uporządkowana, a wartości, które przechowujesz w tablicy są w jakiś sposób porównywalne). Aby to zadziałało, musisz być w stanie powiedzieć wyszukiwarce binarnej, czy ma ona szukać „w lewo”, czy „w prawo” bieżącego elementu. Ale uważam, że nie ma nic złego w przechowywaniu indexczasu wstawiania, a następnie używaniu go, jeśli otrzymujesz element z tej samej tablicy.