max pleaner - 1 year ago 60
Ruby Question

# Combine arrays and preserve ordering - but prioritize one array's ordering over another

Say I have two arrays:

``````Arr1 = ["1-a", "1-b", "1-c"]
Arr2 = ["2-a", "2-b", "2-c"]
``````

I know how to combine them into an array, preserving their order:

``````  Arr1.zip(Arr2).flatten(1)
# => ["1-a", "2-a", "1-b", "2-b", "1-c", "2-c"]
``````

In this example I'd consider Arr1 to be 'prioritized' over Arr2 because "1-a" appears before "2-a" and "1-c" appears before "2-c".

Here's what happens if Arr2 is 'prioritized':

``````Arr2.zip(Arr1).flatten(1)
# => ["2-a", "1-a", "2-b", "1-b", "2-c", "1-c"]
``````

With these examples, 'priority' is a binary state. But what if I wanted to use a decimal? Something like this:

``````# Arr1's order is 50% as important as Arr2's order

Arr1_priority = 0.5
results = []
Arr2.each_with_index do |element, index|
results << element
if (1.to_f - (index.to_f / results.length.to_f)) <= Arr1_priority
# only push Arr1 item if the iterator is 50% done
results << Arr1.shift
end
end

results
# => ["2-a", "2-b", "1-a", "2-c", "1-b"]
``````

With this implementation,Arr1 will only start to be included in the results after 50% of Arr2's elements are added.

But I'm not confident this gets the job done as well as possible.
Does
`.5`
priority mean really mean that Arr1 only starts appearing halfway through? My hunch is no. It'd be better if Arr1's elements gradually started to appear.

Right now this graph describes what's happening in this attempt to achieve "50% priority"

``````y axis: percentage of added nodes that are Arr1
x axis: percent completion of Arr2 iteration

100% |
|
75%  |
|
50%  |           X   X    X
|
25%  |
|
0%  |  X    X
-------------------------
0%  25%  50%  75%  100%
``````

But the result array will only be 25% Arr1. It should be 50%. This is what I want to happen:

``````y axis: percentage of added nodes that are Arr1
x axis: percent completion of Arr2 iteration

100% |                     X
|
75%  |                X
|
50%  |           X
|
25%  |       X
|
0%  |  X
-------------------------
0%  25%  50%  75%  100%
``````

Here's what I wrote

``````class Array

# helper method to help with testing
def mean
map(&:to_f).reduce(&:+) / length.to_f
end

# target is another array
# priority is a number between 0 and 1
#   if 0, then target will not be merged in at all
#   if 1, then the result will be ~50% composed of target
# returns array with the same length as self
# Note that the result will not contain all of self.concat(target)

def priority_merge(priority, target)
# clone the arrays to avoid side-effects
arr1, arr2 = [self, target].map(&:clone)
# get the original length to determine the results length
arr1_len = arr1.length.to_f
# convert priority to float
priority = priority.to_f
# initialize a results set
results = []
# populate the results set
arr1_len.to_i.times do |arr1_idx|
# determine the percentage completed through iteration
pct_iterated = arr1_idx.to_f / arr1_len.to_f
# calculate per-run likelihood of favoring target
per_run_priority = pct_iterated * priority
# conclusively determine which array this iteration will pull from
num_true_cases = (100.0 * per_run_priority).to_i
cases = num_true_cases.times.map { true }.concat((100 - num_true_cases).times.map { false })
priority_run_result = cases.sample
# push from arr2 if the priority run result is true, otherwise push from arr1
results << (priority_run_result ? arr2 : arr1).shift
end
results
end
end
``````

and testing it

``````a1 = 50.times.map { 1 }
a2 = 50.times.map { 2 }

puts "MERGE CASE 1"
result = 50.times.map do
result = a1.priority_merge(1.0, a2)
result.select { |item| item == 2 }.count.to_f / a1.length.to_f
end
puts result.mean
# => is around 50%

puts "MERGE CASE 0.5"
result = 50.times.map do
result = a1.priority_merge(0.5, a2)
result.select { |item| item == 2 }.count.to_f / a1.length.to_f
end
puts result.mean
# => is around 25%
puts "MERGE CASE 0"
result = 50.times.map do
result = a1.priority_merge(0.0, a2)
result.select { |item| item == 2 }.count
end
puts result.mean
# => is 0%
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download