Project

General

Profile

Feature #12810

Improve `Set#find_index` performance

Added by Asche (Thomas Charbonnel) almost 3 years ago. Updated over 2 years ago.

Status:
Rejected
Priority:
Normal
Target version:
-
[ruby-core:77490]

Description

Hello everyone!

I've toyed a bit with the Set class lately and have found some performance issues with method find_index. Github gist here: https://gist.github.com/thomascharbonnel/f023ca137f2b2b7021cbe2d580485cd4

I'm thinking it would be possible to add an index as default value for each new item of Set (instead of a boolean like now), find_index would then be executed in O(1).
I can attach a patch in a few days if everybody is cool with the idea.

Thanks!
Thomas.

History

Updated by herwin (Herwin W) almost 3 years ago

Quoting the first line of http://ruby-doc.org/stdlib-2.3.1/libdoc/set/rdoc/Set.html:

Set implements a collection of unordered values

This would mean the set {1,2,3} is exactly the same as the sets {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2} and {3,2,1}. This is a property of the mathematical concept of sets (see https://en.wikipedia.org/wiki/Set_%28mathematics%29, which also describes the order of the items as being irrelevant). So actually, I don't see how using Set#find_index would make any sense. The current implementation just accidentally preserves the order of the items in the set via undocumented behaviour, relying on that would be scary.

Updated by shyouhei (Shyouhei Urabe) over 2 years ago

  • Assignee set to knu (Akinori MUSHA)
  • Status changed from Open to Assigned

Seems a design issue. Let me assign this to the library's maintainer.

Updated by knu (Akinori MUSHA) over 2 years ago

  • Status changed from Assigned to Rejected

As commented by Herwin W and replied to the submitter in a personal mail, Set has no sense of index where elements are theoretically unordered. It's just that a Set happens to respond to find_index via the Enumerable module and have an order due to its implementation.

If you need find_index then Set is not likely the solution for your problem. You should use Hash directly.

Thanks for the feedback anyway!

Also available in: Atom PDF