关于排列后数组的一些思考(1)

DC_er 发布于2019-08-14 11:32 / 1184人阅读

摘要：问题上看到了一个问题数组排序之后更加再对其进行操作时间缩短了对楼主的实例代码进行了一下重构，代码如下把最高的回答看了下，也就是在的时候，在判定的时候，没有排列时候，每次都要重新进行判断，而排列完之后，当排列完数据大于判断时候，后面所有的数

问题: 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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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