首页
关于
友情链接
推荐
百度一下
腾讯视频
百度一下
腾讯视频
Search
1
【笔记】用Javascript实现椭圆曲线加密算法
28 阅读
2
USTC Hackergame 2022 个人题解
20 阅读
3
欢迎使用 Typecho
18 阅读
4
【折腾记录】香橙派在Docker环境下部署Nextcloud
18 阅读
5
【学习笔记】FourierTransform-关于二维DCT变换可以被表示为矩阵相乘这档事
14 阅读
默认分类
登录
Search
标签搜索
Note
CPP
CTF
C
JavaScript
Math
Bilibili
Python
Docker
php
RSA
ECC
Crypto
Blog
Bash
FPGA
GAMES
Homework
HackerGame
依言 - Eyan
累计撰写
35
篇文章
累计收到
4
条评论
首页
栏目
默认分类
页面
关于
友情链接
推荐
百度一下
腾讯视频
百度一下
腾讯视频
搜索到
5
篇与
的结果
2022-07-07
【笔记】234树笔记
代码在这,测试是通过了。具体的细节以后再研究吧。function Tree234Node(rootNode){ this.rootNode = rootNode; this.elements = []; this.childs = []; this.debugCode = Math.floor(Math.random()*1000000); } function Tree234(){ this.root = new Tree234Node(this); this.root.elements = []; this.root.childs = []; this.root.parentNode = 0; } Tree234Node.prototype.getParentNode = function(){ let value = this.elements[0]; let nowParentNode = 0; let checkingNode = this.rootNode.root; //console.log(value, checkingNode) while(true){ //console.log('qwq77', checkingNode) for(let i = 0; i < checkingNode.elements.length; i += 1){ if(checkingNode.elements[i] === value){ return nowParentNode; } } if(checkingNode.childs.length === 0){ return 0; } //console.log('qwq78') let nextNodePos = checkingNode.childs.length-1; for(let i = 0; i < checkingNode.childs.length; i += 1){ if(checkingNode.elements[i] > value){ nextNodePos = i; break; } } //console.log('qwq79', checkingNode.childs, checkingNode.childs.length-1, checkingNode) nowParentNode = checkingNode; checkingNode = checkingNode.childs[nextNodePos]; //console.log('qwq80', checkingNode) } } Tree234Node.prototype.insert = function(node){ let value = node.elements[0]; let pos = this.elements.length; for(let i = 0; i < this.elements.length; i += 1){ if(value < this.elements[i]){ pos = i; break; } if(value === this.elements[i]){ return 0; } } let parentNodeRef = this.getParentNode(); if(this.elements.length <= 2){ this.elements.splice(pos, 0, value); if(node.childs.length > 0){ this.childs.splice(pos, 1); this.childs.splice(pos, 0, node.childs[1]); this.childs.splice(pos, 0, node.childs[0]); } return 0; } else { let pop = new Tree234Node(this.rootNode); pop.elements=[this.elements[1]]; pop.childs = [new Tree234Node(this.rootNode), new Tree234Node(this.rootNode)]; pop.childs[0].elements = [this.elements[0]]; pop.childs[1].elements = [this.elements[2]]; if(node.childs.length > 0){ pop.childs[0].childs = [this.childs[0], this.childs[1]]; pop.childs[1].childs = [this.childs[2], this.childs[3]]; } let insertChildPos = pos <= 1 ? 0 : 1; pop.childs[insertChildPos].insert(node); if (parentNodeRef===0) { return pop; } else { return parentNodeRef.insert(pop); } } } Tree234.prototype.insert = function(value){ if(this.root.elements.length === 0){ this.root.elements = [value]; this.root.childs = []; return; } // search nearest node let checkingNode = this.root; while(true){ if(checkingNode.childs.length === 0){ break; } let childPos = checkingNode.elements.length; for(let i = 0; i < checkingNode.elements.length; i += 1){ if(value < checkingNode.elements[i]){ childPos = i; break; } } checkingNode = checkingNode.childs[childPos]; } let insertNode = new Tree234Node(this); insertNode.elements = [value]; let ret = checkingNode.insert(insertNode); if(ret !== 0){ this.root = ret; } } Tree234Node.prototype.printTreeRoot = function(){ //console.log('qwq23') let elementList = []; maxLayer = 0; let collector = (node, layer)=>{ //console.log('qwq24', node.debugCode) if(layer > maxLayer){ maxLayer = layer; } if (node.childs.length === 0) { elementList.push({layer:layer,element:'['}); for(let i = 0; i < node.elements.length; i += 1){ elementList.push({layer:layer,element:node.elements[i]}); } elementList.push({layer:layer,element:']'}); } else { elementList.push({layer:layer,element:'['}); collector(node.childs[0], layer+1); elementList.push({layer:layer,element:node.elements[0]}); collector(node.childs[1], layer+1); if(node.elements.length === 1){ elementList.push({layer:layer,element:']'}); return; } elementList.push({layer:layer,element:node.elements[1]}); collector(node.childs[2], layer+1); if(node.elements.length === 2){ elementList.push({layer:layer,element:']'}); return; } elementList.push({layer:layer,element:node.elements[2]}); collector(node.childs[3], layer+1); elementList.push({layer:layer,element:']'}); return; } } collector(this, 0); padding=' '; printString = ''; for(let i = 0; i <= maxLayer; i += 1){ for(let j = 0; j < elementList.length; j += 1){ //console.log(elementList[j].element) tmp_str = elementList[j].element.toString(); if(elementList[j].layer !== i){ printString += padding.substr(0, tmp_str.length); } else { printString += tmp_str; } printString += ' '; } printString += '\n'; } console.log(printString); } Tree234.prototype.printTree = function(){ this.root.printTreeRoot(); } Tree234Node.prototype.search = function(value){ //console.log(this) for(let i = 0; i < this.elements.length; i += 1) { if(this.elements[i] === value){ //console.log('qwq3') return this; } else if (this.elements[i] > value && this.childs.length !== 0){ let ret = this.childs[i].search(value); if(ret){ //console.log('qwq4') //console.log(ret) return ret; } } } if (this.childs.length !== 0) { let ret = this.childs[this.childs.length-1].search(value); if(ret){ return ret; } } } Tree234.prototype.search = function(value){ return this.root.search(value); } Tree234Node.prototype.delete = function(value){ // Case 1: If x is in a leaf node. Here we default the element to be deleted on the leaf node. // Case 1.1: If x is either in a 3-node or 4-node. if(this.elements.length >= 2){ //console.log('qwq31',this.elements, pos) for(let i = 0; i < this.elements.length; i += 1){ if(value === this.elements[i]){ this.elements.splice(i, 1); break; } } //console.log('qwq32',this.elements) return; } let parentNodeRef = this.getParentNode(); if(parentNodeRef === 0){ //this.elements = [this.childs[0].elements[0], this.elements[0], this.childs[1].elements[0]]; //parentNodeRef.childs=[this.childs[0].childs[0], this.childs[0].childs[1], this.childs[1].childs[0], this.childs[1].childs[1]]; //return; } // find pos let pos = -1; for(let i = 0; i < parentNodeRef.childs.length; i += 1){ if(this.elements[0] === parentNodeRef.childs[i].elements[0]){ pos = i; } } //console.log('qwq36', value, pos) // Case 1.2: If x is in a 2-node and the parent node is not a 2-node. //if(parentNodeRef.elements.length >= 2){ if(true){ let mergeDirection = pos === 0 ? 1 : 0; let caseType = 0; if(pos !== 0 && parentNodeRef.childs[pos-1].elements.length >=2){ caseType = 1; mergeDirection = 0; } if(pos !== parentNodeRef.childs.length-1 && parentNodeRef.childs[pos+1].elements.length >=2){ caseType = 1; mergeDirection = 1; } let parentElementPos = mergeDirection === 1 ? pos : pos-1; let neighborNodePos = mergeDirection === 1 ? pos+1 : pos-1; // Case 1.2.1: If the node containing x has 3-node or 4-node siblings if(caseType === 1){ this.elements = mergeDirection === 1 ? [value, parentNodeRef.elements[parentElementPos]] : [parentNodeRef.elements[parentElementPos], value] ; let negElemmentPos = mergeDirection === 1 ? 0 : parentNodeRef.childs[parentElementPos].elements.length-1; parentNodeRef.elements[parentElementPos] = parentNodeRef.childs[neighborNodePos].elements[negElemmentPos]; parentNodeRef.childs[neighborNodePos].elements.splice(negElemmentPos, 1); if(this.childs.length !== 0){ let neighborChildPos = mergeDirection === 1 ? 0 : parentNodeRef.childs[parentElementPos].childs.length-1; let neighborChild = parentNodeRef.childs[neighborNodePos].childs[neighborChildPos]; parentNodeRef.childs[neighborNodePos].childs.splice(neighborChildPos, 1); //console.log('qwq50', value, this.childs.length, neighborChild.elements, this.childs[0].elements) this.childs = mergeDirection === 1 ? [this.childs[0], this.childs[1], neighborChild] : [neighborChild, this.childs[0], this.childs[1]] ; //console.log('qwq49', value, this.childs.length, neighborChild.elements, this.childs[0].elements) } //console.log('qwq55', this.elements, parentNodeRef.elements, parentNodeRef.childs.length, parentNodeRef.childs[1].elements) //console.log('qwq56', this.childs.length, parentNodeRef.elements, parentNodeRef.childs[1].childs.length) } // Case 1.2.2: If both the siblings are 2-node but the parent node is either a 3-node or a 4-node else { //console.log('qwq54', parentNodeRef.childs[0].elements, parentNodeRef.childs[1].elements, parentNodeRef.elements) let parentElementValue = parentNodeRef.elements[parentElementPos]; parentNodeRef.delete(parentElementValue); //console.log('qwq53', parentNodeRef.childs[0].elements, parentNodeRef.childs[1].elements, parentNodeRef.elements) let neighborNode = parentNodeRef.childs[neighborNodePos]; parentNodeRef.childs.splice(neighborNodePos, 1); //console.log('qwq52', neighborNode.elements, neighborNodePos, parentNodeRef.childs[1].elements) this.elements = mergeDirection === 1 ? [value, parentElementValue, neighborNode.elements[0]] : [neighborNode.elements[0], parentElementValue, value] ; //parentNodeRef.elements.splice(parentElementPos, 1); //parentNodeRef.childs.splice(parentElementPos, 0, this); if(this.childs.length !== 0){ //let neighborChilds = parentNodeRef.childs.splice(neighborNodePos, 1).childs; let neighborChilds = neighborNode.childs; this.childs = mergeDirection === 1 ? this.childs.concat(neighborChilds) : neighborChilds.concat(this.childs) ; //console.log('qwq48', value, this.childs.length) } } this.delete(value); // Case 1.2.3: If both siblings and the parent node are a 2-node. //console.log('qwq45', value, this.elements, parentNodeRef.childs.length, parentNodeRef.getParentNode().elements) //console.log('qwq41', value, this.elements, parentNodeRef.childs[0].elements, parentNodeRef.elements, parentNodeRef.getParentNode().elements) //console.log('qwq43', value, this.elements, parentNodeRef.elements, parentNodeRef.getParentNode().elements) //console.log('qwq45', value, this.elements, parentNodeRef.elements, parentNodeRef.childs[0].elements, parentNodeRef.childs[1].elements) } } Tree234.prototype.delete = function(value){ if(this.root.elements.length === 1 && this.root.childs.length === 0){ this.root.elements = []; return; } let deleteNode = this.root.search(value); if(deleteNode.childs.length === 0){ deleteNode.delete(value); } else { // Find the predecessor of the node containing x // search nearest node let checkingNode = deleteNode; let pos = 0; for(let i = 0; i < checkingNode.elements.length; i += 1){ if(value === checkingNode.elements[i]){ pos = i; break; } } checkingNode = checkingNode.childs[pos]; while(true){ if(checkingNode.childs.length === 0){ break; } checkingNode = checkingNode.childs[checkingNode.childs.length-1]; } let predecessorValue = checkingNode.elements[checkingNode.elements.length-1]; checkingNode.delete(predecessorValue); deleteNode.elements[pos] = predecessorValue; } if(this.root.childs.length === 2 && this.root.childs[0].elements.length === 1 && this.root.childs[1].elements.length === 1){ this.root.elements = [this.root.childs[0].elements[0], this.root.elements[0], this.root.childs[1].elements[0]]; if(this.root.childs[0].childs.length !== 0){ this.root.childs = [this.root.childs[0].childs[0], this.root.childs[0].childs[1] , this.root.childs[1].childs[0], this.root.childs[1].childs[1]]; } else { this.root.childs = []; } } }References[硬核图解红黑树并手写实现](https://juejin.cn/post/6947666874226180133)B-Trees visualization2-3-4 Trees: A Visual Introduction2-3-4 Trees algorithmtutor.com[【考研】数据结构:红黑树(2022新增考点)](https://blog.csdn.net/qq_34438969/article/details/121010725?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2~default~CTRLIST~default-1-121010725-blog-78073742.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2~default~CTRLIST~default-1-121010725-blog-78073742.pc_relevant_default&utm_relevant_index=1)算法导论习题练习——红黑树的插入和删除
2022年07月07日
2 阅读
0 评论
0 点赞
2021-07-30
【学习笔记】Hashtable学习笔记 & uthash 的简单使用
序言众所周知,哈希表是时间复杂度为o(1)的一种查找方式。当要查找的数据比较多,又没有什么规律时,因为哈希表的时间复杂度几乎不随着数据量的增加而增大,于是使用哈希表就是一种不错的数据查找方式。之后嘛,我在做 leetcode 的一道题的时候,使用的是C语言,但有需要使用到哈希表的数据结构,于是就自己手撸了一个。结果嘛,因为是自己造轮子,所以效果自然不是特别理想。后来才知道 leetcode 里的c语言可以直接使用 UT_Hash 这个库,所以这里也简单记录下用法。(简介略)哈希表这种数据结构有什么用呢?这里简单举个我记忆中之前在某本算法书里看到的例子:比如你有一家水果店,店里就卖两种水果:苹果卖5元,香蕉卖10元。那么各商品的价格可以用下表来表示:fruit.namefruit.priceApple5Banana10到目前为止,我们还只有两种水果,若是客人拿着水果来向我们询问价格的话,我们可以很轻松地写出一个函数:# 伪代码 def get_price(fruit): if fruit == 'Apple': return 5 else: return 10好,现在我们给获取价格函数还非常简单,但是,若是随着我们水果店之后的发展,水果的数量变多了呢:fruit.namefruit.priceApple5Banana10Watermelon8Peach12Grape9..........水果数量躲起来之后,再一个个if...else...判断就会比较麻烦了。不过我们还可以使用遍历的方法去查询:# 伪代码 def get_price(fruit): for item in fruits: if item.name == fruit: return item.price虽然这样的函数的编写还是非常容易的。但是很显然,这样的查询的时间复杂度为 o(n) 。随着水果数量的增加,查询所需的时间也会比较快的增加。有没有办法能降低这一过程的时间复杂度呢?在储存所有的水果的价格的时候,我们会开辟一段内存用于储存水果的价格。所以,查询的过程就可以看作通过给定输入的水果名称得到储存着水果价格的地址的函数。所以,只要能降低这个函数的时间复杂度,那就好办了。仔细观察一下上面的水果,我们可以发现他们的首字母都不同,那么,我们可以用这么一个方式去储存水果的价格:先开辟长度为26的一段内存空间,然后再按照26个英文字母的排序将它们放到指定的空间。即:fruits[x]fruit.namefruit.price0Apple51Banana102NullNull...NullNull6Grape9...NullNull22Watermelon8...NullNull25NullNull这样的话,之后查询水果的价格就可以又方便又快捷了: # 伪代码 def get_price(fruit): return fruits[fruit[0] - 'A'].price好的!我们成功地把查询水果价格的时间复杂度降到了 o(1) ,来再多的水果也不怕!当然,你可能会反驳:世界上又不是只有这么点水果,要是遇上首字母相同的水果该怎么办啊!不要慌\~,这种问题我们还是有很多解决方法的。我这里举两种例子。假如我们又多了个叫做 berry 的水果吧,它和我们的 banana 重复啦:其一就是:虽然我们遇到了首字母相同的水果,但这毕竟是少数。我们可以先不直接储存水果的价格,而是储存一个包含所有相同首字母的水果的链表的首个元素地址,这样子,我们在查询 B开头的水果的时候,虽不能直接定位到 Berry ,但 B 开头的水果已经比所有的水果少多了,我们再在这些水果中遍历查找指定的水果,速度还是比直接遍历查找快多了。其二就是:虽然这两个水果的首字母重复了,但它们的第二个字母不同啊,所以我们可以开辟 26*26=676 长度的内存,按照它们的前两个字母插入指定的位置。查找的时候再按照它前两个字母来计算出对应的地址。就算水果前两个字母都相同了,我们也还可以继续扩展到第三位,第四位...总不可能两个水果名字完全相同吧。以上,我们就可以算是找到了一种可以比较快速定位要查找的目标的算法了。虽然我们可以看到,在这个过程中有不少的内存被浪费掉了,不过确实是降低了查询的时间复杂度,可以看作一种“空间换时间”了。上面我们讨论的做法其实就和哈希表的思想比较接近了。通过区首字母来获取地址的方式可以看作哈希表的哈希函数,只不过一般的哈希表都不会使用这么简单的哈希函数,而是使用一些碰撞率更低的函数,以让插入哈希表的元素能够更均匀的分布在内存中。而上面遇到的首字母相同的情况就可以看作发生了哈希碰撞了。下面就介绍一下 uthash 这个比较成熟的哈希表的库的使用。UT_Hash 在 C 语言中的运用那么我这里就简单介绍下 uthash 这个库的使用。首先我们要知道的是,哈希表可以看作从一个“东西”到另一个“东西”的映射。例如在之前的例子中,通过水果的名字“字符串”到它的价格“实数”的映射。在进行操作时,我们输入水果的名字,通过哈希函数从而得到储存着这种水果的价格的地址。graph LR A[Fruit] -- "Name: Apple" --> B(Hash Function) B --"Address: 0x123" --> C[Price]对于C语言这样的静态类型语言,我们在指定哈希表之前就应该确定好键值和查找对象的类型。为了简化一些,下面的示例中使用 int 为键值类型,字符串为要找的值的类型。例如现实生活中通过学号去查找这个学号对应的学生的姓名的情况。这种查找若是采用逐一比较的方式的话时间复杂度为 o(n) ,当学生数量很多的时候效率就会非常低。虽然采用例如二分查找的方式能有 o(logn) 的时间复杂度,但很多情况下,学号在最大值和最小值之间并不是均匀分布的,再加上一些其他的原因,二分查找不一定是最优解。所以这里使用哈希表的方式查找。uthash 的使用需要先包含相应的库并建立对应的结构体:#include"uthash.h" struct my_struct { int id; /* key */ char name[10]; UT_hash_handle hh; /* makes this structure hashable */ }; 定义好了一个结构体之后用下面的代码实例化一个哈希表:struct my_struct *g_users = NULL;有了这些之后就可以对这个哈希表进行增删查改的操作了。1. 查下面的代码用来查找指定的哈希表中是否存在着指定键的值。int ikey = 123; // 指定要查找的键(例如学号)。 struct my_struct *s; // 查找到的结果将保存在这里(例如姓名)。 HASH_FIND_INT(g_users, &ikey, s ); // uthash 提供的查找函数。 if(s) // exists.可以看到,其中的 HASH_FIND_INT 就是这段代码的核心。通过示例代码我们不难看出它的结构。它的三个参数分别代表了:在哪个哈希表(g_users)中查找关键字为某个值(&ikey)的数据并保存在这个地址(s)中。2. 增接下来介绍下增加元素的部分:void add_user(int ikey, char *value_buf) { struct my_struct *s; HASH_FIND_INT(g_users, &ikey, s); // 插入前先查看key值是否已经在hash表g_users里面了 if (s==NULL) { // g_users 内不存在 ikey 时才进行插入操作。 s = (struct my_struct*)malloc(sizeof(struct my_struct)); // 为插入的元素开辟空间。 s->ikey = ikey; HASH_ADD_INT(g_users, ikey, s ); // 执行插入操作。 } strcpy(s-> value, value_buf); // 别忘了给s赋值。 } 同样,上面的代码也是比较显然了。需要注意的就是 uthash 要求 key 必须是唯一的,所以这里我们在插入前要先查找是否存在同 key 的元素,不存在再进行插入。由于uthash要求键(key)必须唯一,而uthash内部未对key值得唯一性进行很好的处理,因此它要求外部在插入操作时要确保其key值不在当前的hash表中,这就需要,在插入操作时,先查找hash表看其值是否已经存在,不存在在时再进行插入操作,在这里需要特别注意以下两点:插入时,先查找,当键不在当前的hash表中时再进行插入,以确保键的唯一性。需调用插入接口函数时需要明确告诉接口函数,自己定义的键变量的名字是什么。之后在 HASH_ADD_INT 内,这个函数也有三个参数。其含义就相当于建立一个在 g_users 内,从 ikey 到 s 的一个映射。有了这个映射,我们之后再 g_users 内查找的时候,输入 ikey 的时候就可以找到 s 了。不过需要注意的是,这个时候我们还是仅建立了从 ikey 到 s 的地址的映射,与 s 内的具体的内容无关。所以,之后我们还要手动给 s 这个结构体内的 name 进行赋值。3. 删接下来是删除操作,用于在指定的哈希表中删除一个指定的元素:void delete_user(int ikey) { struct my_struct *s = NULL; HASH_FIND_INT(g_users, &ikey, s); if (s!=NULL) { HASH_DEL(g_users, s); free(s); } } 同样,这一部分也还是比较容易理解的,先查找到要删除的元素,然后去删除。删除操作的接口函数为 HASH_DEL ,只需要告诉该接口要释放哪个 hash 表(这里是 g_users )里的哪个节点(这里是 s ),需要注意:释放申请的hash结构体变量,uthash函数只将结构体从hash表中移除,并未释放该结构体所占据的内存。以上,就实现了一个哈希表的增删查改操作了。什么,你问改在哪里?前面都那么多示例了,你先查到对应的结构体然后进行修改不久可以了嘛。除了常见的增删查改操作外,uthash还有一些其他的功能,这里简单摘录下。(下面基本转载于《c开源hash项目 uthash的用法总结》[1]。)4. 清空 Hash 表void delete_all() { struct my_struct *current_user, *tmp; HASH_ITER(hh, users, current_user, tmp) { HASH_DEL(g_users,current_user); free(current_user); } } 5. 统计 Hash 表中已存在的元素数unsigned int num_users; num_users = HASH_COUNT(g_users); printf("there are %u items\n", num_users); 6. 遍历元素void print_users() { struct my_struct *s; for(s=g_users; s != NULL; s=s->hh.next) { printf("user ikey %d: value %s\n", s->ikey, s->value); } } uthash 的实际使用在 uthash 的官方github页面下有一篇使用示例[3],已经写的比较详细,这里不再赘述。本想在这里放一段自己在leetcode里实际使用到uthash的代码来着,不过因为时间久远已经找不到了,就之后再补吧。。Referencesc开源hash项目 uthash的用法总结C语言中哈希表uthash的使用uthash/tests/example.c
2021年07月30日
2 阅读
0 评论
0 点赞
2021-06-09
【学习笔记】FourierTransform-关于二维DCT变换可以被表示为矩阵相乘这档事
前言暂略。前置知识需要一定编程基础,理解连续/离散傅里叶变换原理与计算方法。正文首先,让我们来看一下DCT的公式:$$ F(u)= \begin{cases} \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}f(x), & n\ne m \\ \frac{2}{\sqrt{N}}\sum_{x=0}^{N-1}f(x)\cos\frac{(2x+1)u\pi}{2N}, &n=m \end{cases} $$具体推导过程可见前文。上式即为DCT的公式表达。而在具体到计算时,例如要处理一个长度为8的时域信号时,可以展开为:通过观察我们可以发现在变换的具体表达上很像矩阵相乘的样子。因此,我们可以进一步改写为:其中,最左边的$[F(u)]$为变换后的矩阵,即为频域的矩阵。最右边的$f[x]$为变换前的时域矩阵。而中间的矩阵在N确定时为一确定矩阵,我们把它称之为DCT的变换矩阵A。而A可以写为: $$ A[x,y]= \begin{cases} \frac{1}{\sqrt{N}}, & y= 0 \\ \frac{2}{\sqrt{N}}\cos\frac{(2x+1)y\pi}{2N}, &y\ne 0 \end{cases} $$所以,我们可以把一维的DCT变换表现为矩阵相乘的形式,即:$F=A[f(x)]$。这是一维的情况,那么二维的呢?我们首先来看下二维离散余弦变换的一般公式(为了写的方便稍微换了下写法):$$ F(u,v)=\alpha(u)\alpha(v)\sum_{x=0}^{M-1}\sum_{y=0}^{N-1}f(x,y)\cos\frac{(2x+1)u\pi}{2M}\cos\frac{(2y+1)v\pi}{2N} $$其中:$$ \alpha(u)= \begin{cases} \frac{1}{\sqrt{N}}, & u= 0 \\ \frac{2}{\sqrt{N}}, &u\ne 0 \end{cases} \alpha(v)= \begin{cases} \frac{1}{\sqrt{N}}, & v= 0 \\ \frac{2}{\sqrt{N}}, &v\ne 0 \end{cases} $$可以看到,二维的DCT表达起来和一维的DCT变换差不多,基本上就是在原始数据的x方向做一次一维DCT,然后再在y方向再做一次一维 DCT。而事实上也就是那样。所以对于一个指定的$[f(x,y)]$,我们要做的就是对它的每一列都做一次DCT变换,再转置一次后再做一次DCT变换,最后再转置回来,就完成了二维的DCT。具体可以表示为:$$ [F(u,v)]=(A((A[f(x,y)])^T)) ^T $$再因为转置矩阵的性质:$$ (AB)^T = B^T A^T $$所以我们可以进一步化简:$$ [F(u,v)]=(A((A[f(x,y)])^T)) ^T\\ =(A([f(x,y)]^T A^T)) ^T\\ =([f(x,y)]^T A^T) ^T A^T\\ =A[f(x,y)]A^T $$(写的格式有点问题见谅。。)所以我们就得到了二维DCT变换公式:$$ F(u,v)=A[f(x,y)]A^T $$编码实现为了进一步巩固学习内容,这里使用C语言写一个小DEMO,实现二维DCT的效果。代码除了math库和stdio库外不包含任何第三方库。编写完成后会使用matlab对所得结果进行验证。首先,进行DCT需要用到矩阵运算,这里先给出简易的矩阵运算代码。typedef struct { int rows; int cols; double** p; } Matrix; Matrix initMatrix(int rows, int cols) { Matrix mat; mat.rows = rows; mat.cols = cols; mat.p = (double**)malloc(sizeof(double*)*rows); // new double*[rows];//分配rows_num个指针 for (int i = 0; i < rows; ++i) { mat.p[i] = (double*)malloc(sizeof(double)*cols); // new double[cols];//为p[i]进行动态内存分配,大小为cols } return mat; } Matrix initMatrixWithValue(int rows, int cols, double* p) { Matrix mat = initMatrix(rows, cols); for (int i = 0; i < mat.rows; i++) { for (int j = 0; j < mat.cols; j++) { mat.p[i][j] = *p++; } } return mat; } Matrix matrixTrans(Matrix mat) { Matrix res = initMatrix(mat.cols, mat.rows); for (int i = 0; i < mat.rows; i++) { for (int j = 0; j < mat.cols; j++) { res.p[j][i] = mat.p[i][j]; } } return res; } Matrix matrixMul(Matrix m1, Matrix m2){ Matrix res = initMatrix(m1.rows, m2.cols); for (int i = 0; i < m1.rows; i++) { for (int j = 0; j < m2.cols; j++) { res.p[i][j] = 0; for (int k = 0; k < m1.cols; k++) { res.p[i][j] += (m1.p[i][k] * m2.p[k][j]); } } } return res; } //矩阵显示 void showMatrix(Matrix mat) { //cout << rows_num <<" "<<cols_num<< endl;//显示矩阵的行数和列数 for (int i = 0; i < mat.rows; i++) { for (int j = 0; j < mat.cols; j++) { printf("%.4f ", mat.p[i][j]); } printf("\n"); } printf("\n"); }上述代码实现了矩阵的初始化,加法,乘法和转置运算。Matrix get4x4DCTMatrixL(){ Matrix mat = initMatrix(4, 4); for(int i = 0;i < 4;i++){ for(int j = 0;j < 4;j++){ double c = (i==0) ? sqrt(1.0/4) : sqrt(2.0/4); mat.p[i][j] = c * cos( (j + 0.5) * PI * i / 4); } } return mat; }这段代码即为生成DCT变换矩阵的代码。这里是一个处理4x4的数据的矩阵。之后若是要进行DCT变换,只要按照上文去做计算即可。为了进行测试,这里我先用matlab生成一段数据用于测试。代码如下:clc;clear f = (rand(4,4)*100); dct2(f);f = 40.1808 18.3908 90.2716 33.7719 7.5967 23.9953 94.4787 90.0054 23.9916 41.7267 49.0864 36.9247 12.3319 4.9654 48.9253 11.1203 ans = 156.9409 -54.8586 -28.9792 51.3964 43.0922 -19.6215 -0.1741 18.9064 -26.9619 28.4906 -3.5949 26.3422 -6.7750 39.6837 -3.5258 -9.3417接下来我们就在c语言中对上述数据进行计算,并对答案进行比较。代码如下:#include <stdio.h> #include <stdlib.h> #include <math.h> #define PI 3.1415926f typedef struct { int rows; int cols; double** p; } Matrix; Matrix initMatrix(int rows, int cols) { Matrix mat; mat.rows = rows; mat.cols = cols; mat.p = (double**)malloc(sizeof(double*)*rows); // new double*[rows];//分配rows_num个指针 for (int i = 0; i < rows; ++i) { mat.p[i] = (double*)malloc(sizeof(double)*cols); // new double[cols];//为p[i]进行动态内存分配,大小为cols } return mat; } Matrix initMatrixWithValue(int rows, int cols, double* p) { Matrix mat = initMatrix(rows, cols); for (int i = 0; i < mat.rows; i++) { for (int j = 0; j < mat.cols; j++) { mat.p[i][j] = *p++; } } return mat; } Matrix matrixTrans(Matrix mat) { Matrix res = initMatrix(mat.cols, mat.rows); for (int i = 0; i < mat.rows; i++) { for (int j = 0; j < mat.cols; j++) { res.p[j][i] = mat.p[i][j]; } } return res; } Matrix matrixMul(Matrix m1, Matrix m2){ Matrix res = initMatrix(m1.rows, m2.cols); for (int i = 0; i < m1.rows; i++) { for (int j = 0; j < m2.cols; j++) { res.p[i][j] = 0; for (int k = 0; k < m1.cols; k++) { res.p[i][j] += (m1.p[i][k] * m2.p[k][j]); } } } return res; } //矩阵显示 void showMatrix(Matrix mat) { //cout << rows_num <<" "<<cols_num<< endl;//显示矩阵的行数和列数 for (int i = 0; i < mat.rows; i++) { for (int j = 0; j < mat.cols; j++) { printf("%.4f ", mat.p[i][j]); } printf("\n"); } printf("\n"); } Matrix get4x4DCTMatrixL(){ Matrix mat = initMatrix(4, 4); for(int i = 0;i < 4;i++){ for(int j = 0;j < 4;j++){ double c = (i==0) ? sqrt(1.0/4) : sqrt(2.0/4); mat.p[i][j] = c * cos( (j + 0.5) * PI * i / 4); } } return mat; } int main(){ Matrix dctm = get4x4DCTMatrixL(); double testF_a[4*4] = { 40.1808, 18.3908, 90.2716, 33.7719, 7.5967, 23.9953, 94.4787, 90.0054, 23.9916, 41.7267, 49.0864, 36.9247, 12.3319, 4.9654, 48.9253, 11.1203 }; Matrix testF = initMatrixWithValue(4, 4, testF_a); Matrix tmp = matrixMul(dctm, testF); Matrix ans = matrixMul(tmp, matrixTrans(dctm)); showMatrix(ans); return 0; }我们把它编译运行试试:[ame@RaMizy ws]$ gcc test_dct.c -o test_dct -lm && ./test_dct 156.9409 -54.8586 -28.9792 51.3964 43.0922 -19.6215 -0.1741 18.9063 -26.9619 28.4906 -3.5949 26.3423 -6.7750 39.6837 -3.5258 -9.3417 可以看到,我们的代码计算结果与matlab的结果在合理的误差范围内基本一致。结果存在的微小误差可认为来自于不同的计算方式及精度带来的截断误差。结尾至此,已经基本讲完了DCT的矩阵相关。但由于时间所限,我也不可能讲的很完整,也难免会有些问题。就之后再补充吧。原本也想讲下像是蝶式算法之类的快速算法,就之后再细写吧。reference先放这里了。Reference二维离散余弦变换(2D-DCT)DCT变换展开时用到的示例图片DCT变换自学笔记离散余弦变换(DCT)的来龙去脉图像的DCT算法 matlab代码参考快速离散余弦变换代码实现(FDCT)H.264中整数DCT变换,量化,反量化,反DCT究竟是如何实现的?H264___DCT蝶形算法____理解H264-整数DCT变换和蝶形变换代码实现
2021年06月09日
14 阅读
0 评论
0 点赞
2019-12-06
【学习/笔记】RSA算法的c++实现
emmm先转载一篇文章吧RSA算法原理(一)非常推荐的一篇文章,我原本就想写个讲RSA算法的文章,然后发现这篇文章基本就可以满足我的要求了,所以就直接转过来了。这里主要讲c++代码。#include <bits/stdc++.h> #include <math.h> #include<ctime> using namespace std; #define randomInt(a,b) (rand()%(b-a+1)+a) typedef long long int ll; #define int ll struct rsakeys{ int p, q, n, fn, d, e; }; rsakeys* rsakey; ll mod_mul(ll a, ll b, ll mod){ ll res = 0; while (b){ if (b & 1) res = (res + a) % mod; a = (a + a) % mod; b >>= 1; } return res; } ll mod_pow(ll a, ll n, ll mod){ ll res = 1; while (n){ if (n & 1) res = mod_mul(res, a, mod); a = mod_mul(a, a, mod); n >>= 1; } return res; } // Miller-Rabin随机算法检测n是否为素数 bool Miller_Rabin(ll n){ if (n == 2) return true; if (n < 2 || !(n & 1)) return false; ll m = n - 1, k = 0; while (!(m & 1)) { k++; m >>= 1; } for (int i = 1; i <= 20; i++) // 20为Miller-Rabin测试的迭代次数 { ll a = rand() % (n - 1) + 1; ll x = mod_pow(a, m, n); ll y; for (int j = 1; j <= k; j++) { y = mod_mul(x, x, n); if (y == 1 && x != 1 && x != n - 1) return false; x = y; } if (y != 1) return false; } return true; } int gcd(int a,int b){ int r; while(b){ r=a%b; a=b; b=r; } return a; } int creat_prime(){ int tmp = 4; while(!Miller_Rabin(tmp))tmp=rand(); return tmp; } int create_keys(rsakeys* key){ srand((unsigned)time(NULL)); key->p = creat_prime(); cout<<"Your p is: "<<key->p<<endl; key->q = creat_prime(); cout<<"Your q is: "<<key->q<<endl; key->n=key->p*key->q; cout<<"Your n is: "<<key->n<<endl; key->fn = (key->p-1) * (key->q-1); cout<<"Your fn is: "<<key->fn<<endl; while(1){ key->e = rand()%key->fn; if(gcd(key->e,key->fn)==1)break; } cout<<"Your e is: "<<key->e<<endl; int k = 1; while((k*key->fn+1)%key->e){ k++; } key->d = (k*key->fn+1)/(key->e); cout<<"Your d is: "<<key->d<<endl; } int create_keys_by_pq(int p, int q, rsakeys* key){ cout<<p<<" "<<q<<endl; key->n = p * q; cout<<"Your n is: "<<key->n<<endl; key->fn = (p-1) * (q-1); cout<<"Your fn is: "<<key->fn<<endl; while(1){ key->e = rand()%key->fn; if(gcd(key->e,key->fn)==1)break; } cout<<"Your e is: "<<key->e<<endl; int k = 1; while((k*key->fn+1)%key->e){ k++; } key->d = (k*key->fn+1)/(key->e); cout<<"Your d is: "<<key->d<<endl; } int write_to_file(rsakeys* key){ ofstream d, e, n; d.open("d"); d<<key->d; e.open("e"); e<<key->e; n.open("n"); n<<key->n; d.close();e.close();n.close(); return 0; } int read_file(rsakeys* key){ ifstream d, e, n; d.open("d"); d>>key->d; e.open("e"); e>>key->e; n.open("n"); n>>key->n; d.close();e.close();n.close(); return 0; } signed main(){ rsakey = (rsakeys*)malloc(sizeof(rsakeys)); cout<<"============================================================"<<endl; cout<<"1. Creat keys and write to file."<<endl; cout<<"2. Creat keys by given p and q and write to file."<<endl; cout<<"3. Read keys from file."<<endl; cout<<"4. Encrypt a number."<<endl; cout<<"5. Decrypt a number."<<endl; cout<<"============================================================"<<endl; int d, e, n; while(1){ char command[64]; ll msg; ll key; ll inn; scanf("%s",command); if(!strcmp(command,"1")){ create_keys(rsakey); write_to_file(rsakey); } if(!strcmp(command,"2")){ int p,q; cin>>p>>q; create_keys_by_pq(p,q,rsakey); write_to_file(rsakey); } if(!strcmp(command,"3")){ read_file(rsakey); } if(!strcmp(command,"4")){ scanf("%d",&msg); cout<<mod_pow(msg,rsakey->e,rsakey->n)<<endl; } if(!strcmp(command,"5")){ scanf("%d",&msg); cout<<mod_pow(msg,rsakey->d,rsakey->n)<<endl; } } return 0; }就酱啦,再扔篇参考文章溜了。。。[[2]RSA密码的实现-你也能看的懂的python实现方法][2]
2019年12月06日
4 阅读
0 评论
0 点赞
2019-11-26
【笔记/学习】c++实现b站弹幕姬
差不多是为了后续某个功能插件的开发,于是开了这么个坑。之后还可以学习下相关知识,同时由于考试腾不出太多时间学习新知识所以拿旧项目顶一下,于是就有了这篇文章。。Step1.查找b站弹幕的http请求随便点开一个b站的直播间,打开f12,点击网络,刷新下,找有没有弹幕的相关请求包。之后可以发现“msg”这个包点开,从内容看,应该就是我们要找的弹幕包了(这里先略去具体的分析过程)然后就是http请求包的具体分析了。从浏览器中可以看到请求的网址,消息头和相关参数,下一步我们就要用c++去模拟请求了。step2.WinInet库的简单使用虽然用c++模拟请求时可以直接用底层的socket去发送请求,但为了方便,所以还是去直接使用相关库了。wininet库有点类似python的request库,这里就简单介绍使用wininet库去请求了。首先是使用wininet库必须包含的头文件:#include <Windows.h> #include <wininet.h> #pragma comment(lib,"wininet.lib")这里本来想贴一个之前学习时对我帮助挺大的一个网站的,结果找不到了,只能凭着自己的记忆写了。。首先,我们看一眼刚才的请求包,得知请求的网址是http://api.live.bilibili.com/ajax/msg,接下来我们用wininet的函数将网址分解。这里简单贴一段示例代码,看完应该就知道这个函数怎么用了:展开查看void CrackUrl() { URL_COMPONENTS uc; char Scheme[1000]; char HostName[1000]; char UserName[1000]; char Password[1000]; char UrlPath[1000]; char ExtraInfo[1000]; uc.dwStructSize = sizeof(uc); uc.lpszScheme = Scheme; uc.lpszHostName = HostName; uc.lpszUserName = UserName; uc.lpszPassword = Password; uc.lpszUrlPath = UrlPath; uc.lpszExtraInfo = ExtraInfo; uc.dwSchemeLength = 1000; uc.dwHostNameLength = 1000; uc.dwUserNameLength = 1000; uc.dwPasswordLength = 1000; uc.dwUrlPathLength = 1000; uc.dwExtraInfoLength = 1000; InternetCrackUrl("http://hoge:henyo@www.cool.ne.jp:8080/masapico/api_sample.index", 0, 0, &uc); printf("scheme: '%s'\n", uc.lpszScheme); printf("host name: '%s'\n", uc.lpszHostName); printf("port: %d\n", uc.nPort); printf("user name: '%s'\n", uc.lpszUserName); printf("password: '%s'\n", uc.lpszPassword); printf("url path: '%s'\n", uc.lpszUrlPath); printf("extra info: '%s'\n", uc.lpszExtraInfo); printf("scheme type: "); switch(uc.nScheme) { case INTERNET_SCHEME_PARTIAL: printf("partial.\n"); break; case INTERNET_SCHEME_UNKNOWN: printf("unknown.\n"); break; case INTERNET_SCHEME_DEFAULT: printf("default.\n"); break; case INTERNET_SCHEME_FTP: printf("FTP.\n"); break; case INTERNET_SCHEME_GOPHER: printf("GOPHER.\n"); break; case INTERNET_SCHEME_HTTP: printf("HTTP.\n"); break; case INTERNET_SCHEME_HTTPS: printf("HTTPS.\n"); break; case INTERNET_SCHEME_FILE: printf("FILE.\n"); break; case INTERNET_SCHEME_NEWS: printf("NEWS.\n"); break; case INTERNET_SCHEME_MAILTO: printf("MAILTO.\n"); break; default: printf("%d\n", uc.nScheme); } }然后是代码:#define URL_STRING L"http://api.live.bilibili.com/ajax/msg"//Bilive API TCHAR szHostName[128]; TCHAR szUrlPath[256]; URL_COMPONENTS crackedURL = { 0 }; crackedURL.dwStructSize = sizeof(URL_COMPONENTS); crackedURL.lpszHostName = szHostName; crackedURL.dwHostNameLength = ARRAYSIZE(szHostName); crackedURL.lpszUrlPath = szUrlPath; crackedURL.dwUrlPathLength = ARRAYSIZE(szUrlPath); InternetCrackUrl(URL_STRING, (DWORD)URL_STRING, 0, &crackedURL);之后是和服务器建立连接:HINTERNET hInternet = InternetOpen(L"Mozilla/5.0 (Windows NT 6.1) AppleWebKit/535.1 (KHTML, like Gecko) Chrome/15.0.849.0 Safari/535.1", INTERNET_OPEN_TYPE_DIRECT, NULL, NULL, 0); if (hInternet == NULL) return -1; HINTERNET hHttpSession = InternetConnect(hInternet, crackedURL.lpszHostName, crackedURL.nPort, NULL, NULL, INTERNET_SERVICE_HTTP, 0, 0); if (hHttpSession == NULL) { InternetCloseHandle(hInternet); std::cout << GetLastError(); return -2; } HINTERNET hHttpRequest = HttpOpenRequest(hHttpSession, L"POST", crackedURL.lpszUrlPath, NULL, L"", NULL, 0, 0); if (hHttpRequest == NULL) { InternetCloseHandle(hHttpSession); InternetCloseHandle(hInternet); return -3; }这三个函数从名字应该就能基本理解它们的作用了,我自己也不是特别精通就不讲了,感觉学过socket编程的话应该不难理解emm。。然后就是向服务器发送请求了。#define _HTTP_ARAC L"Content-Type: application/x-www-form-urlencoded\r\n" char _HTTP_POST[] = "roomid=5322&csrf_token=&csrf=&visit_id=";//roomid parameters. DWORD dwRetCode = 0; DWORD dwSizeOfRq = sizeof(DWORD); if (!HttpSendRequest(hHttpRequest, _HTTP_ARAC, 0, _HTTP_POST, sizeof(_HTTP_POST)) || !HttpQueryInfo(hHttpRequest, HTTP_QUERY_STATUS_CODE | HTTP_QUERY_FLAG_NUMBER, &dwRetCode, &dwSizeOfRq, NULL) || dwRetCode >= 400) { InternetCloseHandle(hHttpRequest); InternetCloseHandle(hHttpSession); InternetCloseHandle(hInternet); return -4; }经过实验,发现在基本的请求头的基础上必须要加上content-type,服务器才能正确的返回json数据,参数方面只需要roomid,其他参数都留空就可以正常使用。HttpSendRequest()就是发送http请求的函数了,应该不难看懂吧。最后就是接收服务器返回的数据了#define READ_BUFFER_SIZE 1024 std::string strRet = ""; BOOL bRet = FALSE; char szBuffer[READ_BUFFER_SIZE + 1] = { 0 }; DWORD dwReadSize = READ_BUFFER_SIZE; while (true){ bRet = InternetReadFile(hHttpRequest, szBuffer, READ_BUFFER_SIZE, &dwReadSize); if (!bRet || (0 == dwReadSize)){ break; } szBuffer[dwReadSize] = '\0'; strRet.append(szBuffer); }代码应该不难看懂吧,不过最初写这段代码的时候我被坑过。虽然InternetReadFile()可以指定自己要接收的字节数,但实际每次接收的数据不一定是你写的字节数,最后总会有几个字节是乱码。所以必须用到函数给出的接收到的字节数,在后面手动加一个'\0'才行。这样,我们就得到了想要的数据并储存到string里了。step3.项目的c++实现这里json数据的解析我用的是CJsonObject,用法参考我上篇转载的博文。这里有个需要注意的地方:我们每次的请求实际上返回的是最近的10条弹幕的数据,而我们要的是持续的弹幕姬,所以我的做法是循环进行请求,每次请求后与上次的请求进行比较,打印出不同的数据,来达到想要的效果。typedef struct { int uid; std::string name; std::string time; std::string text; } DM_DATA; DM_DATA old_list[10] = { 0 }; DM_DATA new_list[10] = { 0 };这里简单定义一个结构体,并认为:假如弹幕的发送者uid,发送时间,发送内容都相同的话,就认为这是同一条弹幕,就不打印。如果有人在一秒内发送多条相同的弹幕那我也没办法啦╮( ̄▽ ̄)╭不过这种情况并不常见而且也没多大影响。neb::CJsonObject oJson(strRet); for (int i = 0; i < 10; i++) { oJson["data"]["room"][i].Get("uid", new_list[i].uid); if (new_list[i].uid == 0)break; oJson["data"]["room"][i].Get("nickname", new_list[i].name); oJson["data"]["room"][i].Get("timeline", new_list[i].time); oJson["data"]["room"][i].Get("text", new_list[i].text); } for (int j = 0; j < 10; j++) { int k = 1; for (int i = 0; i < 10; i++) { if (old_list[i].uid == new_list[j].uid && old_list[i].name == new_list[j].name && old_list[i].time == new_list[j].time && old_list[i].text == new_list[j].text)k = 0; } if (k)std::cout << "[" << new_list[j].name << "]" << new_list[j].text << std::endl; } for (int i = 0; i < 10; i++) { old_list[i].uid = new_list[i].uid; old_list[i].name = new_list[i].name; old_list[i].time = new_list[i].time; old_list[i].text = new_list[i].text; } Sleep(3000);neb::CJsonObject oJson(strRet);这条语句用来处理刚刚接收的json数据,然后下面的三个循环应该很好理解,第一个循环用来把接收到的数据存入新数组,第二个循环进行新数组与旧数组的比较,如不相同则打印,第三个循环把新数组的内容存入旧数组中。最后的Sleep(3000);用来防止请求过快被服务器ban。最后我们需要的就是循环了,由于有点偷懒的原因,所以最后就加一句goto label;,把label:放在HttpSendRequest 的前面就可以了。这样程序的设计就基本完成了。不过还需要注意的一点是,服务器返回的数据是utf8编码的,而大多数中文的windows默认是GBK编码,所以直接转换数据会乱码。最开始的时候我从网上copy了个utf8转gbk的函数,不过现在有更简单的方法,直接在代码的最前面加上一句system("chcp 65001");把控制台的编码换成utf8就ok了。最后放个我在github上的这个项目的旧版本吧:https://github.com/panedioic/CPPDanmaku参考资料:[[1]【python】b站直播弹幕获取][2]by 猫先生的早茶[[3]WinInet编程详解]4获取bilibili直播弹幕的WebSocket协议][3]by 炒鸡嗨客协管徐by skilledprogrammer[[4]C++实现Http Post请求][5]by DoubleLi[[5]WinInet使用详解][6]by analogous_love
2019年11月26日
4 阅读
0 评论
0 点赞