+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-07(2)

2019-08(89)

2019-09(94)

2019-10(15)

2019-11(5)

实例:python 实现有向图找环(自己写的,没有优化,不喜勿喷)

发布于2020-04-24 18:41     阅读(367)     评论(0)     点赞(20)     收藏(5)


0

1

2

3

4

5

6

7

  1. 题目来源:2020华为软件精英挑战赛–初赛
  2. 题目说明:
    2.1 输入信息:输入为包含资金流水的文本文件,每一行代表一次资金交易记录,包含本端账号ID, 对端账号ID, 转账金额,用逗号隔开。
    本端账号ID和对端账号ID为一个32位的无符号整数
    转账金额为一个32位的无符号整数
    转账记录最多为28万条
    每个账号平均转账记录数< 10
    账号A给账号B最多转账一次
    举例如下,其中第一行[1,2,100]表示ID为1的账户给ID为2的账户转账100元:
    1,2,100
    1,3,100
    2,4,90
    3,4,50
    4,1,95
    2,5,95
    5,4,90
    4,6,30
    6,7,29
    7,4,28
    2.2 输出信息:输出信息为一个文件,包含如下信息:
    第一行输出:满足限制条件下的循环转账个数。
    说明:数据集经过处理,会保证满足条件的循环转账个数小于300万。
    第二行开始:输出所有满足限制条件的循环转账路径详情。
    输出循环转账路径要按照指定排序策略进行排序:每条循环转账中,ID(ID转为无符号整数后)最小的第一个输出;总体按照循环转账路径长度升序排序;同一级别的路径长度下循环转账账号ID序列,按照字典序(ID转为无符号整数后)升序排序。
    举例如下:
    4
    1,2,4
    1,3,4
    4,6,7
    1,2,5,4
    2.3 限制条件:循环转账的路径长度最小为3(包含3)最大为7(包含7),例如账户A给账户B转账,账户B给账户A转账,循环转账的路径长度为2,不满足循环转账条件。
  3. 题目理解:
    在这里插入图片描述
    说明:2,4,1,2 是长度为 3 的环,按照升序的要求是:1,2,4
    本案例是以邻接表的形式找环,利用 sort 对 graph.keys() 得到的 key 值进行从小到大的排序,为了在找环过程中出现重复找环的情况,进行了剪枝优化,即:比自己小的 key 不再去查找,本案例用的最基本的 for 循环,对于十万以内的环查找速度较快,但是不建议用python 程序参加比赛,主要是太慢了。当然自己也想过用多进程多线程进行优化,然而效果并没有多大的提升,本文可以很好的帮助小白理解操作,大佬不喜勿喷啊,毕竟作为一个妹子码代码不容易,自己一个人走了太多的弯路了,不过个人很欢迎大佬前来指导一二。
    废话不多说,下面上代码。
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/4/23 13:04
# @Author  : xueli
# @Software: win10 Tensorflow1.13.1 python3.6.3
import time

def func(graph,s):#graph图  s指的是开始结点
    path =[]
    for x1 in graph[s]:
        if x1 > s:
            try:
                nodes2 = graph[x1]
            except KeyError as e:
                pass
            else:
                for x2 in nodes2:
                    if x2 > s:
                        try:
                            nodes3 = graph[x2]
                        except KeyError as e:
                            pass
                        else:
                            for x3 in nodes3:
                                if s == x3:
                                    A = [s,x1,x2]
                                    if len(set(A)) == len(A):
                                        path.append(A)
                                elif x3 > s:
                                    try:
                                        nodes4 = graph[x3]
                                    except KeyError as e:
                                        pass
                                    else:
                                        for x4 in nodes4:
                                            if s == x4:
                                                A = [s,x1,x2,x3]
                                                if len(set(A)) == len(A):
                                                    path.append(A)
                                            elif x4 > s:
                                                try:
                                                    nodes5 = graph[x4]
                                                except KeyError as e:
                                                    pass
                                                else:
                                                    for x5 in nodes5:
                                                        if s == x5:
                                                            A = [s,x1,x2,x3,x4]
                                                            if len(set(A)) == len(A):
                                                                path.append(A)
                                                        elif x5 > s:
                                                            try:
                                                                nodes6 = graph[x5]
                                                            except KeyError as e:
                                                                pass
                                                            else:
                                                                for x6 in nodes6:
                                                                    if s == x6:
                                                                        A = [s,x1,x2,x3,x4,x5]
                                                                        if len(set(A)) == len(A):
                                                                            path.append(A)
                                                                    elif x6 > s:
                                                                        try:
                                                                            nodes7 = graph[x6]
                                                                        except KeyError as e:
                                                                            pass
                                                                        else:
                                                                            for x7 in nodes7:
                                                                                if s == x7:
                                                                                    A = [s,x1,x2,x3,x4,x5,x6]
                                                                                    if len(set(A)) == len(A):
                                                                                        path.append(A)
                                                                                    else:
                                                                                        break
    return path

def savePredict(AA2):
    t2 = time.time()
    with open(result_name, 'w') as f:
        f.write(str(len(dd))+'\n')
        for aa in AA2:
            ww = str(aa)
            q1 = ww.strip(']')
            qq = q1.strip('[')
            bb = qq.replace(" ", "")
            f.write(str(bb)+"\n")
    print('write_time', time.time() - t2)
if __name__ == '__main__':
    t1 = time.time()
    file_name = "./data/test_data.txt"
    result_name = "result.txt"
    with open(file_name) as f:
        a = []
        c = []
        for line in f.readlines():
            line = line.strip('\n')  # 去掉换行符\n
            b = line.split(',')  # 将每一行以空格为分隔符转换成列表
            a.append(int(b[0]))
            c.append(int(b[1]))
    print('read_time', time.time() - t1)
    graph = {}
    data_list = [a,c]
    for x in range(len(a)):
        if a[x] in graph:
            graph[a[x]] += [c[x]]
        else:
            graph[a[x]] = [c[x]]
    s = sorted(graph.keys())
    t4 = time.time()
    dd = []
    for i in s:
        d = func(graph, i)
        if d != []:
            for ii in d:
                dd.append(ii)
    dd.sort()
    print('func_time', time.time() - t4)
    AA2 = sorted(dd, key=lambda i: len(i), reverse=False)
    print(len(dd))
    savePredict(AA2)
    print('总时:', time.time() - t1)

运行结果:
在这里插入图片描述
代码和数据已经上传到GitHub,感兴趣的可以下载下来。
https://github.com/xueli-lxl/python

0

1

2

3

4

5

6

7



所属网站分类: 技术文章 > 博客

作者:天青色等烟雨

链接: https://www.pythonheidong.com/blog/article/341386/6be33e0f4740beaa5ff5/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

20 0
收藏该文
已收藏

评论内容:(最多支持255个字符)