Найти узкое место в алгоритме слияния Scala

Question

Я изучаю Scala и в качестве отправной точки Я пытаюсь написать алгоритм mergeSort. У меня возникла проблема с исполнением части слияния.

Я знаю, что на этом сайте есть другие реализации, но я хотел бы знать, почему моя работа не работает.

Это мой код:

@tailrec 
    def merge(l1:List[Int], l2:List[Int], acc:List[Int]): List[Int] = { 

     if(l1.isEmpty || l2.isEmpty) l1 ++ l2 ++ acc 
     else if(l1.last> l2.last) merge(l1.init, l2, l1.last :: acc) 
     else merge(l1, l2.init, l2.last :: acc) 
    } 

    val a1 = List(1,4,65,52151) 
    val a2 = List(2,52,124,5251,124125125) 

    println(merge(a1, a2, List())) 

Как вы можете видеть, функцию слияния является хвостовой рекурсией и (если я не ошибается) метода списка, что я использую должна принять постоянное время.

Код получает очень медленный со списком из 100000 элементов.

Answer 1

last и init ужасно дороги в списке: O (N). Эффективными операциями являются head и tail: O (1). Если вы не можете работать с самого начала, переверните списки вверх (O (N), но только один раз, а не на каждой итерации), или отмените вывод в конце, но вам нужно работать в начале списка.

Answer 2

Лучший способ найти узкие места - это профилировать. Я понимаю, что у netbeans есть бесплатный; если вы можете получить jprofiler или yourkit, они очень приятны в использовании. В этом конкретном случае я хотел бы указать, что last и init являются O (n), потому что List является (однократно) связанным списком.