Ermittelt den Index des Array-Elements schneller als O (n)

Vorausgesetzt, ich habe ein RIESIGES Array und einen Wert daraus. Ich möchte einen Index des Werts im Array erhalten. Gibt es einen anderen Weg, als anzurufen Array#index, um ihn zu bekommen? Das Problem ergibt sich aus der Notwendigkeit, ein wirklich großes Array zu behalten und sehr Array#indexoft anzurufen.

Nach einigen Versuchen stellte ich fest, dass das Zwischenspeichern von Indizes innerhalb von Elementen durch Speichern von Strukturen mit (value, index)Feldern anstelle des Werts selbst einen großen Leistungsschritt darstellt (20-facher Gewinn).

Trotzdem frage ich mich, ob es eine bequemere Möglichkeit gibt, den Index von en element ohne Caching zu finden (oder ob es eine gute Caching-Technik gibt, die die Leistung steigert).

Konvertieren Sie das Array in einen Hash. Dann suchen Sie nach dem Schlüssel.

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

Warum nicht Index oder Index verwenden?

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')

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

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

Andere Antworten berücksichtigen nicht die Möglichkeit, dass ein Eintrag mehrmals in einem Array aufgeführt wird. Dies gibt einen Hash zurück, bei dem jeder Schlüssel ein eindeutiges Objekt im Array ist und jeder Wert ein Array von Indizes ist, das dem Standort des Objekts entspricht:

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] }

Dies ermöglicht eine schnelle Suche nach doppelten Einträgen:

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

Gibt es einen guten Grund, keinen Hash zu verwenden? Lookups sind O(1)vs. O(n)für das Array.

Wenn es sich um ein sortiertes Array handelt, können Sie einen binären Suchalgorithmus ( O(log n)) verwenden. Erweitern Sie beispielsweise die Array-Klasse mit dieser Funktionalität:

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

Wenn Sie eine Kombination aus der Antwort von @ sawa und dem dort aufgeführten Kommentar verwenden, können Sie einen "schnellen" Index und einen Index für die Array-Klasse implementieren.

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

Wenn Ihr Array eine natürliche Reihenfolge hat, verwenden Sie die binäre Suche.

Verwenden Sie die binäre Suche.

Die binäre Suche hat O(log n)Zugriffszeit.

Hier sind die Schritte zur Verwendung der binären Suche:

• Wie ist die Reihenfolge Ihres Arrays? Ist es zum Beispiel nach Namen sortiert?
• Verwenden Sie bsearchdiese Option , um Elemente oder Indizes zu finden

Codebeispiel

# 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

Trotzdem frage ich mich, ob es eine bequemere Möglichkeit gibt, den Index von en element ohne Caching zu finden (oder ob es eine gute Caching-Technik gibt, die die Leistung steigert).

Sie können die binäre Suche verwenden (wenn Ihr Array geordnet ist und die Werte, die Sie im Array speichern, in irgendeiner Weise vergleichbar sind). Damit dies funktioniert, müssen Sie in der Lage sein, der binären Suche mitzuteilen, ob sie "nach links" oder "nach rechts" des aktuellen Elements suchen soll. Aber ich glaube, es ist nichts Falsches daran, das indexbeim Einfügen zu speichern und es dann zu verwenden, wenn Sie das Element aus demselben Array erhalten.