我想尽可能高效地创建一个“几乎排序”的数组(为了探索列表中随机细微变化的影响,我希望经常调用这个例程)。
我有 Ruby 代码可以做我想做的事:
sortme = [ 'X','A','B','W','S','J','7','9','Q','E' ]
n = sortme.length
correctly_sorted = sortme.sort
# ["7", "9", "A", "B", "E", "J", "Q", "S", "W", "X"]
# Specific to this case, I'd like the disorder to be strongest at the
# start of the array. In general, I would like to be able to control
# it, in relation to the sorted positions.
sort_adjust = Array.new( n ) { |i| i + ( rand() * 50 ) / (i+10) }
adjust_indexes = (0...n).sort_by { |i| sort_adjust[i] }
# e.g. [0, 2, 1, 3, 4, 5, 6, 7, 9, 8]
almost_sorted = adjust_indexes.map { |i| correctly_sorted[i] }
# Example output
# ["7", "A", "9", "B", "E", "J", "Q", "S", "X", "W"]
我的解决方案执行两个 sort
,一个 map
,并调用 rand()
N 次来填充一个临时数组。有什么方法可以减少对 Array
的方法调用次数,并提高效率吗?或者减少我调用 rand()
的次数,但仍然可以控制项目的洗牌?
最佳答案
如何应用标准和高效array shuffling algorithm , 但添加随机化?
基本算法为每个位置 i 选择一个随机位置 n>=j>=i 来交换值。相反,决定以概率 p 进行交换。对于 p=1,您有标准的改组算法(其中所有排列出现的可能性相同),对于 p=0,数组将保持排序。
关于ruby - 创建一个几乎排序的数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21111242/