非常有趣的体验,非常有趣的项目 - 文件夹比较工具
一个有些意思的项目--文件夹对比工具(一)
前言
为什么会写这个,因为遇到了有意思的事情,简而言之就是,面试某意向公司,没过;其中一位面试官非常nice,还仔细看了我博客,觉得是不是面试时没展现出来,因此第二天专程打电话过来,给了我一个额外机会,就是花几天时间做一个小项目,过几天提交给他。
这是背景,项目是关于做一个工具,可以指定两个目录进行对比,如果某个文件如a.txt在两个目录都存在,就对比其内容并呈现,呈现效果可以参考beyond compare或者git diff。
花了三天多时间编码,两天时间写文档,最终做了一个满足需求的简陋工具出来,幸不辱命吧;项目麻雀虽小,五脏俱全,也写了需求分析文档、概要设计、详细设计等,项目本身也非常有意思,所以给大家分享一下。
其中一个核心点就是文本差异对比算法,因此先来篇文章讲解一下,铺垫铺垫。
差异对比,很多人会想到beyond compare、git、svn等。这里以git来说吧,git作为版本管理工具,真的也太方便了,很多时候想推荐给非互联网行业的朋友们。
版本管理工具,最重要的一点就是不同版本的差异对比,看下图:
从图上来说,右边那一行比左边,就是多了几个字符”xxxww“;但是对于软件来说,怎么才知道,只是多了几个字符呢,毕竟,按理来说,插入了几个字符后,原来在右侧的字符*右移,其实在程序看来,是从插入的地方开始,两个字符串已经开始是不同的了。
但是软件并没有从插入的地方开始的右侧字符,全标记为差异,所以,软件是怎么识别出来的呢?
字符串转换
其实以上的问题可以用下面的例子来简单阐述:
假设有一个原始字符串是:ABCABBA,现在我们想把它变成:CBABAC,是不是有很多种方式呢?
比如,最简单的方式,ABCABBA依次删掉:ABCABBA,现在,是不是变成一个空字符串了,删7个字符,一共操作7次;接下来,再在空字符串基础上,依次加上:CBABAC,加了6次。
最终,操作了13次,就把ABCABBA变成了CBABAC。
但是,这太暴力了,也不是很优雅,直观的感觉就是,太傻了,好像不需要这么多次吧?
所以,寻找一个算法,以保证:转换成功的同时,保证尽可能少的编辑次数。
这就是最短diff算法,diff就是把原始字符串变成目标字符串,要进行的各种增删操作;或者也可以和数学里的delta对比,我查了下,delta就有变动的意思。
"最短diff"这个算法有多种实现,在git diff的代码中,就有4种实现供我们选择,分别是:
myers, minimal, patience, histogram。
在git help diff的文档中,有简要介绍:
默认的是myers算法,什么时候用其他的呢,这边有篇文档:https://luppeng.wordpress.com/2020/10/10/when-to-use-each-of-the-git-diff-algorithms/,有需要的同学可以看看。
这篇就简单说下我对myers的理解,算法比较复杂,我也没怎么弄懂,大家也跟着有个概念就行了(狗头)
diff的另一种直观展示
大佬们想了一个办法来表示diff。还是上面的例子,ABCABBA转换为CBABAC。
根据这两个字符串构造下面一张图,横轴是原始内容,纵轴是目标内容。
这个图要这么看,左上角是零坐标,水平是x轴,上下是y轴,x轴从(0,0)点到(1,0)点,为A字符;(1,0)到(2,0)是B字符,依次类推,横轴上的8个点,有7个空,依次为ABCABBA,即原始字符串的内容。y轴也是同理。
现在规定了,(0,0)处,你拥有原始字符串ABCABBA,当前指向第一个字符A。此时,向右表示删除对应的字符,向下表示新增对应字符,对角线则表示原内容保持不动(或者说先删再加,即不变)
现在举个例子:
-
从(0,0)移动到(1,0),需要删掉A,此时,ABCABBA从当前光标所在处,删掉A,变成了BCABBA,此时光标指向BCABBA的第一个字符B;
从(1,0)再向右移动一格到(2,0),此时要删去B,变成了CABBA
-
沿着x轴,继续移动到(3,0),删除C,变成ABBA;继续移动到(4,0),删除A,变成BBA;继续到(5,0),删除B,变成BA;继续到(6,0),删除B,变成A;继续到(7,0),删除A,变成空。
到目前为止,我们来到了7,0,字符串变成空的了;开始往下走,往下走的过程,是增加对应字符,比如,从(7,0),走到(7,1),增加字符C,变成“C”;再走到(7,2),变成CB;再到(7,3),变成CBA;
最终走到(7,6),变成了CBABAC.
大家可能发现了,只要沿着那个图一路走,从(0,0)到达右下角(7,6),原始字符串就能变成目标字符串。
当然,这条路是比较暴力的,先删除原始字符串(一路往右),再新增目标字符串(一路向下)。
diff的图形表示之路线演示
我们来随便画个其他路线试试。
现在(0,0)处,我们为原始字符串ABCABBA,
- 接下来是向右一步-A,变成BCABBA。
- 向下,+C,变成CBCABBA
- 遇到对角线,对角线对应字符B,此时可以理解为删掉B,再加上B,相当于光标前移,依然是CB|CABBA,我们用|表示光标位置
- 向下,在当前光标处+A,变成CBA|CABBA;加B,变成CBAB|CABBA;再-C,变成CBAB|ABBA
- 又遇到对角线,对角线对应字符A,此时光标移动,变成CBABA| BBA
- 从(4,5)移动到(4,6),加C,变成CBABAC|BBA
- 从(4,6)移动到(7,6),依次删除BBA,即变成CBABAC
所以,我们再一次成功到达了右下角,此时字符串也变成了CBABAC。我们也可以算一下,移动了多少次
-A,+C,+A,+B,-C,+C,-B,-B,-A,合计是9次(走对角线的话,没有实际修改字符,不算在内)。
Myers 算法大概理解
如果前面都理解了的话,我们大概知道,从图中的左上角,到达右下角的每一条路线,都是有效的diff。
而Myers的目标,应该就是从众多的路线中,选出一条距离最短(向右的次数 + 向下的次数之和;走对角线不算)的路线。
而这条最短的路线,就是最短diff算法的答案。
Myers的算法我还不是很理解,但是如果按照我们暴力的思路,就是每条路线的距离都计算一下(向右的次数 + 向下的次数之和;走对角线不算),然后取最短的路线即可。
网上有不少资料,有兴趣可以阅读:
https://chenshinan.github.io/2019/05/02/git%E7%94%9F%E6%88%90diff%E5%8E%9F%E7%90%86%EF%BC%9AMyers%E5%B7%AE%E5%88%86%E7%AE%97%E6%B3%95/
原始论文:
https://neil.fraser.name/writing/diff/myers.pdf
本文由mdnice多平台发布
推荐阅读
-
15 个非常有趣的开源项目推荐
-
源码为您提供,零基础搭建的免费网址导航站--中国妖怪百集,收集了大量古代文献中的妖怪,非常详细的记录了妖怪的来历、描述甚至图片,让您对中国的妖怪文化有一个整体的了解,茶余饭后的消遣非常有趣,类似的网站还有很多,期待您的探索! 导航站的另一个特点是汇集了大量咖啡平时用的非常好的工具软件,其中大部分都是在线的,不需要下载安装,包括文档协作、分享,图片、音频、视频处理,格式转换,文件传输,各个网站的视频下载等等,兼职就是一个工具百宝箱! 如果你觉得这些网站不符合你的使用习惯,或者想添加一些自己收藏的网站,那么把源码交给你,只需简单修改就可以变成符合自己使用习惯的独特导航了! 如何修改 导航站采用纯静态构建,下载源代码后,只需要修改 html 文件中的代码块即可,代码块结构如下: 只需要修改四个地方,分别对应网站的四个关键信息: 修改相应网站的 URL 地址 修改相应网站的徽标 修改相应网站的名称
-
15 个非常有趣的开源项目推荐
-
非常有趣的体验,非常有趣的项目 - 文件夹比较工具
-
对话NGC蔡岩:从机制创新到价值沉淀,解析DeFi产品开发逻辑 |链捕手 - 真正的DeFi产品首先要有足够的安全性和稳定性,如果能在此基础上有一些功能创新,那就非常好了。像 Uniswap 这样逐渐成为 DeFi 基础架构的产品,可遇而不可求。 链式捕手:固定利率协议之前关注度比较高,但观察下来发现,大部分协议还是类似于传统金融CDO(抵押债务凭证)的玩法,风险系数很高,您如何理解这块业务的价值和风险? 蔡岩:确实有些定息协议类似CDO玩法,背后绑定一个债券,但并不是所有的定息协议都是这样的玩法,像这种CDO玩法的主要代表项目是88mph,背后绑定的是Aave、Compoud这样的借贷协议,在此基础上做定息和浮息债券;像APWine,背后同样是Aave,它会发行期货收益代币来锁定你的收益;Notional本身是做借贷市场的,在此基础上做定息协议。 非 CDO 的玩法,比如 Horizon,更像是一个利率撮合器,背后需要用户通过拍卖产生更合适的目标收益率;像 Saffron、BarnBridge 等是通过风险分级来定义不同的收益率。总的来说,创新还是挺多的。 价值层面是创新和想象力,因为在传统金融领域,比如银行做固定收益证券,或者评级机构给风险分级,这些业务都非常大,利润也很丰厚。而 DeFi 的对口业务给了类似业务很大的想象空间。尤其是固定利率协议的成熟产品不多,尝试各种微创新是很有意义的。 风险程度还是要具体到不同的玩法,比如,在 Aave、Compoud 等借贷协议的固定利率协议背后,如果这些借贷协议受到攻击,与之绑定的固定利率协议也会受损。 同样,如果自己做借贷市场,可能更需要更强的开发能力。再有,如果该程序的机制或参数设计不当,同样会导致协议运行不稳定,并可能造成大量用户清盘。 总的来说,风险在于固定利率协议的设计,这是一个非常复杂的过程,需要不断地尝试和出错。 链式捕捉器:刚刚提到背后是Aave/Compound的固定费率协议风险较大,您认为Aave最大的不确定性和创新点分在哪里? 蔡岩:其实爱钱进一直被认为是走在行业前列的项目,他们的迭代速度非常快,比如率先尝试闪贷、推出新的经济激励模式、推出目前业内首个安全模块、尝试L2解决方案等等。 而在主要的借贷业务上,他们又十分谨慎,比如在抵押率、清算系数等风险参数的设计上相对于其他借贷协议较为保守,并不会存在为了吸引更多借贷资金而降低风险的要求。 与许多 DeFi 项目一样,即使 Aave 进行了多次审计,也无法保证不存在漏洞。前段时间,Aave 刚进入 V2 阶段时,白帽黑客就指出了某个漏洞。 之前的创新点可能是闪电借贷,这是当时业内独一无二的新产品功能,也为 Aave 带来了不少收益。当然,也有人批评闪电贷只能方便黑客实现资金效益的最大化,但工具本身并没有错,未来闪电贷肯定会有更多的应用场景。 其次是安全模块的设计,这有点像项目本身的储备金库,保障项目的安全性,这也是爱维开创的先河。说实话,目前大多数项目都没有做到代币模式的良性或正向运营,也做不到像Aave一样的安全模块,这是一个不小的门槛。 Chaincatcher从某种程度上来说,挖矿模式是DeFi财富效应的根本支撑,但Aave的CEO却说挖矿机制带来的动力是不可持续的,您怎么看这个观点? 蔡岩:"挖矿机制 "不可能失效,因为它是一种激励机制,或者说是项目冷启动的一种方式。但流动性开采亚博体育手机客户端不会一直高涨。比如去年11月的流行性挖矿高APY持续了一两个月就崩盘了,导致DeFi市场大幅回调。 Aave、Uniswap、Synthetix等项目真正爆发进入市值前15名也是在今年2月,我更倾向于这是头部DeFi长期价值的体现。虽然大家都喜欢抢高APY的矿机,但我个人很少参与挖矿,所以我并不觉得流动性挖矿是DeFi的基本面支撑。
-
41 个下载免费 3D 模型的最佳网站-使用说明:使用权限可能因型号而异。因此,在下载文件之前,请仔细检查每个下载页面上的许可证和使用权限。 17. Clara.io Clara.io 是一个创建 3D 内容的全球平台,也是一个培养新 3D 艺术家的社区。Clara.io 提供+100,000个免费的3D模型,包括OBJ,Blend,STL,FBX,DAE,Babylon.JS,Three.JS格式,用于 Clara.io,Unity 3D,Blender,Sketchup,Cinema 4D,3DS Max和Maya。 使用说明:免费,标准和专业帐户仅供个人使用,如果您需要将 clara.io 用于商业用途,请与销售团队联系。 18. 3DExport 3DExport是一个市场,您可以在其中购买和销售用于CG项目的3D模型,3D打印模型和纹理。它提供15 +不同的3D格式供下载,如3DS MAX(.max),Cinema4D(.c4d),Maya(.mb,.ma),Lightwave(.lwo),Softimage(.xsi),Wavefront OBJ(.obj),Autodesk FBX(.fbx)等。它还提供15种不同的语言! 使用说明:免费下载仅供个人和非商业用途。 19. 3D Warehouse 3D Warehouse是一个开放的库,允许用户共享和下载SketchUp 3D模型,用于建筑,设计,施工和娱乐!任何人都可以免费制作,修改和重新上传内容到3D仓库,您可以找到任何您能想到的东西,如家具,电子产品,室内产品等。 使用说明:3D Warehouse中的所有模型都是免费的,因此任何人都可以下载文件以用于SketchUp甚至其他软件,如AutoCAD,Revit和ArchiCAD。 20. CadNav.com CadNav是CGI平面设计师和CAD / CAM / CAE工程师的在线3D模型库,我们提供超过50000 +免费3D模型和CAD模型下载。在CadNav网站上,您可以下载高质量的多边形网格3D模型,3D CAD实体对象,纹理,Vray材料,3D作品,CAD图纸等。 使用说明:免费下载仅供个人和非商业用途。 21. All3dfree.net 就像网站名称一样,它提供免费的3D模型,还包括Vray材料,CAD块,2d和3d纹理集合,无需注册即可免费下载。它是不断更新的,因此您可以查找或请求3DS,MAX,C4D,skp,OBJ,FBX,MTL等格式的模型。 使用说明:所有资源均不允许用于商业用途,否则您将承担责任。 22. Hum3D 自2005年以来,Hum3D帮助来自3多个国家的80D艺术家节省3D建模时间,并制作逼真的3D模型,用于电影,视频游戏,AR应用程序和可视化。所有模型均由首席3D艺术家进行验证,他们检查其是否符合专业要求和最新的3D建模标准。 使用说明:免费下载仅供个人和非商业用途。 23. Artist-3D.com 艺术家-3D 库存的免费 3D 模型下载按通用类别排序。它为人体解剖学、汽车、家具、火箭、卫星等模型提供 AutoDesk 3DS Max 格式。您还可以在浏览他们的网站时找到教程和类似类型的建模。 使用说明:使用权限可能因型号而异。因此,在下载文件之前,请仔细检查每个下载页面上的许可证和使用权限。 24. Free the models 就像本网站的标题一样,它为3d应用程序和3d游戏引擎提供免费的内容模型。您可以为您的任何项目找到许多有趣且有用的模型!它提供3ds,wavefront,bryce,poser,lightwave,md2和unity3d格式的模型。还有一个很棒的纹理集合,可以在您最喜欢的建模和渲染程序中使用。 使用说明:您从这里下载的所有内容都可以免费使用,除非它不能包含在另一个免费的网络或CD收藏中,也不能单独出售。否则,您可以在商业游戏,3D应用程序或渲染作品中使用它。您不必提供信用,但如果您这样做,那就太好了。 25. Resources.blogscopia 本网站由一家名为Scopia的公司创建。他们制作3D图像和视频,您可以找到许多为CGI工作的信息架构设计的模型,所有这些都可以在现实生活中使用。您可以免费下载它们,但是,如果您想一次下载它们,您可以支付 3 到 9 欧元。 使用说明:您可以免费下载模型部分的所有文件。每个压缩文件都包含您也可以在此处找到的许可证。基本上,您可以对文件执行任何操作。唯一的限制是不归属于Scopia的重新分发。 26.ambientCG 1000+公共领域PBR材料适合所有人!环境CG是使用许多不同的方法和资产类型创建的,例如照片纹理(PBR),贴花(PBR),图集(PBR),照片纹理(普通),物质存档(SBSAR),雕刻画笔,3D模型和地形。您可以在所有项目中*使用它们! 使用说明:在 ambientCG 上提供下载的所有 PBR 材料、画笔、照片和 3D 模型均根据知识共享 CC0 1.0 通用许可提供。您可以复制、修改、分发和执行作品,即使是出于商业目的,也无需征得许可。信用将不胜感激。 不要满足于平庸的大理石纹理 - 立即使用我们的免费PBR大理石纹理升级您的3D设计。 27.Pixar One Twenty Eight 这是一个提供官方动画行业经典纹理的网站:皮克斯,创建于 1993 年,该纹理库包括 128 个重复纹理,现在免费提供。 它包含您来到的纹理,包括砖块和动物毛皮。肯定会有一些你可以使用的东西。 使用说明:皮克斯动画工作室的《Pixar One Twenty Eight》根据知识共享署名4.0国际许可协议进行许可。即使出于商业目的,您也可以重新混合、调整和构建您的作品,只要您以相同的条款对新创作进行信用和许可。 访问数以千计的免费纹理并提升您的设计游戏 - 立即开始下载! 28. 3DXO 即使有近 620 个免费贴纸可供下载,3DXO 也不是最大的资源,但它的内容非常有用,不需要注册。无论是简单的墙壁或地板,还是一些奇怪的小东西,您都需要的纹理都可以在此网站上看到。 使用说明:使用权限可能因型号而异。因此,在下载文件之前,请仔细检查每个下载页面上的许可证和使用权限。 29. 3DModelsCC0 3DModelsCC0 与其他产品的不同之处在于它包含超过 250+ 个高质量 3D 模型,并且本网站上的所有内容都是免费的,完全是公共领域!使用我们的模型时无需信用或归属! 使用说明:为每个人提供完全免费的公共领域内容。 30.Sketch up texture club Sketchup Texture Club是一个非营利性的教育和信息门户网站,由3D社区的图像促进协会管理,特别强调面向学生和建筑和室内设计专业人士的可视化和渲染技术,以及所有正在学习3D可视化的人。 使用说明:您无需支付版税或使用费。纹理可以免费下载和使用。不允许将纹理作为竞争产品出售或重新分发,即使图像被修改也是如此。 31. FlippedNormals FlippedNormal 是一个提供计算机图形和 3D 资产的市场,您可以找到许多用于雕刻、建模、纹理、概念艺术、3D 模型、游戏资产或课程的高级资产! 使用说明:使用权限可能因型号而异。因此,在下载文件之前,请仔细检查每个下载页面上的许可证和使用权限。 32. NASA 3D NASA 3D网站是一个在线门户,提供与太空和各种NASA任务相关的大量三维模型和模拟。该网站是用户友好的,并提供有关每个型号的详细信息。该网站允许用户探索和下载几种不同格式的模型,包括 OBJ、STL 和 FBX,只需单击下载按钮即可。 使用说明: 要下载模型,只需单击模型页面上的下载按钮并选择所需的格式。 33. 3DAGOGO (Astroprint) 3DAGOGO 是一个提供广泛 3D 模型的网站,包括角色、车辆和建筑物。3DAGOGO 的独特功能之一是它专注于适合 3D 打印的模型,使其成为希望创建物理原型或模型的设计师的绝佳资源。要使用 3DAGOGO,设计师只需在网站上搜索他们正在寻找的模型类型,然后下载 STL 格式的文件。 使用说明: 要使用 3DAGOGO,只需搜索所需的 3D 模型类型并下载 STL 格式的文件。根据需要自定义模型,并确保在将其用于商业目的之前检查使用权限。 34. FreeCAD FreeCAD是一款了不起的3D建模软件,可让您在计算机上创建令人难以置信的3D设计。该软件可免费下载和使用,它提供了广泛的工具和功能,可用于创建用于各种目的的3D模型。 该网站易于浏览,您可以找到开始使用FreeCAD的所有必要信息。此外,该网站还提供一系列教程和指南,可帮助您了解 3D 建模的来龙去脉。 使用说明: 要下载模型,请访问网站并从库中选择所需的模型。该网站还提供了一系列使用该软件的教程和指南。 35. Pinshape Pinshape是一个提供一系列3D打印模型的网站。网站上提供的型号质量很高,因此您可以确保您的最终印刷产品看起来很棒。该网站提供了广泛的模型,包括从家居用品到小雕像和珠宝的所有物品。 但这还不是Pinshape所能提供的全部!该网站还允许用户上传和共享自己的3D模型。这意味着您不仅可以下载出色的模型,还可以通过分享自己的设计为社区做出贡献。此外,Pinshape 提供了一系列自定义选项,因此您可以调整和调整模型以满足您的特定需求。 使用说明: 要下载模型,请在网站上创建一个帐户,搜索所需的模型,然后单击下载按钮。该网站还为每种型号提供了一系列定制选项。 36.Yeggi Yeggi 提供了大量免费的 3D 模型,您可以下载各种格式的模型,例如 STL、OBJ 和 FBX。该网站易于使用,您可以按关键字、类别或特定网站搜索模型。 Yeggi 对于任何寻找 3D 模型的人来说都是一个很好的资源。它提供了大量的模型集合,从日常物品到复杂的机械,以及介于两者之间的一切。该网站的收藏量在不断增长,每天都有新的型号增加。 使用说明: 要下载模型,请在网站上搜索所需的模型,然后单击下载按钮。该网站还提供指向托管模型的原始网站的链接。 37. Open3DModel 来自开放3D模型的图像 Open3DModel具有各种类别的模型,包括建筑,车辆和角色。无论您需要建筑物,汽车还是人的3D模型,都可以在此网站上找到。 该网站易于浏览,您可以按类别或关键字搜索模型。每个模型都附带预览图像和详细信息,例如文件格式、大小和多边形数量。此信息可以帮助您选择适合您需求的模型。 使用说明: 要下载模型,请访问网站,从库中选择所需的模型,然后单击下载按钮。 使用最好的 3D 资产管理工具简化您的 3D 制作流程。立即试用它们,将您的 3D 项目提升到一个新的水平! 38. 3DExport 对于那些为其 3D 设计项目寻找 3D 模型、纹理和其他资源的人来说,该平台是一个很好的资源。该网站有大量模型可供选择,包括 3D 打印对象、游戏资产等。用户可以按类别、文件格式或价格范围浏览,以找到适合其项目的完美资源。此外,3DExport 还提供一系列教程和其他 3D 资源,以帮助用户提高技能并创建更令人印象深刻的设计。 使用说明: 要使用 3DExport,只需创建一个帐户并浏览可用型号。您可以按类别、格式和价格进行搜索,以找到所需的型号。找到喜欢的模型后,只需下载它并开始在您的项目中使用它。 39.Blend Swap Blend Swap是一个社区驱动的市场,提供与Blender软件兼容的各种免费3D模型。该平台允许用户共享和下载模型、纹理和其他资产,以便在他们的项目中使用。 使用说明: 创建免费帐户后,您可以浏览社区上传的大量3D模型。当您找到要使用的一个时,只需下载它并将其导入您选择的 3D 软件即可。 40. 3DShook 3DShook 是一个高级 3D 模型市场,提供一系列用于建筑、游戏等各个行业的高质量模型。该平台提供基于订阅的模型,具有不同的定价计划,允许用户访问一系列模型。 使用说明: 注册免费帐户后,只需浏览3D模型库,选择您喜欢的模型,然后以您需要的格式下载它们。 41. Smithsonian X 3D 史密森尼 X 3D 对于正在寻找历史文物和文物的高质量 3D 模型的设计师来说,这是一个独特的资源。该平台提供了大量3D模型,这些模型是根据史密森尼博物馆和研究中心中的真实物体扫描创建的。 使用说明: