算法在实际业务场景中并非完全无用

发表于

从事业务开发的同学经常会抱怨经常面试要刷算法，实际上平常的开发99%以上的事情都不会用到。
实际情况确实是这样。平常在写业务逻辑代码时，几乎完全不需要。
当然有些技术原理在背八股文的时候，懂一点算法能帮助你更好的理解。
而有些特殊业务场景，懂一些算法，确实能帮助你很好的解决问题。
下面举两个业务中产品提出的需求作为例子，简单描述如何利用算法有效解决。

一、从题库（50道题）中随机抽出10道题,且不能重复

  • 最简单的思路：

    • 循环10次，每次取50以内的随机数
    • 创建一个hashmap，判断生成的随机数是否在map存在，存在则重新生成
    • 这个方法的缺点时，极端情况下，会多次生成重复的随机数导致要不断重新生成

  • 经过一番思考，我设计了一下从m个数中取n个数的算法(m>n), 保证算法只会循环n次

  • 那时我还是使用Java进行开发

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int[] randomArr(int m, int n) {

    if (m < n) {
        return new int[]{};
    }
    int[] result = new int[n];
    int[] data = new int[m];

    for (int i = 0; i < m; i++) {
        data[i] = i;
    }

    int end = m;

    for (int j = 0; j < n; j++) {
        int y = ThreadLocalRandom.current().nextInt(end);
        result[j] = data[y];
        data[y] = data[end - 1];
        data[end - 1] = result[j];
        end--;
    }

    return result;
}
  • 后面我才发现原来这个算法叫 洗牌算法（Shuffle Algorithm），或者叫随机乱置算法。

通过搜索关键字匹配对应的标签id

  • 产品提供了400个标签名称以及对应的标签id，希望能通过搜索的方式找到最相似的标签id，希望能支持模糊匹配

  • 一般思路：

    • 方案1:
      1. 将400条数据一次性加载的程序内存
      2. 遍历数据400条使用字符串的contains方法，找到第一条匹配数据就跳出，否则继续
    • 方案2:
      1. 直接将数据导入到ES搜索引擎，利用ES自带的分词等搜索功能
      2. 通过调ES，搜索得到标签id

  • 简单分析方案：

    • 方案1，性能太差，极端情况需要遍历所有数据
    • 方案2，需要新搭建ES集群，实现代价比较高

  • 经过一番思考，以及从产品本身实际需求上出发，我涉及出以下的方案

    1. 将数据的标签名字使用中文分词库gse进行分词
    2. 将分词和对应的标签数据，构建前缀匹配树
    3. 当搜索时，使用提前构建好的前缀匹配树，即可快速找到对应的标签id

  • 这时我已经转使用Go来开发了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

type TrieNode struct {
	children map[rune]*TrieNode
	isEnd    bool
}

func NewTrieNode() *TrieNode {
	return &TrieNode{
		children: make(map[rune]*TrieNode),
		isEnd:    false,
	}
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{
		root: NewTrieNode(),
	}
}

func (t *Trie) Insert(word string) {
	node := t.root
	for _, char := range word {
		if _, ok := node.children[char]; !ok {
			node.children[char] = NewTrieNode()
		}
		node = node.children[char]
	}
	node.isEnd = true
}

func (t *Trie) Search(word string) bool {
	node := t.root
	for _, char := range word {
		if _, ok := node.children[char]; !ok {
			return false
		}
		node = node.children[char]
	}
	return node.isEnd
}

func (t *Trie) FuzzySearch(prefix string) []string {
	var result []string
	node := t.root
	for _, char := range prefix {
		if _, ok := node.children[char]; !ok {
			return result
		}
		node = node.children[char]
	}
	t.collectWords(node, prefix, &result)
	return result
}

func (t *Trie) collectWords(node *TrieNode, prefix string, result *[]string) {
	if node.isEnd {
		*result = append(*result, prefix)
	}

	for char, child := range node.children {
		t.collectWords(child, prefix+string(char), result)
	}
}
  • 这个算法就是经典的Trie字典树（前缀树），如果我之前没了解过这些算法，可能一时间没那么快能想到用这个方式高效完成这个需求。

总结

  • 了解一些算法，在实际业务开发，有时候也能运用到。
  • 另外，现在处于AI时代，即时不了解算法，善于组织语言和上下文，向AI提问，基本它也能引导你找到合适的解决方案。