特色

交换友链~~~

RT >_<

博主大学生、计算机领域、原OIer,自认为计算机水平还是不错哒,希望和各类朋友多多交流,也希望与各位感兴趣的博主多多交流,当然,重点是想要交换一波友情链接,同类网站、个人网站优先。

另外,笔者想好好维护这个博客,并作为个人性质,所以谢绝任何有商业推广性质的网站交换友链哦~

联系QQ:519954392

邮箱:maohanyang789@163.com

往事:大学物理,一门感触深刻的课程

之前常问,计算机这个专业根本和大学物理不沾边,学校怎么会将大学物理设为必修课呢?现在看来,最期末结课时间,最令我感触深刻的,竟然就是这个曾经最看不起的课程了。

老毕,毕楷杰,选课的时候还真以为是中国人呢,通过幽默,细腻的教学方式,深深感动了一个班的学生。

每次专门回答Zero等奇怪问题的Zero Position,专门抽最后一排回答问题的有趣规则,每逢节日的奇装异服,还有家庭表演,这就是用心吧。

课程中的点点滴滴越发模糊,但是每节课,总会有那么一些无法忘记的经典。诸如“企鹅与中国人”这个我现在都不知道要表达什么意思的梗,短波杀手“鸽子pupu”,物理学之精粹“Parsimony”,不知道已经说错多少年的“广义双节棍”。

课程人数从上学期的7-8排,缩减了2/3左右,但是这个的原因,大概仅仅是现在GPA至上的产物吧。否则完全无法理解为什么这样一个老师会导致学生的净流出?不过我并不在意,即使这次考试没有能够及格,我也绝不会后悔。而且最后留下的都是真爱了吧。

在薛定谔那只奇奇怪怪的猫的注视下,课程走到了尾声,故写下文章用于记忆~

SharedApplication: Linux Shared Memory Wrapper in C++, Lockfree Queue

Introduction

SharedApplication is a class used for sharing data between processes, support malloc between multi-process and could be derived to create multi-process data structure.

SharedQueue is a lockfree queue with fixed capacity, derived from the SharedApplication. Easy to use.

Code

Github:https://github.com/mhy12345/SharedApplication

Usage

SharedApplication

Create a SharedApplication instance with a unique APPKEY. The APPKEY is used to tell the operating system which Shared Memory you are going to alloc.

Then, we can do some basic configuration to our application.

Set the size of the memory you are going to alloc, and this must called before start. If it wasn’t called, then the default size will be 1024 bytes.

Some other configurations are also available.

After the configurations, you can start the sApp, simple write:

Then, in you program, you can use malloc to alloc memory.

In other process, if you use the same APPKEY, and use same order of malloc, and same size, then the contents in the memory allocated should be synchronized.

Shared Queue

The SharedQueue is a private inherited form the SharedApplication, means you can just replace SharedApplication with SharedQueue.

In the main function, you can use  sQueue like a normal queue.

Attentions

  • In the SharedApplication, make sure you alloc each memory block using the same order and size
  • The destructive function must be called, otherwise the shared memory cannot be deleted.

SharedApplication: 共享内存操作原理

共享内存是Linux里面一个进程通讯的实现机制,通过系统API将同一块内存块挂载在到两个进程的内存地址空间中,从而实现共享内存的操作。

对于一块共享内存,我们用Key和Id进行标识,Key为用户自定义的一个值,不同进程倘若使用了同一个Key,即视为他们需要同一块共享内存。通过Key,用户可以向系统申请开一个指定大小的共享内存,并返回这块内存的内部标识Id,之后的挂载操作都需要用Id进行制定。

有关共享内存的API都封装在了<sys/shm.h>文件中,具体有

通过自定义Token新建共享内存,并返回标识符: appId = shmget(TOKEN,size,0666)

通过标识符挂在已经建好的共享内存到本地内存空间: ptr = shmat(appId,NULL,0)

取消挂载: shmdt(ptr)

删除共享内存: shmctl(appId,IPC_RMID,NULL)

每一次需要共享内存,强行调用这些语句看起来比较的繁琐,因此我希望写一个共享内存的操控框架,使得每次只需要极少的代码,就可自动完成诸如共享内存挂载,新建等要求。这也是SharedApplication的编写背景。

 

VHDL学习笔记

VHDL学习笔记

  • entity/architecture:
    • entity:实体,描述所设计的系统的外部接口信号,定义电路设计中所有的输入和输出端口
    • architecture:结构体 ,描述系统内部的结构和行为,理解为实体的派生类,实体只是给定了输入输出的信号类型,而具体输入输出的如何关联,是由architecture决定
    • generic:类属,对于实体外加一些属性定义???
  • 端口方向
    • in
    • out
    • inout
    • buffer
  • process:进程,进程间并行,进程内部串行计算,进程的参数表示进程对于哪一个信号的变化敏感

相关资源

VHDL英文版文档:https://www.nandland.com/vhdl/tutorials/index.html

 

无锁数据结构设计 之 内存顺序实际表现

这是mhy12345的无锁数据结构教程的第四篇,在详解了C++内存顺序之后,谈谈C++内存顺序在实际运行中的一些影响。

从原理上出发看看C++内存顺序的含义:是由于计算机缓存等内存结构性质导致的线程间单原子变量读写互相不可见的情形。

不过,稍微仔细想想,发现这其实只是一种理论概率上的情形。

首先在考虑内存顺序的误差时,我们先举一个锁的例子——

锁,是为了防止线程之间的资源竞争,

假设一个线程在1%的时间需要独占某一个资源,两个没有加锁的线程产生了竞争导致程序崩溃的概率1%

则,在某一时刻,两个线程同时占有某资源且发生崩溃的概率应为10^{-6}

别看这概率很小,但是我们的程序是若干时点的概念,我们若将时点设为10^6个(这个数应该是有一段程序运行间线程期望切换次数决定的),则发生崩溃的概率为

    \[(1-10^{-6})^{10^6}-1 = 63%\]

因此我们发现,对于线程而言,加锁确实是必不可少的。

不过确实给我们一个提示:为什么我们一定要研究理论上那一丁点的小概率事件呢?假设我告诉你崩溃的概率只有10^-20,那我们还需不需要加锁呢?

我们在开始

 

来自新世界 影评

这是继《1984》《动物庄园》《美丽新世界》之后,我看到的另一部反乌托邦的作品。也是第一部以动画形式观看的同类作品。

总体感受:气势磅礴、构思自然、环环相扣、引人入胜。

这部作品,精彩之处,大概在于其设定设计了从上古社会(即我们现在所处的世界)逐渐发展到的新世界。也就是说,在设定上,已经超出了大部分架空的作品。改朝、换代,这个只在历史书上出现过得词,给人一种极大的沉重感。不论是里面99.8%无能力者对抗对0.2%PK者的“太古社会”,还是由“神之力”所构建的樱花奴隶王朝,最终都在风雨飘摇中飞散……再完美的社会制度,也不过是这样。感慨万千……

这部作品被归类为反乌托邦,也拥有这类作品共同的特点:拥有一个非常强大固执的社会体系,主角在一番奋斗之后,并没有成功改变什么东西。《1984》中,乌托邦由武力暴政维持,民生凋敝,而《美丽新世界》中,虽没有太多提及,但是可以看出社会是建立在一定的科技技术上的;而这部作品,社会所需求的物资,来源于“咒力”。从这里可以总结出一个特点,即乌托邦式社会需要建立在一个非常强大而且自给自足的生产力上(《1984》中那种根本没有消耗的除外)。这确实给正在学习马原的我一些想法,或者说,给我了一些思考的导向性问题。以我现在所了解的资料,从社会主义的分阶段实现,以及马克思思想中社会主义与资本主义的关系中,确实可以看出整个思想体系,都在思考着如何解决这种社会生产力方面的问题。

最重要的是,自新的BGM简直是太配了,甚至即使他是网易云里面听过的最久远的歌,却一点违和感都没有。这也是我觉得这部番最棒的一个部分。

 

如何写一个简单的对拍

最近很多同学问我

  • “数据结构的某PA交上去WA了怎么办,我明明过了样例的呀!”
  • “我如何才知道我的程序在大数据下跑的多块?小数据什么算法都看不出差别?”
  • “求救,我已经盯着我的程序看了两个小时了”

其实这种东西都可以通过一种叫做对拍的方式解决。对拍的核心思路是:写一个程序造数据,写一个程序暴力跑数据,然后和你的正解程序的输出进行比较。

这里面涉及到了三个程序:

  • 数据生成程序gen.py/.cpp
  • 暴力程序std.cpp
  • 对拍程序check.py/.sh/.bat

gen.py

全称generator.py,他的作用是你调用一次这个程序,自动给你生成一个随机输入数据,我们以PA4为例,我们可以写一个这样的程序。

将这个程序写入 gen.py 中,则每次调用 python3 gen.py 都可以在 input.txt 文件中生成一组规模100000的数据!

到这里,我们已经可以解决不清楚程序运行速度的问题了:你最大规模数据都有了,为啥还不能看出来呢?

std.cpp

对于大部分题目,我们都能找到一种不那么好的解法,比如PA4,我们实际上可以讲每天的区间即权值,放到一个struct数组里面,对于每一个时刻,查询包含该时刻的区间权值最大值。

放代码恐怕我就要被邓公请去喝茶了,所以大家自己写咯。

目标是写一个程序,交到网站上不会WA,只会TLE的那种。

check.py

现在一个比较直接的方式是:每次运行一边generator,在运行一边std,比较输出文件。但是这样非常慢。为什么我们不能将这个过程自动化呢?

这里需要科普几个终端命令:

首先,我们可以通过bash/bat等批处理文件实现,不过看在读者基本都不会愿意再学一门新语言,我们直接用我们会的python实现,python的 os.system() 可以调用一个系统命令,并且返回结果。

大概程序长成这样,调用 python3 check.py 就自动无线循环造数据测试啦。

这里我们需要修改 gen.py 里的数据范围,使得刚好到你的暴力程序能两三秒跑出来的规模。这样一分钟你就可以测试三四十组数据了。

 

这就是一个最简单的对拍程序。对拍对于数据结构的题简直是神器,因为这类问题总是会存在一个非常暴力,但是不容易写错的解法。而且熟练之后,三个程序加起来也就是二十分钟的事。

*注,上面的代码都是手打的,没有测试过哦……错了评论一下就好了,思路是对的

问:写这个耗费时间啊!

答:你盯着代码不动更费时间。

问:不会写暴力,或者暴力我也可能写错怎么办

答:找A了的同学的代码当std

电影爬虫日记 之 豆瓣网爬虫记录

2017年9月29日

最近接到了一个小任务,要求爬取豆瓣、时光网等网站的电影信息并进行少量的数据处理。爬电影确实不是一个难的东西,不就是选择一个相对简单的目标url,写一个脚本进行访问。但是,要想要为何不借此机会,好好研究一下python中的异步以及多线程机制呢?说不定还就写出一个像scrapy一样的爬虫框架了呢!

爬取豆瓣电影列表这件事,也不算什么复杂的工作,因为豆瓣电影本身没有反爬虫机制。

电影列表抓取

方案A

网址:https://movie.douban.com/tag/2017

里面有2017年的所有电影,但是其中有混杂很多的电视剧啥的,总数也仅仅只有4000个。


2017年9月30日

方案B

网址:https://movie.douban.com/typerank?type_name=剧情&type=11&interval_id=100:90&action=

倘若枚举每一个分类的每一个得分档次的每一页,就可以得到大约20000个电影。这可以说非常全面了。


2017年10月7日

电影信息抓取

豆瓣对于每一个电影都有一个自己的id,这个在之前爬取爬虫列表的部分就已经预处理出来了。

页面链接就是普通的电影页面:https://movie.douban.com/subject/26425068/

然而,当我尝试开始使用诸如多线程爬虫时……

豆瓣把我给封掉了……

现在可以确认的消息是

  1. 通过urllib.request.urlopen进行访问,单线程会在几千次左右被封
  2. 通过多线程访问可以在一分钟内被封
  3. 通过IP代理暂时没有看出效果

首先我尝试的是直接将爬取的数据写入数据库,但是感觉比较迷……因为容易被封IP,需要在八小时后自动重新启动。判重等问题非常难处理。

另一种尝试则是通过在ID对应文件中写入数据。网上的爬虫用的是第二种,但是感觉第一种可能会方便一些……吧……