我正在学习排队论,在这个理论中,我经常遇到以下情况。
设x,y都是非负整数的n元组(描述n个队列的长度).此外,x和y都有称为“主队列”的区分队列。例如,
X= 3,6,1,9,5,2与x‘=1
Y= 6,1,5,9,5与y‘=5
(根据Python的术语,我正在计算队列0-5。)
如何有效地在{0,1,...,5}上实现/构造以下置换f?
,
这将给出置换0,5,1,3,4,2。
我的解决方案包括多次跟踪x和y上的索引和循环,而且效率很低。(大致查看我的应用程序中的n >= 1,000,000 )。
任何帮助都将不胜感激。
发布于 2011-11-16 02:39:32
因为你必须做排名,你不能得到线性和需要排序。所以看起来很简单。在O( 1 )中做1,在O(n)中做2,只需遍历n元组。同时,您可以构造x和y的副本,只包含3的副本,但不只是包含值,而是使用原值的元组及其索引。
在你的例子中,x和元组左是[3,0,1,2,2,5],y-与-元组-左是[6,0,1,1,5,2]。
然后对x与元组左和y与元组左(它将是O(n.log n))进行排序,并从相应元组的第二个元素中读取置换。
在你的例子中,排序x和.将是[1,2,2,5,3,0]并排序为y-.将是[1,1,5,2,6,0]。现在,从第二个元素中可以很好地看到5 : f(2)=1,f(5)=2,f(0)=0。
编辑:在Javascript中包括O(n+L):
function qperm (x, y, xprime, yprime) {
var i;
var n = x.length;
var qperm = new Array(n);
var countsx = [], countsy = []; // same as new Array()
qperm[xprime] = yprime; // doing 1.
for (i = 0; i < n; ++i) {
if (x[i] == y[i] && i != xprime && i != yprime) { // doing 2.
qperm[i] = i; }
else { // preparing for 4. below
if (i != xprime) {
if (countsx[x[i]]) countsx[x[i]]++; else countsx[x[i]] = 1; }
if (i != yprime) {
if (countsy[y[i]]) countsy[y[i]]++; else countsy[y[i]] = 1; } }
// finishing countsx and countsy
var count, sum;
for (i = 0, count = 0; i < countsx.length; ++i) {
if (countsx[i]) {
sum = count + countsx[i];
countsx[i] = count;
count = sum; }
for (i = 0, count = 0; i < countsy.length; ++i) {
if (countsy[i]) {
sum = count + countsy[i];
countsy[i] = count;
count = sum; }
var yranked = new Array(count);
for (i = 0; i < n; ++i) {
if (i != yprime && (x[i] != y[i] || i == xprime)) { // doing 4. for y
yranked[countsy[y[i]]] = y[i];
countsy[y[i]]++; } }
for (i = 0; i < n; ++i) {
if (i != xprime && (x[i] != y[i] || i == yprime)) { // doing 4. for x and 5. at the same time
// this was here but was not right: qperm[x[i]] = yranked[countsx[x[i]]];
qperm[i] = yranked[countsx[x[i]]];
// this was here but was not right: countsy[y[i]]++; } } }
countsx[x[i]]++; } }
return qperm; }希望它是正确的;-)
https://stackoverflow.com/questions/8145777
复制相似问题