根据给定的顺序对数组进行排序

我有两个数组。第一个数组包含排序顺序。第二个数组包含任意数量的元素。根据给定的顺序对数组进行排序

我有第二个数组中的所有元素（值明智）保证在第一个数组中，我只与数字一起工作的属性。

A = [1,3,4,4,4,5,2,1,1,1,3,3] 
Order = [3,1,2,4,5]

当我有点A，我想的元素出现在由Order指定的顺序：

[3, 3, 3, 1, 1, 1, 1, 2, 4, 4, 4, 5]

注意重复是公平的游戏。 A中的元素不应该改变，只能重新排序。我怎样才能做到这一点？

来源

2012-05-13 MxyL

你不应该用大写字母开始你的变量名，因为它们会变成常量。另外，除'Order'中的'A'外，没有其他值吗？ –

对于这种特殊情况，是的，没有其他值。如果某些数组本来具有其他值，则在进入此类之前会被过滤掉。 – MxyL

>> source = [1,3,4,4,4,5,2,1,1,1,3,3] 
=> [1, 3, 4, 4, 4, 5, 2, 1, 1, 1, 3, 3] 
>> target = [3,1,2,4,5] 
=> [3, 1, 2, 4, 5] 
>> source.sort_by { |i| target.index(i) } 
=> [3, 3, 3, 1, 1, 1, 1, 2, 4, 4, 4, 5]

来源

2012-05-13 18:18:25 Gareth

+1。你打败了我19秒，我删除了我的答案:-) –

@MichaelKohl你提出了一个很好的观点，如果这个数组可能会变大，那么这个方法可能会被重新考虑，但是这对于大多数目的来说应该足够快 – Gareth

如果（且仅当！）@加雷思的答案被证明是过于缓慢，而不是去：

# Pre-create a hash mapping value to index once only… 
index = Hash[ Order.map.with_index.to_a ] #=> {3=>0,1=>1,2=>2,4=>3,5=>4} 

# …and then sort using this constant-lookup-time 
sorted = A.sort_by{ |o| index[o] }

基准：

require 'benchmark' 

order = (1..50).to_a.shuffle 
items = 1000.times.map{ order.sample } 
index = Hash[ order.map.with_index.to_a ] 

Benchmark.bmbm do |x| 
    N = 10_000 
    x.report("Array#index"){ N.times{ 
    items.sort_by{ |n| order.index(n) } 
    }} 
    x.report("Premade Hash"){ N.times{ 
    items.sort_by{ |n| index[n] } 
    }} 
    x.report("Hash on Demand"){ N.times{ 
    index = Hash[ order.map.with_index.to_a ] 
    items.sort_by{ |n| index[n] } 
    }} 
end 

#=>      user  system  total  real 
#=> Array#index  12.690000 0.010000 12.700000 (12.704664) 
#=> Premade Hash  4.140000 0.000000 4.140000 ( 4.141629) 
#=> Hash on Demand 4.320000 0.000000 4.320000 ( 4.323060)

来源

2012-05-13 18:41:16 Phrogz

'＃sort_by'已经在内部生成了一个映射值的临时数组 - 这个哈希缓存比[文档中提到的]（http://apidock.com/ruby/Enumerable/sort_by）元组数组更有效率吗？ – Gareth

@Gareth是的，因为对于大小为_m_的数组中的_n_值，使用'Array＃index'平均需要_n * m/2_操作（最坏情况：_n * m_），而使用哈希查找总是只使用_m_操作或者在计算中包含散列时间的情况下为_n + m_）。而且，'index'的_n_必须在红宝石缓慢的土地上进行，而使用散列准备的_n_几乎完全在C中。参见我的编辑。 – Phrogz

@Gareth但是，正如你在评论中所说的，你的答案在大多数情况下可能会“足够快”。例如，用10个值中的一个对50个项目进行排序，使用你的方式约30μs，按我的方式15-20μs。 :) – Phrogz

另一种可能的解决方案没有明确的排序：

source = [1,3,4,4,4,5,2,1,1,1,3,3] 
target = [3,1,2,4,5] 
source.group_by(&lambda{ |x| x }).values_at(*target).flatten(1)

来源

2012-05-14 14:05:57

根据给定的顺序对数组进行排序

回答

相关问题