Задача. Merge sort

Реализуйте конкурентное решение merge sort (сортировка слиянием), используя горутины и каналы.

В качестве опорной точки можно взять эту последовательную реализацию:

package main
import "fmt"
func Merge(left, right [] int) [] int{
  merged := make([] int, 0, len(left) + len(right))
  for len(left) > 0 || len(right) > 0{
    if len(left) == 0 {
      return append(merged,right...)
    }else if len(right) == 0 {
      return append(merged,left...)
    }else if left[0] < right[0] {
      merged = append(merged, left[0])
      left = left[1:]
    }else{
      merged = append(merged, right [0])
      right = right[1:]
    }
  }
  return merged
}
func MergeSort(data [] int) [] int {
  if len(data) <= 1 {
    return data
  }
  mid := len(data)/2
  left := MergeSort(data[:mid])
  right := MergeSort(data[mid:])
  return Merge(left,right)
}
func main(){
  data := [] int{9,4,3,6,1,2,10,5,7,8}
  fmt.Printf("%v\n%v\n", data, MergeSort(data))
}

Код с решением будет завтра.

#задача

Ответ на «Merge sort»

package main
import "fmt"
func Merge(left, right [] int) [] int{
  merged := make([] int, 0, len(left) + len(right))
  for len(left) > 0 || len(right) > 0{
    if len(left) == 0 {
      return append(merged,right...)
    }else if len(right) == 0 {
      return append(merged,left...)
    }else if left[0] < right[0] {
      merged = append(merged, left[0])
      left = left[1:]
    }else{
      merged = append(merged, right [0])
      right = right[1:]
    }
  }
  return merged
}
func MergeSort(data [] int) [] int {
  if len(data) <= 1 {
    return data
  }
  done := make(chan bool)
  mid := len(data)/2
  var left [] int
  go func(){
    left = MergeSort(data[:mid])
    done <- true
  }()
  right := MergeSort(data[mid:])
  <-done
  return Merge(left,right)
}
func main(){
  data := [] int{9,4,3,6,1,2,10,5,7,8}
  fmt.Printf("%v\n%v\n", data, MergeSort(data))
}

В начале при сортировке слиянием мы рекурсивно разделяем массив на right и left стороны и на строках 30-34 вызываем MergeSort для обеих сторон.

Теперь нужно сделать так, чтобы Merge(left, right) выполнялась после получения возвращаемых значений от обоих рекурсивных вызовов, то есть и left и right должны обновляться до того, как Merge(left, right) сможет быть выполнена. Для этого на строке 26 мы вводим канал типа bool и отправляем в него true сразу после выполнения left = MergeSort(data[:mid] (строка 32).

Операция <-done блокирует код на строке 35 до инструкции Merge(left,right), чтобы она не продолжилась, пока горутина не завершится. После завершения горутины и получения true в канале done код переходит к инструкции Merge(left, right) на строке 36.

#задача

Вопрос с собеседования. Какие есть способы достать данные из JSON?

Ответ завтра.

#собеседование

Ответ на «Какие есть способы достать данные из JSON?»

Тут можно либо демаршализовать (Unmarshal) JSON и разлить его данные в объект с фиксированной структурой. Либо можно залить данные в пустой интерфейс.

Для всего этого используется json.Unmarshal()

Ответ на «Что такое горутины и зачем они нужны?»

Горутина (goroutine) — это функция, которая выполняется асинхронно. Чтобы запустить горутину нужно лишь написать что-то вроде этого:

go someFunc(args…) {
  //тут действия
  }()

Весит одна горутина около 4кб. Так что, если у вас 4ГБ оперативной памяти, то можно одновременно запустить немало горутин 🙂

Они нужны, если нам параллельно требуется сделать несколько действий. Например, ваш скрипт должен опросить множество сторонних сервисов и поработать с ответом. А что делать, если некоторые из сервисов долго отвечают? Как говорится, семеро одного не ждут! Каждому по горутине, и тогда не придется ждать «отстающих».

Ответ на «Расскажите об ООП в Golang»

Формально оно в Go есть, но не совсем в том виде, в каком оно есть в PHP или Java.

В Go мы создаем структуры (читайте «классы») с определенными полями (свойствами), и далее создаем «экземпляры» этих структур. Методы описываются отдельно, а не внутри структур.

Ответ на «Если в функции есть return, обязательно ли она вернет то, что указано в return?»

Мы привыкли, что обычно, если код внутри функции добрался до return, то на выходе мы получим то, что стоит после return. Но в Go есть интересная особенность: если есть именованный выходной параметр (параметры), то функция вернет последнее его значение, несмотря на то, что написано в return.

package main
import "fmt"

// Основной метод
func main() {
// функция возвращает два значения
m, d := calculator(105, 7)

fmt.Println("105 x 7 = ", m)

fmt.Println("105 / 7 = ", d)
}
// функция с именованными аргументами

func calculator(a, b int) (mul int, div int) {

defer func() {
mul = 95
div = 27
}()

// здесь простое назначение т.к. инициализация произошла выше
//функция вернет именно эти переменные
mul = a * b

div = a / b

// здесь у вас есть ключевое слово return

return 1, 2
}

Функция вернет в итоге: 95 и 27.

Вопрос с собеседования. Что такое ломтик Golang?

Ответ завтра.

#собеседование