二进制搜索，从Java为ActionScript [英] Binary search, from java to Actionscript

问题描述

喜
我想下面的Java二进制搜索程序转换为AS3。 我认为的compareTo是一个内置的Java方法和'>>>'SA型按位运算的。

任何人都可以既熟悉的ActionScript 3和Java帮助呢？

 包二进制;

公共类搜索{

  公共静态INT查找（字符串[]键，目标字符串）{
    诠释高= keys.length;
    INT低= -1;
    而（高 - 低→1）{
      INT探头=（低+高）＆GT;＆GT;＆GT; 1;
      如果（键[探头] .compareTo（目标）大于0）
        高=探头;
      其他
        低=传感器;
    }

    如果（低==  -  1 ||键[小] .compareTo（目标）= 0）
      返回-1;
    其他
      回报低;
  }
}
 

解决方案

您应该使用尽可能多的内置Flash功能成为可能。它使你的code更容易维护和生成的SWF会更快和更小。检查出阵列的的indexOf（）方法

这是家庭作业或者你有一些其他的原因，使用手写搜索？

编辑：我要补充的是，内置的搜索开始，你所提供的指数线性搜索。如果你有一个大的和已排序数组，二进制搜索可能会更快。你必须尝试，其中交叉是 - 它可能会低至10。如果您的数组尚未排序，内置线性搜索将击败过合并排序和二进制搜索的裤子

第二次修改：我很好奇多大的数组必须是对indexOf（）成为慢，所以我跑了几个测试。在搜索中50项的数组，的indexOf（）更快的所有项目。在搜索100000项的数组，的indexOf（）是快高达约100，则二进制搜索支配

要找到50,000项出10万的项目，二分查找0.0078ms同时的indexOf（）以3.382ms。

下面是测试code。我从来没有演出前测试AS3，所以看着经过的时间静止的机器上是最好的，我已经得到了。 （sprintf的是张贴在这样执行，它只是用来生成字符串。）

 私有静态无功myarray的：阵列;

    公共静态功能设置（）：无效{
        myArray的=新的Array（）;
        对于（VAR我：= 0; I＆LT; 50; ++ I）{
            myArray的[I] =的sprintf（S％06D，我）;
        }
    }

    公共静态函数timingTest（）：无效{
        如果（myarray的== NULL）{
            建立（）;
        }

        VAR启动：数=的getTimer（）;
        对于（VAR记者：INT = 0; J＆LT; 5000; ++ j）条{
            如果（的binarySearch（myarray的，s000049）！= 49）{
                跟踪（哎呀！）;
            }
        }
        跟踪（平均每毫秒的binarySearch+（的getTimer（） - 开始）/ J）;

        开始=的getTimer（）;
        对于（VAR K：INT = 0; K＆LT; 5000; ++ K）{
            如果（myArray.indexOf（s000049）！= 49）{
                跟踪（哎呀！）;
            }
        }
        跟踪（平均每毫秒的indexOf+（的getTimer（） - 开始）/ K）;
    }

    公共静态功能的binarySearch（键：阵列，目标：字符串）：INT {
        VAR高：INT = keys.length;
        VAR低：= -1;
        而（高 - 低→1）{
            VAR探头：INT =（低+高）/ 2;
            如果（键[探头]＆GT;目标）
                高=探头;
            其他
                低=传感器;
        }
        如果（低== -1 ||键[小]！==目标）
            返回-1;
        其他
            回报低;
    }
}
 

Hi
I am trying to convert the following java binary search routine to as3. I assume that 'compareTo' is a built in java method and that '>>>' s a type of bitwise operation.

Can anyone familiar with both actionscript 3 and Java help with this?

package binary;

public class Finder {

  public static int find( String[ ] keys, String target) {
    int high = keys.length;
    int low = -1;
    while (high - low>1) {
      int probe = (low + high)>>> 1;
      if (keys[probe].compareTo(target) > 0)
        high = probe;
      else
        low = probe;
    }

    if (low==-1 || keys[low].compareTo(target) !=0)
      return -1;
    else
      return low;
  }
}

解决方案

You should use the built-in Flash features as much as possible. It makes your code easier to maintain and the resulting SWF will be faster and smaller. Check out the indexOf() method on Array.

Is this homework or do you have some other reason for using a hand-written search?

Edit: I should add that the built-in search is a linear search starting with the index you provide. If you have a large and already sorted array, the binary search may be faster. You'll have to experiment where the cross-over is--it could be as low as 10. If your array is not already sorted, the built-in linear search will beat the pants off the combined sort and binary search.

Second Edit: I was curious how large the array had to be for indexOf() to become slower so I ran a few tests. Searching an array of 50 items, indexOf() is faster for all items. Searching an array of 100,000 items, indexOf() is faster up to about 100, then the binary search dominates.

To find the 50,000th item out of 100,000 items, binary search takes 0.0078ms while indexOf() takes 3.382ms.

Here's the test code. I've never performance tested AS3 before, so watching elapsed time on a quiescent machine is the best I've got. (sprintf is the implementation posted on SO. It is just used to generate strings.)

    private static var myArray:Array;

    public static function setup():void {
        myArray = new Array();
        for (var i:int=0; i < 50; ++i) {
            myArray[i] = sprintf("s%06d", i);
        }
    }

    public static function timingTest():void {
        if (myArray == null) {
            setup();
        }

        var start:Number = getTimer();
        for (var j:int=0; j < 5000; ++j) {
            if (binarySearch(myArray, "s000049") != 49) {
                trace("oops!");
            }
        }
        trace("avg msecs per binarySearch " + (getTimer() - start)/j);

        start = getTimer();
        for (var k:int=0; k < 5000; ++k) {
            if (myArray.indexOf("s000049") != 49) {
                trace("oops!");
            }
        }
        trace("avg msecs per indexOf " + (getTimer() - start)/k);
    }

    public static function binarySearch(keys:Array, target:String):int {
        var high:int = keys.length;
        var low:int = -1;
        while (high - low > 1) {
            var probe:int = (low + high) / 2;
            if (keys[probe] > target)
                high = probe;
            else
                low = probe;
        }
        if (low == -1 || keys[low] !== target)
            return -1;
        else
            return low;
    }
}

这篇关于二进制搜索，从Java为ActionScript的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！