O (n)보다 빠르게 배열 요소의 인덱스 가져 오기

O (n)보다 빠르게 배열 요소의 인덱스 가져 오기

---

나는 거대한 배열과 그것의 값을 가지고 있습니다. 배열 값의 인덱스를 얻고 싶습니다. Array#index그것을 얻기 위해 전화 하는 것보다 다른 방법 이 있습니까? 문제는 정말 거대한 배열을 유지하고 Array#index엄청난 시간을 호출 할 필요가 있기 때문입니다.

몇 번의 시도 끝에 값 자체 대신 필드가있는 구조체를 저장하여 요소 내부에 인덱스 를 캐싱(value, index) 하면 성능이 크게 향상 된다는 것을 발견했습니다 (20 배 승리).

그래도 캐싱없이 en 요소의 인덱스를 찾는 더 편리한 방법이 있는지 궁금합니다 (또는 성능을 향상시킬 좋은 캐싱 기술이 있습니다).

---

배열을 해시로 변환합니다. 그런 다음 열쇠를 찾으십시오.

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

---

index 또는 rindex를 사용하지 않는 이유는 무엇입니까?

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

색인 : 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

---

다른 답변은 배열에 여러 번 나열된 항목의 가능성을 고려하지 않습니다. 그러면 각 키가 배열의 고유 한 개체이고 각 값이 개체가있는 위치에 해당하는 인덱스 배열 인 해시가 반환됩니다.

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

이렇게하면 중복 항목을 빠르게 검색 할 수 있습니다.

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

---

해시를 사용하지 않는 합당한 이유가 있습니까? 조회는 어레이 O(1)와 비교 O(n)됩니다.

---

그것은 만약 정렬 된 배열은 이진 검색 알고리즘을 사용할 수있다 ( O(log n)). 예를 들어 다음 기능으로 Array 클래스를 확장합니다.

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

---

Taking a combination of @sawa's answer and the comment listed there you could implement a "quick" index and rindex on the array class.

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

---

If your array has a natural order use binary search.

Use binary search.

Binary search has O(log n) access time.

Here are the steps on how to use binary search,

• What is the ordering of you array? For example, is it sorted by name?
• Use bsearch to find elements or indices

Code example

# 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

---

Still I wonder if there's a more convenient way of finding index of en element without caching (or there's a good caching technique that will boost up the performance).

You can use binary search (if your array is ordered and the values you store in the array are comparable in some way). For that to work you need to be able to tell the binary search whether it should be looking "to the left" or "to the right" of the current element. But I believe there is nothing wrong with storing the index at insertion time and then using it if you are getting the element from the same array.

참고URL : https://stackoverflow.com/questions/6242311/get-index-of-array-element-faster-than-on