Найти категории, в которых есть похожие продукты - Низкая эффективность - Go - PullRequest
Новая
       82

Найти категории, в которых есть похожие продукты - Низкая эффективность - Go

1 голос
/ 02 мая 2020

Здравствуйте, извините, мой английский sh

У меня есть список категорий и продуктов, связанных с каждой категорией

cats = [cat1, cat2, cat3]

prod = {
 cat1 = [a, b, c]
 cat2 = [d, e, c]
 cat3 = [z, x, w]
}

Что я хочу 

{
    group1: [cat1, cat2]
    group2: [cat3]
}

Мне нужно сгруппировать категории, которые разделяют некоторые из ваших продуктов

У меня все работает, но у меня есть 400,000 категории, это не хорошо, чтобы сделать две петли из этого количества. Мой алгоритм занимает 4 дня до завершения sh

Я только начал с golang, кто-нибудь есть идеи, как решить эту проблему? Спасибо

  • Группы могут быть любого размера
  • Количество продуктов варьируется между категориями
  • Процент сходства может измениться 
func main() {

    cats, prod := getDataDB()

    for _, cat1 := range cats {

        for _, cat2 := range cats {

            result := percentageSimilarity(prod[cat1], prod[cat2])

            if result > 50{
                // save group
            }

        }

    }

}

func percentageSimilarity(a, b []string) int {

    sum := 0
    percentage := 0

    if len(a) > len(b) {

        for _, key := range a {

            if contains(b, key) {
                sum++
            }

        }

        percentage = sum * 100 / len(b)

    } else {

        for _, key := range b {

            if contains(a, key) {
                sum++
            }

        }

        percentage = sum * 100 / len(a)

    }

    return percentage

}

func contains(s []string, e string) bool {
    for _, a := range s {
        if a == e {
            return true
        }
    }
    return false
}

1 Ответ

1 голос
/ 02 мая 2020

Во-первых, сортируйте свои категории от наименьшего количества продуктов к большинству.

Затем создайте карту из продукта в массив категорий, в котором содержится этот продукт.

Теперь сделать что-то вроде этого: 

for each category
   create empty category_shared_products map from category to count of shared products
   for each product
      for each other_category containing that product
          add/increment category_shared_products[other_category]
   decide what to merge this category into (if anything)

Есть много деталей, чтобы получить право. Но теперь вместо того, чтобы рассматривать каждую пару категорий, мы рассматриваем только пары категорий, которые на самом деле имеют общие продукты.

...