關于排列后數組的一些思考(1)

DC_er 發布于2019-08-14 11:32 / 1203人閱讀

摘要：問題上看到了一個問題數組排序之后更加再對其進行操作時間縮短了對樓主的實例代碼進行了一下重構，代碼如下把最高的回答看了下，也就是在的時候，在判定的時候，沒有排列時候，每次都要重新進行判斷，而排列完之后，當排列完數據大于判斷時候，后面所有的數

問題: stackoverflow上看到了一個問題數組排序之后更加再對其進行操作時間縮短了

對樓主的實例代碼進行了一下重構，代碼如下：

public class Main {

    public static void main(String[] args) {
        noSortedTime();

        sortedTime();

    }

    private static void noSortedTime() {
        int[] data = initialize();
        calculateTime(data);
    }

    public static int[] initialize() {
        int arraySize = 32768;
        int data[] = new int[arraySize];
        Random ran = new Random(0);
        for (int c = 0; c < arraySize; ++c) {
            data[c] = ran.nextInt() % 256;
        }
        return data;
    }

    private static void sortedTime() {
        int[] data = initialize();
        Arrays.sort(data);
        calculateTime(data);
    }

    private static void calculateTime(int[] data) {
        long start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 100000; i++) {
            for (int c = 0; c < data.length; c++) {
                if (data[c] < 128) {
                    sum += data[c];
                }
            }
        }
        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

把up最高的回答看了下，也就是在loop的時候，在判定if (data[c] > 128) 的時候，沒有排列時候，每次都要重新進行判斷，而排列完之后，當排列完數據大于128判斷時候，后面所有的數據都不需要進行if的判斷，由此減少了判定方向，減少了運行時間，由于128大概是255的一般左右，所以我當時的認為應該時間也是一般左右，但得到的偏差比較大，而且sum是負數，debug后發現ran.nextInt() % 256;可能產生負數，于是我把initialize()方法改成了如下：

public static int[] initialize() {
    int arraySize = 30000;
    int data[] = new int[arraySize];
    Random ran = new Random(0);
    for (int c = 0; c < arraySize; ++c) {
        int i = ran.nextInt() % 256;
        if (i > 0) {
            data[c] = i;
        } else {
            data[c] = -i;
        }   
    }
    return data;
}

這時候，得到了結果是：
20.666892876
sum = 95197000000
9.225126652
sum = 95197000000

之后我覺得如果以128作為判定條件太折中，如果是用極端點的條件來進行如小于1會不會排列好的數組會非常快的完成呢，或者大于254會不會兩邊的速度差不多呢，進行了實驗小于1的話得到的結果是：
8.647651855
sum = 0
8.641952252
sum = 0
大于254的結果是：
8.942171349
sum = 3111000000
8.821620658
sum = 3111000000

上述結果很明顯得到我們的猜想是錯誤的，我又重新去把回答up最高的答案仔細讀了一遍，發現了又Branch predictor這個概念，是處理器中對于if else這類condition的判斷預測,具體里面的概念灰常不懂，只能先放著了。

GPU云服務器云服務器關于c語言數組的代碼排列數組 js 二維數組全排列數組降序排列java

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/63979.html

Python | 遞歸

摘要：那假如我們用遞歸來描述這種情況呢定義基本情況其它情形所以在上述求和中的定義又用到了自己本身的定義，這就構成了遞歸。說起遞歸，我覺得其實大部分人應該是不陌生的，遞歸廣泛存在于生活中。比如： showImg(https://segmentfault.com/img/remote/1460000007420204?w=294&h=450); The woman in this image ...

qieangel2013 2019-07-31 10:52 評論0 收藏0
記一次JavaScript API練習題

摘要：當我完成這個題目并且看到其他大神的答案時，我就覺得我真的很有必要記錄一下這道題，并且思考它在中的實現。表示被查找的值方法返回一個由替換值替換一些或所有匹配的模式后的新字符串。舉一反三，多多思考，多多實踐才是學習前端的最佳實踐。之前，我在Codewars上看到一道名為Recover a secret string from random triplets的題，這道題使我沉思了很久，最終...

scq000 2019-08-26 11:50 評論0 收藏0
也談前端面試常見問題之『數組亂序』

摘要：看完部分的源碼，首先迫不及待想跟大家分享的正是本文主題數組亂序。這是一道經典的前端面試題，給你一個數組，將其打亂，返回新的數組，即為數組亂序，也稱為洗牌問題。關于數組亂序，正確的解法應該是，復雜度。前言終于可以開始 Collection Functions 部分了。可能有的童鞋是第一次看樓主的系列文章，這里再做下簡單的介紹。樓主在閱讀 underscore.js 源碼的時候，學到...

tracy 2019-08-19 18:42 評論0 收藏0
[Leetcode] Next Permutation 下一個排列

摘要：因為增加高位會帶來更大的增益。所以對于一個長為的序列，我們增加第位的前提是，前位已經達到了最大排列方法。因為是找下一個數，所以我們要找一個比小卻盡可能大的數，所以找到。把換到的位置后，后三位仍然是個降序的排列。 Next Permutation Implement next permutation, which rearranges numbers into the lexicogr...

young.li 2019-08-14 12:34 評論0 收藏0