Как искать огромный кусок карт [строка] строка одновременно

Question

Мне нужно найти огромный slicemaps[string]string. Моя мысль заключалась в том, что это хороший шанс для канала go и пойти в рутины.

План состоит в том, чтобы разделить срез на части и отправить их параллельно. Но я был шокирован тем, что моя параллельная версия пришла в тупик, в то время как поиск всего фрагмента сделал трюк.

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

//Search for a giving term 
//This function gets the data passed which will need to be search 
//and the search term and it will return the matched maps 
// the data is pretty simply the map contains { key: andSomeText } 
func Search(data []map[string]string, term string) []map[string]string { 

    set := []map[string]string{} 

    for _, v := range data { 
     if v["key"] == term { 

      set = append(set, v) 
     } 

    } 
    return set 

} 

Так что это очень хорошо подходит для поиска фрагментов карт для данного SearchTerm.

Теперь я подумал, что если мой кусочек будет иметь как 20K записей, я хотел бы сделать поиск в параллельном

// All searches all records concurrently 
// Has the same function signature as the the search function 
// but the main task is to fan out the slice in 5 parts and search 
// in parallel 
func All(data []map[string]string, term string) []map[string]string { 
    countOfSlices := 5 

    part := len(data)/countOfSlices 

    fmt.Printf("Size of the data:%v\n", len(data)) 
    fmt.Printf("Fragemnt Size:%v\n", part) 

    timeout := time.After(60000 * time.Millisecond) 

    c := make(chan []map[string]string) 

    for i := 0; i < countOfSlices; i++ { 
     // Fragments of the array passed on to the search method 
     go func() { c <- Search(data[(part*i):(part*(i+1))], term) }() 

    } 

    result := []map[string]string{} 

    for i := 0; i < part-1; i++ { 
     select { 
     case records := <-c: 
      result = append(result, records...) 
     case <-timeout: 
      fmt.Println("timed out!") 
      return result 
     } 
    } 
    return result 
} 

Вот мои тесты:

У меня есть функция для создания моих тестовых данных и 2 теста.

func GenerateTestData(search string) ([]map[string]string, int) { 
    rand.Seed(time.Now().UTC().UnixNano()) 
    strin := []string{"String One", "This", "String Two", "String Three", "String Four", "String Five"} 
    var matchCount int 
    numOfRecords := 20000 
    set := []map[string]string{} 
    for i := 0; i < numOfRecords; i++ { 
     p := rand.Intn(len(strin)) 
     s := strin[p] 
     if s == search { 
      matchCount++ 
     } 
     set = append(set, map[string]string{"key": s}) 
    } 
    return set, matchCount 
} 

2 испытаний: первый раз пересекает срез и второй поиск в параллельном

func TestSearchItem(t *testing.T) { 

    tests := []struct { 
     InSearchTerm string 
     Fn   func(data []map[string]string, term string) []map[string]string 
    }{ 
     { 
      InSearchTerm: "This", 
      Fn:   Search, 
     }, 
     {InSearchTerm: "This", 
      Fn: All, 
     }, 
    } 

    for i, test := range tests { 

     startTime := time.Now() 
     data, expectedMatchCount := GenerateTestData(test.InSearchTerm) 
     result := test.Fn(data, test.InSearchTerm) 

     fmt.Printf("Test: [%v]:\nTime: %v \n\n", i+1, time.Since(startTime)) 
     assert.Equal(t, len(result), expectedMatchCount, "expected: %v to be: %v", len(result), expectedMatchCount) 

    } 
} 

Было бы здорово, если бы кто-то может объяснить мне, почему мой параллельный код так медленно? Что не так с кодом и чего я здесь не хватает, а также тем, что рекомендуемым способом было бы поиск огромных фрагментов в памяти 50K +.

Answer 1

Это похоже на простое опечатку. Проблема заключается в том, что вы делите свой первоначальный большой кусок на 5 частей (countOfSlices), и вы правильно запустить 5 goroutines искать каждую часть:

for i := 0; i < countOfSlices; i++ { 
    // Fragments of the array passed on to the search method 
    go func() { c <- Search(data[(part*i):(part*(i+1))], term) }() 

} 

Это означает, что вы должны ожидать результатов, но вы не знаете , Вы ожидаете 4000-1 результаты:

for i := 0; i < part-1; i++ { 
    select { 
    case records := <-c: 
     result = append(result, records...) 
    case <-timeout: 
     fmt.Println("timed out!") 
     return result 
    } 
} 

Очевидно, что если вы только начали 5 goroutines, каждый из которых поставляет 1 один результат, можно только ожидать, так как многие (5). И так как ваш цикл ждет гораздо больше (что никогда не придет), он истекает так, как ожидалось.

Измените условие к этому:

for i := 0; i < countOfSlices; i++ { 
    // ... 
} 

Answer 2

Есть две проблемы, - как icza заметки, которые вы никогда не закончите выбор, как вам нужно использовать countOfSlices, а затем и ваш вызов Поиск не получите вам данные так как вам нужно выделить это, прежде чем вызывать функцию fun(), поэтому выделите срез снаружи и передайте его.

Возможно, вы все равно не уверены, что для выполнения этой конкретной работы параллельно с такими простыми данными (возможно, с более сложными данными на машине с большим количеством ядер было бы целесообразно)?

Убедитесь, что при тестировании, которое вы пытаетесь поменять порядок ваших тестовых прогонов, вы можете быть удивлены результатами!Также, возможно, попробуйте инструменты для сравнения, имеющиеся в тестовом пакете, который много раз запускает ваш код для вас и усредняет результаты, это может помочь вам лучше понять, ускоряет ли разветвление.

Answer 3

Параллельность - это не параллельность. Go - это массовый параллельный язык, а не параллельный. Даже используя многоядерную машину, вы будете платить за обмен данными между процессорами при обращении к общему срезу в потоках вычислений. Например, вы можете использовать параллельный поиск только для первого совпадения. Или делать что-то с результатами (скажем, печатать их или писать в какой-либо Writer или сортировать) пока продолжить поиск.

func Search(data []map[string]string, term string, ch chan map[string]string) { 
    for _, v := range data { 
     if v["key"] == term { 
      ch <- v 
     } 
    } 
} 
func main(){ 
... 
    go search(datapart1, term, ch) 
    go search(datapart2, term, ch) 
    go search(datapart3, term, ch) 
... 
    for vv := range ch{ 
     fmt.Println(vv) //do something with match concurrently 
    } 
... 
} 

Рекомендуемый способ поиска огромного фрагмента состоял в том, чтобы сортировать его или создавать двоичное дерево. Магии нет.