开发者社区> usher.yue> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Lua中table内建排序与C/C++/Java/php/等内排序算法的排序效率比较

简介: Lua这类脚本语言在处理业务逻辑作为配置文件的时候方便省事 但是在大量需要 运算的地方就显得略微不足   按照 Lua内建排序算法 对比C/C++ PHP Java等的快速排序算法进行一下比较。
+关注继续查看

Lua这类脚本语言在处理业务逻辑作为配置文件的时候方便省事 但是在大量需要 运算的地方就显得略微不足   按照 Lua内建排序算法 对比C/C++ PHP Java等的快速排序算法进行一下比较。

快速排序算法是基于冒泡排序,优化而来,时间复杂度T(n)=O(nLog2n)  ,可见内部采用了二分策略 。

发现在LuaIDE LDT下直接运行效率要比 通过C++加载运行Lua脚本效率高的多  拿500W个数据排序 来说  ,脚本如下

同样的排序脚本Lua解释器的内置排序算法在LDT下,运行速度比通过C/C++内嵌Lua解释器调用的快14倍之多

 而C/C++的快速排序速度又是Lua 内嵌排序算法的速度的40倍之多,LDT下的lua排序的3倍之多,起码在我的电脑上 看到的是这样的效果。

PHP实现的快速排序算法

PHP简直不敢用它做排序,页面缓存池容量太小了,5W个数据排序就已经吃不消了。。。。。  效率远不如Lua 所以还是老老实实的用它做web CRUD吧。。就算配置了 页面内存池大小也无法满足需求  5000就花费了接近2s

~~~还是附上代码吧

<?php
   define('ARRAY_SIZE',5000);
   
   function QuickSort($arr,$low,$high)
   {
     if($low>$high)
	   return ;
	 $begin=$low;
	 $end=$high ;
	 $key=$arr[$begin];
     while($begin<$end)
	 {
	    while($begin<$end&&$arr[$end]>=$key)
		   --$end ;
		$arr[$begin]=$arr[$end];
        while($begin<$end&&$arr[$begin]<=$key)
		  ++$begin;
		$arr[$end]=$arr[$begin];
		
	 }
	  $arr[$begin]=$key;
      QuickSort($arr,$low,$begin-1);
	  QuickSort($arr,$begin+1,$high);
   }
   $arr=array();
   echo '插入前时间:'.time().'<br/>';
   for($i=0;$i<ARRAY_SIZE;$i++)
   {
     array_push($arr,rand(1,50000));
   }
   echo '插入后时间:'.time().'<br/>';
   echo '排序前时间:'.time().'<br/>';
   QuickSort($arr,0,ARRAY_SIZE-1);
   echo '排序后时间:'.time().'<br/>';

?>



Java实现的快速排序算法如果不是因为Java大数据处理JVM容易出现栈溢出,那么效率上和C/C++持平   甚至优于这一点JVM做的很漂亮  据一位大哥说是just in Time Compile技术,和.NET一样 小段代码执行效率特别高,大程序就不行了。

Java编程语言和环境中,即时编译器(JIT compiler,just-in-time compiler)是一个把Java的字节码(包括需要被解释的指令的程序)转换成可以直接发送给处理器(processor)的指令的程序。当你写好一个Java程序后,源语言的语句将由Java编译器编译成字节码,而不是编译成与某个特定的处理器硬件平台对应的指令代码(比如,Intel的Pentium微处理器或IBM的System/390处理器)。字节码是可以发送给任何平台并且能在那个平台上运行的独立于平台的代码。 
  过去,大多数用任何语言写的程序在每个电脑平台上都必须重编译,甚至有时需要重写。Java最大的优点之一就是你只需要写和编译一次程序。在任何平台上,Java都会将编译好的字节码解释成能被特定的处理器所理解的指令。尽管如此,Java虚拟机一次只能处理一条字节码指令。在特定的系统平台上使用Java即时编译器(实际上是第二个编译器)能把字节码编译成特定系统的代码(虽然这个程序最初已经在这个平台上被编译过)。一旦代码被JIT编译器(重)编译后,它在电脑上通常就会运行地更快。

  
  即时编译器(JIT compiler)随虚拟机一起供给的,并可选使用。它把字节码编译成可立即执行的指定平台的可执行代码。Sun微系统建议,选择JIT编译器选项通常会使程序运行地更快,尤其是当某个可执行的方法被重复使用时

print("插入前时间",os.clock())
--定义table变量
sorTable={}  
for i=1,5000000,1 do
  sorTable[i]=i
end
print('插入数据后时间:',os.clock())
print('插入了',#sorTable,'个数据!')
print('排序前时间:',os.clock())
table.sort(sorTable,
function(a,b)
  if(a<b) then 
    return true
  else
   return false
  end
end 
)
print("排序后时间:",os.clock())

如上代码在 LDT内直接运行 如下结果 显示6s排序完 500W个数组的数据,但是同样的 Lua脚本内嵌到C++解释器解释执行效率缺可怕的要命


通过Lua C++加载上述Lua脚本运行之后结果如下,缺花了80S多,插入和排序的速度都变慢了   所以 利用C++加载Lua 做类似操作 是得不偿失的同样的Lua脚本通过 C++内嵌解释调用速度变得如此之慢,下面再看看C++PHP JAVA中内排序算法的效率。


对于C/C++处理大批量数据,那绝对是优势,下面是使用 快速排序算法 实现 500W数据内容排序,仅仅花了2s的时间是LDT下的三倍 ,是通过C/C++加载Lua脚本的40倍之多。

#include "stdafx.h"
#include "time.h"
#include "stdlib.h"
#include "stdio.h"
#define ARRSIZE 5000000


//快速排序  
//以key为基准 进行递归排序 思路来源于  冒泡排序算法
///把数据一分为二  key的两边分别是 大于key  小于key的数据 进行递归从而进行排序
//时间复杂度是 nlog2n
void QuickSort(int arr[],int low,int high)
{
	if(low>=high)
		return ;
	int begin=low ; //记录当前调用的起点index
	int end=high  ; //记录当前的终点index
	int key=arr[begin]; //以此为轴进行划分 
	while(begin<end)
	{
		while(begin<end&&arr[end]>=key)  //从右边寻找一个小 值
			end--;
		arr[begin]=arr[end];
		while(begin<end&&arr[begin]<=key)//从左边寻找一个大的值
			begin++;
		 arr[end]=arr[begin];
	}
	arr[begin]=key; //最后将key放入到剩余位置 
	QuickSort(arr,low,begin-1);  //left 递归
	QuickSort(arr,begin+1,high);  //right 递归
}

int  _tmain(int argc,char*argv[])
{
	int *pArray=new int[ARRSIZE];
	time_t  tm ;
	time(&tm);
	printf("插入前时间:%d\n",tm);
	srand((unsigned int)time(NULL));
	for (int i=0;i<ARRSIZE;i++)
	{
		pArray[i]=rand();
	}
	time(&tm);
	printf("插入后时间:%d\n",tm);
	time(&tm);
	printf("排序前时间:%d\n",tm);
	QuickSort(pArray,0,ARRSIZE-1);
	time(&tm);
	printf("排序后时间:%d\n",tm);
	delete []pArray;
	return  0 ;
}


运行结果可想而知,对于C/C++来说 耗费时间几乎为2s ,所以对于Lua这一类脚本语言来说 处理大数据运算绝对不是明智之举

基于Java的快速排序算法,我有些不敢相信自己的眼睛了 同样的快速排序算法 跑在JVM上的java居然比C++快一些  500W个排序数据   花了不到2s的时间.........................

import java.lang.String; 
import java.util.Date;
import java.util.Random;
public class QuickSort 
{  
	public static final int MAX_SIZE=5000000;
	//实例初始化
	{
		this.a=new int[MAX_SIZE];
		///
		System.out.println("插入前时间:"+new Date().getTime()+"ms");
		Random rm=new Random(100) ;
		for(int i=0;i<QuickSort.MAX_SIZE;i++)
		{
		   this.a[i]=rm.nextInt(50000) ; //随机数
		}
		System.out.println("插入后时间:"+new Date().getTime()+"ms");
		System.out.println("排序前时间:"+new Date().getTime()+"ms");
		QuickSortMethod(this.a,0,this.a.length-1); 
		System.out.println("排序后时间:"+new Date().getTime()+"ms");
		//System.out.println(Arrays.toString(this.a));
	}
	//快速排序算法java实现  和C++一样
	public void QuickSortMethod(int[] arr,int low,int high)
	{
		if(low>=high)
			return ;
		int begin=low;
		int end=high;
		int key=arr[begin]; //key  
		while(begin<end)
		{
			while(begin<end&&arr[end]>=key)
			{
				 --end;
			}
			arr[begin]=arr[end];
			while(begin<end&&arr[begin]<=key)
			{
				++begin;
			}
			arr[end]=arr[begin];			
		}
		arr[begin]=key;
		QuickSortMethod(arr,low,begin-1);
		QuickSortMethod(arr,begin+1,high);
		
	}
	private int[] a;
    public static void  main(String[]argv)
    {
    	new QuickSort();
	}
}

上图



QQ 4223665    技术交流群

 群号是387761601
 

欢迎大家一起交流软件技术












版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
提高 Java 效率的 35 个小技巧,用了的都说好。。
代码优化 ,一个很重要的课题。可能有些人觉得没用,一些细小的地方有什么好修改的,改与不改对于代码的运行效率有什么影响呢?这个问题我是这么考虑的,就像大海里面的鲸鱼一样,它吃一条小虾米有用吗?没用,但是,吃的小虾米一多之后,鲸鱼就被喂饱了。
230 0
Java交互界面实现计算器开发设计【附函数源码】
使用Java开发的简易计算器,包括加、减、乘、除、平方、立方、小数等运算,适合学习GUI编程实践,
37 0
如何用Java实现位图转矢量图?
通过前面几篇图片转字符、灰度图的文章介绍之后,接下来我们再来看一个有意思的东西,基于前文的基础,实现位图转矢量图的功能
457 0
Java实现GIF图转字符动图实例demo
上一篇文章介绍了静态图转字符的实现demo;接下来也该是动态图转字符的demo了 从前面几篇文章的学习过程中,要想实现这个功能就属于信手拈来了 单张图转字符完成之后,动图无非是每一张静态图都转一遍,保存最后的结果即可 这里我们就不介绍基础的JDK写法了(感兴趣的可以到前面几篇文章中获取),我们直接进入进阶的玩法 接下来我们借助开源项目 github.com/liuyueyi/qu… 来迅速的实现输出Gif字符图
79 0
Java实现图片转字符输出示例demo
前面几篇博文介绍了使用jdk来对图片做一些有意思的转换,接下来我们再介绍一个有意思的玩法,直接根据图片,输出一个二维字符数组,实现用字符来实现绘画的场景 各位小伙伴可能都有看到过一些有趣的注释,比如大佛,美女之类的,通关本文,相信你也很可以很简单的实现类似的场景 作者:一灰灰 链接:https://juejin.cn/post/7033040253673799711 来源:稀土掘金 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
44 0
Java实现Gif图转字符动图
前面介绍了两篇基于jdk实现图片灰度处理、转字符图片的操作,接下来我们在将之前的能力扩展一下,支持将一个gif图灰度化或者转gif字符图 本文的实现主要在前面两篇文章的基础上来实现,推荐没有看过的小伙伴也可以瞅一眼
50 0
java后端实现token自动续期,这方案有点优雅
在前后端分离的开发模式下,前端用户登录成功后后端服务会给用户颁发一个token。前端(如vue)在接收到 token后会将token存储到LocalStorage中。
1372 0
SpringBoot整合Java Mail实现Outlook / Office365发送邮件
日常开发过程中,我们经常需要使用到邮件发送任务,比方说验证码的发送、日常信息的通知等。日常比较常用的邮件发送方包括:163、QQ等,本文主要讲解Outlook SMTP的开启方式、OutLook STARTTTL的配置、如何通过JavaMail来实现电子邮件的发送等。
3014 0
在Java中实现完整的单例模式
个人认为单例模式是设计模式中最简单也是最常用的一种,是对有限资源合理利用的一种方式。这个模式看似简单,但是其中蕴含了关于并发、类加载、序列化等一系列深层次的知识,如果理解不够深,就有可能在高并发时遇到难以预期的异常,或者会造成资源浪费。
46 0
Java NIO三件套之Buffer实现原理解析
目前很多高性能的Java RPC框架都是基于Netty实现的,而Netty的设计原理又离不开Java NIO。本篇笔记是对NIO核心三件套:缓冲区(Buffer)、选择器 (Selector)和通道(Channel),其中之一的缓冲区Buffer实现原理的学习总结
71 0
+关注
usher.yue
算法相关技术专家
文章
问答
文章排行榜
最热
最新
相关电子书
更多
使用C++开发PHP7扩展
立即下载
继承与功能组合
立即下载
复杂PHP系统性能瓶颈排查及优化
立即下载