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

转：经典算法

Submitted by gouki on 2013, March 27, 10:21 AM

在微博上突然看到一篇贴子：
【#SAE技术分享#】《经典排序算法集锦》大多数排序算法都给出了每一步的状态，以方便初学者更容易理解，通俗易懂，部分难以理解的排序算法则给出了大量的图示，也算是一个特色吧~http://t.cn/SySUjx

附了一张图：
大小: 135.44 K 尺寸: 236 x 376 浏览: 1794 次 点击打开新窗口浏览全图
果然非常有用，因此，我也就转载了一下。。。原文地址我就不贴了，不过我暂时先将它的目录贴出来吧

Tags: 算法

PHP | 评论:0 | 阅读:19701

集体智慧编程笔记（一）：相似度算法

Submitted by gouki on 2010, July 15, 8:52 AM

本文内容全部来自《集体智慧编程》一书，原书采用的是python，因为没有python编程环境，所以用PHP实现

PHP代码
  1. <?php  
  2. //filename:test_collecting_preferences  
  3. //数据和代码来自《集体智慧编程》  
  4. //原文采用python实现，尝试用PHP进行转换  
  5. //@description 搜集用户偏好寻找相近用户  
  6. $datalist = array(  
  7.     'Lisa Rose' => array(  
  8.         'Lady in the Water' => 2.5,  
  9.         'Snake on a Plane' => 3.5,  
  10.         'Just My Luck' => 3.0,  
  11.         'Superman Returns' => 3.5,  
  12.         'You, Me and Dupree' => 2.5,  
  13.         'The Night Listener'=> 3.0  
  14.     ),  
  15.     'Gene Seymour' => array(  
  16.         'Lady in the Water' => 3.0,  
  17.         'Snake on a Plane' => 3.5,  
  18.         'Just My Luck' => 1.5,  
  19.         'Superman Returns' => 5.0,  
  20.         'You, Me and Dupree' => 3.5,  
  21.         'The Night Listener'=> 3.0  
  22.     ),  
  23.     'Michael Phillips' => array(  
  24.         'Lady in the Water' => 2.5,  
  25.         'Snake on a Plane' => 3.0,  
  26.         'Superman Returns' => 3.5,  
  27.         'The Night Listener'=> 4.0  
  28.     ),  
  29.     'Claudia Puig' => array(  
  30.         'Snake on a Plane' => 3.5,  
  31.         'Just My Luck' =>3.0,  
  32.         'Superman Returns' => 4.0,  
  33.         'You, Me and Dupree' => 2.5,  
  34.         'The Night Listener'=>4.5  
  35.     ),  
  36.     'Mick LaSalle' => array(  
  37.         'Lady in the Water' => 3.0,  
  38.         'Snake on a Plane' => 4.0,  
  39.         'Just My Luck' => 2.0,  
  40.         'Superman Returns' => 3.0,  
  41.         'You, Me and Dupree' => 2.0,  
  42.         'The Night Listener'=> 3.0  
  43.     ),  
  44.     'Jack Matthews' => array(  
  45.         'Lady in the Water' => 3.0,  
  46.         'Snake on a Plane' => 4.0,  
  47.         'Superman Returns' => 5.0,  
  48.         'You, Me and Dupree' => 3.5,  
  49.         'The Night Listener'=> 3.0  
  50.     ),  
  51.     'Toby' => array(  
  52.         'Snake on a Plane' => 4.5,  
  53.         'Superman Returns' => 4.0,  
  54.         'You, Me and Dupree' => 1.0,  
  55.     ),  
  56. );  
  57. //欧几里德距离  
  58. //它以经过人们的一致评价的物品为坐标轴，然后将参与评价的人绘制到图上，并考查他们彼此间的距离远近。  
  59. //偏好越相似的人，距离越近。不过我们还需要一个函数来对偏好越相近的情况给出越大的值，  
  60. //为此我们可以将函数值加1（这样可以避免遇到被零整除的错误），并取其倒数  
  61. //公式是 1 / (1 + sqrt (  pow( data[a][1] - data[b][1] .... )  ))  
  62. function sim_distance ( $datalist , $person1 , $person2)  
  63. {  
  64.     $si = array();  
  65.     foreach ( $datalist[$person1] as $moviename => $grade ){  
  66.         if( array_key_exists( $moviename, $datalist[$person2] )){  
  67.             $si[$moviename] = 1;  
  68.         }  
  69.     }  
  70.     if( emptyempty( $si )){  
  71.         return 0;  
  72.     }  
  73.     $powers = 0;  
  74.     foreach ( $si as $moviename=>$val ){  
  75.         $powers += pow( ($datalist[$person1][$moviename] - $datalist[$person2][$moviename] ), 2 );//两者影评分数相减的平方值  
  76.     }  
  77.     return 1 / (1+ sqrt($powers));  
  78. }  
  79. //测试 'Lisa Rose' 和 'Gene Seymour' 的相似度评价  
  80. //原书上求出来是 0.29429805508554946 , PHP 的结果是 0.29429805508555，默认精度没有python高  
  81. echo( sim_distance( $datalist , 'Lisa Rose' , 'Gene Seymour') );  
  82. echo( '<br/>' );  
  83.   
  84. //皮尔逊相关系数  
  85. //该相关系统是判断两组数据与某一直线拟合程序的一种度量。对应的公司比欧几里德距离评价的计算公式要复杂  
  86. //但是它在数据不是很规范时（如影评者对影片的评价总是相对于平均水平偏离很大），会倾向于给出更好的结果  
  87. //皮尔逊相关度评价法首先会找出两位评论者都曾评过的物品  
  88. //计算两者的评分总和与平方和，并求得评分的乘积之和，最后，利用这个结果计算出相关系数  
  89. function sim_person ( $datalist ,$person1 , $person2)  
  90. {  
  91.     $si = array();  
  92.     foreach ( $datalist[$person1] as $moviename => $grade ){  
  93.         if( array_key_exists( $moviename, $datalist[$person2] )){  
  94.             $si[$moviename] = 1;  
  95.         }  
  96.     }  
  97.     if( emptyempty( $si )){  
  98.         return 1;  
  99.     }  
  100.     $n = count( $si );  
  101.     $sum1 = $sum1Sq = $sum2 = $sum2Sq = $pSum = 0;  
  102.     foreach ( $si as $moviename => $val ){  
  103.         $sum1 += $datalist[$person1][$moviename];   //个人影评分数累加  
  104.         $sum1Sq += pow( $datalist[$person1][$moviename], 2 );//个人影评分数平方的累加  
  105.         $sum2 += $datalist[$person2][$moviename];  
  106.         $sum2Sq += pow( $datalist[$person2][$moviename], 2 );  
  107.         $pSum += ( $datalist[$person1][$moviename] * $datalist[$person2][$moviename]);//两人影评之乘积  
  108.     }  
  109.   
  110.     $num = $pSum - ( $sum1 * $sum2 / $n); // 正常情况下，我怎么都觉得这是1吧？  
  111.     $den = sqrt( ( $sum1Sq - pow( $sum1, 2 ) / $n) * ( $sum2Sq - pow( $sum2, 2 ) / $n) );  
  112.     if ( $den == 0 ){  
  113.         return 0;  
  114.     }  
  115.     return ($num / $den );      
  116. }  
  117. //继续测试 'Lisa Rose' 和 'Gene Seymour' 的相似度评价  
  118. //原书上求出来是 0.396059017191 , PHP 的结果是 0.39605901719067，这回。。。位数超过了python  
  119. echo( sim_person( $datalist , 'Lisa Rose' , 'Gene Seymour') );  
  120.   
  121. ?>  

有点长，随便看看吧

Tags: 算法

PHP | 评论:1 | 阅读:19956

Kmeans算法

Submitted by gouki on 2010, April 30, 12:38 PM

做电子商务的不可避免的都会遇到价格区间的问题。这，主要显示在搜索的时候，如果你区间设的过大，那几乎把所有产品都列出来了。那和没有分区间没啥分别。因此，还真有一种算法可以解决这个问题（当然也只是基本解决，看上去不是特别的乱而己）。

这是在老王的博客上看到的：

means算法

Web开发中，CRUD做多了难免厌烦，其实还有很多细节可以挖掘，比如很多电子商务网站上都有商品价格区间，都是诸如1000-2000，2000-3000之类定死的，而没有按商品自己的分布规律来划分，此时有一种名为Kmeans的算法可以使用，效果很好，网上有很多现成的代码可以参阅，比如PHP的版本：

kmeanspp
K-Means Clustering in PHP

--EOF--

到百科看了一下，这么解释K-means：k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。

虽然这样能够处理，老王也给了一个PHP的解决方案，但在实际中，应用的范围并能算是特别大，有时候还是直接手写的。以前的时候，我们是在分类里，直接把几个区间定义好，然后在搜索的时候指定某一分类时，自动调用这个区间。理由是，如果你的产品分的很散，从几块到几千块的都有，这种分类区间，就只能定义到分类上了。

不过上面的算法可以学习一下

Tags: kmeans, 老王, 聚合, 分类, 算法

PHP | 评论:0 | 阅读:23314

MYSQL官方的文章：几种无限分类的算法……

Submitted by gouki on 2008, October 11, 11:04 PM

我只贴一种，其余的去看：http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

The Adjacency List Model

Typically the example categories shown above will be stored in a table like the following (I'm including full CREATE and INSERT statements so you can follow along):

CREATE TABLE category(
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
parent INT DEFAULT NULL);


INSERT INTO category
VALUES(1,'ELECTRONICS',NULL),(2,'TELEVISIONS',1),(3,'TUBE',2),
(4,'LCD',2),(5,'PLASMA',2),(6,'PORTABLE ELECTRONICS',1),
(7,'MP3 PLAYERS',6),(8,'FLASH',7),
(9,'CD PLAYERS',6),(10,'2 WAY RADIOS',6);

SELECT * FROM category ORDER BY category_id;

+-------------+----------------------+--------+
| category_id | name                 | parent |
+-------------+----------------------+--------+
|           1 | ELECTRONICS          |   NULL |
|           2 | TELEVISIONS          |      1 |
|           3 | TUBE                 |      2 |
|           4 | LCD                  |      2 |
|           5 | PLASMA               |      2 |
|           6 | PORTABLE ELECTRONICS |      1 |
|           7 | MP3 PLAYERS          |      6 |
|           8 | FLASH                |      7 |
|           9 | CD PLAYERS           |      6 |
|          10 | 2 WAY RADIOS         |      6 |
+-------------+----------------------+--------+
10 rows in set (0.00 sec)

In the adjacency list model, each item in the table contains a pointer to its parent. The topmost element, in this case electronics, has a NULL value for its parent. The adjacency list model has the advantage of being quite simple, it is easy to see that FLASH is a child of mp3 players, which is a child of portable electronics, which is a child of electronics. While the adjacency list model can be dealt with fairly easily in client-side code, working with the model can be more problematic in pure SQL.

Retrieving a Full Tree

The first common task when dealing with hierarchical data is the display of the entire tree, usually with some form of indentation. The most common way of doing this is in pure SQL is through the use of a self-join:

SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS';

+-------------+----------------------+--------------+-------+
| lev1        | lev2                 | lev3         | lev4  |
+-------------+----------------------+--------------+-------+
| ELECTRONICS | TELEVISIONS          | TUBE         | NULL  |
| ELECTRONICS | TELEVISIONS          | LCD          | NULL  |
| ELECTRONICS | TELEVISIONS          | PLASMA       | NULL  |
| ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS  | FLASH |
| ELECTRONICS | PORTABLE ELECTRONICS | CD PLAYERS   | NULL  |
| ELECTRONICS | PORTABLE ELECTRONICS | 2 WAY RADIOS | NULL  |
+-------------+----------------------+--------------+-------+
6 rows in set (0.00 sec)

Tags: mysql, 无限分类, 算法, 存储结构, 官方

DataBase | 评论:0 | 阅读:23274

Base64转换：AQAB=65537，你知道为什么吗？[转]

Submitted by gouki on 2008, August 2, 7:56 PM

什么是Base64？

按照RFC2045的定义，Base64被定义为：Base64内容传送编码被设计用来把任意序列 的8位字节描述为一种不易被人直接识别的形式。（The Base64 Content-Transfer-Encoding is designed to represent arbitrary sequences of octets in a form that need not be humanly readable.）

为什么要使用Base64？

在设计这个编码的时候，我想设计人员最主要考虑了3个问题：
1.是否加密？
2.加密算法复杂程度和效率
3.如何处理传输？

    加密是肯定的，但是加密的目的不是让用户发送非常安全的Email。这种加密方式主要就是“防君子不防小人”。即达到一眼望去完全看不出内容即可。
基 于这个目的加密算法的复杂程度和效率也就不能太大和太低。和上一个理由类似，MIME协议等用于发送Email的协议解决的是如何收发Email，而并不 是如何安全的收发Email。因此算法的复杂程度要小，效率要高，否则因为发送Email而大量占用资源，路就有点走歪了。

    但 是，如果是基于以上两点，那么我们使用最简单的恺撒法即可，为什么Base64看起来要比恺撒法复杂呢？这是因为在Email的传送过程中，由于历史原 因，Email只被允许传送ASCII字符，即一个8位字节的低7位。因此，如果您发送了一封带有非ASCII字符（即字节的最高位是1）的Email通 过有“历史问题”的网关时就可能会出现问题。网关可能会把最高位置为0！很明显，问题就这样产生了！因此，为了能够正常的传送Email，这个问题就必须 考虑！所以，单单靠改变字母的位置的恺撒之类的方案也就不行了。关于这一点可以参考RFC2046。
基于以上的一些主要原因产生了Base64编码。

» 阅读全文

Tags: base64, 算法

Javascript | 评论:0 | 阅读:25683