国外程序员整理的 PHP 资源大全

ziadoz 在 Github 发起维护的一个 PHP 资源列表,内容包括:库、框架、模板、安全、代码分析、日志、第三方库、配置工具、Web 工具、书籍、电子书、经典博文等等。


依赖管理

依赖和包管理库

 

其他的依赖管理

其他的相关依赖管理

 

框架

Web开发框架

其他框架

其他Web开发框架

框架组件

来自web开发框架的独立组件

微型框架

微型框架和路由

  • Silex - 基于Symfony2组件的微型框架
  • Slim - 另一个简单的微型框架
  • Bullet PHP -用于构建REST APIs的微型框架
  • Fast Route - 快速路由库
  • Pux -另一个快速路由库

 

其他微型框架

其他相关的微型框架和路由

模板

模板化和词法分析的库和工具

  • Twig -一个全面的模板语言
  • Twig Cache Extension -一个用于Twig的模板片段缓存库
  • Mustache -一个Mustache模板语言的PHP实现
  • Phly Mustache -另一个Mustache模板语言的PHP实现
  • MtHaml - 一个HAML 模板语言的PHP实现
  • PHPTAL -一个 TAL 模板语言的PHP实现
  • Plates -一个原生PHP模板库
  • Lex -一个轻量级模板解析器

静态站点生成器

预处理工具来生成web页面的内容。

  • Sculpin -转换Markdown和Twig为静态HTML的工具
  • Phrozn - 另一个转换Textile,Markdown和Twig为HTML的工具

HTTP

用于HTTP和网站爬取的库

  • Guzzle -一个全面的HTTP客户端
  • Buzz -另一个HTTP客户端
  • Requests -一个简单的HTTP库
  • HTTPFul -一个链式HTTP库
  • Goutte -一个简单的web爬取器
  • PHP VCR -录制和重放HTTP请求的库

 

URL

解析URL的库

 

Email

发送和解析邮件的库

文件

文件处理和MIME类型检测库

 

Streams 流

处理流的库

  • Streamer - 一个面向对象的流包装库

 

Dependency Injection依赖注入

实现依赖注入设计模式的库

  • Pimple - 一个小的依赖注入容器
  • Auryn - 另一个依赖注入容器
  • Orno Di -另一个可伸缩的依赖注入容器
  • PHP DI -一个使用注释实现的依赖注入
  • Acclimate -一个依赖注入容器和服务定位的通用接口

 

Imagery 图像

处理图像的库

 

Testing 测试

测试代码和生成测试数据的库

  • PHPUnit -一个单元测试框架
  • DBUnit -PHPUnit的数据库测试库
  • ParaTest - PHPUnit的并行测试库
  • PHPSpec -基于功能点设计的单元测试库
  • Codeception -一个全栈测试框架
  • AspectMock -  PHPUnit/ Codeception 模拟框架。
  • Atoum -一个简单的测试库
  • Mockery -一个用测试的模拟对象库
  • Phake -另一个用测试的模拟对象库
  • Prophecy -一个可选度很高的模拟框架
  • Faker -一个伪数据生成库
  • Samsui - 另一个伪数据生成库
  • Alice -富有表现力的一代库
  • Behat -一个行为驱动开发(BDD)测试框架
  • Pho -一个行为驱动开发测试框架
  • Mink -Web验收测试
  • HTTP Mock - 一个在单元测试模拟HTTP请求的库
  • VFS Stream -一个用于测试的虚拟文件系统流的包装器
  • VFS -另一个用于测试虚拟文件系统
  • Locust -一个用Python编写的现代加载测试库

 

Continuous Integration 持续集成

持续集成的库和应用

  • Travis CI - 一个持续集成平台
  • PHPCI -一个PHP的开源持续集成平台
  • Sismo - 一个持续测试服务库
  • Jenkins一个 PHP 支持的持续集成平台
  • JoliCi - 一个用PHP编写的由Docker支持的持续集成客户端

 

Documentation 文档

生成项目文档的库

  • Sami -一个API文档生成器
  • APIGen -另一个API文档生成器
  • PHP Documentor 2 -一个API文档生成器
  • phpDox - 一个PHP项目的文档生成器(不限于API文档)

 

Security 安全

生成安全的随机数,加密数据,扫描漏洞的库

 

Passwords 密码

处理和存储密码的库和工具

 

Code Analysis 代码分析

分析,解析和处理代码库的库的工具

Debugging 调试

调试代码的库和工具

 

Build Tools 构建工具

项目构建和自动化工具

  • Go -一个简单的PHP构建工具
  • Bob - 一个简单的项目自动化工具
  • Phake -一个PHP克隆库
  • Box - 一个构建PHAR文件的工具
  • Phing -一个灵感来自于Apache Ant的PHP项目构建系统

 

Task Runners 任务运行器

自动运行任务的库

  • Task -一个灵感来源于Grunt和Gulp的纯PHP任务运行器
  • Robo -一个面向对象配置的PHP任务运行器
  • Bldr -一个构建在Symfony组件上的PHP任务运行器

 

Navigation导航

构建导航结构的工具

 

Asset Management 资源管理

管理,压缩和最小化web站点资源的工具

  • Assetic - 一个资源管理的管道库
  • Pipe -另一个资源管理的管道库
  • Munee -一个资源优化库
  • JShrink -一个JavaScript最小化库
  • Puli - 一个检测资源绝对路径的库

 

Geolocation 地理位置

为地理编码地址和使用纬度经度的库。

  • GeoCoder -一个地理编码库
  • GeoTools -一个地理工具相关的库
  • PHPGeo -一个简单的地理库
  • GeoJSON -一个地理JSON的实现

 

Date and Time 日期和时间

处理日期和时间的库

 

Event 事件

时间驱动或非阻塞事件循环实现的库

 

Logging 日志

生成和处理日志文件的库

  • Monolog - 一个全面的日志工具
  • KLogger -一个易用的PSR-3兼容的日志类

 

E-commerce 电子商务

处理支付和构建在线电子商务商店的库和应用

  • OmniPay -一个框架混合了多网关支付处理的库
  • Payum - 一个支付抽象库
  • Sylius - 一个开源的电子商务解决方案
  • Thelia -另一个开源的电子商务解决方案
  • Money - 一个Fowler金钱模式的PHP实现
  • Sebastian Money -另一个处理货币值的库
  • Swap -一个汇率库

 

PDF

处理PDF文件的库和软件

  • Snappy -一个PDF和图像生成器库
  • WKHTMLToPDF -一个将HTML转换为PDF的工具

 

Database 数据库

使用对象关系映射(ORM)或数据映射技术的数据库交互库

  • Doctrine -一个全面的DBAL和ORM
  • Doctrine Extensions -一个Doctrine行为扩展的集合
  • Propel - 一个快速的ORM,迁移库和查询构架器
  • Eloquent -Laravel 4 ORM
  • Baum -一个Eloquent的嵌套集实现
  • Spot2 -一个MySQL的ORM映射器
  • RedBean -一个轻量级,低配置的ORM
  • Pomm -一个PostgreSQL对象模型管理器
  • ProxyManager -一个为数据映射生成代理对象的工具集

 

Migrations 迁移

帮助管理数据库模式和迁移的库

 

NoSQL

处理NoSQL后端的库

  • MongoQB -一个MongoDB查询构建库
  • Monga -一个MongoDB抽象库
  • Predis - 一个功能完整的Redis库

 

Queue 队列

处理事件和任务队列的库

 

Search 搜索

在数据上索引和执行查询的库和软件

 

Command Line 命令行

构建命令行工具的库

  • Boris - 一个微型PHP REPL
  • PsySH - 另一个微型PHP REPL
  • Pecan -一个事件驱动和非阻塞内核
  • GetOpt - 一个命令行选择解析器
  • OptParse -另一个命令行选择解析器
  • Commando -另一个简单的命令行选择解析器
  • GetOptionKit -另一个命令行选择解析器
  • Cron Expression -计算cron运行日期的库
  • ShellWrap -一个简单的命令行包装库
  • Hoa Console -另一个命令行库
  • Shunt - 一个在多台远程机器上并行运行命令行的库
  • Cilex -一个构建命令行工具的微型框架

 

Authentication 身份验证

实现身份验证的库

  • Sentry -一个混合的身份验证和授权的框架库
  • Sentry Social -一个社交网络身份验证库
  • Opauth -一个多渠道的身份验证框架
  • OAuth2 -一个OAuth2身份验证服务,资源服务器和客户端库
  • OAuth2 Server -另一个OAuth2服务器实现
  • PHP oAuthLib -另一个OAuth库
  • TwitterOAuth -一个Twitter OAuth库
  • TwitterSDK -一个完全测试的Twitter SDK
  • Hawk -一个Hawk HTTP身份认证库
  • HybridAuth -一个开源的社交登陆库

 

Markup 标记

处理标记的库

 

Strings 字符串

解析和处理字符串的库

 

Numbers 数字

处理数字的库

 

Filtering and Validation 过滤和验证

过滤和验证数据的库

  • Filterus - 一个简单的PHP过滤库
  • Respect Validate -一个简单的验证库
  • Valitron -另一个验证库
  • Upload - 一个处理文件上传和验证的库
  • DMS Filter - 一个注释过滤库
  • MetaYaml -一个支持YAML,JSON和XML的模式验证库
  • ISO-codes -验证各种ISO和ZIP编码的库(IBAN, SWIFT/BIC, BBAN, VAT, SSN, UKNIN)

 

 REST和API

开发REST-ful API的库和web工具

  • Apigility -一个使用Zend Framework 2构建的API构建器
  • Hateoas -一个HOATEOAS REST web服务库
  • HAL -一个超文本应用语言(HAL)构建库
  • Negotiation -一个内容协商库
  • Drest -一个将Doctrine实体暴露为REST资源节点的库
  • Restler -一个将PHP方法暴露为RESTful web API的轻量级框架

 

Caching 缓存

缓存数据的库

 

数据结构和存储

实现数据结构和存储技术的库

  • Ardent -一个数据结构库
  • PHP Collections - 一个简单的集合库
  • Serializer -一个序列化和反序列化数据的库
  • PHP Object Storage -一个对象存储库
  • Fractal -一个转换复杂数据结构到JSON输出的库
  • Totem -一个管理和穿件数据交换集的库
  • PINQ -一个PHP实时Linq库
  • JsonMapper -一个将内嵌JSON结构映射为PHP类的库

 

Notifications 通知

处理通知软件的库

 

Deployment 部署

项目部署库

  • Pomander -一个PHP应用部署工具
  • Rocketeer -PHP世界里的一个快速简单的部署器
  • Envoy -一个用PHP运行SSH任务的工具
  • Plum - 一个部署库

 

国际化和本地化

国际化(I18n)和本地化(L10n)

 

第三方API

访问第三方API的库

 

Extensions 扩展

帮组构建PHP扩展的库

  • Zephir -用于开发PHP扩展,且介于PHP和C++之间的编译语言
  • PHP CPP -一个开发PHP扩展的C++库

 

Miscellaneous 杂项

不在上面分类中的有用库和工具

 

Software 软件

创建一个开发环境的软件

PHP安装

在你的电脑上帮助安装和管理PHP的工具

  • HomeBrew -一个OSX包管理器
  • HomeBrew PHP -一个HomeBrew的PHP通道
  • PHP OSX - 一个OSX下的PHP安装器
  • PHP Brew -一个PHP版本管理和安装器
  • PHP Env - 另一个PHP版本管理器
  • PHP Switch - 另一个PHP版本管理器
  • PHP Build - 另一个PHP版本安装器
  • VirtPHP - 一个创建和管理独立PHP环境的工具

 

Development Environment 开发环境

创建沙盒开发环境的软件和工具

  • Vagrant -一个便携的开发环境工具
  • Ansible - 一个非常简单的编制框架
  • Puppet -一个服务器自动化框架和应用
  • PuPHPet -一个构建PHP开发虚拟机的web工具
  • Protobox -另一个构建PHP开发虚拟机的web工具
  • Phansible - 一个用Ansible构建PHP开发虚拟机的web工具

 

Virtual Machines 虚拟机

相关的PHP虚拟机

  • HipHop PHP -Facebook出品的PHP虚拟机,运行时和JIT
  • HippyVM -另一个PHP虚拟机
  • Hack - 一个PHP进行无缝操作的 HHVM编程语言

IDE 集成开发环境

支持PHP的集成开发环境

 

Web Applications Web应用

基于Web的应用和工具

  • 3V4L一个在线的PHP shell
  • DBV -一个数据库版本控制应用
  • PHP Queue -一个管理后端队列的应用
  • Composer as a Service - 作为一个zip文件下载Composer包的工具
  • MailCatcher - 一个抓取和查看邮件的web工具

 

Resources 资源

各种提高你的PHP开发技能和知识的资源,比如书籍,网站,文章

PHP网站

PHP相关的有用网站

 

Other Websites 其他网站

web开发相关的有用网站

 

PHP 书籍

PHP相关的非常好的书籍

 

其他书籍

与一般计算和web开发相关的书

 

PHP视频

PHP相关的非常不错的视频

 

PHP阅读

PHP相关的阅读资料

 

PHP Internals Reading PHP内核阅读

阅读PHP内核或性能相关的资料

发表在 涨姿势 | 留下评论

再一次, 不要使用(include/require)_once(转载)

最近关于apc.include_once_override的去留, 我们做了几次讨论, 这个APC的配置项一直一来就没有被很好的实现过.

在这里, 我想和大家在此分享下, 这个问题的原因, 以及对我们的一些启示.

关于使用include还是include_once(以下,都包含require_once), 这个讨论很长了, 结论也一直有, 就是尽量使用include, 而不是include_once, 以前最多的理由的是, include_once需要查询一遍已加载的文件列表, 确认是否存在, 然后再加载.

诚然, 这个理由是对的, 不过, 我今天要说的, 是另外一个的原因.

我们知道, PHP去判断一个文件是否被加载, 是需要得到这个文件的opened_path的, 意思是说, 比如:

  1. <?php
  2. set_include_path(“/tmp/:/tmp2/”);
  3. include_once(“2.php”);
  4. ?>

当PHP看到include_once “2.php”的时候, 他并不知道这个文件的实际路径是什么, 也就无法从已加载的文件列表去判断是否已经加载, 所以在include_once的实现中, 会首先尝试解析这个文件的真实路径(对于普通文件这个解析仅仅类似是检查getcwd和文件路径, 所以如果是相对路径, 一般是不会成功), 如果解析成功, 则查找EG(include_files), 如果存在则说明包含过了, 返回, 否则open这个文件, 从而得到这个文件的opened_path. 比如上面的例子, 这个文件存在于 “/tmp2/2.php”.

然后, 得到了这个opened_path以后, PHP去已加载的文件列表去查找, 是否已经包含, 如果没有包含, 那么就直接compile, 不再需要open file了.

1. 尝试解析文件的绝对路径, 如果能解析成功, 则检查EG(included_files), 存在则返回, 不存在继续
2. 打开文件, 得到文件的打开路径(opened path)
3. 拿opened path去EG(included_files)查找, 是否存在, 如果存在则返回, 不存在继续
4. 编译文件(compile_file)

这个在大多数情况下, 不是问题, 然而问题出在当你使用APC的时候…

在使用APC的时候, APC劫持了compile_file这个编译文件的指针, 从而直接从cache中得到编译结果, 避免了对实际文件的open, 避免了对open的system call.

然而, 当你在代码中使用include_once的时候, 在compile_file之前, PHP已经尝试去open file了, 然后才进入被APC劫持的compile file中, 这样一来, 就会产生一次额外的open操作. 而APC正是为了解决这个问题, 引入了include_once_override, 在include_once_override开启的情况下, APC会劫持PHP的ZEND_INCLUDE_OR_EVAL opcode handler, 通过stat来确定文件的绝对路径, 然后如果发现没有被加载, 就改写opcode为include, 做一个tricky解决方案.

但是, 很可惜, 如我所说, APC的include_once_override实现的一直不好, 会有一些未定义的问题, 比如:

  1. <?php
  2. set_include_path(“/tmp”);
  3. function a($arg = array()) {
  4.     include_once(“b.php”);
  5. }
  6. a();
  7. a();
  8. ?>

然后, 我们的b.php放置在”/tmp/b.php”, 内容如下:

  1. <?php
  2.   class B {}
  3. ?>

那么在打开apc.include_once_override的情况下, 连续访问就会得到如下错误:

  1. Fatal error – include() : Cannot redeclare class b

(后记 2012-09-15 02:07:20: 这个APC的bug我已经修复: #63070)

排除这些技术因素, 我也一直认为, 我们应该使用include, 而不是include_once, 因为我们完全能做到自己规划, 一个文件只被加载一次. 还可以借助自动加载, 来做到这一点.

你使用include_once, 只能证明, 你对自己的代码没信心.

所以, 建议大家, 不要再使用include_once

本文地址: http://www.laruence.com/2012/09/12/2765.html

发表在 涨姿势 | 留下评论

几个JavaScript版本的大整数运算库(转载)

转载的一个哥们儿的 留下链接 http://www.cnitblog.com/yemoo/archive/2007/10/10/34623.html

大整数运算一般用于密钥计算中。下面是作者从google过来的四个运算库。

http://www.onicos.com/staff/iz/amuse/javascript/expert/BigInt.txt

ps:这个在使用减法是时候有点问题

// var a = new BigInt(’10000000000000000′);
// var b = new BigInt(’1′);

a-b结果为10000004294967295,所以该方法还有待改进
这是比较早期的一个 JavaScript 版本的大数运算库,由日本高手出雲所作,其中只包含了加减乘除、模(求余)和比较运算。

http://www.faireal.net/demo/bigint0.5/beta28/
这是另一个日本高手的作品,这个库中包含的功能非常全,它的历史可以参见该文。

http://www.leemon.com/crypto/BigInt.js
这个是美国高手 Leemon Baird 的作品,所实现的功能也非常全。

http://www.ohdave.com/rsa/BigInt.js
最后这个来自 dave 的 RSA In JavaScript 网站,这个虽然功能没有前两个强大,但是使用比较方便,做一般的浏览器端加密部分已经够用了。

添加一个新的运算库:

 /*
 Copyright (c) 2012 Daniel Trebbien and other contributors
Portions Copyright (c) 2003 STZ-IDA and PTV AG, Karlsruhe, Germany
Portions Copyright (c) 1995-2001 International Business Machines Corporation and others

All rights reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, provided that the above copyright notice(s) and this permission notice appear in all copies of the Software and that both the above copyright notice(s) and this permission notice appear in supporting documentation.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

Except as contained in this notice, the name of a copyright holder shall not be used in advertising or otherwise to promote the sale, use or other dealings in this Software without prior written authorization of the copyright holder.
*/
(function() {
    var m, h = function() {
        this.form = this.digits = 0;
        this.lostDigits = !1;
        this.roundingMode = 0;
        var a = this.DEFAULT_FORM,
        b = this.DEFAULT_LOSTDIGITS,
        c = this.DEFAULT_ROUNDINGMODE;
        if (4 == h.arguments.length) a = h.arguments[1],
        b = h.arguments[2],
        c = h.arguments[3];
        else if (3 == h.arguments.length) a = h.arguments[1],
        b = h.arguments[2];
        else if (2 == h.arguments.length) a = h.arguments[1];
        else if (1 != h.arguments.length) throw "MathContext(): " + h.arguments.length + " arguments given; expected 1 to 4";
        var d = h.arguments[0];
        if (d != this.DEFAULT_DIGITS) {
            if (d < this.MIN_DIGITS) throw "MathContext(): Digits too small: " + d;
            if (d > this.MAX_DIGITS) throw "MathContext(): Digits too large: " + d;
        }
        if (a != this.SCIENTIFIC && a != this.ENGINEERING && a != this.PLAIN) throw "MathContext() Bad form value: " + a;
        if (!this.isValidRound(c)) throw "MathContext(): Bad roundingMode value: " + c;
        this.digits = d;
        this.form = a;
        this.lostDigits = b;
        this.roundingMode = c
    };
    h.prototype.getDigits = function() {
        return this.digits
    };
    h.prototype.getForm = function() {
        return this.form
    };
    h.prototype.getLostDigits = function() {
        return this.lostDigits
    };
    h.prototype.getRoundingMode = function() {
        return this.roundingMode
    };
    h.prototype.toString = function() {
        var a = null,
        b = 0,
        c = null,
        a = this.form == this.SCIENTIFIC ? "SCIENTIFIC": this.form == this.ENGINEERING ? "ENGINEERING": "PLAIN",
        d = this.ROUNDS.length,
        b = 0;
        a: for (; 0 < d; d--, b++) if (this.roundingMode == this.ROUNDS[b]) {
            c = this.ROUNDWORDS[b];
            break a
        }
        return "digits=" + this.digits + " form=" + a + " lostDigits=" + (this.lostDigits ? "1": "0") + " roundingMode=" + c
    };
    h.prototype.isValidRound = function(a) {
        var b = 0,
        c = this.ROUNDS.length,
        b = 0;
        for (; 0 < c; c--, b++) if (a == this.ROUNDS[b]) return ! 0;
        return ! 1
    };
    h.prototype.PLAIN = 0;
    h.prototype.SCIENTIFIC = 1;
    h.prototype.ENGINEERING = 2;
    h.prototype.ROUND_CEILING = 2;
    h.prototype.ROUND_DOWN = 1;
    h.prototype.ROUND_FLOOR = 3;
    h.prototype.ROUND_HALF_DOWN = 5;
    h.prototype.ROUND_HALF_EVEN = 6;
    h.prototype.ROUND_HALF_UP = 4;
    h.prototype.ROUND_UNNECESSARY = 7;
    h.prototype.ROUND_UP = 0;
    h.prototype.DEFAULT_FORM = h.prototype.SCIENTIFIC;
    h.prototype.DEFAULT_DIGITS = 9;
    h.prototype.DEFAULT_LOSTDIGITS = !1;
    h.prototype.DEFAULT_ROUNDINGMODE = h.prototype.ROUND_HALF_UP;
    h.prototype.MIN_DIGITS = 0;
    h.prototype.MAX_DIGITS = 999999999;
    h.prototype.ROUNDS = [h.prototype.ROUND_HALF_UP, h.prototype.ROUND_UNNECESSARY, h.prototype.ROUND_CEILING, h.prototype.ROUND_DOWN, h.prototype.ROUND_FLOOR, h.prototype.ROUND_HALF_DOWN, h.prototype.ROUND_HALF_EVEN, h.prototype.ROUND_UP];
    h.prototype.ROUNDWORDS = "ROUND_HALF_UP ROUND_UNNECESSARY ROUND_CEILING ROUND_DOWN ROUND_FLOOR ROUND_HALF_DOWN ROUND_HALF_EVEN ROUND_UP".split(" ");
    h.prototype.DEFAULT = new h(h.prototype.DEFAULT_DIGITS, h.prototype.DEFAULT_FORM, h.prototype.DEFAULT_LOSTDIGITS, h.prototype.DEFAULT_ROUNDINGMODE);
    m = h;
    var u, F = function(a, b) {
        return (a - a % b) / b
    },
    J = function(a) {
        var b = Array(a),
        c;
        for (c = 0; c < a; ++c) b[c] = 0;
        return b
    },
    l = function() {
        this.ind = 0;
        this.form = m.prototype.PLAIN;
        this.mant = null;
        this.exp = 0;
        if (0 != l.arguments.length) {
            var a, b, c;
            1 == l.arguments.length ? (a = l.arguments[0], b = 0, c = a.length) : (a = l.arguments[0], b = l.arguments[1], c = l.arguments[2]);
            "string" == typeof a && (a = a.split(""));
            var d, e, i, f, g, j = 0,
            k = 0;
            e = !1;
            var h = k = k = j = 0,
            p = 0;
            f = 0;
            0 >= c && this.bad("BigDecimal(): ", a);
            this.ind = this.ispos;
            "-" == a[0] ? (c--, 0 == c && this.bad("BigDecimal(): ", a), this.ind = this.isneg, b++) : "+" == a[0] && (c--, 0 == c && this.bad("BigDecimal(): ", a), b++);
            e = d = !1;
            i = 0;
            g = f = -1;
            h = c;
            j = b;
            a: for (; 0 < h; h--, j++) {
                k = a[j];
                if ("0" <= k && "9" >= k) {
                    g = j;
                    i++;
                    continue a
                }
                if ("." == k) {
                    0 <= f && this.bad("BigDecimal(): ", a);
                    f = j - b;
                    continue a
                }
                if ("e" != k && "E" != k) { ("0" > k || "9" < k) && this.bad("BigDecimal(): ", a);
                    d = !0;
                    g = j;
                    i++;
                    continue a
                }
                j - b > c - 2 && this.bad("BigDecimal(): ", a);
                e = !1;
                "-" == a[j + 1] ? (e = !0, j += 2) : j = "+" == a[j + 1] ? j + 2 : j + 1;
                k = c - (j - b); (0 == k || 9 < k) && this.bad("BigDecimal(): ", a);
                c = k;
                k = j;
                for (; 0 < c; c--, k++) h = a[k],
                "0" > h && this.bad("BigDecimal(): ", a),
                "9" < h ? this.bad("BigDecimal(): ", a) : p = h - 0,
                this.exp = 10 * this.exp + p;
                e && (this.exp = -this.exp);
                e = !0;
                break a
            }
            0 == i && this.bad("BigDecimal(): ", a);
            0 <= f && (this.exp = this.exp + f - i);
            p = g - 1;
            j = b;
            a: for (; j <= p; j++) if (k = a[j], "0" == k) b++,
            f--,
            i--;
            else if ("." == k) b++,
            f--;
            else break a;
            this.mant = Array(i);
            k = b;
            if (d) {
                b = i;
                j = 0;
                for (; 0 < b; b--, j++) j == f && k++,
                h = a[k],
                "9" >= h ? this.mant[j] = h - 0 : this.bad("BigDecimal(): ", a),
                k++
            } else {
                b = i;
                j = 0;
                for (; 0 < b; b--, j++) j == f && k++,
                this.mant[j] = a[k] - 0,
                k++
            }
            if (0 == this.mant[0]) {
                if (this.ind = this.iszero, 0 < this.exp && (this.exp = 0), e) this.mant = this.ZERO.mant,
                this.exp = 0
            } else e && (this.form = m.prototype.SCIENTIFIC, f = this.exp + this.mant.length - 1, (f < this.MinExp || f > this.MaxExp) && this.bad("BigDecimal(): ", a))
        }
    },
    G = function() {
        var a;
        if (1 == G.arguments.length) a = G.arguments[0];
        else if (0 == G.arguments.length) a = this.plainMC;
        else throw "abs(): " + G.arguments.length + " arguments given; expected 0 or 1";
        return this.ind == this.isneg ? this.negate(a) : this.plus(a)
    },
    v = function() {
        var a;
        if (2 == v.arguments.length) a = v.arguments[1];
        else if (1 == v.arguments.length) a = this.plainMC;
        else throw "add(): " + v.arguments.length + " arguments given; expected 1 or 2";
        var b = v.arguments[0],
        c,
        d,
        e,
        i,
        f,
        g,
        j,
        k = 0;
        d = k = 0;
        var k = null,
        h = k = 0,
        p = 0,
        s = 0,
        r = 0,
        n = 0;
        a.lostDigits && this.checkdigits(b, a.digits);
        c = this;
        if (0 == c.ind && a.form != m.prototype.PLAIN) return b.plus(a);
        if (0 == b.ind && a.form != m.prototype.PLAIN) return c.plus(a);
        d = a.digits;
        0 < d && (c.mant.length > d && (c = this.clone(c).round(a)), b.mant.length > d && (b = this.clone(b).round(a)));
        e = new l;
        i = c.mant;
        f = c.mant.length;
        g = b.mant;
        j = b.mant.length;
        if (c.exp == b.exp) e.exp = c.exp;
        else if (c.exp > b.exp) {
            k = f + c.exp - b.exp;
            if (k >= j + d + 1 && 0 < d) return e.mant = i,
            e.exp = c.exp,
            e.ind = c.ind,
            f < d && (e.mant = this.extend(c.mant, d), e.exp -= d - f),
            e.finish(a, !1);
            e.exp = b.exp;
            k > d + 1 && 0 < d && (k = k - d - 1, j -= k, e.exp += k, k = d + 1);
            k > f && (f = k)
        } else {
            k = j + b.exp - c.exp;
            if (k >= f + d + 1 && 0 < d) return e.mant = g,
            e.exp = b.exp,
            e.ind = b.ind,
            j < d && (e.mant = this.extend(b.mant, d), e.exp -= d - j),
            e.finish(a, !1);
            e.exp = c.exp;
            k > d + 1 && 0 < d && (k = k - d - 1, f -= k, e.exp += k, k = d + 1);
            k > j && (j = k)
        }
        e.ind = c.ind == this.iszero ? this.ispos: c.ind;
        if ((c.ind == this.isneg ? 1 : 0) == (b.ind == this.isneg ? 1 : 0)) d = 1;
        else {
            do {
                d = -1;
                do
                if (b.ind != this.iszero) if (f < j || c.ind == this.iszero) k = i, i = g, g = k, k = f, f = j, j = k, e.ind = -e.ind;
                else if (! (f > j)) {
                    h = k = 0;
                    p = i.length - 1;
                    s = g.length - 1;
                    c: for (;;) {
                        if (k <= p) r = i[k];
                        else {
                            if (h > s) {
                                if (a.form != m.prototype.PLAIN) return this.ZERO;
                                break c
                            }
                            r = 0
                        }
                        n = h <= s ? g[h] : 0;
                        if (r != n) {
                            r < n && (k = i, i = g, g = k, k = f, f = j, j = k, e.ind = -e.ind);
                            break c
                        }
                        k++;
                        h++
                    }
                }
                while (0)
            } while ( 0 )
        }
        e.mant = this.byteaddsub(i, f, g, j, d, !1);
        return e.finish(a, !1)
    },
    w = function() {
        var a;
        if (2 == w.arguments.length) a = w.arguments[1];
        else if (1 == w.arguments.length) a = this.plainMC;
        else throw "compareTo(): " + w.arguments.length + " arguments given; expected 1 or 2";
        var b = w.arguments[0],
        c = 0,
        c = 0;
        a.lostDigits && this.checkdigits(b, a.digits);
        if (this.ind == b.ind && this.exp == b.exp) {
            c = this.mant.length;
            if (c < b.mant.length) return - this.ind;
            if (c > b.mant.length) return this.ind;
            if (c <= a.digits || 0 == a.digits) {
                a = c;
                c = 0;
                for (; 0 < a; a--, c++) {
                    if (this.mant[c] < b.mant[c]) return - this.ind;
                    if (this.mant[c] > b.mant[c]) return this.ind
                }
                return 0
            }
        } else {
            if (this.ind < b.ind) return - 1;
            if (this.ind > b.ind) return 1
        }
        b = this.clone(b);
        b.ind = -b.ind;
        return this.add(b, a).ind
    },
    o = function() {
        var a, b = -1;
        if (2 == o.arguments.length) a = "number" == typeof o.arguments[1] ? new m(0, m.prototype.PLAIN, !1, o.arguments[1]) : o.arguments[1];
        else if (3 == o.arguments.length) {
            b = o.arguments[1];
            if (0 > b) throw "divide(): Negative scale: " + b;
            a = new m(0, m.prototype.PLAIN, !1, o.arguments[2])
        } else if (1 == o.arguments.length) a = this.plainMC;
        else throw "divide(): " + o.arguments.length + " arguments given; expected between 1 and 3";
        return this.dodivide("D", o.arguments[0], a, b)
    },
    x = function() {
        var a;
        if (2 == x.arguments.length) a = x.arguments[1];
        else if (1 == x.arguments.length) a = this.plainMC;
        else throw "divideInteger(): " + x.arguments.length + " arguments given; expected 1 or 2";
        return this.dodivide("I", x.arguments[0], a, 0)
    },
    y = function() {
        var a;
        if (2 == y.arguments.length) a = y.arguments[1];
        else if (1 == y.arguments.length) a = this.plainMC;
        else throw "max(): " + y.arguments.length + " arguments given; expected 1 or 2";
        var b = y.arguments[0];
        return 0 <= this.compareTo(b, a) ? this.plus(a) : b.plus(a)
    },
    z = function() {
        var a;
        if (2 == z.arguments.length) a = z.arguments[1];
        else if (1 == z.arguments.length) a = this.plainMC;
        else throw "min(): " + z.arguments.length + " arguments given; expected 1 or 2";
        var b = z.arguments[0];
        return 0 >= this.compareTo(b, a) ? this.plus(a) : b.plus(a)
    },
    A = function() {
        var a;
        if (2 == A.arguments.length) a = A.arguments[1];
        else if (1 == A.arguments.length) a = this.plainMC;
        else throw "multiply(): " + A.arguments.length + " arguments given; expected 1 or 2";
        var b = A.arguments[0],
        c,
        d,
        e,
        i = e = null,
        f,
        g = 0,
        j,
        k = 0,
        h = 0;
        a.lostDigits && this.checkdigits(b, a.digits);
        c = this;
        d = 0;
        e = a.digits;
        0 < e ? (c.mant.length > e && (c = this.clone(c).round(a)), b.mant.length > e && (b = this.clone(b).round(a))) : (0 < c.exp && (d += c.exp), 0 < b.exp && (d += b.exp));
        c.mant.length < b.mant.length ? (e = c.mant, i = b.mant) : (e = b.mant, i = c.mant);
        f = e.length + i.length - 1;
        g = 9 < e[0] * i[0] ? f + 1 : f;
        j = new l;
        var g = this.createArrayWithZeros(g),
        m = e.length,
        k = 0;
        for (; 0 < m; m--, k++) h = e[k],
        0 != h && (g = this.byteaddsub(g, g.length, i, f, h, !0)),
        f--;
        j.ind = c.ind * b.ind;
        j.exp = c.exp + b.exp - d;
        j.mant = 0 == d ? g: this.extend(g, g.length + d);
        return j.finish(a, !1)
    },
    H = function() {
        var a;
        if (1 == H.arguments.length) a = H.arguments[0];
        else if (0 == H.arguments.length) a = this.plainMC;
        else throw "negate(): " + H.arguments.length + " arguments given; expected 0 or 1";
        var b;
        a.lostDigits && this.checkdigits(null, a.digits);
        b = this.clone(this);
        b.ind = -b.ind;
        return b.finish(a, !1)
    },
    I = function() {
        var a;
        if (1 == I.arguments.length) a = I.arguments[0];
        else if (0 == I.arguments.length) a = this.plainMC;
        else throw "plus(): " + I.arguments.length + " arguments given; expected 0 or 1";
        a.lostDigits && this.checkdigits(null, a.digits);
        return a.form == m.prototype.PLAIN && this.form == m.prototype.PLAIN && (this.mant.length <= a.digits || 0 == a.digits) ? this: this.clone(this).finish(a, !1)
    },
    B = function() {
        var a;
        if (2 == B.arguments.length) a = B.arguments[1];
        else if (1 == B.arguments.length) a = this.plainMC;
        else throw "pow(): " + B.arguments.length + " arguments given; expected 1 or 2";
        var b = B.arguments[0],
        c,
        d,
        e,
        i = e = 0,
        f,
        g = 0;
        a.lostDigits && this.checkdigits(b, a.digits);
        c = b.intcheck(this.MinArg, this.MaxArg);
        d = this;
        e = a.digits;
        if (0 == e) {
            if (b.ind == this.isneg) throw "pow(): Negative power: " + b.toString();
            e = 0
        } else {
            if (b.mant.length + b.exp > e) throw "pow(): Too many digits: " + b.toString();
            d.mant.length > e && (d = this.clone(d).round(a));
            i = b.mant.length + b.exp;
            e = e + i + 1
        }
        e = new m(e, a.form, !1, a.roundingMode);
        i = this.ONE;
        if (0 == c) return i;
        0 > c && (c = -c);
        f = !1;
        g = 1;
        a: for (;; g++) {
            c <<= 1;
            0 > c && (f = !0, i = i.multiply(d, e));
            if (31 == g) break a;
            if (!f) continue a;
            i = i.multiply(i, e)
        }
        0 > b.ind && (i = this.ONE.divide(i, e));
        return i.finish(a, !0)
    },
    C = function() {
        var a;
        if (2 == C.arguments.length) a = C.arguments[1];
        else if (1 == C.arguments.length) a = this.plainMC;
        else throw "remainder(): " + C.arguments.length + " arguments given; expected 1 or 2";
        return this.dodivide("R", C.arguments[0], a, -1)
    },
    D = function() {
        var a;
        if (2 == D.arguments.length) a = D.arguments[1];
        else if (1 == D.arguments.length) a = this.plainMC;
        else throw "subtract(): " + D.arguments.length + " arguments given; expected 1 or 2";
        var b = D.arguments[0];
        a.lostDigits && this.checkdigits(b, a.digits);
        b = this.clone(b);
        b.ind = -b.ind;
        return this.add(b, a)
    },
    q = function() {
        var a, b, c, d;
        if (6 == q.arguments.length) a = q.arguments[2],
        b = q.arguments[3],
        c = q.arguments[4],
        d = q.arguments[5];
        else if (2 == q.arguments.length) b = a = -1,
        c = m.prototype.SCIENTIFIC,
        d = this.ROUND_HALF_UP;
        else throw "format(): " + q.arguments.length + " arguments given; expected 2 or 6";
        var e = q.arguments[0],
        i = q.arguments[1],
        f,
        g = 0,
        g = g = 0,
        j = null,
        k = j = g = 0;
        f = 0;
        g = null;
        k = j = 0; ( - 1 > e || 0 == e) && this.badarg("format", 1, e); - 1 > i && this.badarg("format", 2, i); ( - 1 > a || 0 == a) && this.badarg("format", 3, a); - 1 > b && this.badarg("format", 4, b);
        c != m.prototype.SCIENTIFIC && c != m.prototype.ENGINEERING && ( - 1 == c ? c = m.prototype.SCIENTIFIC: this.badarg("format", 5, c));
        if (d != this.ROUND_HALF_UP) try { - 1 == d ? d = this.ROUND_HALF_UP: new m(9, m.prototype.SCIENTIFIC, !1, d)
        } catch(l) {
            this.badarg("format", 6, d)
        }
        f = this.clone(this); - 1 == b ? f.form = m.prototype.PLAIN: f.ind == this.iszero ? f.form = m.prototype.PLAIN: (g = f.exp + f.mant.length, f.form = g > b ? c: -5 > g ? c: m.prototype.PLAIN);
        if (0 <= i) a: for (;;) {
            f.form == m.prototype.PLAIN ? g = -f.exp: f.form == m.prototype.SCIENTIFIC ? g = f.mant.length - 1 : (g = (f.exp + f.mant.length - 1) % 3, 0 > g && (g = 3 + g), g++, g = g >= f.mant.length ? 0 : f.mant.length - g);
            if (g == i) break a;
            if (g < i) {
                j = this.extend(f.mant, f.mant.length + i - g);
                f.mant = j;
                f.exp -= i - g;
                if (f.exp < this.MinExp) throw "format(): Exponent Overflow: " + f.exp;
                break a
            }
            g -= i;
            if (g > f.mant.length) {
                f.mant = this.ZERO.mant;
                f.ind = this.iszero;
                f.exp = 0;
                continue a
            }
            j = f.mant.length - g;
            k = f.exp;
            f.round(j, d);
            if (f.exp - k == g) break a
        }
        b = f.layout();
        if (0 < e) {
            c = b.length;
            f = 0;
            a: for (; 0 < c; c--, f++) {
                if ("." == b[f]) break a;
                if ("E" == b[f]) break a
            }
            f > e && this.badarg("format", 1, e);
            if (f < e) {
                g = Array(b.length + e - f);
                e -= f;
                j = 0;
                for (; 0 < e; e--, j++) g[j] = " ";
                this.arraycopy(b, 0, g, j, b.length);
                b = g
            }
        }
        if (0 < a) {
            e = b.length - 1;
            f = b.length - 1;
            a: for (; 0 < e; e--, f--) if ("E" == b[f]) break a;
            if (0 == f) {
                g = Array(b.length + a + 2);
                this.arraycopy(b, 0, g, 0, b.length);
                a += 2;
                j = b.length;
                for (; 0 < a; a--, j++) g[j] = " ";
                b = g
            } else if (k = b.length - f - 2, k > a && this.badarg("format", 3, a), k < a) {
                g = Array(b.length + a - k);
                this.arraycopy(b, 0, g, 0, f + 2);
                a -= k;
                j = f + 2;
                for (; 0 < a; a--, j++) g[j] = "0";
                this.arraycopy(b, f + 2, g, j, k);
                b = g
            }
        }
        return b.join("")
    },
    E = function() {
        var a;
        if (2 == E.arguments.length) a = E.arguments[1];
        else if (1 == E.arguments.length) a = this.ROUND_UNNECESSARY;
        else throw "setScale(): " + E.arguments.length + " given; expected 1 or 2";
        var b = E.arguments[0],
        c,
        d;
        c = c = 0;
        c = this.scale();
        if (c == b && this.form == m.prototype.PLAIN) return this;
        d = this.clone(this);
        if (c <= b) c = 0 == c ? d.exp + b: b - c,
        d.mant = this.extend(d.mant, d.mant.length + c),
        d.exp = -b;
        else {
            if (0 > b) throw "setScale(): Negative scale: " + b;
            c = d.mant.length - (c - b);
            d = d.round(c, a);
            d.exp != -b && (d.mant = this.extend(d.mant, d.mant.length + 1), d.exp -= 1)
        }
        d.form = m.prototype.PLAIN;
        return d
    };
    u = function() {
        var a, b = 0,
        c = 0;
        a = Array(190);
        b = 0;
        a: for (; 189 >= b; b++) {
            c = b - 90;
            if (0 <= c) {
                a[b] = c % 10;
                l.prototype.bytecar[b] = F(c, 10);
                continue a
            }
            c += 100;
            a[b] = c % 10;
            l.prototype.bytecar[b] = F(c, 10) - 10
        }
        return a
    };
    var t = function() {
        var a, b;
        if (2 == t.arguments.length) a = t.arguments[0],
        b = t.arguments[1];
        else if (1 == t.arguments.length) b = t.arguments[0],
        a = b.digits,
        b = b.roundingMode;
        else throw "round(): " + t.arguments.length + " arguments given; expected 1 or 2";
        var c, d, e = !1,
        i = 0,
        f;
        c = null;
        c = this.mant.length - a;
        if (0 >= c) return this;
        this.exp += c;
        c = this.ind;
        d = this.mant;
        0 < a ? (this.mant = Array(a), this.arraycopy(d, 0, this.mant, 0, a), e = !0, i = d[a]) : (this.mant = this.ZERO.mant, this.ind = this.iszero, e = !1, i = 0 == a ? d[0] : 0);
        f = 0;
        if (b == this.ROUND_HALF_UP) 5 <= i && (f = c);
        else if (b == this.ROUND_UNNECESSARY) {
            if (!this.allzero(d, a)) throw "round(): Rounding necessary";
        } else if (b == this.ROUND_HALF_DOWN) 5 < i ? f = c: 5 == i && (this.allzero(d, a + 1) || (f = c));
        else if (b == this.ROUND_HALF_EVEN) 5 < i ? f = c: 5 == i && (this.allzero(d, a + 1) ? 1 == this.mant[this.mant.length - 1] % 2 && (f = c) : f = c);
        else if (b != this.ROUND_DOWN) if (b == this.ROUND_UP) this.allzero(d, a) || (f = c);
        else if (b == this.ROUND_CEILING) 0 < c && (this.allzero(d, a) || (f = c));
        else if (b == this.ROUND_FLOOR) 0 > c && (this.allzero(d, a) || (f = c));
        else throw "round(): Bad round value: " + b;
        0 != f && (this.ind == this.iszero ? (this.mant = this.ONE.mant, this.ind = f) : (this.ind == this.isneg && (f = -f), c = this.byteaddsub(this.mant, this.mant.length, this.ONE.mant, 1, f, e), c.length > this.mant.length ? (this.exp++, this.arraycopy(c, 0, this.mant, 0, this.mant.length)) : this.mant = c));
        if (this.exp > this.MaxExp) throw "round(): Exponent Overflow: " + this.exp;
        return this
    };
    l.prototype.div = F;
    l.prototype.arraycopy = function(a, b, c, d, e) {
        var i;
        if (d > b) for (i = e - 1; 0 <= i; --i) c[i + d] = a[i + b];
        else for (i = 0; i < e; ++i) c[i + d] = a[i + b]
    };
    l.prototype.createArrayWithZeros = J;
    l.prototype.abs = G;
    l.prototype.add = v;
    l.prototype.compareTo = w;
    l.prototype.divide = o;
    l.prototype.divideInteger = x;
    l.prototype.max = y;
    l.prototype.min = z;
    l.prototype.multiply = A;
    l.prototype.negate = H;
    l.prototype.plus = I;
    l.prototype.pow = B;
    l.prototype.remainder = C;
    l.prototype.subtract = D;
    l.prototype.equals = function(a) {
        var b = 0,
        c = null,
        d = null;
        if (null == a || !(a instanceof l) || this.ind != a.ind) return ! 1;
        if (this.mant.length == a.mant.length && this.exp == a.exp && this.form == a.form) {
            c = this.mant.length;
            b = 0;
            for (; 0 < c; c--, b++) if (this.mant[b] != a.mant[b]) return ! 1
        } else {
            c = this.layout();
            d = a.layout();
            if (c.length != d.length) return ! 1;
            a = c.length;
            b = 0;
            for (; 0 < a; a--, b++) if (c[b] != d[b]) return ! 1
        }
        return ! 0
    };
    l.prototype.format = q;
    l.prototype.intValueExact = function() {
        var a, b = 0,
        c, d = 0;
        a = 0;
        if (this.ind == this.iszero) return 0;
        a = this.mant.length - 1;
        if (0 > this.exp) {
            a += this.exp;
            if (!this.allzero(this.mant, a + 1)) throw "intValueExact(): Decimal part non-zero: " + this.toString();
            if (0 > a) return 0;
            b = 0
        } else {
            if (9 < this.exp + a) throw "intValueExact(): Conversion overflow: " + this.toString();
            b = this.exp
        }
        c = 0;
        var e = a + b,
        d = 0;
        for (; d <= e; d++) c *= 10,
        d <= a && (c += this.mant[d]);
        if (9 == a + b && (a = F(c, 1E9), a != this.mant[0])) {
            if ( - 2147483648 == c && this.ind == this.isneg && 2 == this.mant[0]) return c;
            throw "intValueExact(): Conversion overflow: " + this.toString();
        }
        return this.ind == this.ispos ? c: -c
    };
    l.prototype.movePointLeft = function(a) {
        var b;
        b = this.clone(this);
        b.exp -= a;
        return b.finish(this.plainMC, !1)
    };
    l.prototype.movePointRight = function(a) {
        var b;
        b = this.clone(this);
        b.exp += a;
        return b.finish(this.plainMC, !1)
    };
    l.prototype.scale = function() {
        return 0 <= this.exp ? 0 : -this.exp
    };
    l.prototype.setScale = E;
    l.prototype.signum = function() {
        return this.ind
    };
    l.prototype.toString = function() {
        return this.layout().join("")
    };
    l.prototype.layout = function() {
        var a, b = 0,
        b = null,
        c = 0,
        d = 0;
        a = 0;
        var d = null,
        e, b = 0;
        a = Array(this.mant.length);
        c = this.mant.length;
        b = 0;
        for (; 0 < c; c--, b++) a[b] = this.mant[b] + "";
        if (this.form != m.prototype.PLAIN) {
            b = "";
            this.ind == this.isneg && (b += "-");
            c = this.exp + a.length - 1;
            if (this.form == m.prototype.SCIENTIFIC) b += a[0],
            1 < a.length && (b += "."),
            b += a.slice(1).join("");
            else if (d = c % 3, 0 > d && (d = 3 + d), c -= d, d++, d >= a.length) {
                b += a.join("");
                for (a = d - a.length; 0 < a; a--) b += "0"
            } else b += a.slice(0, d).join(""),
            b = b + "." + a.slice(d).join("");
            0 != c && (0 > c ? (a = "-", c = -c) : a = "+", b = b + "E" + a + c);
            return b.split("")
        }
        if (0 == this.exp) {
            if (0 <= this.ind) return a;
            d = Array(a.length + 1);
            d[0] = "-";
            this.arraycopy(a, 0, d, 1, a.length);
            return d
        }
        c = this.ind == this.isneg ? 1 : 0;
        e = this.exp + a.length;
        if (1 > e) {
            b = c + 2 - this.exp;
            d = Array(b);
            0 != c && (d[0] = "-");
            d[c] = "0";
            d[c + 1] = ".";
            var i = -e,
            b = c + 2;
            for (; 0 < i; i--, b++) d[b] = "0";
            this.arraycopy(a, 0, d, c + 2 - e, a.length);
            return d
        }
        if (e > a.length) {
            d = Array(c + e);
            0 != c && (d[0] = "-");
            this.arraycopy(a, 0, d, c, a.length);
            e -= a.length;
            b = c + a.length;
            for (; 0 < e; e--, b++) d[b] = "0";
            return d
        }
        b = c + 1 + a.length;
        d = Array(b);
        0 != c && (d[0] = "-");
        this.arraycopy(a, 0, d, c, e);
        d[c + e] = ".";
        this.arraycopy(a, e, d, c + e + 1, a.length - e);
        return d
    };
    l.prototype.intcheck = function(a, b) {
        var c;
        c = this.intValueExact();
        if (c < a || c > b) throw "intcheck(): Conversion overflow: " + c;
        return c
    };
    l.prototype.dodivide = function(a, b, c, d) {
        var e, i, f, g, j, k, h, p, s, r = 0,
        n = 0,
        o = 0;
        i = i = n = n = n = 0;
        e = null;
        e = e = 0;
        e = null;
        c.lostDigits && this.checkdigits(b, c.digits);
        e = this;
        if (0 == b.ind) throw "dodivide(): Divide by 0";
        if (0 == e.ind) return c.form != m.prototype.PLAIN ? this.ZERO: -1 == d ? e: e.setScale(d);
        i = c.digits;
        if (0 < i) e.mant.length > i && (e = this.clone(e).round(c)),
        b.mant.length > i && (b = this.clone(b).round(c));
        else if ( - 1 == d && (d = e.scale()), i = e.mant.length, d != -e.exp && (i = i + d + e.exp), i = i - (b.mant.length - 1) - b.exp, i < e.mant.length && (i = e.mant.length), i < b.mant.length) i = b.mant.length;
        f = e.exp - b.exp + e.mant.length - b.mant.length;
        if (0 > f && "D" != a) return "I" == a ? this.ZERO: this.clone(e).finish(c, !1);
        g = new l;
        g.ind = e.ind * b.ind;
        g.exp = f;
        g.mant = this.createArrayWithZeros(i + 1);
        j = i + i + 1;
        f = this.extend(e.mant, j);
        k = j;
        h = b.mant;
        p = j;
        s = 10 * h[0] + 1;
        1 < h.length && (s += h[1]);
        j = 0;
        a: for (;;) {
            r = 0;
            b: for (;;) {
                if (k < p) break b;
                if (k == p) {
                    c: do {
                        var q = k,
                        n = 0;
                        for (; 0 < q; q--, n++) {
                            o = n < h.length ? h[n] : 0;
                            if (f[n] < o) break b;
                            if (f[n] > o) break c
                        }
                        r++;
                        g.mant[j] = r;
                        j++;
                        f[0] = 0;
                        break a
                    } while ( 0 );
                    n = f[0]
                } else n = 10 * f[0],
                1 < k && (n += f[1]);
                n = F(10 * n, s);
                0 == n && (n = 1);
                r += n;
                f = this.byteaddsub(f, k, h, p, -n, !0);
                if (0 != f[0]) continue b;
                o = k - 2;
                n = 0;
                c: for (; n <= o; n++) {
                    if (0 != f[n]) break c;
                    k--
                }
                if (0 == n) continue b;
                this.arraycopy(f, n, f, 0, k)
            }
            if (0 != j || 0 != r) {
                g.mant[j] = r;
                j++;
                if (j == i + 1) break a;
                if (0 == f[0]) break a
            }
            if (0 <= d && -g.exp > d) break a;
            if ("D" != a && 0 >= g.exp) break a;
            g.exp -= 1;
            p--
        }
        0 == j && (j = 1);
        if ("I" == a || "R" == a) {
            if (j + g.exp > i) throw "dodivide(): Integer overflow";
            if ("R" == a) {
                do {
                    if (0 == g.mant[0]) return this.clone(e).finish(c, !1);
                    if (0 == f[0]) return this.ZERO;
                    g.ind = e.ind;
                    i = i + i + 1 - e.mant.length;
                    g.exp = g.exp - i + e.exp;
                    i = k;
                    n = i - 1;
                    b: for (; 1 <= n && g.exp < e.exp && g.exp < b.exp; n--) {
                        if (0 != f[n]) break b;
                        i--;
                        g.exp += 1
                    }
                    i < f.length && (e = Array(i), this.arraycopy(f, 0, e, 0, i), f = e);
                    g.mant = f;
                    return g.finish(c, !1)
                } while ( 0 )
            }
        } else 0 != f[0] && (e = g.mant[j - 1], 0 == e % 5 && (g.mant[j - 1] = e + 1));
        if (0 <= d) return j != g.mant.length && (g.exp -= g.mant.length - j),
        e = g.mant.length - ( - g.exp - d),
        g.round(e, c.roundingMode),
        g.exp != -d && (g.mant = this.extend(g.mant, g.mant.length + 1), g.exp -= 1),
        g.finish(c, !0);
        if (j == g.mant.length) g.round(c);
        else {
            if (0 == g.mant[0]) return this.ZERO;
            e = Array(j);
            this.arraycopy(g.mant, 0, e, 0, j);
            g.mant = e
        }
        return g.finish(c, !0)
    };
    l.prototype.bad = function(a, b) {
        throw a + "Not a number: " + b;
    };
    l.prototype.badarg = function(a, b, c) {
        throw "Bad argument " + b + " to " + a + ": " + c;
    };
    l.prototype.extend = function(a, b) {
        var c;
        if (a.length == b) return a;
        c = J(b);
        this.arraycopy(a, 0, c, 0, a.length);
        return c
    };
    l.prototype.byteaddsub = function(a, b, c, d, e, i) {
        var f, g, j, k, l, h, m = 0;
        f = h = 0;
        f = a.length;
        g = c.length;
        b -= 1;
        k = j = d - 1;
        k < b && (k = b);
        d = null;
        i && k + 1 == f && (d = a);
        null == d && (d = this.createArrayWithZeros(k + 1));
        l = !1;
        1 == e ? l = !0 : -1 == e && (l = !0);
        h = 0;
        m = k;
        a: for (; 0 <= m; m--) {
            0 <= b && (b < f && (h += a[b]), b--);
            0 <= j && (j < g && (h = l ? 0 < e ? h + c[j] : h - c[j] : h + c[j] * e), j--);
            if (10 > h && 0 <= h) {
                do {
                    d[m] = h;
                    h = 0;
                    continue a
                } while ( 0 )
            }
            h += 90;
            d[m] = this.bytedig[h];
            h = this.bytecar[h]
        }
        if (0 == h) return d;
        c = null;
        i && k + 2 == a.length && (c = a);
        null == c && (c = Array(k + 2));
        c[0] = h;
        a = k + 1;
        f = 0;
        for (; 0 < a; a--, f++) c[f + 1] = d[f];
        return c
    };
    l.prototype.diginit = u;
    l.prototype.clone = function(a) {
        var b;
        b = new l;
        b.ind = a.ind;
        b.exp = a.exp;
        b.form = a.form;
        b.mant = a.mant;
        return b
    };
    l.prototype.checkdigits = function(a, b) {
        if (0 != b) {
            if (this.mant.length > b && !this.allzero(this.mant, b)) throw "Too many digits: " + this.toString();
            if (null != a && a.mant.length > b && !this.allzero(a.mant, b)) throw "Too many digits: " + a.toString();
        }
    };
    l.prototype.round = t;
    l.prototype.allzero = function(a, b) {
        var c = 0;
        0 > b && (b = 0);
        var d = a.length - 1,
        c = b;
        for (; c <= d; c++) if (0 != a[c]) return ! 1;
        return ! 0
    };
    l.prototype.finish = function(a, b) {
        var c = 0,
        d = 0,
        e = null,
        c = d = 0;
        0 != a.digits && this.mant.length > a.digits && this.round(a);
        if (b && a.form != m.prototype.PLAIN) {
            c = this.mant.length;
            d = c - 1;
            a: for (; 1 <= d; d--) {
                if (0 != this.mant[d]) break a;
                c--;
                this.exp++
            }
            c < this.mant.length && (e = Array(c), this.arraycopy(this.mant, 0, e, 0, c), this.mant = e)
        }
        this.form = m.prototype.PLAIN;
        c = this.mant.length;
        d = 0;
        for (; 0 < c; c--, d++) if (0 != this.mant[d]) {
            0 < d && (e = Array(this.mant.length - d), this.arraycopy(this.mant, d, e, 0, this.mant.length - d), this.mant = e);
            d = this.exp + this.mant.length;
            if (0 < d) {
                if (d > a.digits && 0 != a.digits && (this.form = a.form), d - 1 <= this.MaxExp) return this
            } else - 5 > d && (this.form = a.form);
            d--;
            if (d < this.MinExp || d > this.MaxExp) {
                b: do {
                    if (this.form == m.prototype.ENGINEERING && (c = d % 3, 0 > c && (c = 3 + c), d -= c, d >= this.MinExp && d <= this.MaxExp)) break b;
                    throw "finish(): Exponent Overflow: " + d;
                } while ( 0 )
            }
            return this
        }
        this.ind = this.iszero;
        if (a.form != m.prototype.PLAIN) this.exp = 0;
        else if (0 < this.exp) this.exp = 0;
        else if (this.exp < this.MinExp) throw "finish(): Exponent Overflow: " + this.exp;
        this.mant = this.ZERO.mant;
        return this
    };
    l.prototype.isGreaterThan = function(a) {
        return 0 < this.compareTo(a)
    };
    l.prototype.isLessThan = function(a) {
        return 0 > this.compareTo(a)
    };
    l.prototype.isGreaterThanOrEqualTo = function(a) {
        return 0 <= this.compareTo(a)
    };
    l.prototype.isLessThanOrEqualTo = function(a) {
        return 0 >= this.compareTo(a)
    };
    l.prototype.isPositive = function() {
        return 0 < this.compareTo(l.prototype.ZERO)
    };
    l.prototype.isNegative = function() {
        return 0 > this.compareTo(l.prototype.ZERO)
    };
    l.prototype.isZero = function() {
        return this.equals(l.prototype.ZERO)
    };
    l.prototype.ROUND_CEILING = m.prototype.ROUND_CEILING;
    l.prototype.ROUND_DOWN = m.prototype.ROUND_DOWN;
    l.prototype.ROUND_FLOOR = m.prototype.ROUND_FLOOR;
    l.prototype.ROUND_HALF_DOWN = m.prototype.ROUND_HALF_DOWN;
    l.prototype.ROUND_HALF_EVEN = m.prototype.ROUND_HALF_EVEN;
    l.prototype.ROUND_HALF_UP = m.prototype.ROUND_HALF_UP;
    l.prototype.ROUND_UNNECESSARY = m.prototype.ROUND_UNNECESSARY;
    l.prototype.ROUND_UP = m.prototype.ROUND_UP;
    l.prototype.ispos = 1;
    l.prototype.iszero = 0;
    l.prototype.isneg = -1;
    l.prototype.MinExp = -999999999;
    l.prototype.MaxExp = 999999999;
    l.prototype.MinArg = -999999999;
    l.prototype.MaxArg = 999999999;
    l.prototype.plainMC = new m(0, m.prototype.PLAIN);
    l.prototype.bytecar = Array(190);
    l.prototype.bytedig = u();
    l.prototype.ZERO = new l("0");
    l.prototype.ONE = new l("1");
    l.prototype.TEN = new l("10");
    u = l;
    "function" === typeof define && null != define.amd ? define({
        BigDecimal: u,
        MathContext: m
    }) : "object" === typeof this && (this.BigDecimal = u, this.MathContext = m)
}).call(this);

这个是使用方法:http://www.cnblogs.com/linjiqin/p/3413894.html

ps:最后一个方法挺好用,起码数据结果是正确的~

 

发表在 javascript | 留下评论

  1、海量日志数据,提取出某日访问百度次数最多的那个IP。

首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方 法,比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率 最大的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。

或者如下阐述(雪域之鹰):

算法思想:分而治之+Hash

1.IP地址最多有2^32=4G种取值情况,所以不能完全加载到内存中处理;

2.可以考虑采用“分而治之”的思想,按照IP地址的Hash(IP)%1024值,把海量IP日志分别存储到1024个小文件中。这样,每个小文件最多包含4MB个IP地址;

3.对于每一个小文件,可以构建一个IP为key,出现次数为value的Hash map,同时记录当前出现次数最多的那个IP地址;

4.可以得到1024个小文件中的出现次数最多的IP,再依据常规的排序算法得到总体上出现次数最多的IP;

 2、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。

假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的10个查询串,要求使用的内存不能超过1G。

给出的最终算法是:

第一步、先对这批海量大数据预处理,在O(N)的时间内用Hash表完成统计(之前写成了排序,特此订正。July、2011.04.27);

第二步、借助堆这个数据结构,找出Top K,时间复杂度为N‘logK。

即,借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query, 分别和根元素进行对比所以,我们最终的时间复杂度是:O(N) + N’*O(logK),(N为1000万,N’为300万)。ok,更多,详情,请参考原文。

或者:采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

  3、有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。

方案:顺序读文件中,对于每个词x,取hash(x)%5000,然后按照该值存到5000个小文件(记为x0,x1,…x4999)中。这样每个文件大概是200k左右。

如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。

对每个小文件,统计每个文件中出现的词以及相应的频率(可以采用trie树/hash_map等),并取出出现频率最大的100个词(可以用含100 个结点的最小堆),并把100个词及相应的频率存入文件,这样又得到了5000个文件。下一步就是把这5000个文件进行归并(类似与归并排序)的过程 了。

  4、有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。

还是典型的TOP K算法,解决方案如下:

方案1:

顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件(记为)中。这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。

找一台内存在2G左右的机器,依次对用hash_map(query, query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的 query_cout输出到文件中。这样得到了10个排好序的文件(记为)。

对这10个文件进行归并排序(内排序与外排序相结合)。

方案2:

一般query的总量是有限的,只是重复的次数比较多而已,可能对于所有的query,一次性就可以加入到内存了。这样,我们就可以采用trie树/hash_map等直接来统计每个query出现的次数,然后按出现次数做快速/堆/归并排序就可以了。

方案3:

与方案1类似,但在做完hash,分成多个文件后,可以交给多个文件来处理,采用分布式的架构来处理(比如MapReduce),最后再进行合并。

  5、 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?

方案1:可以估计每个文件安的大小为5G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

遍历文件a,对每个url求取hash(url)%1000,然后根据所取得的值将url分别存储到1000个小文件(记为a0,a1,…,a999)中。这样每个小文件的大约为300M。

遍历文件b,采取和a相同的方式将url分别存储到1000小文件(记为b0,b1,…,b999)。这样处理后,所有可能相同的url都在对应 的小文件(a0vsb0,a1vsb1,…,a999vsb999)中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相 同的 url即可。

求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。

方案2:如果允许有一定的错误率,可以使用Bloom filter,4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。

Bloom filter日后会在本BLOG内详细阐述。

  6、在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数。

方案1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32 * 2 bit=1 GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看 bitmap,把对应位是01的整数输出即可。

方案2:也可采用与第1题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。

  7、腾讯面试题:给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?

与上第6题类似,我的第一反应时快速排序+二分查找。以下是其它更好的方法:

方案1:oo,申请512M的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。

dizengrong:

方案2:这个问题在《编程珠玑》里有很好的描述,大家可以参考下面的思路,探讨一下:

又因为2^32为40亿多,所以给定一个数可能在,也可能不在其中;

这里我们把40亿个数中的每一个用32位的二进制来表示

假设这40亿个数开始放在一个文件中。

然后将这40亿个数分成两类:

1.最高位为0

2.最高位为1

并将这两类分别写入到两个文件中,其中一个文件中数的个数<=20亿,而另一个>=20亿(这相当于折半了);

与要查找的数的最高位比较并接着进入相应的文件再查找

再然后把这个文件为又分成两类:

1.次最高位为0

2.次最高位为1

并将这两类分别写入到两个文件中,其中一个文件中数的个数<=10亿,而另一个>=10亿(这相当于折半了);

与要查找的数的次最高位比较并接着进入相应的文件再查找。

…….

以此类推,就可以找到了,而且时间复杂度为O(logn),方案2完。

附:这里,再简单介绍下,位图方法:

使用位图法判断整形数组是否存在重复

判断集合中存在重复是常见编程任务之一,当集合中数据量比较大时我们通常希望少进行几次扫描,这时双重循环法就不可取了。

位图法比较适合于这种情况,它的做法是按照集合中最大元素max创建一个长度为max+1的新数组,然后再次扫描原数组,遇到几就给新数组的第几位置 上 1,如遇到5就给新数组的第六个元素置1,这样下次再遇到5想置位时发现新数组的第六个元素已经是1了,这说明这次的数据肯定和以前的数据存在着重复。这 种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效 率还能提高一倍。

欢迎,有更好的思路,或方法,共同交流。

  8、怎么在海量数据中找出重复次数最多的一个?

方案1:先做hash,然后求模映射为小文件,求出每个小文件中重复次数最多的一个,并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求(具体参考前面的题)。

  9、上千万或上亿数据(有重复),统计其中出现次数最多的钱N个数据。

方案1:上千万或上亿的数据,现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了,可以用第2题提到的堆机制完成。

  10、一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。

方案1:这题是考虑时间效率。用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度)。然后是找出出现最频繁的前 10 个词,可以用堆来实现,前面的题中已经讲到了,时间复杂度是O(n*lg10)。所以总的时间复杂度,是O(n*le)与O(n*lg10)中较大的哪一 个。

附、100w个数中找出最大的100个数。

方案1:在前面的题中,我们已经提到了,用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。

方案2:采用快速排序的思想,每次分割之后只考虑比轴大的一部分,知道比轴大的一部分在比100多的时候,采用传统排序算法排序,取前100个。复杂度为O(100w*100)。

方案3:采用局部淘汰法。选取前100个元素,并排序,记为序列L。然后一次扫描剩余的元素x,与排好序的100个元素中最小的元素比,如果比这个最 小的要大,那么把这个最小的元素删除,并把x利用插入排序的思想,插入到序列L中。依次循环,知道扫描了所有的元素。复杂度为O(100w*100)。

发表于 ltwen | 留下评论