БЛОГ НА HUSL


Задача по golang каналы. Помогите понять, правильно ли я понял задание и что не так с решением

Автор вопроса: Петр Иванов

Задание

Вот моё решение, на проверке пишет WA

package main
func main() {
}
func Merge2Channels (f func(int)int , in1 <-chan int, in2 <- chan int, out chan<- int, n int){

    go func(){
        for i := 0; i < n; i++{
        out <-(f(<-in1) + f(<-in2))
        }
    }()

}

Проверял таким способом 

package main
import "fmt"
func main() {
n :=2
in1 := make(chan int,2)
in2 := make(chan int,2)
out := make(chan int)
Merge2Channels (f,in1,in2,out,n)
in1<-4
in2<-5
in1<-3
in2<-6

fmt.Println(<-out)
fmt.Println(<-out)

}
func Merge2Channels (f func(int)int , in1 <-chan int, in2 <- chan int, out chan<- int, n int){

    go func(){
        for i := 0; i < n; i++{
        out <-(f(<-in1) + f(<-in2))
        }
    }()

}
func f (i int) int {
    return (i*i)
}

Что собственно не так? Merge2Channels не блокирует ничего, если каналы буфферизованные, я же не знаю что они там подают. P.S. Если что выглядит не так не судите строго, это мой hello world на golang.


Источник

Ответы (6 шт):

Автор решения: Михаил Чеботарев

Тут все гораздно сложнее.

  1. каналы будут отдавать числа в определенном порядке, и в этом же порядке нам нужно писать в 3ий канал. При этом вычисления над каждой парой имеют разные интервалы: какое-то медленнее, какое-то быстрее.

  2. по 2 корутины при чтении из 2х каналов;

  3. по 2 корутины при вычислении над каждым числом f(x);

  4. накапливание результата в массиве с жестко заданной длиной.

корутина при записи в 3ий канал.

Пункты 2 и 5 не удалось проверить. Локально все работает. Но их лядский сервер на один и тот же (отличались комменты) выдавал:

'/temp/compiling/source' cannot be extracted via extract () /bin/sh ./build.sh

Лучший результат без этих пунктов 2.009 секунды. Почти, но не ОК.

При это пробовал перезапускать точно рабочие решения на Python (Другие задачи) и SQL - когда запускается, когда нет. В общем, очевидно, что неполадки на сервере, уж в прогамме "сложить 2 числа" миддл ошибаться не может.

Сжег 60 итераций. И забил, после того как подтвердилось, что 1 код (даже на python|C++|SQL) выдает разные рузультаты.

→ Ссылка
Автор решения: Eugene Soroko

У меня тоже не вышло выполнить на OK.
Мне удалось воссоздать такие ошибки перечисленные в ТЗ:

  • Блокировку функции (WA + логи)
  • Неверные вычисления (WA + логи)
  • Считывание большего кол-ва значений чем нужно (WA + логи)
  • Считывание меньше (WA + логи)
  • Слижком долгое выполнение (IL)

Пожалуй не удалось только привысить объем памяти..
Но при этом все равно упирался в какую-то ошибку с WA, но с пустыми логами..

Учитывая, что время на решение по сути закончилось вот мои варианты
Самый простой, который проходит IL

import "sync"

func Merge2Channels(f func(int) int, in1 <-chan int, in2 <-chan int, out chan<- int, n int) {
    go func() {
        var wg sync.WaitGroup
        var x1, x2 int
        for i := 0; i < n; i++ {
            wg.Add(2)
            go func() {
                defer wg.Done()
                x1 = f(<-in1)
            }()
            go func() {
                defer wg.Done()
                x2 = f(<-in2)
            }()
            wg.Wait()
            out <- x1 + x2
        }
    }()
}
→ Ссылка
Автор решения: Aleksei Pershinov

Интересно, топику несколько лет. А я только вчера решал эту задачу. Сегодня пошел искать новые задачи по каналам, чтобы попрактиковаться - наткнулся на этот топик.

На всякий, приложу свои размышления и решение.

  1. В данном случае нам необходимо распараллелить запуск fn() так как именно эта функция может выполняться N время по условиям задачи.
  2. Таким образом нам нужно параллельно вычитать значения из каналов, и также параллельно применить к ним вычисления из fn()

Прежде чем смотреть решение, рекомендую попробовать продумать самостоятельно.

Решение Намеренно оставил все так, как решил изначально. Можно улучшить.

func merge2Channels(fn func(int) int, in1 <-chan int, in2 <-chan int, out chan<- int, n int) {
    
    type t struct {
        i int
        n int
    }

    ch1 := make(chan t)
    ch2 := make(chan t)
    
    for i := 0; i < n; i ++ {
        go func(num int){
            x1 := <- in1
            ch1 <- t{i: num, n: fn(x1)}
        }(i)
    }
    for i := 0; i < n; i ++ {
        go func(num int){
            x2 := <- in2
            ch2 <- t{i: num, n: fn(x2)}
        }(i)
    }
    

    go func(){
        x1sl := make([]t, 0, n)
        x2sl := make([]t, 0, n)
    
        for i := 0; i < n; i ++{
            x1sl = append(x1sl, <- ch1)
            x2sl = append(x2sl, <- ch2)
        }
        
        for _, x1 := range x1sl {
            for _, x2 := range x2sl {
                if x1.i == x2.i {
                    out <- x1.n + x2.n
                    break
                }
            }
        }
    }()
}

Passed. OK. Время работы: 5.202761ms.

→ Ссылка
Автор решения: Andrey Zloy

Можно обойтись select'ом

func Merge2Channels(
    f func(int) int, in1 <-chan int, in2 <-chan int, out chan<- int, n int) {
    go func() {
        for range n {
            in1, in2 := in1, in2
            var val1, val2 int
            for range 2 {
                select {
                case val1 = <-in1:
                    in1 = nil
                case val2 = <-in2:
                    in2 = nil
                }
            }
            out <- f(val1) + f(val2)
        }
    }()
}
→ Ссылка
Автор решения: Pak Uula

Я думаю, эта задача на асинхронное выполнение функции f.

В решении, предоставленным топик-стартером, функции f вызываются последовательно:

  • прочитать аргументы
  • вызывать f для первого
  • вызывать f для второго
  • повторить ...

В результате, если f выполняется секунду, то на выдачу каждого результата потребуется 2 секунды, а всего на "слияние" двух каналов из примера уйдёт 4 секунды.

Если же функцию f вызывать в отдельной горутине, то на всё про всё уйдёт 1 секунда, так как 4 экземпляра f будут ждать одновременно.

Вот как это можно сделать:

func Merge2Channels(
    f func(int) int,
    in1 <-chan int, 
    in2 <-chan int,
    out chan<- int,
    n int) {
    resultChannels := make([]chan int, n)
    for i := range resultChannels {
        resultChannels[i] = make(chan int, 1)
    }
    go resultWriter(out, resultChannels...)

    go func() {
        mergeWorker(f, in1, in2, resultChannels...)
    }()
}

// Функция mergeWorker читает значения из in1 и in2 и асинхронно вызывает
// функцию merge для прочитанных значений. Она создает n горутин, каждая из
// которых асинхронно выполняет функцию f в отдельных горутинах и пишет
// результаты в соответствующие каналы resultChannels.
//
// Параметры:
//   - f: функция, которую нужно применить к значениям из in1 и in2.
//   - in1, in2: каналы, из которых будут прочитаны значения.
//   - resultChannels: каналы, в которые будут отправлены результаты
//     выполнения функции f для каждой пары значений из in1 и in2.
func mergeWorker(
    f func(int) int,
    in1, in2 <-chan int,
    resultChannels ...chan int) {
    for _, ch := range resultChannels {
        x1 := <-in1
        x2 := <-in2
        go merge(f, x1, x2, ch)
    }
}

// Функция resultWriter читает результаты из каналов и записывает их в out в
// порядке перечисления каналов в mergeWorker. Это обеспечивает,
// что результаты будут записаны в out в том порядке,
// в котором были прочитаны x1 и x2 из in1 и in2,
// несмотря на задержки в выполнении функции f.
//
// Параметры:
//   - out: канал, в который будут отправлены результаты.
//   - resultChannels: каналы, из которых будут читаться результаты
//     выполнения функции f.
func resultWriter(out chan<- int, resultChannels ...chan int) {
    for _, ch := range resultChannels {
        result := <-ch
        // Отправляем результат в out канал
        out <- result
    }
}

// Функция merge асинхронно вызывает функцию f для двух значений x1 и x2,
// суммирует результаты и отправляет их в канал result_ch. Это позволяет
// избежать задержек в Merge2Channels, так как f может выполняться долго.
//
// Параметры:
//   - f: функция, которую нужно применить к значениям x1 и x2.
//   - x1, x2: значения, к которым применяется функция f.
//   - result_ch: канал, в который отправляется результат выполнения f(x1) + f(x2).
func merge(f func(int) int, x1, x2 int, result_ch chan<- int) {
    // Каналы для результатов вызова функции f
    ch1 := make(chan int, 1)
    ch2 := make(chan int, 1)
    // Запускаем асинхронные вызовы функции f для x1 и x2
    go callF(f, x1, ch1)
    go callF(f, x2, ch2)
    result1 := <-ch1
    result2 := <-ch2

    result := result1 + result2
    // Отправляем результат в канал
    result_ch <- result
}

// Функция callF выполняет функцию f и отправляет результат в канал f_out. 
// Это позволяет выполнять f параллельно для разных значений x.
//
// Параметры:
//   - f: функция, которую нужно выполнить.
//   - x: значение, к которому применяется функция f.
//   - f_out: канал, в который отправляется результат выполнения функции f.
func callF(f func(int) int, x int, f_out chan<- int) {
    f_out <- f(x)
}

Замер времени выполнения и сравнение с функцией из поста ТС

func main() {
    fmt.Println("Merge2Channels с асинхронным выполнением функции f:")
    doIt(Merge2Channels)
    fmt.Println("Merge2Channels с последовательным выполнением функции f:")
    doIt(Merge2ChannelsNaive)
}

func doIt(
    mergeFunction func(
        f func(int) int, in1 <-chan int, in2 <-chan int, out chan<- int, n int)) {
    n := 2
    in1 := make(chan int, 2)
    in2 := make(chan int, 2)
    out := make(chan int)
    mergeFunction(f, in1, in2, out, n)
    start := time.Now()
    in1 <- 4
    in2 <- 5
    in1 <- 3
    in2 <- 6
    fmt.Println(<-out)
    fmt.Println(<-out)
    elapsed := time.Since(start)
    fmt.Printf("Execution time: %s\n", elapsed)
}

func f(i int) int {
    time.Sleep(time.Second) // Симуляция долгой работы функции
    return (i * i)
}

func Merge2ChannelsNaive(
    f func(int) int, in1 <-chan int, in2 <-chan int, out chan<- int, n int) {

    go func() {
        for i := 0; i < n; i++ {
            out <- (f(<-in1) + f(<-in2))
        }
    }()

}

Результат

Merge2Channels с асинхронным выполнением функции f:
41
45
Execution time: 1.000566627s
Merge2Channels с последовательным выполнением функции f:
41
45
Execution time: 4.002539125s
→ Ссылка
Автор решения: Vitaly

Я тоже ошибок не увидел.

Странный момент, но у меня этот код сработал.

В ответ я получил:

41
45

Как и должно быть

4 * 4 + 5 * 5 = 41

3 * 3 + 6 * 6 = 45

→ Ссылка

licensed under cc by-sa 3.0 with attribution.