手机浏览 RSS 2.0 订阅 膘叔的简单人生 , 腾讯云RDS购买 | 超便宜的Vultr , 注册 | 登陆
浏览模式: 标准 | 列表全部文章

最小完美哈希函数

不好意思,这是一个标题党,主要是这个词语太让人震惊,但现在它又将变的地了。所以我先记录一下。

什么是完美哈希函数?
這一段內容來自:(http://www.kuqin.com/algorithm/20111108/314569.html)
最小完美哈希函数是什么,要从定义说起,这个名字很长,一步步解释。

  1. 哈希函数 任意函数h(x)都可以说哈希函数,一般来说,一个良好的哈希函数可以尽量避免重复。x的集合是参数域,h(x)的集合是值域。
  2. 完美哈希函数  完美哈希函数,就是完全不会冲突的哈希函数,这要求函数的值域至少比参数域要大
  3. 最小完美哈希函数 最小完美哈希函数,就是指函数的值域和参数域的大小完全相等,一个也不多
  4. 保序最小完美哈希函数 保序的意思就是指这个哈希之后顺序是不变的,同时还能满足其他两个条件。
这个函数的优点就是形式上很完美,就像给一个排好序的文档编上的序号一般紧凑可靠。但是这个函数有两个缺点,一是必须事前必须知道原数据集,二 是需要花一定的CPU来生成这个函数。我认为,对于数据仓库类的线下搜索应用,这个算法是有用武之地的。但对于强调实时的数据业务,这个算法是不适合的。
----------
這裏還有一個點評:(http://liulixiang.info/blog/tag/%E6%9C%80%E5%B0%8F%E5%AE%8C%E7%BE%8E%E5%93%88%E5%B8%8C%E5%87%BD%E6%95%B0/)

点评:(by liulixiang)

“最小完美哈希函数”从概念上很完美,生成的思想也很不错,不过实际运用中并不是那么常见:应用中已知数据集再做哈希的情况不是特别多,对时空的复杂度要求也没有过于苛刻,普通的方法即可承受。另外一般数据集很大,生成该函数的开销也太大。

---------
參考文檔:

最小完美哈希函数方法来自于Czech, Havas, Majewski等的论文:

An optimal algorithm for generating minimal perfect hash functions(Czech等1991)

Graphs, hypergraphs and hashing(Havas等1993)

A family of perfect hashing methods(Majeki等1996)

本文大部分转述或摘抄自《深入搜索引擎——海量信息的压缩、索引和查询》(该书豆瓣链接) 一书(Page 173~181),该书由梁斌翻译(原版即大名鼎鼎的MG——“Managing Gigabytes: Compressing and Indexing Documents and Image, Second Edition” 由Ian H. Witten, Alistair Moffat, Timothy C.Bell合著)(MG网站

转:如何彻底删除 Mac OS X 里那巨大的 sleepimage 文件(当 sudo pmset -a hibernatemode 0 无效时)

這篇文章很有意思,它。居然是模仿了windows下面那些操作:創建一個同名文件,然後設為只讀(windows下面因為有一些奇怪,即,如果目錄名和文件名一樣,先有目錄的時候,同名文件是不能寫入的,也不能創建,所以在windows下面的時候,我們為了防止會創建這種病毒性文件,可以預先創建一個同名目錄。黑黑,好象就是當年優盤的autorun.inf的無敵解決方法)
現在開始轉貼內容 :http://apple4.us/2012/07/how-to-remove-sleepimage-in-mac-os-x-when-pmset-command-does-not-work.html

用 SSD 的朋友硬盘空间不大,需要节省。而 Mac OS X 的冬眠模式会自动放一个和内存等大的名叫「sleepimage」的文件到 /private/var/vm 目录,换言之,你的内存是多少 GB,就有多少 GB 的硬盘空间会被这个文件吃掉。

江疆以前介绍过用命令行方法禁用冬眠模式,只要在终端里运行 sudo pmset -a hibernatemode 0 即可。但这招在 Mac OS X 10.7 (Lion) 上似乎行不通,禁用之后删除 sleepimage,过不了多久它又会死灰复燃。

我试过一个叫 SmartSleep 的软件,同样无效。

最后网上搜到一个偏方,问题解决。分享给大家。

  1. 打开 TextEdit,建立一个空的文本文件,取名为 sleepimage,保存到桌面。
  2. 去 Finder 里找到这个文件,选中,按 return,将后缀名(.rtf 或 .txt)删除。
  3. 在 Finder 里按 Command + Shift + G,输入 /private/var/vm,回车。
  4. 新开一个 Finder 窗口,将桌面的 sleepimage 文件拖入上述第三步中的窗口。这时系统会要求你输入管理员账号密码。
  5. 在 /private/var/vm 中选中 sleep image,按 Command + i,把 Locked 勾上。

完毕。

(这个偏方的原理是将一个体积极小的同名文件放入 sleepimage 所在的目录(/private/var/vm),并禁止系统对该文件进行写操作。)

----------EOF------

我試著看了一下我的本地:

mac$ ls -lh
total 20971520
-rw------T  1 root  wheel   8.0G  7 22 20:07 sleepimage
-rw-------  1 root  wheel    64M  6 21 14:31 swapfile0
-rw-------  1 root  wheel    64M  7 22 21:04 swapfile1
-rw-------  1 root  wheel   128M  7 22 21:04 swapfile2
-rw-------  1 root  wheel   256M  7 22 21:04 swapfile3
-rw-------  1 root  wheel   512M  7 22 21:04 swapfile4
-rw-------  1 root  wheel   1.0G  7 22 21:04 swapfile5
好吧,8G空间就这么没有了。。。凄凉啊。不过我还不敢删除,毕竟 ,我真的有时候会用到没电。。。。

转:你的周围需要这6种人

转的文章,很不错,来自36氪,http://www.36kr.com/p/137604.html
内容不全部转,图片不转,只有内容:
几乎没有什么不可思议的产品是一个人就能完成的。你需要其他人来帮助你,你也需要去帮助别人。在一个好的团队中,都需要哪种类型的人进驻?来自Forbes的Jessica Hagy告诉我们,你的周围需要这6种人:
1. “怂恿者”( Instigator):

怂恿者,是那种会推动你,让你思考的人。他会一直地让你有动力早起做事,尝试并将事情变为可能。你会希望这个人充满活力并保持热情。这是灵感之声。

2. 支持者:

他是一个大粉丝,一个强有力的支持者,并且还是一个为你和你的工作进行狂热传播的人。让他得到奖励,持续让他们参与。这是动力之声。

3. 怀疑者:

他是魔鬼的代言人,常常会指出一些尖锐的问题,还能提前发现问题。你会需要他的这种态度。因为他们常常能看到你角度以外的事,并希望你的成功会与安全同行。这是理智之声。

4. 严厉者:

他是让你把事情做好的爱找茬的“大声公”,也是冲动的管家,他会确保团队目标在截止日期前完成目标。这是前进之声。

5. 连结者:

他会帮助你找到新的途径和新的盟友。这个人打破路障并为你找到魔法实现的方法。你需要他帮你接近你所不能接近的人和地方。这是合作之声。

6. 标杆:

他是你可信赖的顾问,你的北极星,也是你想要赶超的那个人。他是你的指导单位,是作为时刻提醒你,你也可以做神奇事情的存在。你需要让他感到骄傲。这是权威之声。

你是哪种人?你的团队有这6种人吗?
--------------------
好象,很多公司都会有万精油,你们公司有吗?

转:梅耶尔9条创新原则温故:创新需要约束

本文來自Cnbeta。原文地址是:http://www.cnbeta.com/articles/197699.htm,沒有全部復制,要看詳細請去該網頁

据国外媒体报道,雅虎日前宣布任命前谷歌高管玛丽莎·梅耶尔(Marissa Mayer)担任CEO,这令业界感到震惊。梅耶尔现年37岁,拥有丰富的行业经验,多年来一直负责谷歌最具人气产品的外观和体验等项目,最近还负责了谷歌的地理位置和本地化服务等,主要管理谷歌公司1000多名产品经理。同时,梅耶尔还是谷歌运营委员会的成员之一,也是谷歌重要的资深高管。

四 年多以前,即2008年2月19日,美国知名商业杂志之一《Fast Company》网站曾发表了一篇文章,介绍了时任谷歌搜索产品与用户体验副总裁梅耶尔的9条创新原则。作为谷歌的第20名员工以及长期负责核心业务的高 管,梅耶尔正是凭借这9条原则引领谷歌发展成为全球最知名的互联网企业之一。

以下是梅耶尔的9条创新原则:

1、持续创新,而非一步成型

“有 两种不同类型的程序员。一些人喜欢连续几个月,甚至连续几年编码,并希望自己能够开发出完美的产品。这是一种城堡建设法。很多公司喜欢这种方法,苹果就是 一个典型的例子。如果你做对了,开发出一款完善的产品,那么你会令全世界感到惊叹。但问题在于,如果你做错了,你花了5年时间、耗费100名人力开发的产 品不受市场欢迎,那无异于一记重击也有一些人倾向于边开发、边完善。这正是我们的做法,即我们的‘迅速、频繁发布’战略。向人们灌输我们文化的最难之处 就在于,有的工程师向我展示产品原型,我也很喜欢,但他们却说,‘哦,它还没有完成,还不符合谷歌的标准,还不像是一款谷歌产品’。他们想使用城堡建设 法,添加所有的功能,使之成为完美的产品。而我告诉他们,‘谷歌产品应当是尽早进入谷歌实验室,然后不断完善,吸纳市场需求的元素,并使之成为伟大的产 品’。这种实验方法的好处在于,你永远不会远离市场需求,市场会把你拉回来。”

2、创意无处不在

“我们有一个很好的内部候选名单,所有人都可以提供创意,并且可以看到这个名单。这就像一个投票箱,人们可以表达他们对这个创意的观点。正是这些观点引出了新的创意。”

3、追逐梦想的权利

我们允许工程师将20%的时间用于研究他们喜欢的任何项目,我们相信他 们可以创造出有趣的产品。”

4、调整产品,而非封杀它

“谷歌CEO埃里克·施密特(Eric Schmidt)曾这样对我说:任何能够进入谷歌实验室的项目,从核心上看在其它方面也一定有可取之处,即便市场对此没有反馈。我们的工作就是将产品转化得符合市场需求。”

5、尽可能多地分享信息

每周一,所有员工都会发一封电子邮件,里面有五到七个要点,介绍他们上周的工作。作为一家搜索公司,我们将所有邮件纳入一个巨大的 网页,然后提供索引。如果你想知道谁在从事地图研究,那么就可以搜索到。这使得我们可以在全公司共享自己知道的信息,并减少重复。”

6、用户,还是用户

“我过去这样说这句话:‘用户,而非金钱’。我们坚信,如果我们专注于用户,金钱会来的。在一个真正虚拟的业务上,只要我们取得成功,人们就会通过订阅的方式为此付费。只要拥有足够多的用户,广告商也会愿意付费资助这个网站。”

7、数据远离政治

“我遇到过其他公司负责设计的人员,他们总说,‘设计是公司最具政治性的领域之一,有的设计师喜欢绿色,有的设计师喜欢紫色,那么谁的设计方案会被采纳?谁与老板关系好,谁的设计就会被采纳。’”

“有 些公司认为设计是艺术,而我们认为设计是科学。谁的设计方案最受欢迎,或者你更倾向于哪种美感并不重要,这全靠数据说话。进行一次1%的测试(即在1%的 用户中进行测试),哪些设计在两周时间内获得最佳的用户反馈,我们就推出哪项设计。我们有一个学术氛围非常好的环境,可以一直进行这些测试。”

“我们可能会在实时流量中进行50到100项测试,每项测试的默认数据来决定设计成果。我们一直通过这种方法尝试不同的方案。”

8、创新需要约束

“这是我最喜欢的观点之一。人们总认为,创新就需要毫无约束,但工程师在有约束的情况下更能进步。他们希望这样评论自己的创意:‘我们知道你说这不可能,但我们仍然要这样做,直到成功。’”

9、你很优秀?我们正在招聘。

我开始在谷歌工作, 工程师们被要求为招聘工程师而撰写宣传语。我们进行了一次比赛,我写了‘你很优秀?我们正在招聘。来谷歌吧。’这则广告语的点击率相当于其他广告语的八 倍。”

“现在谷歌的员工数量已经相当于我进入谷歌时的一千余倍,这令我感到惊讶。不过更重要的是那些没有改变的东西,即来这里工作的人们的 类型,以及他们喜欢的工作类型。这与我们这些谷歌的前20名员工几乎完全相同。这就是公司文化中愿意解决重大问题、愿意为世界做贡献、坚信我们可以在坚守 标准和价值观的前提下建立成功企业的元素。”

-----------

有些东西确实不错。其实我更关心的是第一项

Tags: 创新

apns 二三事

今天要說的還是推送,NND,這個推送這玩意,折騰死人
1、aps中是否只能有badge/alert/sound等參數?
答:不是,這個只是最基本的參數,可以有很多參數,但aps標記需要一定存在,其他參數可以自定義,比如:

JavaScript代码
  1. {  
  2.     "aps" : {  
  3.     },  
  4.     "acme2" : [ 5,  8 ]  
  5. }  

aps参数可以是空,但一定要有,上面这个可不是我杜撰的,这是官方的例子:http://developer.apple.com/library/ios/#documentation/NetworkingInternet/Conceptual/RemoteNotificationsPG/ApplePushService/ApplePushService.html#//apple_ref/doc/uid/TP40008194-CH100-SW12

2、aps中的content-available是什么意思
答:这个是有特殊需要的时候才需要用,比如用来后台下载?说实话,我在官方没找到文档,反而在adobe找到一个小的介绍 :
第一个介绍:http://www.adobe.com/devnet/digitalpublishingsuite/articles/dps-push-notification.html

Table 3. Parameters for APNS messages

Property value description
alert <string> The text message to display to the user. No localization arguments are supported.
badge <number> If non-zero, it displays the number on the icon of the application. If zero, no number is displayed.
content-available 0 | 1 Non-zero indicates a Newsstand push message. The receipt of this will wake the viewer to begin a background download. See Notes.
sound "default" Only the default notification sound is supported.
productID <string> Product.

Notes about Newsstand background downloading

  1. Background downloads are limited to once every 24 hours, +/- 1 hour (or so). You can send as many alert messages you like, but only background downloading will be throttled.
  2. Background downloading will only happen over WiFi connections. If the user is on 3G and the push is received, the background download is lost.
  3. A valid subscription via Apple or direct entitlement (CDS, TCS, PCD, Dovetail, or other) must exist.
  4. Only the most recent folio will be background-downloaded. The user must be entitled to this content.
  5. Apple attempts a number of times to deliver the push payload. As such, the actual download may begin a significant amount of time after it was originally sent or scheduled.

用了content-available参数后,下一次接收一定是在24小时后。看上面的notes

还有一个介绍在这里:http://www.viggiosoft.com/blog/blog/2011/10/17/ios-newsstand-tutorial/,这篇博客很详细,还告诉你在APP中怎么设置,内容过长,我就不一一贴出来了。
它这么说:
The push notification message has the same syntax as standard push notifications with the only difference that the payload must contain the content-available key set to 1:

JavaScript代码
  1. {  
  2.   "aps":{  
  3.     "content-available":1,  
  4.         },  
  5.    "device_tokens": ["E9623F5CFDE92B40DA4AA90B97B70428BCD8FFCBA067BE17A6EF5102651E66E9"]  
  6. }  

There is one importation limitation related to the frequency of pushes: to limit the consumption of resources due to background downloading (which, by the way, we’ll happen only if the device is connected to a Wi-Fi network) Newsstand push notifications are coalesced and only one background download is permitted per day. For testing purposes you can remove this limit by setting an appropriate key in the user defaults (do this at startup in your App Delegate)
大小: 96.37 K
尺寸: 251 x 376
浏览: 1890 次
点击打开新窗口浏览全图

Tags: apns, apple