当前位置:  互联网>综合
本页文章导读:
    ▪快速排序 详解      快速排序算法是一种分治排序算法,它将数组划分为两部分,然后分别对这两部分进行排序。它将重排序数组,使之满足一下三个条件: 1,对于某个i,a[i]在最终的位置上 2,a[l]…a[i-1]中的.........
    ▪Java - 通过IP地址获取用户所在地      最近在做一个互联网项目,不可避免和其他互联网项目一样,需要各种类似的功能。其中一个就是通过用户访问网站的IP地址显示当前用户所在地。在没有查阅资料之前,我第一个想到的.........
    ▪集体智慧编程学习之优化系统      优化系统的想法真不好简单地说的明白,这样吧,我爸在陕西西安,我妈在安徽的合肥,我弟弟在深圳,打算坐飞机到北京我这里玩。家人都比较节省,打算到了机场后互相等对方,然后一起.........

[1]快速排序 详解
    来源: 互联网  发布时间: 2013-10-24

快速排序算法是一种分治排序算法,它将数组划分为两部分,然后分别对这两部分进行排序。它将重排序数组,使之满足一下三个条件:

1,对于某个i,a[i]在最终的位置上

2,a[l]…a[i-1]中的元素都比a[i]小

3,a[i+1] …a[r]中的元素都比a[i]大

通过划分后完成本轮排序,然后递归地处理子文件。

如果数组中有一个或者0个元素,就什么都不做。否则,调用以下算法实现快速排序:

int partition(Itema[],int l,int r)

{

       int i=l-1,j=r;

       Item v=a[r];

       for (;;)

       {

              while (less(a[++i],v))

              {

                     ;

              }

 

              while (less(v,a[--j]))

              {

                     if (j==1)

                     {

                            break;

                     }

              }

              if (i>=j)

              {

                     break;

              }

              exch(a[i],a[j]);

       }

       exch(a[i],a[r]);

 

       return i;

}

变量v保存了划分元素a[r],i和j分别是左扫描指针和右扫描指针。划分循环使得i增加j减小,while循环保持一个不变的性质---------i左侧没有元素比v大,j右侧没有元素比v小。一旦两个指针相遇,我们就交换啊a[i]和a[r],,这样v左侧的元素都小于v,v右侧的元素都大于等于v,结束划分过程。

划分是一个不确定的过程,当两个指针相遇,就通过break语句结束。测试j==1用来防止划分元素是文件总的最小元素。

voidquichsort(Item a[],int l,int r)

{

       int i;

       if (r<=l)

       {

              return;

       }

 

       i=partition(a,l,r);

       quichsort(a,l,i-1);

       quichsort(a,i+1,r);

}

注:快速排序是一个递归划分过程,我们对一个文件进行划分,划分原则是将一些元素放在它最终的位置上,对数组进行排序使比划分元素小的元素都在划分元素的左边,比划分元素大的元素都在划分元素的右边,然后分别对左右两部分进行递归处理。然后,从数组的左端进行扫描,直到找到一个大于划分元素的元素,同时从数据的右端开始扫描,直到找到一个小于划分元素的元素。使扫描停止的这个两个元素,显然在最终的划分数组中的位置相反,于是交换二者。继续这一过程,我们就可以保证比划分元素小的元素都在划分元素的左边,比划分元素大的元素都在划分元素的右边。

  性能特征:

  快速排序最坏情况下使用N*N/2次比较

  快速排序平均情况下使用2*N*㏒N次比较

  快速排序算法是一种不稳定的算法。

  算法示意图

A    

    S

    0

    R

    T

     I

     N

    G

    E

    X  

A   

M   

   P

     L

    E

A

A

E

E

 

 

 

 

O

 

S

 

 

 

R

A

A

E

 

 

 

 

 

 


    
[2]Java - 通过IP地址获取用户所在地
    来源: 互联网  发布时间: 2013-10-24

最近在做一个互联网项目,不可避免和其他互联网项目一样,需要各种类似的功能。其中一个就是通过用户访问网站的IP地址显示当前用户所在地。在没有查阅资料之前,我第一个想到的是应该有这样的RESTFUL服务,可能会有免费的,也有可能会是收费的。后来查阅了相关资料和咨询了客服人员发现了一款相当不错的库:GEOIP。

中文官网:http://www.maxmind.com/zh/home?pkit_lang=zh

英文官网:http://www.maxmind.com/en/home

而且GeoIP也提供了如我之前猜测的功能:Web Services,具体可以看这里:http://dev.maxmind.com/geoip/legacy/web-services

这里我就把官方的实例搬过来吧,Web Services :

首先来个Java 版本:

import java.net.MalformedURLException;
import java.net.URL;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class OmniReader {
    public static void main(String[] args) throws Exception {
        String license_key = "YOUR_LICENSE_KEY";
        String ip_address = "24.24.24.24";

        String url_str = "http://geoip.maxmind.com/e?l=" + license_key + "&i=" + ip_address;

        URL url = new URL(/blog_article/url_str/index.html);
        BufferedReader in = new BufferedReader(new InputStreamReader(url.openStream()));
        String inLine;
        
        while ((inLine = in.readLine()) != null) {
            // Alternatively use a CSV parser here.
            Pattern p = Pattern.compile("\"([^\"]*)\"|(?<=,|^)([^,]*)(?:,|$)"); 
            Matcher m = p.matcher(inLine);

            ArrayList fields = new ArrayList();
            String f;
            while (m.find()) {
                f = m.group(1);
                if (f!=null) {
                    fields.add(f);
                }
                else {
                    fields.add(m.group(2));
                }
            }
            
            String countrycode = fields.get(0);
            String countryname = fields.get(1);
            String regioncode = fields.get(2);
            String regionname = fields.get(3);
            String city = fields.get(4);
            String lat = fields.get(5);
            String lon = fields.get(6);
            String metrocode = fields.get(7);
            String areacode = fields.get(8);
            String timezone = fields.get(9);
            String continent = fields.get(10);
            String postalcode = fields.get(11);
            String isp = fields.get(12);
            String org = fields.get(13);
            String domain = fields.get(14);
            String asnum = fields.get(15);
            String netspeed = fields.get(16);
            String usertype = fields.get(17);
            String accuracyradius = fields.get(18);
            String countryconf = fields.get(19);
            String cityconf = fields.get(20);
            String regionconf = fields.get(21);
            String postalconf = fields.get(22);
            String error = fields.get(23);
        }

        in.close();
    }
}

C#版本:

private string GetMaxMindOmniData(string IP) {
  System.Uri objUrl = new System.Uri("http://geoip.maxmind.com/e?l=YOUR_LICENSE_KEY&i=" + IP);
  System.Net.WebRequest objWebReq;
  System.Net.WebResponse objResp;
  System.IO.StreamReader sReader;
  string strReturn = string.Empty;

  try
    {
      objWebReq = System.Net.WebRequest.Create(objUrl);
      objResp = objWebReq.GetResponse();

      sReader = new System.IO.StreamReader(objResp.GetResponseStream());
      strReturn = sReader.ReadToEnd();

      sReader.Close();
      objResp.Close();
    }
  catch (Exception ex)
    {
    }
  finally
    {
      objWebReq = null;
    }

  return strReturn;
}

Ruby版本:

#!/usr/bin/env ruby

require 'csv'
require 'net/http'
require 'open-uri'
require 'optparse'
require 'uri'

fields = [:country_code,
          :country_name,
          :region_code,
          :region_name,
          :city_name,
          :latitude,
          :longitude,
          :metro_code,
          :area_code,
          :time_zone,
          :continent_code,
          :postal_code,
          :isp_name,
          :organization_name,
          :domain,
          :as_number,
          :netspeed,
          :user_type,
          :accuracy_radius,
          :country_confidence,
          :city_confidence,
          :region_confidence,
          :postal_confidence,
          :error]

options = { :license => "YOUR_LICENSE_KEY", :ip => "24.24.24.24" }
OptionParser.new { |opts|
  opts.banner = "Usage: omni-geoip-ws.rb [options]"

  opts.on("-l", "--license LICENSE", "MaxMind license key") do |l|
    options[:license] = l
  end

  opts.on("-i", "--ip IPADDRESS", "IP address to look up") do |i|
    options[:ip] = i
  end
}.parse!

uri = URI::HTTP.build(:scheme => 'http',
                      :host   => 'geoip.maxmind.com',
                      :path   => '/e',
                      :query  => URI.encode_www_form(:l => options[:license],
                                                     :i => options[:ip]))

response = Net::HTTP.get_response(uri)

unless response.is_a?(Net::HTTPSuccess)
  abort "Request failed with status #{response.code}"
end

omni = Hash[fields.zip(response.body.encode('utf-8', 'iso-8859-1').parse_csv)]

if omni[:error]
  abort "MaxMind returned an error code for the request: #{omni[:error]}"
else
  puts
  puts "MaxMind Omni data for #{options[:ip]}";
  puts
  omni.each { |key, val| printf "  %-20s  %s\n", key, val }
  puts
end

最后再来个Perl版本吧:

#!/usr/bin/env perl

use strict;
use warnings;

use Encode qw( decode );
use Getopt::Long;
use LWP::UserAgent;
use Text::CSV_XS;
use URI;
use URI::QueryParam;

my @fields = qw(
    country_code
    country_name
    region_code
    region_name
    city_name
    latitude
    longitude
    metro_code
    area_code
    time_zone
    continent_code
    postal_code
    isp_name
    organization_name
    domain
    as_number
    netspeed
    user_type
    accuracy_radius
    country_confidence
    city_confidence
    region_confidence
    postal_confidence
    error
);

my $license_key = 'YOUR_LICENSE_KEY';
my $ip_address  = '24.24.24.24';

GetOptions(
    'license:s' => \$license_key,
    'ip:s'      => \$ip_address,
);

my $uri = URI->new('http://geoip.maxmind.com/e');
$uri->query_param( l => $license_key );
$uri->query_param( i => $ip_address );

my $ua = LWP::UserAgent->new( timeout => 5 );
my $response = $ua->get($uri);

die 'Request failed with status ' . $response->code()
    unless $response->is_success();

my $csv = Text::CSV_XS->new( { binary => 1 } );
$csv->parse( decode( 'ISO-8859-1', $response->content() ) );

my %omni;
@omni{@fields} = $csv->fields();

binmode STDOUT, ':encoding(UTF-8)';

if ( defined $omni{error} && length $omni{error} ) {
    die "MaxMind returned an error code for the request: $omni{error}\n";
}
else {
    print "\nMaxMind Omni data for $ip_address\n\n";
    for my $field (@fields) {
        print sprintf( "  %-20s  %s\n", $field, $omni{$field} );
    }
    print "\n";
}

以上都是基于Web Services的,这里我再写个使用本地库的实例,而项目中也使用的是本地库。

首先在项目中需要添加库文件:GeoLiteCity,然后就可以利用这个文件得到城市和国家信息了,Java代码:

public class GeoBusiness {
	/**
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		System.out.println(getLocationByIp("220.181.111.147").getCity());
		System.out.println(getLocationByIp("220.181.111.147").getCountryName());
	}

	public static Location getLocationByIp(String ipaddr) throws IOException {
		String sep = System.getProperty("file.separator");
		String dir = Play.configuration.getProperty("geoip.datdir");
		String dbfile = dir + sep + "GeoLiteCity.dat";
		LookupService cl = new LookupService(dbfile,
				LookupService.GEOIP_MEMORY_CACHE);
		Location location = cl.getLocation(ipaddr);

		cl.close();
		return location;
	}
}

更详细的功能比如获取省,经纬度可以参考我最前面给出的网址。


作者:huxiweng 发表于2013-5-19 8:28:52 原文链接
阅读:0 评论:0 查看评论

    
[3]集体智慧编程学习之优化系统
    来源: 互联网  发布时间: 2013-10-24

优化系统的想法真不好简单地说的明白,这样吧,我爸在陕西西安,我妈在安徽的合肥,我弟弟在深圳,打算坐飞机到北京我这里玩。家人都比较节省,打算到了机场后互相等对方,然后一起坐车租车到我住的地方。然后让我给订机票,这可难住我了。

我查了qunar,一天从西安,合肥,深圳到北京有很多班飞机,怎么样让他们总的机票价格最少,并且在机场互相等待的时间降到最低,这里假设一个人等10分钟相当于1块钱,这样我们的目标就是schedulcost=(父亲机票钱+母亲hf-bj机票钱+弟弟机票钱+父亲等候分钟/10+母亲等候分钟/10+弟弟等候时间/10)最小,这里面有可能父亲,或者母亲或者弟弟的等候分钟是0。

先定义我的家人:

people = [('baba','XA'),
          ('mama','HF'),
          ('didi','sz')]
爸爸从西安出发,妈妈从合肥出发,弟弟从深圳出发;


再定义航班信息:

flights = [('XA','BJ') : [('06:30', '08:30', 600), ('07:45', '10:15', 500)....],
	('HF','BJ') : [('06:45', '09:30', 900), ('07:25', '10:45', 800)....],
	('SZ','BJ') : [('06:25', '10:30', 1200), ('08:05', '12:10', 1300)....],
]

从西安到北京的航班有:6:30出发,8:30到达,机票600元;07:45出发,10:15到达,机票500元。。。

从合肥到北京的航班有:6:45出发,9:30到达,机票900元;07:25出发,10:45到达,机票800元。。。

从深圳到北京的航班有:6:25出发,10:30到达,机票1200元;08:05出发,12:10到达,机票1300元。。。


下面假设我定的航班是:

sol = [2,2,1]
从西安到北京的第二班,从合肥到北京的第二班,从西安到北京的第一班


下面就可以算计我上面定的航班的花费了:其中

def schedulecost(sol):
  totalprice=0
  latestarrival=0

  for d in range(len(sol)):
    origin=people[d][1]
    outbound=flights[(origin,'BJ')][int(sol[d])]
    
    totalprice+=outbound[2]
    
    if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
  
  totalwait=0  
  for d in range(len(sol)):
    origin=people[d][1]
    outbound=flights[(origin,'BJ')][int(sol[d])]
    totalwait+=latestarrival-getminutes(outbound[1]) 
  
  return totalprice+totalwait/10
很好懂,shedulecost计算了总的航班机票钱和总的等候时间,

计算总的等候时候先找出最晚到达的一班飞机的时间latestarrival。


我们的目标:找出某种组合的sol,让schedulecost最低;


因为一天内的航班有很多,并且我已经把问题简单到最低,所以在现实情况中很容易sol的各种组合数会上亿。

如果shedulecost稍微复杂的话,在各种sol中找到最优解是不现实的。下面看看几种可能的做法:
(一)随机搜索法

最简单的,随机计算其中的一部分结果,比如100条可能的解,最终的结果取这部分计算结果中的最小值,这种算法最简单,问题也最明显。

下面的实现,第一个参数是每种可能结果的范围,比如从西安到北京一天有100个航班,从合肥到北京一天有80个航班,从深圳到北京一天有150个航班,那么domain的定义就是domain=[(0,100),(0,80),(0,150)];第二个参数就是上面定义的schedulecost函数;

def randomoptimize(domain,costf):
  best=999999999
  bestr=None
  for i in range(0,1000):
    # Create a random solution
    r=[float(random.randint(domain[i][0],domain[i][1])) 
       for i in range(len(domain))]
    
    # Get the cost
    cost=costf(r)
    
    # Compare it to the best one so far
    if cost<best:
      best=cost
      bestr=r 
  return r
一千次的尝试可能是总解总很说得好的一部分,但是在多试几次之后,也许会得到一个差不多的解;


随机搜索法的问题在于,随机搜索是跳跃性的,这次的计算和上次的计算之前没有任何关系,也就是最新一次计算并没能利用之前已发现的优解,下面看看几种改进的算法:


(二)模拟爬山法
爬山法从一个随机解开始,然后在其临近的解中寻找更好的题解。在本例中,亦即找到所有相对于最初的随机安排,能够让某个人乘坐的航班稍早或者稍晚一些的安排,沃恩对每一个相邻的时间安排都进行成本计算,具有最低成本的安排将成为新的题解。重复这一过程知道没有相邻安排能够改善成本为止:

def hillclimb(domain,costf):
  # Create a random solution
  sol=[random.randint(domain[i][0],domain[i][1])
      for i in range(len(domain))]
  # Main loop
  while 1:
    # Create list of neighboring solutions
    neighbors=[]
    
    for j in range(len(domain)):
      # One away in each direction
      if sol[j]>domain[j][0]:
        neighbors.append(sol[0:j]+[sol[j]+1]+sol[j+1:])
      if sol[j]<domain[j][1]:
        neighbors.append(sol[0:j]+[sol[j]-1]+sol[j+1:])

    # See what the best solution amongst the neighbors is
    current=costf(sol)
    best=current
    for j in range(len(neighbors)):
      cost=costf(neighbors[j])
      if cost<best:
        best=cost
        sol=neighbors[j]

    # If there's no improvement, then we've reached the top
    if best==current:
      break
  return sol

之所以叫爬山法,就是我们沿着一条下坡路一直走到坡底,这个方法的速度很快,并且找到的结果一般会比随机搜索法好一些。但是也有个问题,这种算法的假设是最优解就在初始下坡位置的波谷处,第一次的随机解会影响最终的效果。所以这种算法可以求出局部最优解,而不是全局最优解。


(三)模拟退火法

退火指合金在加热后再慢慢冷却的过程。大量的原子因为受到激发而向周围跳跃,然后又逐渐稳定到一个低能阶的状态。

有时候在找到最优解前转向一个更差的解是有必要的。退火法一个随机解开始,用一个变量表示温度,温度在最开始会很高,尔后慢慢变低。每一次迭代周期,算法会随机选中题解中的某个数字,然后朝某个方向变化。这个算法和爬山法的区别是。爬山法每次的迭代都会朝成本最低的发展,而退火法不一定,有一定的比

    
最新技术文章:
▪用户及权限基础 2---- Linux权限    ▪用户及权限基础 3---- Linux扩展权限    ▪git 简明教程(1) --创建及提交
▪背包 代码    ▪json对象的封装与解析    ▪01背包,完全背包,多重背包 ,模板代码
▪apache安装详解    ▪HDU 4668 Finding string (解析字符串 + KMP)    ▪《TCP-IP详解 卷1:协议》学习笔记(二)
▪《TCP-IP详解 卷1:协议》学习笔记(持续更新...    ▪windows下使用swig    ▪gensim试用
▪Linux Shell脚本编程--nc命令使用详解    ▪solr对跨服务器表联合查询的配置    ▪递归和非递归实现链表反转
Web服务器/前端 iis7站长之家
▪用C语言写CGI入门教程    ▪用hdfs存储海量的视频数据的设计思路    ▪java多线程下载的实现示例
▪【原创】eAccelerator 一个锁bug问题跟踪    ▪hadoop学习之ZooKeeper    ▪使用cuzysdk web API 实现购物导航类网站
▪二维数组中的最长递减子序列    ▪内嵌W5100的网络模块WIZ812MJ--数据手册    ▪xss 跨站脚本攻击
▪RobotFramework+Selenium2环境搭建与入门实例    ▪什么是API    ▪用PersonalRank实现基于图的推荐算法
▪Logtype    ▪关于端口号你知道多少!    ▪Linux基本操作 1-----命令行BASH的基本操作
▪CI8.7--硬币组合问题    ▪Ruby on Rails 学习(五)    ▪如何使用W5300实现ADSL连接(二)
▪不允许启动新事务,因为有其他线程正在该会...    ▪getting start with storm 翻译 第六章 part-3    ▪递归求排列和组合(无重复和有重复)
▪工具类之二:RegexpUtils    ▪Coding Interview 8.2    ▪Coding Interview 8.5
▪素因子分解 Prime factorization    ▪C# DllImport的用法    ▪图的相关算法
▪Softmax算法:逻辑回归的扩展    ▪最小生成树---Kruskal算法---挑战程序设计竞赛...    ▪J2EE struts2 登录验证
▪任意两点间的最短路径---floyd_warshall算法    ▪Sqoop实现关系型数据库到hive的数据传输    ▪FFMPEG采集摄像头数据并切片为iPhone的HTTP Stream...
▪Ubuntu 13.04 – Install Jetty 9    ▪TCP/IP笔记之多播与广播    ▪keytool+tomcat配置HTTPS双向证书认证
▪安装phantomjs    ▪Page Redirect Speed Test    ▪windows media player 中播放pls的方法
▪sre_constants.error: unbalanced parenthesis    ▪http headers    ▪Google MapReduce中文版
▪The TCP three-way handshake (connect)/four wave (closed)    ▪网站反爬虫    ▪Log4j实现对Java日志的配置全攻略
▪Bit Map解析    ▪Notepad 快捷键 大全    ▪Eclipse 快捷键技巧 + 重构
▪win7 打开防火墙端口    ▪Linux Shell脚本入门--awk命令详解    ▪Linux Shell脚本入门--Uniq命令
▪Linux(Android NDK)如何避免僵死进程    ▪http Content-Type一览表    ▪Redis实战之征服 Redis + Jedis + Spring (二)
▪Tomcat7.0.40 基于DataSourceRealm的和JDBCRealm的资源...    ▪利用SQOOP将ORACLE到HDFS    ▪django输出 hello world
▪python re    ▪unity3D与网页的交互    ▪内存共享基本演示
▪python join    ▪不再为无限级树结构烦恼,且看此篇    ▪python实现变参
▪打开文件数限制功能不断地制造问题    ▪Arduino Due, Maple and Teensy3.0 的 W5200性能测试    ▪Selenium实例----12306网站测试
▪基于协同过滤的推荐引擎    ▪C4.5决策树    ▪C#HTTP代理的实现之注册表实现
▪nosql和关系型数据库比较?    ▪如何快速比较这两个字符串是否相等?    ▪hdoj 1863 畅通工程 最小生成树---prime算法
 


站内导航:


特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

©2012-2021,,E-mail:www_#163.com(请将#改为@)

浙ICP备11055608号-3