LIS算法-判断物体上升还是下降

LIS算法又称最长公共子序列,即找出一组数中最长的子序列,比如我们可以用于判断一个物体是在上升还是下降

如何判断物体是在上升还是下降,单纯用末尾数字-首位数字,可能结果并不准确,因为物体可能是一个抖动形的移动趋势。

我们的航班系统会实时收集飞机的坐标,比如在飞机起飞/降落的时候收集它的坐标位置,因为飞机的起飞或降落不是呈现高度递增或递减的,很有可能是先上升了一段高度,由于气流的原因又下降了一段距离再上升

比如一个我们收集了飞机一段高度数据为:{ 2000, 3125, 3325, 2000, 3325, 4025, 4575, 5625, 6900, 7925, 7950, 7925, 7700, 7275, 7050, 6925, 6500, 6350, 5400, 4825, 3150, 2250 }

使用LIS算法正序求得:{2000 2250 3150 4025 4575 4825 6350 6925 7950 },

逆序求得:{2000 3125 3325 5400 5625 6500 6900 7050 7275 7700 7925 7950}

我们从结果中分析逆序LTS更长,表明飞机是在下降的趋势。

实现源码

public static int[] longestIncreasingSubsequence(int[] arr) {
    int i, n = arr.length, top, temp;
    int[] stack = new int[n + 1];
    int[] idxes = new int[n];
    top = 0;
    int idx = 0;// 记录LIS序列中元素对应的arr下标,便于修正LIS中下标错位的元素

    /* 为了方便top始终指向栈顶,stack从下标1开始使用,stack[0]设置为-1不使用 */
    stack[0] = -1;

    // -----------------------------------
    // 一个for循环加一个二分查找,算法时间复杂度是o(NlogN)
    // -----------------------------------
    for (i = 0; i < n; i++) {
        temp = arr[i];
        /* 比栈顶元素大数就入栈 */
        if (temp > stack[top]) {
            stack[++top] = temp;
            idxes[idx++] = i;
        } else {
            int low = 1, high = top;
            int mid;
            /* 二分检索栈中比temp大的第一个数 */
            while (low <= high) {
                mid = (low + high) / 2;
                if (temp > stack[mid]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            /* 用temp替换 */
            stack[low] = temp;
            idxes[low - 1] = i;
        }
    }

    print(idxes);
    int[] lis = Arrays.copyOfRange(stack, 1, top + 1);
    print(lis); // 得到递增的最长子序列,但不一定是原数组的最长上升子序列

    return lis;
}

 

 

关于join查询使用遇到的问题

今天发现服务器上的一个sql执行非常慢,两张关联表查询

有一张关注表user_focus,和一张关注备注表user_focus_note

sql如下:

select t1.FLYID,t1.FLYKEY,t1.ISPUSH,t1.NOTIFYSTATE,t2.description,t2.remind_times from USER_FOCUS t1 left join USER_FOCUS_note t2 on t1.ID=t2.user_focus_id where (t1.USERID=’1378416183′ or t1.PHONEID=’18820063′) and t1.ORDERTYPE=’0′ and t1.NOTIFYSTATE=’0′ and t1.UPDATETIME >= ‘2016-09-24 00:00:00′ UNION select t3.FLYID,t3.FLYKEY,t3.ISPUSH,t3.NOTIFYSTATE,t4.description,t4.remind_times from USER_FOCUS t3 left join USER_FOCUS_note t4 on t3.ID=t4.user_focus_id where (t3.USERID=’1378416183′ or t3.PHONEID=’18820063′) and t3.ORDERTYPE=’0’ and t3.NOTIFYSTATE in (1,2) and t3.UPDATETIME >= ‘2016-10-24 09:55:19′;

进一步分析,发现下面sql执行很慢,基本上再20s以上,但返回结果只有1000多条

select t1.FLYID,t1.FLYKEY,t1.ISPUSH,t1.NOTIFYSTATE,t2.description,t2.remind_times from USER_FOCUS t1 left join USER_FOCUS_NOTE t2 on t1.ID=t2.user_focus_id where (t1.USERID=’1378416183′ or t1.PHONEID=’18820063′) and t1.ORDERTYPE=’0′ and t1.NOTIFYSTATE=’0’ and t1.UPDATETIME >= ‘2016-09-24 00:00:00’

其中user_focus有1600万条数据,PHONEID,USERID,UPDATETIME 都建了索引,

去掉关联查询后,速度一下子就提升上来了,基本100ms就执行完了,所以确定是使用left join的问题,查看了下user_focus_note表,发现有18w条数据,数据量不大啊,怎么回事?

仔细查看了sql,这里有用到t1.ID=t2.user_focus_id,USER_FOCUS_NOTE 表user_focus_id建立了一个索引,重新执行sql,速度果然很快。USER_FOCUS 表虽然只有1000多条数据满足,但是查询USER_FOCUS_NOTE表时都需要扫描全表,这样就有180000*1000条扫描,所以查询肯定很慢

总结:类似两个大表,或一个大表、一个小表做关联查询时,一定要建立好索引。