Ruby # index 메서드 VS 바이너리 검색

주어진 요소와 배열에서 Ruby # index 메서드는 배열에있는 요소의 위치를 반환합니다. 필자는 내장 검색 엔진보다 성능이 뛰어날 것으로 기대하는 바이너리 검색을 사용하여 자체 인덱스 메소드를 구현했습니다. 놀랍게도 내장 된 컴퓨터는 실험에서 약 3 배 빠릅니다.Ruby # index 메서드 VS 바이너리 검색

루비스트는 이유를 알고 있습니까?

출처

2011-09-15 Terry Li

누가 Ruby'# index' 메소드가 이미 이진 검색으로 구현되지 않았다고 말 했나요? 그리고 누가 그 메소드가 루비에서 구현되었다고 말 했나요? :-) –

@Platinum Azure 아, 이진 검색으로 C로 구현 될 수 있습니다. 고마워요! –

당신은 그것을 얻었다! :-) –

내장 된 #index is not a binary search은 단순한 반복 검색에 불과합니다. 그러나 Ruby보다는 C로 구현되어 자연스럽게 몇 배 더 빠르다.

출처

2011-09-15 19:30:55 harbichidian

감사합니다. 그래도 정말 이상합니다. 바이너리 검색 방식을 채택하지 않은 이유가 있었습니까? –

이진 검색은 두 요소를 비교할 수 있다는 것을 의미합니다. 두 요소가 같은지 여부를 확인할 수있는 것과는 반대입니다. 또한 문서에서 인수와 동일한 * first * 객체를 반환한다고 말합니다. 바이너리 검색은 항상 해당 요소를 반환하지는 않습니다. 게다가 #bsearch (배열이 정렬되었다고 가정) 버전은 #index보다 느리지 않습니다. https://gist.github.com/1220440 –

#bsearch 구현이 Ruby와 Ruby 사이의 차이를 이길 수 있다고 가정합니다. 이진 검색과 순차 검색 사이의 차이점은 무엇입니까? –

Ruby # index 메서드 VS 바이너리 검색

답변

관련 문제