Lua中table内建排序与C/C++/Java/php/等内排序算法的排序效率比较-阿里云开发者社区

开发者社区> usher.yue> 正文

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面向对象编程》之十八
本节从初学者的角度出发,尝试去编写一个实现数组排序的简单算法,一步一步地调试最终完成,简明生动,通俗易懂。
1327 0
Java排序算法&amp;nbsp;希尔排序
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。
930 0
java 算法基础之二快速排序算法
java 算法基础之二快速排序算法
1859 0
Java排序算法_选择排序
选择排序的基本操作就是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。算法不稳定,O(1)的额外的空间,比较的时间复杂度为O(n^2),交换的时间复杂度为O(n),并不是自适应的。
753 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
3975 0
用Java实现几种常见的排序算法
用Java语言实现的各种排序,包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。
512 0
排序算法之归并排序(JAVA)
归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为:       1)划分子表       2)合并半子表       首先我们来讨论归并算法,归并算法将一系列数据放到一个向量中,索引范围为[first,last],这个序列由两个排好序的子表构成,以索引中点(mid)
2304 0
JAVA算法系列 快速排序
java算法系列之排序 手写快排 首先说一下什么是快排,比冒泡效率要高,快排的基本思路是首先找到一个基准元素,比如数组中最左边的那个位置,作为基准元素key,之后在最左边和最右边设立两个哨兵,i 和 j 之后,开始按住左哨兵(i),让右哨兵(j)往左走(j--),找到比key小的元素后,按住右哨兵(...
751 0
+关注
usher.yue
算法相关技术专家
431
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载