How to use bloom filter to build a large in memory cache in Java 2

  • Bloomfilter is designed as an array(A) of m bits. Initially all these bits are set to 0.
To add item:
  • In order to add any item, it needs to be feed through k hash functions. Each hash function will generate a number which can be treated as a position of the bits array and we shall set that value of that position to 1. For example - first hash function (hash1) on item I produce a bit position x, similarly second and third hash functions produce position y and z.

    A[x] = A[y] = A[z] = 1

To find item:
  • Similar process will be repeated, item will be hashed three times through three different hash functions. Each hash function will produce an integer which will be treated as a position of the array. We shall inspect those x, y, z positions of the bit array and see if they are set to 1 or not. If no, for sure no one ever tried to add this item into bloomfilter, but if all the bits are set, it could be a false positive.
To design a good bloomfilter we need to keep track of the following things:
  • Good hash functions that can generate wide range of hash values as quickly as possible
  • The value of m (size of the bit array) is very important. If the size is too small, all the bits will be set to 1 quickly and false positives will grow largely
  • Number of hash functions(k) is also important so that the values get distributed evenly
The formula to calculate k and m:
m = -nlogp / (log2)^2
where p = desired false positive probability
The formula to determine k (number of hash functions):
k = m/n log(2)
where k = number of hash functions, 
m = number of bits and 
n = number of items in the filter
Hashing
  • Hashing is an are which affects the performance of bloomfilter. We need to choose a hash function that is effective yet not time consuming.

  • We can use two hash functions to generate K number of hash functions.

    First we need to calculate two hash function h1(x) and h2(x)
    Next, we can use these two hash functions to simulate k hash functions of the nature gi(x) = h1(x) + ih2(x), where i can range from {1...k}
    
    long hash64 = ...; // calculate a 64 bit hash function
    // split it in two halves of 32 bit hash values
    int hash1 = (int) hash64; 
    int hash2 = (int) (hash64 >>> 32);
    // Generate k different hash functions with a simple loop
    for (int i = 1; i <= numHashFunctions; i ++)
    {
        int nextHash = hash1 + i * hash2;
    }
    

Reference:

http://www.javacodegeeks.com/2014/07/how-to-use-bloom-filter-to-build-a-large-in-memory-cache-in-java.html

2015/10/25

Custom Token Filter Lucene"

In order to implement our filter we will extends the TokenFilter class from the org.apache.lucene.analysis and we will override the incrementToken method. This method returns a boolean value: if a value is still available for processing in the token stream, this method should return true, is the token in the token stream shouldn't be further analyzed this method should return false.

package pl.solr.analysis;

import java.io.IOException;

import org.apache.lucene.analysis.TokenFilter;
import org.apache.lucene.analysis.TokenStream;
import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;

public final class ReverseFilter extends TokenFilter {
  private CharTermAttribute charTermAttr;

  protected ReverseFilter(TokenStream ts) {
    super(ts);
    this.charTermAttr = addAttribute(CharTermAttribute.class);
  }

  @Override
  public boolean incrementToken() throws IOException {
    if (!input.incrementToken()) {
      return false;
    }

    int length = charTermAttr.length();
    char[] buffer = charTermAttr.buffer();
    char[] newBuffer = new char[length];
    for (int i = 0; i < length; i++) {
      newBuffer[i] = buffer[length - 1 - i];
    }
    charTermAttr.setEmpty();
    charTermAttr.copyBuffer(newBuffer, 0, newBuffer.length);
    return true;
  }
}

A TokenStream is a class that can produce a series of tokens when requested, but there are two different styles of TokenStreams: Tokenizer and TokenFilter.

A Tokenizer reads characters from a java.io.Reader and creates tokens, whereas a TokenFilter takes tokens in, and produces new tokens by either adding or removing whole tokens or altering the attributes of the incoming tokens.

public TokenStream tokenStream(String fieldName, Reader reader)
{
    return new StopFilter(true, new LowerCaseTokenizer(reader), stopWords);
}

In this anlyzer, LowerCaseTokenizer produces the initial set of tokens from a Reader and feeds them to a StopFilter. The LowerCaseTokenizer emits tokens that are adjacent letters in the original text, lowercasing each of the characters in the process. Following this word tokenizer and lowercasing, StopFilter removes words in a stop-word list while preserving accurate positionIncrements.

Buffering is a feature that's commonly needed in the TokenStream implementations. Low-level Tokenizers do this to buffer up characters to form tokens at boundaries such as whitespace or nonletter characters. TokenFilters that emit additional tokens into the stream they're filtering must queue an incoming token and the additional ones and emit them one at a time.

the TokenStream never explicitly creates a single object holding all attributes for the token. Instead, you interact with a separate reused attribute interface for each element of the token.

TokenStream subclasses from a class called AttributeSource. AttributeSource is a useful and generic means of providing strongly typed yet fully extensible attributes without reuquiring runtime casting, thus resulting in good performance.

2015/10/25

理解OAuth2.0

名词解释

(1) Third-party application:第三方应用程序,又称客户端(client)
(2) HTTP service: HTTP服务提供商
(3) Resource Owner:资源所有者,又称用户(user)
(4) User Agent:用户代理,即浏览器
(5) Authorization server:认证服务器,即服务提供商专门用来处理认证的服务器
(6) Resource server:资源服务器,即服务提供商存放用户生成的资源的服务器。它与认证服务器,可以是同一台服务器,也可以是不同的服务器

OAuth的思路

OAuth在‘客户端’与‘服务提供商’之间,设置了一个授权层(authroization layer)。‘客户端’不能直接登录‘服务提供商’,只能登录授权层,以此将用户与客户端区分开来。‘客户端’登录授权层所用的令牌(token),与用户的密码不同。用户可以在登录的时候,指定授权层令牌的权限范围和有效期。

‘客户端’登录授权层以后,‘服务提供商’根据令牌的权限范围和有效期,向‘客户端’开发用户储存的资料。

运行流程

- 用户打开第三方应用程序,第三方应用程序要求用户给予授权
- 用户用意给第三方应用程序授权
- 第三方应用程序使用上一步得到的授权,向认证服务器申请令牌
- 认证服务器对第三方应用程序进行认证以后,确认无误,同意发放令牌
- 第三方应用程序使用令牌,向资源服务器申请获取资源
- 资源服务器确认令牌无误,同意向客户端开发资源

第三方应用程序的授权模式

OAuth2.0定义了四种授权方式

  • 授权码模式(authorization code)
  • 简化模式(implicit)
  • 密码模式(resource owner password credentials)
  • 客户端模式(client credentials)

授权码模式

通过第三方应用程序的后台服务器,与‘服务提供商’的认证服务器进行互动

- 用户访问第三方应用程序,后者将前者导向认证服务器
- 用户选择是否给予第三方应用程序授权
- 假设用户给予授权,认证服务器将用户导向第三方应用程序事先指定的‘重定向URI’(redirection URI),同时附上一个授权码
- 第三方应用程序收到授权码,附上早先的‘重定向URI’,向认证服务器申请令牌。这一步是在客户端的后台的服务器上完成,对用户不可见
- 认证服务器核对了授权码和重定向URI,确认无误后,向客户端发送访问令牌(access token)和更新令牌(refresh token)

Reference

http://www.ruanyifeng.com/blog/2014/05/oauth_2_0.html

2015/10/25

iOS UIApplicationMain

1、- (void)applicationWillResignActive:(UIApplication *)application

说明:当应用程序将要入非活动状态执行,在此期间,应用程序不接收消息或事件,比如来电话了

2、- (void)applicationDidBecomeActive:(UIApplication *)application

说明:当应用程序入活动状态执行,这个刚好跟上面那个方法相反

3、- (void)applicationDidEnterBackground:(UIApplication *)application

说明:当程序被推送到后台的时候调用。所以要设置后台继续运行,则在这个函数里面设置即可

4、- (void)applicationWillEnterForeground:(UIApplication *)application

说明:当程序从后台将要重新回到前台时候调用,这个刚好跟上面的那个方法相反。

5、- (void)applicationWillTerminate:(UIApplication *)application

说明:当程序将要退出是被调用,通常是用来保存数据和一些退出前的清理工作。这个需要要设置UIApplicationExitsOnSuspend的键值。

6、- (void)applicationDidReceiveMemoryWarning:(UIApplication *)application

说明:iPhone设备只有有限的内存,如果为应用程序分配了太多内存操作系统会终止应用程序的运行,在终止前会执行这个方法,通常可以在这里进行内存清理工作防止程序被终止

7、- (void)applicationSignificantTimeChange:(UIApplication*)application

说明:当系统时间发生改变时执行

8、- (void)applicationDidFinishLaunching:(UIApplication*)application

说明:当程序载入后执行

9、- (void)application:(UIApplication)application willChangeStatusBarFrame:(CGRect)newStatusBarFrame

说明:当StatusBar框将要变化时执行

10、- (void)application:(UIApplication*)application willChangeStatusBarOrientation:

(UIInterfaceOrientation)newStatusBarOrientation

duration:(NSTimeInterval)duration

说明:当StatusBar框方向将要变化时执行

11、- (BOOL)application:(UIApplication*)application handleOpenURL:(NSURL*)url

说明:当通过url执行

12、- (void)application:(UIApplication*)application didChangeStatusBarOrientation:(UIInterfaceOrientation)oldStatusBarOrientation

说明:当StatusBar框方向变化完成后执行

13、- (void)application:(UIApplication*)application didChangeSetStatusBarFrame:(CGRect)oldStatusBarFrame

说明:当StatusBar框变化完成后执行

UIApplication的一些功能

1.设置icon上的数字图标

//设置主界面icon上的数字图标,在2.0中引进, 缺省为0

[UIApplication sharedApplication].applicationIconBadgeNumber = 4;

2.设置摇动手势的时候,是否支持redo,undo操作

//摇动手势,是否支持redo undo操作。

//3.0以后引进,缺省YES

[UIApplication sharedApplication].applicationSupportsShakeToEdit =YES;

3.判断程序运行状态

//判断程序运行状态,在2.0以后引入

/*

     UIApplicationStateActive,

     UIApplicationStateInactive,

     UIApplicationStateBackground

 */

if([UIApplication sharedApplication].applicationState == UIApplicationStateInactive){

    NSLog(@"程序在运行状态");

}

4.阻止屏幕变暗进入休眠状态

//阻止屏幕变暗,慎重使用,缺省为no 2.0

[UIApplication sharedApplication].idleTimerDisabled =YES;

5.显示联网状态

//显示联网标记 2.0
[UIApplication sharedApplication].networkActivityIndicatorVisible =YES;

6.在map上显示一个地址

NSString* addressText = @"1 Infinite Loop, Cupertino, CA 95014";

// URL encode the spaces

addressText =  [addressText stringByAddingPercentEscapesUsingEncoding:NSASCIIStringEncoding];

NSString* urlText = [NSString stringWithFormat:@"http://maps.google.com/maps?q=%@", addressText];

[[UIApplication sharedApplication] openURL:[NSURL URLWithString:urlText]];

7.发送电子邮件

NSString *recipients = @"mailto:first@example.com?cc=second@example.com,third@example.com&subject = Hello from California!";

NSString *body = @"&body=It is raining in sunny California!";

NSString *email = [NSStringstringWithFormat:@"%@%@", recipients, body];

email = [email stringByAddingPercentEscapesUsingEncoding:NSUTF8StringEncoding];

[[UIApplicationsharedApplication] openURL:[NSURLURLWithString:email]];

8.打电话到一个号码

// Call Google 411
[[UIApplicationsharedApplication] openURL:[NSURLURLWithString:@"tel://8004664411"]];

9.发送短信

// Text to Google SMS
[[UIApplication sharedApplication] openURL:[NSURLURLWithString:@"sms://466453"]];

10.打开一个网址

// Lanuch any iPhone developers fav site
[[UIApplication sharedApplication] openURL:[NSURLURLWithString:@"http://itunesconnect.apple.com"]];

Reference

http://blog.csdn.net/wanna_love/article/details/25073879

2015/10/25

理解OAuth2.0 2

sqlite3_prepare_v2

int sqlite3_prepare_v2(
    sqlite3 *db,                 //指向数据库的指针
    const char *zSql,         //SQL语句
    int nByte,                   //SQL语句的长度 (一般用-1,系统可以自动算出字符串得长度)
    sqlite3_stmt **ppStmt, //指向语句的指针
    const char **pzTail       //SQL中没有用到的一部分,一般为空
);

对整数值的绑定

int sqlite3_bind_int(
    sqlite3_stmt*,            //指向语句的指针
    int,                      //占位符的序号(从1开始以此类推)
    int                       //绑定的值
);

对字符串值的绑定

int sqlite3_bind_text(
    sqlite3_stmt*,            //指向语句的指针
    int,                      //占位符的序号(从1开始以此类推)
    const char*,              //要绑定的值(这里要c类型的字符串(CString),一般我们使用的是oc的字符串(NSString*)要通过- (__strong const char *)UTF8String转一下就可以了)
    int n,                    //该字符串的长度(一般用-1,系统可以自动算出字符串得长度)
    void(*)(void*)            //回调函数(这里博主还没用过所以不是很了解以后会慢慢更新)
);

对二进制数据值的绑定

int sqlite3_bind_blob(
    sqlite3_stmt*,            //指向语句的指针
    int,                      //占位符的序号(从1开始以此类推)
    const void*,              //要绑定的值(这里要的是c类型的比特(Byte),一般我们使用的是oc的NSDATA(NsData*)要通过- (const void *)bytes转一下就可以了)
    int n,                    //数据的长度(用- (NSUInteger)length得到  这里为什么不用-1呢?因为-1对于算字符串长度在行,其他的不一定准所以这里我们手动算出数据的长度)
    void(*)(void*)            //回调函数(这里博主还没用过所以不是很了解以后会慢慢更新)
);

对整数字段的取值

int sqlite3_column_int(
    sqlite3_stmt*,            //指向语句的指针
    int iCol                  //数据库中表中列的序号(从0开始以此类推)
);

对字符串字段的取值

注意这里我们取得是无符号的c字符串我们要先转为有符号C字符串再转为Objective-C字符串

例sname为oc字符串
NSString *sname=[NSString stringWithUTF8String:(const char *)sqlite3_column_text(stmt, 1)];

const unsigned char *sqlite3_column_text(
    sqlite3_stmt*,            //指向语句的指针
    int iCol                  //数据库中表中列的序号(从0开始以此类推)
);

对二进制字段的取值

注意这里我们取得是c二进制我们要转为Objective-C二进制(我们要将byte(c)转为NSData(oc)通过+ (id)dataWithBytes:(const void *)bytes length:(NSUInteger)length;因为这里需要数据的长度所以需要调用int sqlite3_column_bytes(sqlite3_stmt*, int iCol);获取数据的长度)

int length = sqlite3_column_bytes(stmt,3);//获取二进制数据的长度
NSData *img = [NSData dataWithBytes:sqlite3_column_blob(stmt, 3) length:length]; //将二进制数据转换位NSData对象

const void *sqlite3_column_blob(
    sqlite3_stmt*,            //指向语句的指针
    int iCol                  //数据库中表中列的序号(从0开始以此类推)
);

实例

新建一个类(Student)

包含以下属性

@property (retain,nonatomic) NSString *sname;
@property (assign,nonatomic) int sage;
@property (retain,nonatomic) NSData *simage;
@property (assign,nonatomic) int sid;

1.数据库的全表查询

+ (NSMutableArray*)findall
{
    NSMutableArray* stuArray;//在这里只声明不开辟空间 等用的时候再开辟(节省空间)
    sqlite3 *sqlite = [DataBase OpenDB];
    sqlite3_stmt *stmt = nil;
    int flag = sqlite3_prepare_v2(sqlite, "select * from tblstudent", -1, &stmt, nil);
    if (flag == SQLITE_OK) 
    {
        stuArray = [[NSMutableArray alloc] init];//为数组开辟空间
        while (sqlite3_step(stmt) == SQLITE_ROW) //开始指向第一行的上面 判断下一行是否存在(存在:做准备指针移到下一行)(不存在:跳出循环)
        {
            int sid1 = sqlite3_column_int(stmt, 0);
            int sage = sqlite3_column_int(stmt, 2);
            NSString *sname1 = [NSString stringWithUTF8String:(const char *)sqlite3_column_text(stmt, 1)];//获取当前表中当前行第二列的值
            int length = sqlite3_column_bytes(stmt,3);//获取二进制数据的长度 sqlite3_column_bytes():获取当前行某一列的所占内存的字节数
            NSData *img1 = [NSData dataWithBytes:sqlite3_column_blob(stmt, 3) length:length]; //将二进制数据转换位NSData对象
            //定义一个(Student*)对象并将从数据库取来的数据赋值给对象的相应属性
            Student *stu = [[Student alloc] init];//实例化
            stu.sid = sid1;
            stu.sname = sname1;
            stu.simage = img1;
            stu.sage = sage;
            [stuArray addObject:stu];//将一个对象存入数组
            [stu release];//释放对象
        }
    }
    sqlite3_finalize(stmt);//回收stmt对象
    return [stuArray autorelease];//返回包含学生信息的数组  并设为自动释放
}

2.通过姓名或者学号查询

+(Student*)findbysid:(int)sid
{
    Student *stu;//用于返回的学生对象
    sqlite3 *sqlite = [DataBase OpenDB];//打开数据库
    sqlite3_stmt *stmt = nil;//定义sql语句对象
    int flag = sqlite3_prepare_v2(sqlite, "select * from tblstudent where stuid=?", -1, &stmt, nil);//调用预处理函数将sql语句赋值给stmt对象
    if (flag == SQLITE_OK)
    {
        sqlite3_bind_int(stmt, 1, sid);//给问号占位符赋值
        while (sqlite3_step(stmt) == SQLITE_ROW)//因为一个学号肯定对应一个学生所以这里其实只执行一次
        {
            //根据列顺序(从零开始)
            int sid = sqlite3_column_int(stmt, 0);//取整型数据
            int sage = sqlite3_column_int(stmt, 2);
            NSString *sname = [NSString stringWithUTF8String:(const char *)sqlite3_column_text(stmt, 1)];//取nsstring数据
            int length = sqlite3_column_bytes(stmt,3);//获取二进制数据的长度
            NSData *img = [NSData dataWithBytes:sqlite3_column_blob(stmt, 3) length:length]; //将二进制数据转换位NSData对象
            //将从数据库中查询来的数据存到(Student*)对象中,用于返回 
            stu = [[Student alloc]init];//此时开辟空间节省内存
            stu.sid = sid;
            stu.sname = sname;
            stu.simage = img;
            stu.sage = sage;
        }
    }
    sqlite3_finalize(stmt);//回收stmt对象
    return [stu autorelease];//返回包含学生信息的对象
}

3.向数据库增加一条记录

+ (void)insertstudent:(NSString*)name age:(int)age image:(NSData*)image
{
    sqlite3 *sqlite =[ DataBase OpenDB];//打开数据库
    sqlite3_stmt *stmt = nil;//定义sql语句对象
    int flag = sqlite3_prepare_v2(sqlite, "insert into tblstudent(stuname,stuage,stuimage) values(?,?,?)", -1, &stmt, nil);//调用预处理函数将sql语句赋值给stmt对象  多值绑定逗号隔开
    if (flag == SQLITE_OK)
    {
        sqlite3_bind_text(stmt, 1, [name UTF8String],-1,nil);//给问号占位符赋值
        sqlite3_bind_int(stmt, 2, age);//对整型数据的绑定
        sqlite3_bind_blob(stmt, 3, [image bytes], [image length], nil);//对二进制类型数据的绑定 数据的字节数(-1 针对字符串的长度比较准)
        if(sqlite3_step(stmt) == SQLITE_ERROR)//执行insert动作
        {
            NSLog(@"insert error");
        }
    }
    sqlite3_finalize(stmt);//回收stmt对象
}

4.修改更新数据库的数据

+ (void)updatestudent:(Student*) stu
{
    sqlite3 *sqlite = [DataBase OpenDB];//打开数据库
    sqlite3_stmt *stmt = nil;//定义sql语句对象
    int flag = sqlite3_prepare_v2(sqlite, "update tblstudent set stuname=?,stuage=?,stuimage=? where stuid=?", -1, &stmt, nil);//调用预处理函数将sql语句赋值给stmt对象
    if (flag == SQLITE_OK)
    {
        sqlite3_bind_text(stmt, 1, [stu.sname UTF8String],-1,nil);//给问号占位符赋值
        //stu.sname为nsstring    UTF8String    nsstring---->ctring
        sqlite3_bind_int(stmt, 4, stu.sid);//给问号占位符赋值
        sqlite3_bind_int(stmt, 2, stu.sage);//给年龄赋值
        sqlite3_bind_blob(stmt, 3, [stu.simage bytes], [stu.simage length], nil);
        if(sqlite3_step(stmt) == SQLITE_ERROR)//执行update动作
        {
            NSLog(@"update error");
        }
        sqlite3_finalize(stmt);//回收stmt对象
    }
}

5.删除数据库的记录

+ (void)deletebysid:(int) sid
{
    sqlite3 *sqlite=[DataBase OpenDB];//打开数据库
    sqlite3_stmt *stmt=nil;//定义sql语句对象
    int flag=sqlite3_prepare_v2(sqlite, "delete from tblstudent where stuid=?", -1, &stmt, nil);//调用预处理函数将sql语句赋值给stmt对象
    if (flag==SQLITE_OK)
    {
        sqlite3_bind_int(stmt, 1, sid);//给问号占位符赋值  1.语句2.占位符的序号3.给占位符赋得值
        //执行delete动作
        if(sqlite3_step(stmt)==SQLITE_ERROR)//未执行成功
        {
            NSLog(@"delete error");
        }
    }
    sqlite3_finalize(stmt);//回收stmt对象

    NSLog(@"删除了第%d",sid);
}

Reference

http://www.cnblogs.com/jy578154186/archive/2012/10/18/2730113.html

2015/10/25