Доброго времени суток дамы и господа. Героически прохожу курсы с курсеры «Algorithms: Design and Analysis», для прохождения применяю scala. Тут достаточно много людей, проходивших этот самый курс, которые писали код заданий в функциональном стиле. Посему этим героям вопрос: как, блин?
Для тех кто не в курсе, поясню: в курсах есть задания из разряда 1) вот вам входные данные, подсчитайте результат. 2) а теперь все то же самое, только входных данных будет очень много.
И вот когда входных данных становится очень много, я смело выкидываю все эти List, map, flatten и иммутабельность, и заменяю на циклы, массивы и мутабельные данные, чтобы не состариться, пока моя реализация алгоритма чего-то там считает.
Из последнего: сколько кластеров в результате k-clustering будет, при условии что минимальное расстояние между кластерами 3.
Ну я и бахнул вот
val COST = 3
for(i<-Range(0,N)){
for(j<-Range(i,N)){
if(i!=j){
var dif = insane(i).getDif(insane(j))
if(dif<COST) {
insane(i).merge(insane(j))
}
}
}
}
где megre и getParent
def getParent = {
var ret:Node = parent
while(!(ret.parent eq ret)){
ret = ret.parent
}
ret
}
def merge(an:Node){
if(!(an.getParent eq this.getParent))
an.getParent.parent = this
}
Ну и как это должно выглядеть в функциональном стиле, чтобы быстро было достаточно? И литературы мне, господа просветленные.
