1

Let's say I have an array of objects (or hashes) that looks like the following -

a = [ {salary: 10, products: 1}, {salary: 9, products: 1}, {salary: 10, products: 0} ]

I want to remove elements from the array if there exists another element in the array that has a higher product value at the same salary or less. Some pseudo logic to cover those two instances would look like this-

IF EXISTS 'other element' WITH >= products and < salary THEN DELETE

IF EXISTS 'other element' WITH > products and =< salary THEN DELETE

What Ruby methods could help me accomplish this?

Edit: In the above example, the expected output would be {salary: 9, products: 1}. The first element should be deleted in the grounds that there's another element with less salary, but the same (or greater) products. The third element could be deleted either on the grounds that the first element has more products at the same salary, or because the 2nd element has more products as less salary.

Improve this question
11
  • Array#max_by and Array#delete_if or Array#reject Commented Nov 21, 2014 at 0:11
  • I'm aware of those methods, but how do I compare them against the other elements? I'm trying to think of some way to use select or include to reference the array inside of the block to see if such a case exists. Commented Nov 21, 2014 at 0:17
  • Just use delete_if or reject... If you know about these methods, then why are we still talking about this? It's a one liner. Commented Nov 21, 2014 at 0:21
  • You don't need to compare them to other elements, just find the value you want to test against and then use it to build the predicate to Array#reject. Commented Nov 21, 2014 at 0:31
  • @IronSavior Isn't the value to test against different for each element? That's the way I understood the question. Commented Nov 21, 2014 at 0:37

3 Answers 3

Reset to default
2

First, an Alternative Approach

This can be solved with a little decomposition of the problem. The description of the mechanism that you want to employ leads me to believe that you're essentially trying to order the elements by a ratio of products:salary. You can identify these top performers in one pass by sorting them like so (a being the array of hashes):

sorted = a.sort_by{|h| Rational h[:products], h[:salary] }

From there, you can skim from either the top or the bottom of the array sorted as you please. This will probably tell you what you're trying to learn about the data in question.

But in case that's not really what you want...

Solution as Described

If you really want it calculated in exactly the way you describe it, then you will have to make several passes over the collection. I might use the following functional expression.

selected = a.map{ |h|
  h[:salary]
}.uniq.map{ |salary|
  a.select{ |h|
    h[:salary] <= salary
  }.max_by{ |h|
    h[:products]
  }
}.uniq

If you had a very large input set, you could optimize away the select block for some performance gains, but it wouldn't be as easy to read. You'll have to decide whether or not that matters to you.

Please note that this will only select a single element per salary range, so if you were to have two elements with exactly the same salary and products, only one will appear in the final list. If you wanted to include elements that are tied, then it's only slightly more complex:

selected = a.map{ |h|
  h[:salary]
}.uniq.flat_map{ |salary|
  most = 0
  a.select{ |h|
    h[:salary] <= salary
  }.tap{ |group|
    most = group.map{|h| h[:products] }.max
  }.select{ |h|
    h[:products] == most
  }
}.uniq
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Your code returns [{:salary=>9, :products=>1}], which I don't believe is correct.
@CarySwoveland It's correct. Look at the given data again. All the other salaries are higher.
An element is to be rejected if there is another element with a higher product value and... We can stop right there. No element h for which h[products' => 1 is to be rejected, because there are no elements with a product value greater than 1.
@CarySwoveland The questioner says the output should be [{:salary=>9, :products=>1}].
Yes, I see that edit. The question is contradictory. What a mess!
|
1

This works OK, but it's not elegant or efficient:

a.reject { |e1| a.any? { |e2| e1 != e2 && e2[:salary] <= e1[:salary] && e2[:products] >= e1[:products] } }

The problem is that it's O(n^2) - for each element in the array it traverses the array again. If efficiency isn't a huge problem for you then this is probably clearest to start with.

The only other solutions that spring to mind involve transforming the array into a tree or other data structure to get better efficiency, but that will look and feel a lot more complex.

Improve this answer

4 Comments

This is actually closest to what I was looking for. For some reason, it's not quite giving me what I know to be the correct desired output. My actual program uses an array of array of objects but I simplified it in the example for the sake of explaining. This is what I'm trying now a = a.delete_if { |e1| a.any? { |e2| e1 != e2 && e2.sum(&:salary) <= e1.sum(&:salary) && e2.sum(&:score) >= e1.sum(&:score) } }, and this logic runs on an array several times, because the array has more elements added to it itteratively. Seems to not be fully taking into account score when deleting, though.
The problem with one-liners is that they're hard to debug! It looks like that code is exactly equivalent to what I posted so it should work. If you post some test data using objects I can have a look, otherwise it's going to be hard to do much more from here.
Dave, I found the issue. My inner arrays can be duplicates of each other, so they were matching each other since the logic included "or equal to". I just made the score criteria greater than to avoid that, as well as removing duplicates before running this one-liner. I was also switched && to and which seemed to help with some other buggy issues. The final result- a.reject! { |e1| a.any? { |e2| e1 != e2 and e2.sum(&:salary) <= e1.sum(&:salary) and e2.sum(&:score) > e1.sum(&:score) } } Thanks for your help!
Great! My only worry is that and really isn't equivalent to && so that shouldn't really be valid. But as long as it's working for you then I'm happy.
0

One way:

a = [ {salary: 10, products: 1},
      {salary:  9, products: 1},
      {salary: 12, products: 0},
      {salary: 10, products: 0} ]

b = a.group_by {|h| h[:salary]}.values.map {|a| a.max_by { |h| h[:products]}}
  #=> [{:salary=>10, :products=>1},
  #    {:salary=>9, :products=>1},
  #    {:salary=>12, :products=>0}]
a.reject {|h| b.any? {|g|
  (g[:salary] <= h[:salary]) && g[:products] > h[:products]}}
  #=> [{:salary=>10, :products=>1}, {:salary=>9, :products=>1}]

b are, in effect`, the "undominated" hashes; i.e., the only ones that need be considered in the next step. One could skip this step, but it would improve efficiency if the proportion of hashes that are undominated is not too large.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.