根據給定的順序對數組進行排序

我有兩個數組。第一個數組包含排序順序。第二個數組包含任意數量的元素。根據給定的順序對數組進行排序

我有第二個數組中的所有元素（值明智）保證在第一個數組中，我只與數字一起工作的屬性。

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

根據給定的順序對數組進行排序

回答

相關問題