Оптимизация сортировки во время цикла

Я работаю над изменением проблемы коммивояжера. Решение, которое я пытаюсь реализовать, заключается в том, чтобы загрузить мой автомобиль как можно ближе к максимальному, так как обратные поездки в значительной степени дороги.Оптимизация сортировки во время цикла

У меня есть большие наборы данных в следующем формате:

pkgid Latitude Longitude Weight 
42127 8.205561907 34.54574863 37.0660242 
42069 7.640153828 34.03634169 31.91148072 
96632 7.700233671 33.85385033 24.27309403 
93160 7.756960678 35.36007723 22.3526782 
39075 6.881522479 34.19903152 19.56993506 
62579 7.622385316 33.78590124 16.7793145 
93784 7.523606197 35.32735063 16.18484202 
81204 7.597161645 33.81316073 11.54433538

Моего решения принять дальнюю точку на юг и захватить близлежащие сосед, пока мой автомобиль не будет заполнен. У меня есть фрагмент кода, который работает, но очень медленный (секунды за цикл). Я мог бы использовать kmeans или аналогичный метод, но нет хорошего способа гарантировать полную загрузку или отсечение кластеризации с метрикой (что я знаю). Поэтому я написал свой собственный.

##NN Algorithm 
pkg <- data.frame(fread("muh_data")) 
pkg$TripId=0 
NN<-data.frame(setorder(pkg,Latitude)) 
loc<-1 
weight<-0 
current_point<-c(NN[1,3],NN[1,2]) 
TripID=1 

while (dim(NN)[1]>0) 
{ 
    while ((weight<1000)&(dim(NN)[1]>0)){ 
    NN<-NN[-c(loc),] 
    if(dim(NN)[1]==0) 
    {break} 
    NN$NN<-distHaversine(current_point,cbind(NN$Longitude,NN$Latitude)) 
    loc<-which.min(NN$NN) 
    current_point=c(NN[loc,3],NN[loc,2]) 
    whichpkg<-NN[loc,1] 
    if ((weight+pkg[loc,4]>1000)|(dim(NN)[1])==0){ 
    break} 
    weight=weight+pkg[loc,4] 
    pkg[pkg$pkgid==whichpkg,5]<-TripID 
    } 
print(TripID) ##just a visual check where I am at--should end at ~3500 
TripID=TripID+1 
weight=0 
loc<-1 
}

Любые подсказки для ускорения этого?

источник

2015-12-13 RDS

R очень полезен, но не обязательно для выполнения таких пользовательских алгоритмов. Я бы написал его на C или C++ и выложил на него из R. Кроме того, проблемы с типами коммивояжеров нелегко найти оптимальные решения, но * хорошие * решения не трудно получить. –

Сначала используйте профайлер (Rprof), чтобы найти время, в которое проводится время. Затем попробуйте заменить dataframes на матрицы - при доступе к данным очень медленно. то вы можете знать, где сосредоточиться.

источник

2015-12-13 10:21:29

Это похоже на distHaversine, и записи потребляют немного времени. Как один из предложенных комментариев, возможно, пора сделать некоторую оптимизацию - C. Rprof оказывается приятным, сделать это самостоятельно. Переход к матрицам не сэкономил много времени, но, по крайней мере, это помогает мне пик под капотом. – RDS

Оптимизация сортировки во время цикла

ответ

Смежные вопросы