В моем граф-пакете (как в теории графов узлы, соединенные ребрами) у меня есть вектор, указывающий для каждого ребра узел происхождения from, вектор, указывающий для каждого ребра узел назначения to и вектор, обозначающий кривую каждого ребра curve.
По умолчанию я хочу, чтобы ребра имели кривую 0, если между двумя узлами имеется только одно ребро, и кривую 0,2, если между двумя узлами есть два ребра. Код, который я сейчас использую, является циклом for, и он довольно медленный:
curve <- rep(0,5)
from<-c(1,2,3,3,2)
to<-c(2,3,4,2,1)
for (i in 1:length(from))
{
if (any(from==to[i] & to==from[i]))
{
curve[i]=0.2
}
}
Так что в основном я ищу каждое ребро (один индекс в from и один в to), если есть какие-либо другие пары в from и to, которые используют те же узлы (числа).
Я ищу две вещи:
- Способ определения, есть ли какая-либо пара узлов, между которыми есть два ребра (поэтому я могу пропустить цикл, если нет)
- Способ ускорить этот цикл
#
EDIT:
Чтобы сделать это abit более понятным, приведем еще один пример:
from <- c(4L, 6L, 7L, 8L, 1L, 9L, 5L, 1L, 2L, 1L, 10L, 2L, 6L, 7L, 10L, 4L, 9L)
to <- c(1L, 1L, 1L, 2L, 3L, 3L, 4L, 5L, 6L, 7L, 7L, 8L, 8L, 8L, 8L, 10L, 10L)
cbind(from,to)
from to
[1,] 4 1
[2,] 6 1
[3,] 7 1
[4,] 8 2
[5,] 1 3
[6,] 9 3
[7,] 5 4
[8,] 1 5
[9,] 2 6
[10,] 1 7
[11,] 10 7
[12,] 2 8
[13,] 6 8
[14,] 7 8
[15,] 10 8
[16,] 4 10
[17,] 9 10
В этих двух векторах пара 3 идентична паре 10 (оба 1 и 7 в разных порядках), а пары 4 и 12 идентичны (оба 2 и 8). Поэтому я бы хотел, чтобы curve стал:
[1,] 0.0
[2,] 0.0
[3,] 0.2
[4,] 0.2
[5,] 0.0
[6,] 0.0
[7,] 0.0
[8,] 0.0
[9,] 0.0
[10,] 0.2
[11,] 0.0
[12,] 0.2
[13,] 0.0
[14,] 0.0
[15,] 0.0
[16,] 0.0
[17,] 0.0
(как вектор, я дважды транспонировал, чтобы получить номера строк).
Решение
from <- c(4L, 6L, 7L, 8L, 1L, 9L, 5L, 1L, 2L, 1L, 10L, 2L, 6L, 7L, 10L, 4L, 9L)
to <- c(1L, 1L, 1L, 2L, 3L, 3L, 4L, 5L, 6L, 7L, 7L, 8L, 8L, 8L, 8L, 10L, 10L)
srt <- apply(cbind(from,to),1,sort)
dub <- duplicated(t(srt))|duplicated(t(srt),fromLast=T)
curve <- ifelse(dub,0.2,0)
Сравнительные решения
Вот некоторые примеры различных решений
> # for-loop
> system.time(
+ {
+ curve <- rep(0,5)
+ for (i in 1:length(from))
+ {
+ if (any(from==to[i] & to==from[i]))
+ {
+ curve[i]=0.2
+
+ }
+ }
+ })
user system elapsed
171.49 0.05 171.98
from <- sample(1:1000,100000,T)
> to <- sample(1:1000,100000,T)
>
> # My solution:
> system.time(
+ {
+ srt <- apply(cbind(from,to),1,sort)
+ dub <- duplicated(t(srt))|duplicated(t(srt),fromLast=T)
+ curve <- ifelse(dub,0.2,0)
+ })
user system elapsed
16.92 0.00 16.94
>
>
> # Marek 1:
> system.time(
+ {
+ srt <- cbind(pmin(from,to), pmax(from,to) )
+ dub <- duplicated(srt)|duplicated(srt,fromLast=T)
+ curve <- ifelse(dub,0.2,0)
+ })
user system elapsed
2.43 0.00 2.43
>
> # Marek 2:
> system.time(
+ {
+ srt <- cbind(ifelse(from>to,to,from),ifelse(from>to,from,to))
+ dub <- duplicated(srt)|duplicated(srt,fromLast=T)
+ curve <- ifelse(dub,0.2,0)
+ })
user system elapsed
2.67 0.00 2.70
>
> # Maiasaura:
> library(plyr)
>
> system.time(
+ {
+ data=data.frame(cbind(id=1:length(from),from,to))
+ data=ddply(data, .(id), transform, f1=min(from,to),f2=max(from,to))
+ curved=data.frame(data[which(duplicated(data[,4:5])==TRUE),],value=0.2)
+ result=join(data[,4:5],curved[,4:6],by=intersect(names(data)[4:5],names(curved)[4:6]))
+ result$value[which(is.na(result$value))]=0
+ result=data.frame(from,to,curve=result$value)
+ })
user system elapsed
103.43 0.11 103.95
> # Marek 1 + Joshua
> > system.time(
> + {
> + srt <- cbind(pmin(from,to), pmax(from,to) )
> + curve <- ifelse(ave(srt[,1], srt[,1], srt[,2], FUN=length) > 1,
> 0.2, 0)
> + }) user system elapsed
> 7.26 0.00 7.25
, что дает самое быстрое решение:
srt <- cbind(pmin(from,to), pmax(from,to) )
dub <- duplicated(srt)|duplicated(srt,fromLast=T)
curve <- ifelse(dub,0.2,0)