1

AS3 に次のようなポイントの配列があるとします。

(x=584.1, y=279.4),(x=584.1, y=280.4),(x=584.1, y=281.4),(x=584.1, y=282.4),(x=584.1, y=283.4),(x=584.1, y=284.4),(x=584.1, y=285.4),(x=584.1, y=286.4),(x=584.1, y=287.4),(x=585.1, y=287.45),(x=586.1, y=287.45),(x=584.1, y=288.4),(x=585.1, y=288.45),(x=586.1, y=288.45),(x=587.1, y=288.5),(x=588.1, y=288.55),(x=584.1, y=289.4),(x=585.1, y=289.45),(x=586.1, y=289.45),(x=587.1, y=289.5),(x=588.1, y=289.55),(x=584.1, y=290.4),(x=585.1, y=290.45),(x=586.1, y=290.45),(x=587.1, y=290.5),(x=588.1, y=290.55),(x=584.1, y=291.4),(x=585.1, y=291.45),(x=586.1, y=291.45),(x=587.1, y=291.5),(x=588.1, y=291.55),(x=584.1, y=292.4),(x=585.1, y=292.45),(x=586.1, y=292.45),(x=587.1, y=292.5),(x=588.1, y=292.55),(x=584.1, y=293.4),(x=585.1, y=293.45),(x=586.1, y=293.45),(x=587.1, y=293.5),(x=588.1, y=293.55),(x=584.1, y=294.4),(x=585.1, y=294.45),(x=586.1, y=294.45),(x=587.1, y=294.5),(x=588.1, y=294.55),(x=584.1, y=295.4),(x=585.1, y=295.45),(x=586.1, y=295.45),(x=587.1, y=295.5),(x=588.1, y=295.55)

y の最大値と最小値を見つける効率的な方法は何ですか?

4

3 に答える 3

1

[編集] Array.sortOn が最速の場合もあります。配列をソートする必要がある場合はネイティブ関数を使用し、それ以外の場合は Daniel のコードを使用します。

myArray.sortOn('y', Array.NUMERIC);

並べ替えとダニエルのコードでベンチマークを行いました。場合によっては、sortOn/copy の方が配列なしのコピーよりも高速でした。場合によってはそうではありません。いずれにせよ、配列のコピー/ソートンは一貫性のない結果をもたらし、メモリ消費量がはるかに多くなります。以下の結果とベンチマーク。

(デバッグ プレーヤーでは、array.sortOn は常に失われます)

package {

    import flash.display.*;
    import flash.geom.*;
    import flash.text.*;
    import flash.utils.*;

    final public class ArraySortTest extends Sprite {

        /**
         *  @private
         */
        private const arr:Array         = [];

        private const text:TextField    = new TextField();

        public function ArraySortTest():void {

            text.width          = stage.stageWidth;
            text.height         = stage.stageHeight;
            addChild(text);

            var length:int      = 1000;
            var iterations:int  = 5000;
            while (length--) {
                arr.push(new Point(Math.random() * 500, Math.random() * 500));
            }

            var i:int, start:int, result:Point = new Point();

            start   = getTimer();
            i       = iterations;

            while (i--) {
                getMinMax(arr, 'y', result);
            }

            text.appendText('nosort: ' + String(getTimer() - start) + result + '\n');

            start   = getTimer();
            i       = iterations;
            while (i--) {
                getMinMaxSorted(arr, 'y', result);
            }
            text.appendText('sorted: ' + String(getTimer() - start) + result + '\n');


            start   = getTimer();
            i       = iterations;
            while (i--) {
                getMinMaxSortedConcat(arr, 'y', result);
            }
            text.appendText('sorted concat: ' + String(getTimer() - start) + result + '\n');

        }

        private function getMinMaxSortedConcat(input:Array, key:String, result:Point):void {

            input.concat().sortOn('y', Array.NUMERIC);

            result.x = input[0][key];
            result.y = input[int(input.length - 1)][key];
        }

        private function getMinMaxSorted(input:Array, key:String, result:Point):void {

            input.sortOn('y', Array.NUMERIC);

            result.x = input[0][key];
            result.y = input[int(input.length - 1)][key];
        }

        private function getMinMax(input:Array, key:String, result:Point):void {

            var len:Number = input.length;
            var min:Number = Number.MAX_VALUE;
            var max:Number = Number.MIN_VALUE;

            var check:Number;
            for (var i:int = 0; i < len; i++) {
                check = input[i][key];

                if (check < min) {
                    min = check;
                } else if (check > max) {
                    max = check;
                }
            }

            result.x = min;
            result.y = max;
        }
    }
}

結果：

100 elements, 5000 iterations each
nosort: 124(x=3.739513223990798, y=495.2090959995985)
sorted: 109(x=3.739513223990798, y=495.2090959995985)
sorted concat: 115(x=3.739513223990798, y=495.2090959995985)

1000 elements, 5000 iterations each
nosort: 1263(x=0.13151345774531364, y=499.65104297734797)
sorted: 1181(x=0.13151345774531364, y=499.65104297734797)
sorted concat: 1234(x=0.13151345774531364, y=499.65104297734797)

1000 elements, 10000 iterations
nosort: 2474(x=0.18377462401986122, y=499.73958847112954)
sorted: 2371(x=0.18377462401986122, y=499.73958847112954)
sorted concat: 2454(x=0.18377462401986122, y=499.73958847112954)

10000 elements, 1000 iterations
nosort: 2487(x=0.003137858584523201, y=499.816557392478)
sorted: 2961(x=0.003137858584523201, y=499.816557392478)
sorted concat: 3157(x=0.003137858584523201, y=499.816557392478)
于 2012-12-18T06:43:37.293 に答える
1

n > 2 のランダムな入力データの最高値と最低値のみに関心がある場合は、これが最速であると確信しています。

var input:Array = [ {x:584.1, y:279.4}, {x:584.1, y:280.4}, {x:584.1, y:281.4}, ...];

public function MinMaxValues() {
    var len:Number = input.length;
    var min:Number = Number.MAX_VALUE;
    var max:Number = Number.MIN_VALUE;

    var check:Number;
    for (var i:int = 0; i < len; i++) {
        check = input[i]["y"];

        if (check < min) {
            min = check;
        } 

        if (check > max) {
            max = check;
        }
    }
    trace("minimum value of [" + len + "] items is::" + min);
    trace("maximum value of [" + len + "] items is::" + max);

}

于 2012-12-18T08:32:10.210 に答える
0

それだけで、配列をトラバースし、最初のポイントの Y 値を現在の最小値と最大値として取得し、他のすべてを比較します。その配列でデータがどのように編成されているかについて追加情報を提供しない限り、これ以上の方法はないと思います。

于 2012-12-18T06:34:59.867 に答える