最近听闻数据结构与算法实践课的老师又出了和上年一样的选题,不禁想起了去年自己完成作业时的点点滴滴,遗憾当时没有写博客的习惯,之前的一些心得这一年实践的过去也逐渐淡忘了,突然就有了总结一下的想法,希望能有新的收获吧。

阅读全文 »

Recursive division method

Mazes can be created with recursive division, an algorithm which works as follows: Begin with the maze’s space with no walls. Call this a chamber. Divide the chamber with a randomly positioned wall (or multiple walls) where each wall contains a randomly positioned passage opening within it. Then recursively repeat the process on the subchambers until all chambers are minimum sized. This method results in mazes with long straight walls crossing their space, making it easier to see which areas to avoid.

For example, in a rectangular maze, build at random points two walls that are perpendicular to each other. These two walls divide the large chamber into four smaller chambers separated by four walls. Choose three of the four walls at random, and open a one cell-wide hole at a random point in each of the three. Continue in this manner recursively, until every chamber has a width of one cell in either of the two directions.

阅读全文 »

在完成了DNS解析模块之后,我意识到了DNS缓存机制也很有必要。在Redis,Memcache,和.Net自带的Cache之间,考虑到部署问题,最终选择了后者,之前在学习Web及开发的过程中用过System.Web.Caching.Cache这个类库,但是这次的爬虫程序我打算部署为桌面软件,所以选用了System.Runtime.Caching.MemoryCache(后期如有必要也会加入System.Web.Caching.Cache来适配Web端程序)。

MemoryCache的使用网上介绍的不多,不过这个是.NET4.0新引入的缓存对象,估计主要是替换原来企业库的缓存模块,使得.NET的缓存可以无处不在,而不用基于特定的Windows版本上使用。

出于方便考虑,我们将不再实例化新的MemoryCache对象,只对MemoryCache的默认示例Memory.Default进行增删查操作。

基础操作

增加


增加缓存需要提供两个参数,CacheItem类表示缓存中的单个缓存项,

构造函数:
CacheItem(String, Object, String) 用缓存项的指定键、值和区域初始化新的 CacheItem 实例。

三个参数分别为:键、值和区域。

CacheItemPolicy类则表示缓存项的过期信息,只含有默认的构造函数。

增加一条缓存:

1
2
3
4
5
6
7
8
9
10
11
var item = new CacheItem("习大大", "两学一做");
var policy = new CacheItemPolicy();
policy.SlidingExpiration = new TimeSpan(500);
//插入一条key为"习大大",value为"两学一做",500毫秒后自动销毁的缓存
MemoryCache.Default.Add(item, policy);
//重新设置policy的过期时间为当前时间+十分钟
policy.AbsoluteExpiration = DateTimeOffset.Now + TimeSpan.FromMinutes(10);
//注意,如果要使用Sliding时间,则Absolute必须为DateTimeOffset.MaxValue,反之,则Sliding必须为TimeSpan.Zero
policy.SlidingExpiration = TimeSpan.Zero;
//重新插入,覆盖前一条数据
MemoryCache.Default.Add(item, policy);

注意,如果要使用Sliding时间,则Absolute必须为DateTimeOffset.MaxValue,反之,则Sliding必须为TimeSpan.Zero

查询

缓存对象类似于字典集,查询可以直接采用memoryCache[key]来进行,例如我们查询一下前面插入的那条数据:

1
var idea = MemoryCache.Default["习大大"];

移除


参数
key:要移除的缓存项的唯一标识符。
regionName:缓存中的一个添加了缓存项的命名区域。不要为该参数传递值。默认情况下,此参数为null,因为 MemoryCache 类未实现区域。
返回值
Type: System.Object 如果在缓存中找到该项,则为已移除的缓存项;否则为 null。

删除前面加入的那一项:

1
MemoryCache.Default.Remove("习大大");

进一步封装

明白了基本的用法之后,我们就可以对它做进一步的封装,使之使用起来更为便捷:

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Caching;

namespace Crawler.Common
{
/// <summary>
/// 基于MemoryCache的缓存辅助类
/// </summary>
public static class MemoryCacheHelper
{
private static readonly object _locker = new object();

public static bool Contains(string key)
{
return MemoryCache.Default.Contains(key);
}


/// <summary>
/// 获取Catch元素
/// </summary>
/// <typeparam name="T">所获取的元素的类型</typeparam>
/// <param name="key">元素的键</param>
/// <returns>特定的元素值</returns>
public static T Get<T>(string key)
{
if (string.IsNullOrWhiteSpace(key)) throw new ArgumentException("不合法的key!");
if (!MemoryCache.Default.Contains(key))
throw new ArgumentException("获取失败,不存在该key!");
if (!(MemoryCache.Default[key] is T))
throw new ArgumentException("未找到所需类型数据!");
return (T)MemoryCache.Default[key];
}

/// <summary>
/// 添加Catch元素
/// </summary>
/// <param name="key">元素的键</param>
/// <param name="value">元素的值</param>
/// <param name="slidingExpiration">元素过期时间(时间间隔)</param>
/// <param name="absoluteExpiration">元素过期时间(绝对时间)</param>
/// <returns></returns>
public static bool Add(string key, object value, TimeSpan? slidingExpiration = null, DateTime? absoluteExpiration = null)
{
var item = new CacheItem(key, value);
var policy = CreatePolicy(slidingExpiration, absoluteExpiration);
lock (_locker)
return MemoryCache.Default.Add(item, policy);
}

/// <summary>
/// 移出Cache元素
/// </summary>
/// <typeparam name="T">待移出元素的类型</typeparam>
/// <param name="key">待移除元素的键</param>
/// <returns>已经移出的元素</returns>
public static T Remove<T>(string key)
{
if (string.IsNullOrWhiteSpace(key)) throw new ArgumentException("不合法的key!");
if (!MemoryCache.Default.Contains(key))
throw new ArgumentException("获取失败,不存在该key!");
var value = MemoryCache.Default.Get(key);
if (!(value is T))
throw new ArgumentException("未找到所需类型数据!");
return (T)MemoryCache.Default.Remove(key);
}

/// <summary>
/// 移出多条缓存数据,默认为所有缓存
/// </summary>
/// <typeparam name="T">待移出的缓存类型</typeparam>
/// <param name="keyList"></param>
/// <returns></returns>
public static List<T> RemoveAll<T>(IEnumerable<string> keyList = null)
{
if (keyList != null)
return (from key in keyList
where MemoryCache.Default.Contains(key)
where MemoryCache.Default.Get(key) is T
select (T)MemoryCache.Default.Remove(key)).ToList();
while (MemoryCache.Default.GetCount() > 0)
MemoryCache.Default.Remove(MemoryCache.Default.ElementAt(0).Key);
return new List<T>();
}

/// <summary>
/// 设置过期信息
/// </summary>
/// <param name="slidingExpiration"></param>
/// <param name="absoluteExpiration"></param>
/// <returns></returns>
private static CacheItemPolicy CreatePolicy(TimeSpan? slidingExpiration, DateTime? absoluteExpiration)
{
var policy = new CacheItemPolicy();

if (absoluteExpiration.HasValue)
{
policy.AbsoluteExpiration = absoluteExpiration.Value;
}
else if (slidingExpiration.HasValue)
{
policy.SlidingExpiration = slidingExpiration.Value;
}

policy.Priority = CacheItemPriority.Default;

return policy;
}
}
}

普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim)独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。

——来自百度百科

阅读全文 »

在之前的项目中,如果有需要使用验证码,基本都是自己用GDI+画图出来,简单好用,但是却也存在了一些小问题,首先若较少干扰线,则安全性不是很高,验证码容易被机器识别,若多画太多干扰线条,机器人识别率下降的同时,人眼的识别率也同步下降(震惊哭)。更为重要的是,GDI+绘制的验证码一般来说也不会很美观,如果做一个炫酷的登陆界面却配了这样一个验证码,画风诡异,丑到极致。

再后来浏览网页的过程中,发现很多很多网站项目中都使用了一种叫极验验证的验证码,采用移动滑块的方式进行验证,方便美观。而一番搜索之后了解到,官方提供的免费版也足以应付我手头的大多数项目了,不禁想把在MVC学习过程中试着使用极验验证来作为登录的验证码。

阅读全文 »

为了解决单机处理的瓶颈,增强软件的可用性,我们需要将软件部署在多台服务器上启用多个二级子域名以频道化的方式,根据业务功能将网站分布部署在独立的服务器上,或通过负载均衡技术(如:DNS轮询、Radware、F5、LVS等)让多个频道共享一组服务器。当我们将网站程序分部到多台服务器上后,由于Session受实现原理的局限,无法跨服务器同步更新Session,使得登录状态难以通过Session共享。

阅读全文 »

1381 硬币游戏
基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题

有一个简单但是很有趣的游戏。在这个游戏中有一个硬币还有一张桌子,这张桌子上有很多平行线(如下图所示)。两条相邻平行线之间的距离是1,硬币的半径是R,然后我们来抛硬币到桌子上,抛下之后硬币有时候会和一些直线相交(相切的情况也算是相交),有时候不会。
请你来计算一下抛一次硬币之后,该硬币和直线相交数目的期望。

阅读全文 »