快捷導(dǎo)航

如何使用Go語言實(shí)現(xiàn)基于泛型的Jaccard相似度算法

更新時(shí)間：2024年08月06日 11:41:27 作者：Python私教

這篇文章主要介紹了如何使用Go語言實(shí)現(xiàn)基于泛型的Jaccard相似度算法,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友參考下吧

基本原理

跳表：

jaccard相似度：

jaccard相似度的代碼實(shí)現(xiàn)：

時(shí)間復(fù)雜度分析：

快速jaccard算法：

代碼實(shí)現(xiàn)，這個(gè)要求兩個(gè)集合都是有序的：

Jaccard相似度算法的基本實(shí)現(xiàn)

算法：

package zdpgo_algorithm
// Jaccard 計(jì)算兩個(gè)數(shù)組之間的Jaccard相似度
// @param arr1 數(shù)組1
// @param arr2 數(shù)組2
// @return float64 相似度
func Jaccard[T Number](arr1 []T, arr2 []T) float64 {
	// 邊界情況
	if len(arr1) == 0 || len(arr2) == 0 {
		return 0
	}
	// 將兩個(gè)數(shù)組轉(zhuǎn)換為字典
	m1 := make(map[T]struct{}, len(arr1))
	m2 := make(map[T]struct{}, len(arr2))
	for _, v := range arr1 {
		m1[v] = struct{}{}
	}
	for _, v := range arr2 {
		m2[v] = struct{}{}
	}
	// 計(jì)算交集的元素個(gè)數(shù)
	var count float64
	for k, _ := range m1 {
		if _, ok := m2[k]; ok {
			count++
		}
	}
	// 使用算法公式計(jì)算相似度
	// 交集個(gè)數(shù) / (集合1個(gè)數(shù) + 集合2個(gè)數(shù) - 交集個(gè)數(shù))
	// 由于結(jié)果是浮點(diǎn)數(shù)類型，需要手動(dòng)將結(jié)果轉(zhuǎn)換為浮點(diǎn)數(shù)類型
	return count / float64(len(arr1)+len(arr2)-int(count))
}

基本的測試代碼：

package zdpgo_algorithm_test
import (
	"github.com/zhangdapeng520/zdpgo_algorithm"
	"testing"
)
func TestJaccard_Basic(t *testing.T) {
	arr1 := []int{1, 2, 3, 4, 5}
	arr2 := []int{4, 5, 6, 7}
	t.Log(zdpgo_algorithm.Jaccard(arr1, arr2))
}

基于有序數(shù)組的Jaccard相似度算法實(shí)現(xiàn)

算法：

// JaccardSorted 用于兩個(gè)有序數(shù)組的快速Jaccard相似度算法
// 時(shí)間復(fù)雜度：O(n)
// @param arr1 數(shù)組1，要求是有序的
// @param arr2 數(shù)組2，要求是有序的
// @return float64 相似度
func JaccardSorted[T Number](arr1 []T, arr2 []T) float64 {
	if len(arr1) == 0 || len(arr2) == 0 {
		return 0
	}
	// 求交集的個(gè)數(shù)
	count := 0
	for i, j := 0, 0; i < len(arr1) && j < len(arr2); {
		// 兩個(gè)有序的數(shù)組，只有其中的某個(gè)片段是連續(xù)相同的
		if arr1[i] == arr2[j] {
			// 這種情況說明重疊的部分已經(jīng)出現(xiàn)了
			count++
			i++
			j++
		} else if arr1[i] < arr2[j] {
			// 這種情況說明重疊的部分在arr1的后面，讓arr1的索引往后遞增
			i++
		} else {
			// 這種情況說明重疊的部分在arr2的后面，讓arr2的索引往后遞增
			j++
		}
	}
	// 計(jì)算相似度
	return float64(count) / float64(len(arr1)+len(arr2)-count)
}

測試代碼：

func TestJaccardSorted_Basic(t *testing.T) {
	arr1 := []int{1, 2, 3, 4, 5}
	arr2 := []int{4, 5, 6, 7}
	t.Log(zdpgo_algorithm.JaccardSorted(arr1, arr2))
}

到此這篇關(guān)于如何使用Go語言實(shí)現(xiàn)基于泛型的Jaccard相似度算法的文章就介紹到這了,更多相關(guān)Go語言Jaccard相似度算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: