xmliu1988 at gmail.com
2014-Apr-26 09:54 UTC
[R] Faster way to transform vector [3 8 4 6 1 5] to [2 6 3 5 1 4]
Hi,
could anybody help me to find a fast way to fix the following question?
Given a verctor of length N, for example bo = [3 8 4 6 1 5],
I want to drive a vector whose elements are 1, 2, ..., N and the order of
elements is the same as that in verctor bo.
In this example, the result is supposed to be bt = [2 6 3 5 1 4].
I used the following code to solove this:
bo <- c(3, 8, 4, 6, 1, 5)
N <- length(bo)
bt <- rep(0, N)
M <- max(bo)
temp <- bo
for(i in 1 : N)
{
min <- M
i_min <- 0
for(j in 1 : N)
{
if(min >= temp[j])
{
min <- temp[j]
i_min <-j
}
}
bt[i_min] <- i
temp[i_min] <- M+ 1
}> bt
[1] 2 6 3 5 1 4
However, the time complexity is O(N2).
When N is larger than 1000000, it takes too much time.
Is there any faster way to fix it?
best
Xueming
xmliu1988@gmail.com
[[alternative HTML version deleted]]
arun
2014-Apr-26 15:20 UTC
[R] Faster way to transform vector [3 8 4 6 1 5] to [2 6 3 5 1 4]
Hi,
Perhaps,
rank(bo)
#[1] 2 6 3 5 1 4
A.K.
On Saturday, April 26, 2014 11:00 AM, "xmliu1988 at gmail.com"
<xmliu1988 at gmail.com> wrote:
Hi,
could anybody help me to find a fast way to fix the following question?
Given a verctor of length N, for example bo = [3? 8? 4? 6? 1? 5],
I want to drive a vector whose elements are 1, 2, ..., N and the order of
elements is the same as that in verctor bo.
In this example, the result is supposed to be bt = [2? 6? 3? 5? 1 4].
I used the following code to solove this:
bo <- c(3,? 8,? 4,? 6,? 1,? 5)
N <- length(bo)
bt <- rep(0, N)
M <- max(bo)
temp <- bo
? for(i in 1 : N)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? min <- M
? ? ? ? ? ? ? ? i_min <- 0
? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? for(j in 1 : N)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if(min >= temp[j])
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? min <- temp[j]
? ? ? ? ? ? ? ? ? ? ? ? ? i_min <-j
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? bt[i_min] <- i
? ? ? ? ? ? ? ? temp[i_min] <- M+ 1
? ? ? ? ? ? }> bt
[1] 2 6 3 5 1 4
However, the time complexity is O(N2).
When N is larger than 1000000, it takes too much time.
Is there any faster way to fix it?
best
Xueming
xmliu1988 at gmail.com
??? [[alternative HTML version deleted]]
______________________________________________
R-help at r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
William Dunlap
2014-Apr-26 15:35 UTC
[R] Faster way to transform vector [3 8 4 6 1 5] to [2 6 3 5 1 4]
Look into the rank function. If there are duplicated values in the input vector its 'ties' argument says how to deal with them. If there are ties I think your algorithm puts the last one in the first position, e.g., it maps c(101,101,101,102,102) to c(3,2,1,5,4). rank does not include this option, but if that is really what you want to do you can use myRank <- function (x) rev(rank(rev(x), ties = "first")) On Sat, Apr 26, 2014 at 2:54 AM, xmliu1988 at gmail.com <xmliu1988 at gmail.com> wrote:> Hi, > > could anybody help me to find a fast way to fix the following question? > > Given a verctor of length N, for example bo = [3 8 4 6 1 5], > I want to drive a vector whose elements are 1, 2, ..., N and the order of elements is the same as that in verctor bo. > In this example, the result is supposed to be bt = [2 6 3 5 1 4]. > > I used the following code to solove this: > > bo <- c(3, 8, 4, 6, 1, 5) > N <- length(bo) > bt <- rep(0, N) > M <- max(bo) > temp <- bo > for(i in 1 : N) > { > min <- M > i_min <- 0 > > for(j in 1 : N) > { > if(min >= temp[j]) > { > min <- temp[j] > i_min <-j > } > } > bt[i_min] <- i > temp[i_min] <- M+ 1 > } >> bt > [1] 2 6 3 5 1 4 > > However, the time complexity is O(N2). > When N is larger than 1000000, it takes too much time. > Is there any faster way to fix it? > > best > Xueming > > > > xmliu1988 at gmail.com > [[alternative HTML version deleted]] > > ______________________________________________ > R-help at r-project.org mailing list > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide http://www.R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code.-- Bill Dunlap TIBCO Software wdunlap tibco.com
Jorge I Velez
2014-Apr-26 15:41 UTC
[R] Faster way to transform vector [3 8 4 6 1 5] to [2 6 3 5 1 4]
Hi Xueming,
Try
(1:length(bo))[rank(bo)]
In a function the above would be
f <- function(x){
N <- length(x)
(1:N)[rank(x)]
}
f(bo)
# [1] 2 6 3 5 1 4
HTH,
Jorge.-
On Sat, Apr 26, 2014 at 7:54 PM, xmliu1988@gmail.com
<xmliu1988@gmail.com>wrote:
> Hi,
>
> could anybody help me to find a fast way to fix the following question?
>
> Given a verctor of length N, for example bo = [3 8 4 6 1 5],
> I want to drive a vector whose elements are 1, 2, ..., N and the order of
> elements is the same as that in verctor bo.
> In this example, the result is supposed to be bt = [2 6 3 5 1 4].
>
> I used the following code to solove this:
>
> bo <- c(3, 8, 4, 6, 1, 5)
> N <- length(bo)
> bt <- rep(0, N)
> M <- max(bo)
> temp <- bo
> for(i in 1 : N)
> {
> min <- M
> i_min <- 0
>
> for(j in 1 : N)
> {
> if(min >= temp[j])
> {
> min <- temp[j]
> i_min <-j
> }
> }
> bt[i_min] <- i
> temp[i_min] <- M+ 1
> }
> > bt
> [1] 2 6 3 5 1 4
>
> However, the time complexity is O(N2).
> When N is larger than 1000000, it takes too much time.
> Is there any faster way to fix it?
>
> best
> Xueming
>
>
>
> xmliu1988@gmail.com
> [[alternative HTML version deleted]]
>
> ______________________________________________
> R-help@r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>
[[alternative HTML version deleted]]