险峰风景
0%

Posted on Edited on In

标注类

边界排列法

布局类

栅格化法

解决类似喷淋排布的问题

布线类

A-Star 算法

可以有效解决单线路由的问题，可以针对cost公式做一些改进适应更复杂的一些场景

参考资料：http://theory.stanford.edu/~amitp/GameProgramming/

三角剖分

可以将问题规模减少一个量级，得到拓扑结构

轮廓排序配对

适用于：起点集在集中区域，所有点都在轮廓上或者可以映射到轮廓上

最小生成树

基于实际路径及其cost构建最小生成树

以及运筹优化算法（如果可以定义目标及cost的话）

Posted on Edited on In

pytest 上手比较简单.

环境

Python

最好在工作目录建个虚拟环境:

1
2
python -m venv venv
source venv/bin/activate

pytest

安装

1
pip install pytest

资源

文档

在线文档
PDF
想要运行示例,看在线文档第一页就行.
想要系统学习,个人感觉看PDF文档比较好.

帮助

1
pytest --help

可以看到所有的命令行参数及输入输出控制.
其中有一个比较重要的参数可以详细看看:

1
2
3
4
5
6
7
8
9
10
11
12
13
general:
  -k EXPRESSION         only run tests which match the given substring expression. An
                        expression is a python evaluatable expression where all names
                        are substring-matched against test names and their parent
                        classes. Example: -k 'test_method or test_other' matches all
                        test functions and classes whose name contains 'test_method'
                        or 'test_other', while -k 'not test_method' matches those
                        that don't contain 'test_method' in their names. -k 'not
                        test_method and not test_other' will eliminate the matches.
                        Additionally keywords are matched to classes and functions
                        containing extra names in their 'extra_keyword_matches' set,
                        as well as functions which have names assigned directly to
                        them. The matching is case-insensitive.

pytest 默认会collect test_.py 或者 _test.py module 中 以test为前缀的function 或者以Test为前缀的class中以test为前缀的function(no init),
通过这个参数可以自定义控制

示例

入门例子

在工作目录新建:test_sample.py

1
2
3
4
5
6
# test_sample.py
def inc(x):
    return x + 1

def test_answer():
    assert inc(3) == 5

当前目录运行:
1
pytest

便可以看到report.

Report 示例

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
(venv) ➜  ln_pytest pytest
=========================== test session starts ============================
platform darwin -- Python 3.6.5, pytest-5.4.2, py-1.8.1, pluggy-0.13.1
rootdir: ../ln_pytest
collected 5 items

test_cases1.py FF.                                                   [ 60%]
test_cases2.py F.                                                    [100%]

================================= FAILURES =================================
_______________________________ test_answer ________________________________

    def test_answer():
>   	assert inc(3) == 5
E    assert 4 == 5
E     +  where 4 = inc(3)

test_cases1.py:10: AssertionError
_______________________________ test_answer2 _______________________________

    def test_answer2():
>   	assert inc(3) == 5
E    assert 4 == 5
E     +  where 4 = inc(3)

test_cases1.py:14: AssertionError
_______________________________ test_answer ________________________________

    def test_answer():
>       assert inc(3) == 5
E       assert 4 == 5
E        +  where 4 = inc(3)

test_cases2.py:10: AssertionError
========================= short test summary info ==========================
FAILED test_cases1.py::test_answer - assert 4 == 5
FAILED test_cases1.py::test_answer2 - assert 4 == 5
FAILED test_cases2.py::test_answer - assert 4 == 5
======================= 3 failed, 2 passed in 0.39s ========================

Feature

用例(进入) 默认情况下自动发现关键词:“test”,
断言(判断) 灵活易懂

报告

依赖

1
2
pip install allure-pytest
brew install allure

生成测试结果数据

1
pytest --alluredir ./result/

将结果渲染到页面

1
allure serve result -h 127.0.0.1 -p 8080

Markdown

Posted on Edited on In

知识图谱:语义知识形式化表达的框架,节点表示本体,边表示关系.

知识图谱建设对众多NLP基础技术依赖很大,是一个系统工程,需要整体考虑.
所以梳理一下思路对整体认识有帮助.
但,这是一个更偏工程技术的挑战,而且成本也不小,所以既考规划也考技术,整理思路可能只对思路有帮助,实际建设过程却非常有可能遇到七七八八的问题.

需求

这个是第一位需要考虑的,这个会对大范围进行限定,因为会从“我要建知识图谱” => “我要建xxxx的知识图谱”.
需求会明确所面临的是开放领域还是专业领域,这个区别会造成数据来源的不同,以及对结果的要求高低也会不一样.
开放领域的数据可能一般通过从互联网爬取获得.
专业领域一般都有自己的数据积累,更新途径.

专业领域的知识图谱可能原本就会有一些相关应用,只是不叫知识图谱罢了,所以其要求也会更高.

技术

实体提取、关系提取、图谱存储、检索等

实体提取

  • 词典匹配 | 有了词典后就很简单快速,关键是如果要更新的就需要维护词典
  • 统计方法(NER) | 将NER问题转换为序列标注问题,一共那么几个标记,根据训练数据分布,计算当前语序下每个标记的概率,选概率最大的作为标记,这可以识别未登录词

关系提取

如果全部的关系集合预先指定好的话(比如谓词集合),任务也可视为当两个实体同时出现时实体间关系的分类问题.如果不当成分类问题可能就需要当成一个生成问题,根据句法分析后的依存关系生成实体间的关系.

基于依存关系生成主要基于句法分析和依存模版进行关系提取,可以看看EntityRelation的Python工具包实现,及对应的论文Chinese Open Relation Extraction and Knowledge Base
Establishment

关系分类大体可以分为无监督方法(基于模版),监督方法(基于特征/基于核函数/基于深度学习)
基于模版根据固定的语法格式提取实体间的关系,模版的生成可以是专家根据语言规则生成也可以用统计方法生成(利用搜索引擎等其它外部工具验证模版).
人工模版判断实体的上下位关系的准确率比较高,是因为这个模版所涉及到的表达形式比较固定,但对于其它关系可能就比较困难.
其他关系可以考虑使用统计生成模版,步骤是选择一个关系涉及到的实体对提交到搜索引擎,保留结果中包含实体对的的最长子串,这样会可能会得到多个模版,计算每个模版的置信度(只提交问题实体到搜索引擎,取包含实体的结果作为分母,契合某个模版的结果作为其模版的分子计算置信度),可以根据置信度阀值或者TopN提取模版.

基于特征就是根据标记数据训练分类模型,分类模型有很多可选,特征一般可以考虑(词汇相关/数值相关/类型相关/依存相关等等)
基于核函数利用空间转换计算相似度进行关系分类,方法复杂度比较高
基于深度学习从训练数据利用端到端对关系进行打分排序,进行关系分类

图谱存储

关系型数据库/图数据库
前者更新快,查询慢
后者查询快,更新慢

但是前者的使用成本可能会小一些,后者由于是一个相对新,可能需要趟更多的坑.包括但不限于图查询,图索引,子图优化等

检索

SQL/SPARQL

应用

包括知识推理在内应该属于应用范围,
其它应用领域可能有:搜索引擎,智能问答,推荐系统等

Posted on Edited on In

起源

yuange1975 在微博发布了一个趣味问题,看到觉得挺有意思,试着做了一下,相比原需求,多写了一个贷款数据生成的类,便于测试.
需求介绍及算法思路都在代码中注释,最终正确结果等yuange公布.

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
"""
LG
ourantech@163.com
2019-09-04
这是yuange1975的一个兴趣题。just for fun。

需求：
@yuange1975
https://weibo.com/2246379231/I5fgWcrFF?from=page_1005052246379231_profile&wvr=6&mod=weibotime&type=comment

最近在微信的微粒贷里借钱了，发现还款还是一个好的算法征解题。
问题，在微信微粒贷里不同时间借款若干笔，现在有一笔资金，需要还款，求通用的还款算法（还哪些笔欠款）？

已知条件有：
1、微粒贷不支持单笔借款部分还款，一笔还款必须还完。如果支持部分还款，那就问题比较简单了。
2、借款总额度还够，微粒贷还可以马上借款出来。
3、一个还款周期里，不收复利，每天按本金按固定利率算利息。
4、现金的收益利率比借款利率低，否者就不去还款了。
5、假定所有的借款下一还款时间都一样。（微粒贷不同借款还款周期都是每月固定的某一天，如果某笔借款到下一个月的还款时间小于一个月，好像这笔借款第一次还款就会到再下一个月）。这个假设简化一点点。
6、微粒贷每笔借款有最高限额4万，这个没什么影响。
7、微粒贷利率每天万2。
8、现金理财收益每天万1。
9、借款、还款本金必须是100的整数倍。

"""
import random

LOAN_RATIO = 0.0002  # 贷款利率
CASH_RATIO = 0.0001  # 现金收益


class Repay(object):
    """
    还款算法：
    每需要还一笔就迭代一轮看应该最先还哪一笔
    迭代的内容是 计算还款收益，还款收益的主要分为两种情况：
        一是如果手上的金额大于该笔待还款金额，则 还款收益=贷款剩余本金利息-待还款金额现金收益；
        二是如果手上的金额小于待还款金额，则 还款收益=贷款剩余本金利息-与手上现金和大于待还款金额的满足借款规则的最小贷款金额利息-待还款金额现金收益;且增加一笔贷款。
    选择还款收益为正且最大的那一笔贷款最优先还款
    如果没有为正的还款收益贷款，则不还款，停止迭代
    如果手上没有现金，则停止迭代
    如果没有剩余的贷款，则停止迭代
    """
    def __init__(self, loans, cash):
        self.loans = loans
        self.cash = cash
        self.update_loans()

    def plan(self):
        max_repay_income = self.get_max_repay_income()
        while self.loans and max_repay_income > 0:
            self.pay()
            self.update_loans()
            max_repay_income = self.get_max_repay_income()
        return self.loans, self.cash

    def update_loans(self):
        temp = []
        for m, n, i, j, k in self.loans:
            if self.cash >= j:
                temp.append([m, n, i, j, round(self.repay_income_1(i, j), 3)])
            else:
                min_aount = self.min_loan_amount(j, self.cash)
                temp.append([m, n, i, j, round(self.repay_income_2(i, j, min_aount), 3)])
        self.loans = temp

    def get_max_repay_income(self):
        if self.loans:
            return max(i[4] for i in self.loans)
        else:
            return 0

    def pay(self):
        self.loans = sorted(self.loans, key=lambda x: x[4])
        payment = self.loans.pop()
        print(f"还款前现金金额: {self.cash}\t\t\t偿还贷款: {payment[:-1]}\t\t剩余现金金额:{round(self.cash-payment[-2], 2)}")
        if self.cash >= payment[-2]:
            self.cash = round(self.cash - payment[-2], 2)
        else:
            min_aount = self.min_loan_amount(payment[-2], self.cash)
            self.cash = round(self.cash + min_aount - payment[-2], 2)
            self.loans.append([min_aount, 5, min_aount, min_aount, 0])  # 假设为还款而产生的借款都为5期
            print(f"还款时暂时借款：{min_aount}")

    @staticmethod
    def repay_income_1(principal, balance) -> float:
        """
        当手中现金大于待还款金额时，计算还款收益。
        :param principal: 贷款剩余本金
        :param balance: 剩余还款总额
        :return:
        """
        return principal*LOAN_RATIO - balance*CASH_RATIO

    @staticmethod
    def repay_income_2(principal, balance, min_loan) -> float:
        """
        当手中现金小于待还款金额时，先借到使手中金额大于待还款金额的最小借款。在综合计算还款收益。
        :param principal: 贷款剩余本金
        :param balance: 剩余还款总额
        :param min_loan: 最小借款金额
        :return:
        """
        return (principal-min_loan)*LOAN_RATIO - balance*CASH_RATIO

    @staticmethod
    def min_loan_amount(balance, cash_num):
        """
        剩余还款金额大于手中现金是，计算满足规则且覆盖还款金额的最小借款金额。
        规则是借款金额必须是100 的整数倍
        :param balance: 待还款金额
        :param cash_num: 手中现金
        :return:
        """
        from math import ceil
        diff = balance - cash_num
        return 100*ceil(diff/100)


class GenerateData(object):
    """
    用于生成满足规则的测试数据。
    """

    def __init__(self, max_cash, loans_num):
        self.max_cash = max_cash
        self.loans_num = loans_num

    def gen(self):
        cash = round(random.random()*self.max_cash)  # 随机生成手上现金数。
        loans = [self.get_loan() for _ in range(self.loans_num)]  # 随机生成若干笔贷款

        return cash, loans

    @staticmethod
    def get_loan():
        loan = random.randint(5, 400) * 100  # 生成[500, 40000]的借款金额
        months = [5, 10, 20][random.randint(0, 2)]  # 随机生成借款月数
        days = random.randint(0, 30*months)  # 生成[0, 720]天的借款天数(已发生)
        days_1 = random.randint(30, 60)  # 借款时距下一固定还款日期天数

        over_months = (days - days_1)//30 + 1  # 已还款周期数

        remain_loan = round(loan*(1 - over_months/months), 2)   # 剩余借款本金
        remain_loan_inter = round(remain_loan *
                                  (1 + LOAN_RATIO * (days - (30 * (over_months - 1) + days_1))), 2)  # 截止现在剩余还款总额(含息)

        return [loan, months, remain_loan, remain_loan_inter, 0]


if __name__ == '__main__':
    cash_0, loans_0 = GenerateData(100000, 10).gen()

    print(f"初始现金情况：{cash_0}")
    print(f"贷款数据说明： [初始贷款金额, 贷款期数, 剩余贷款本金, 剩余贷款总额]")
    print(f"初始贷款情况：{[i[:-1] for i in loans_0]}\n\n")

    loans_, cash_ = Repay(loans=loans_0, cash=cash_0).plan()
    print(f"\n\n剩余贷款：{[i[:-1] for i in loans_]}")
    print(f"剩余现金金额：{cash_}")

示例结果

Markdown