Median of Two Sorted Arrays

OJ
Divide & Conquer, LeetCode

Problem

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution

基本思路是分别将A、B分别切割，两个左边的部分合并，两个右侧的部分合并，如下所示：

1
2
3
      left_part          |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

如果

1
2
len(left_part) == len(right_part)
max(left_part) <= min(right_part)

第一个条件可以通过设定j的值满足，设置j=(m+n+1)/2，使得左边部分的数量不小于右边数量，所以整体为奇数时，左边部分的最大值即为median。第二个条件需要验证，然后根据相应的情况移动A的切割选取范围。
那么

1
2
median=[max(left_part) + min(right_part)]/2  m+n是偶数
median=[]

寻找A数组的分割位置可以使用binary search
整个算法的时间复杂度为O(log(min(m,n)))
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def median(A, B):
    m, n = len(A), len(B)
    if m > n:
        A, B, m, n = B, A, n, m
    if n == 0:
        raise ValueError
    # 设置half_len=(m + n + 1) / 2, 保证左边部分总是不小于右边
    imin, imax, half_len = 0, m, (m + n + 1) / 2
    while imin <= imax:
        i = (imin + imax) / 2
        j = half_len - i
        if j > 0 and i < m and B[j-1] > A[i]:
            # i 太小
            imin = i + 1
        elif i > 0 and j < n and A[i-1] > B[j]:
            # i 太大
            imax = i - 1
        else:
            # i 刚刚好
            if i == 0: max_of_left = B[j-1]
            elif j == 0: max_of_left = A[i-1]
            else: max_of_left = max(A[i-1], B[j-1])
            # 考虑整体是奇数的情况
            if (m + n) % 2 == 1:
                return max_of_left

            if i == m: min_of_right = B[j]
            elif j == n: min_of_right = A[i]
            else: min_of_right = min(A[i], B[j])
            # 考虑整体是偶数的情况
            return (max_of_left + min_of_right) / 2.0

分享到

Perfect Rectangle

OJ
Geometry, LeetCode

Problem

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example

![](https://leetcode.com/static/images/problemset/rectangle_perfect.gif)

rectangles = [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]
]
Return true. All 5 rectangles together form an exact cover of a rectangular region.

Solution

可以拼凑成矩形的情形应当满足一下条件：

  • 大矩形面积 = sum(小矩形面积)
  • 除了最外边的4个角(corner)，其他角都应该重复偶数次(2或者4次)
  • 重复在同一个点的角(corner)应该方向不同(左下、左上、右下、右上)

解决思路：

  • 使用哈希表维护边角()和其类型，类型分别取值1、2、4、8
  • 这些类型其二进制都只有一个位是1。与运算结果不为0时表示出现重复(方块重叠发生)，否则做或运算并更新哈希表(保持这个值的存在)
  • 单独考虑总体矩形的边角，最后哈希表里值为1、2、4、8的只能且必须有4个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
HashMap<String, Integer> mapp = new HashMap<>();
    public boolean isRectangleCover(int[][] rectangles) {
        if (rectangles.length==0 || rectangles[0].length==0) return false;
        int minx=Integer.MAX_VALUE,miny=Integer.MAX_VALUE,maxx=0,maxy=0,sum=0,count=0;
        for (int[] rect : rectangles) {
            minx = Math.min(minx, rect[0]);
            miny = Math.min(miny, rect[1]);
            maxx = Math.max(maxx, rect[2]);
            maxy = Math.max(maxy, rect[3]);
            if (isRectangleCover_assist(rect[0]+" "+rect[1], 1)) return false;
            if (isRectangleCover_assist(rect[0]+" "+rect[3], 2)) return false;
            if (isRectangleCover_assist(rect[2]+" "+rect[1], 4)) return false;
            if (isRectangleCover_assist(rect[2]+" "+rect[3], 8)) return false;
            sum += (rect[2]-rect[0])*(rect[3]-rect[1]);
        }
        for (Integer tmp : mapp.values())
            // 只有整体矩形的四个边角才是这些值
            if (tmp==1 || tmp==2 || tmp==4 || tmp==8) count += 1;
        return count==4 && sum==(maxx-minx)*(maxy-miny);
    }
    // 确定mapp中是否已经存在两个一样的pair
    public boolean isRectangleCover_assist(String key, int value) {
        if (mapp.containsKey(key) && (mapp.get(key)&value)!=0) return true;
        mapp.put(key, mapp.containsKey(key)?mapp.get(key)|value:value);
        return false;
    }
分享到

Longest Substring

OJ
LeetCode, Sliding window, String

Longest Substring

Problem — Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

Solution
  • 双指针思想，滑动窗口
  • 没找到T包含所有字符时，end指针移动，找到时移动start指针
  • 注意滑动窗口、双指针类的题目一般都是这么解的
1
2
3
4
5
6
7
8
9
10
int lengthOfLongestSubstring(string s) {
    vector<int> map(128,0);
    int counter=0, begin=0, end=0, d=0;
    while(end<s.size()){
        if(map[s[end++]]++>0) counter++;
        while(counter>0) if(map[s[begin++]]-->1) counter--;
        d=max(d, end-begin); //while valid, update d
    }
    return d;
}
Problem — At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is “ece” which its length is 3.

Solution
  • 子串只能包含最多2个不同的字符，所以扫描的时候，count表示子串不同字符的数量
  • 需要记录子串中每个字符出现的次数，第一次出现时count+1，第二次、三次等不需要
  • 加入字符后，如果count>2，需要从子串的头部删除元素，直到满足count<=2为止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lengthOfLongestSubstringTwoDistinct(string s) {
    vector<int> map(128, 0);
    int counter=0, begin=0, end=0, d=0;
    while(end<s.size()){
        // add a new character
        if(map[s[end++]]++==0) counter++;
        // at most 2 distinct characters, so, count <= 2
        // only when map[s[begin]]--==1, we get rid of s[begin] completely
        while(counter>2) if(map[s[begin++]]--==1) counter--;
        // update d
        d=max(d, end-begin);
    }
    return d;
}
Problem — At Most k Distinct Characters

Given a string s, find the length of the longest substring T that contains at most k distinct characters.

Example
For example, Given s = “eceba”, k = 3,

T is “eceb” which its length is 4

Solution

思路同上一题，只需要将2变成k即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lengthOfLongestSubstringKDistinct(string s, int k) {
    vector<int> map(128, 0);
    int counter=0, begin=0, end=0, d=0;
    while(end<s.size()){
        // add a new character
        if(map[s[end++]]++==0) counter++;
        // at most k distinct characters, so, count <= k
        // only when map[s[begin]]--==1, we get rid of s[begin] completely
        while(counter>k) if(map[s[begin++]]--==1) counter--;
        // update d
        d=max(d, end-begin);
    }
    return d;
}

Generalization

对于要求寻找特定要求的子串的问题，通用解法就是滑动窗口的思想，使用哈希表和双指针，可以有如下模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int findSubstring(string s){
    vector<int> map(128,0);
    int counter; // check whether the substring is valid
    int begin=0, end=0; //two pointers, one point to tail and one  head
    int d; //the length of substring

    for() { /* initialize the hash map here */ }

    while(end<s.size()){

        if(map[s[end++]]-- ?){  /* modify counter here */ }

        while(/* counter condition */){

            /* update d here if finding minimum*/

            //increase begin to make it invalid/valid again

            if(map[s[begin++]]++ ?){ /*modify counter here*/ }
        }

        /* update d here if finding maximum*/
    }
    return d;
}

原文地址，感谢作者

分享到

Minimum Window Substring

OJ
LeetCode, Sliding window, String

Problem

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.

Note:

  • If there is no such window in S that covers all characters in T, return the empty string “”.
  • If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution

  • 使用滑动窗口、两个指针的思想，从前到后扫描
  • 没找到T包含所有字符时，end指针移动，找到时移动start指针
  • 注意滑动窗口、双指针类的题目一般都是这么解的
1
2
3
4
5
6
7
8
9
10
11
12
13
string minWindow(string s, string t) {
    vector<int> map(128,0);
    for(auto c: t) map[c]++;
    int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
    while (end<s.size()) {
        if(map[s[end++]]-->0) counter--; //in t
        while(counter==0){ //valid
            if(end-begin<d)  d=end-(head=begin);
            if(map[s[begin++]]++==0) counter++;  //make it invalid
        }
    }
    return d==INT_MAX? "":s.substr(head, d);
}

别人写的精炼代码，拿来参考.

分享到

Substring with Concatenation of All Words

OJ
LeetCode, Sliding window, String

Problem

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: “barfoothefoobarman”
words: [“foo”, “bar”]

You should return the indices: [0,9].
(order does not matter).

Solution

每个单词的长度一致，考虑滑动窗口的思想

  • 使用滑动窗口的思想，双层循环
  • 第一层确定要寻找的单词组合的开头下标
  • 第二层循环试图寻找一个可能的组合，如果成功则记录开头下标；否则，退出第二层循环
  • 程序采用复制哈希表的方式会超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static List<Integer> findSubstring(String S, String[] L) {
    List<Integer> res = new ArrayList<Integer>();
    if (S == null || L == null || L.length == 0) return res;
    int len = L[0].length(); // length of each word
    Map<String, Integer> map = new HashMap<String, Integer>(); // map for L
    for (String w : L) map.put(w, map.containsKey(w) ? map.get(w) + 1 : 1);

    for (int i = 0; i <= S.length() - len * L.length; i++) { // possible start index
        Map<String, Integer> copy = new HashMap<String, Integer>(map);
        for (int j = 0; j < L.length; j++) { // checkc if match
            String str = S.substring(i + j*len, i + j*len + len); // next word
            if (copy.containsKey(str)) { // is in remaining words
                int count = copy.get(str);
                if (count == 1) copy.remove(str);
                else copy.put(str, count - 1);
                if (copy.isEmpty()) { // matches
                    res.add(i);
                    break;
                }
            } else break; // not in L
        }
    }
    return res;
}

这样的代码还有一种写法，也是使用双层循环。第一层循环为单个单词的长度，第二层以固定的步长进行匹配，不推荐这么写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new LinkedList<>();
        if (s.length() == 0 || words.length == 0)
            return ret;
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) map.put(word, map.containsKey(word)?map.get(word)+1:1);
        int len = words[0].length(), start = 0, end = 0, count;
        Map<String, Integer> tmp_map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            tmp_map.clear();
            start = i;
            end = i;
            count = 0;
            while (end + len <= s.length()) {
                String tmp_str = s.substring(end, end + len), tmp = null;
                if (map.containsKey(tmp_str)) { // a word
                    if (tmp_map.containsKey(tmp_str)) tmp_map.put(tmp_str, tmp_map.get(tmp_str)+1);
                    else tmp_map.put(tmp_str, 1);
                    count++;
                    if (tmp_map.get(tmp_str) > map.get(tmp_str)) {
                        while (start <= end && tmp_map.get(tmp_str) > map.get(tmp_str)) {
                            tmp = s.substring(start, start + len);
                            tmp_map.put(tmp, tmp_map.get(tmp) - 1);
                            start += len;
                            count--;
                        }
                    }
                    if (count == words.length) {
                        --count;
                        tmp = s.substring(start, start+len);
                        tmp_map.put(tmp, map.get(tmp)-1);
                        ret.add(start);
                        start += len;
                    }
                    end += len;
                } else { // not a word
                    end += len;
                    start = end;
                    tmp_map.clear();
                    count = 0;
                }
            }
        }
        return ret;
    }
分享到

Remove Duplicate Letters

OJ
Greedy, LeetCode
Problem

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:
Given “bcabc”
Return “abc”

Given “cbacdcbc”
Return “acdb”

Solution

给定字符串s，使用贪心算法一定能得到最优解。需要稍微注意点的是，遇到只出现了一次的字符串的情况

  1. 扫描一遍字符串，获取每个字符对应的出现次数
  2. 扫描一遍字符串，寻找找到最小的字符对应的下标。每扫描到一个字符，其出现次数要-1，如果减完1后是0，表示这个字符是唯一的，所以要在此停顿，处理前面出现的最小字符。(下一次字符出现次数会重新计数)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public String removeDuplicateLetters(String s) {
        if (s.length() == 0) return "";
        int[] map = new int[26];
        for (int i=0; i<s.length(); i++)
            map[s.charAt(i)-'a'] += 1;
        int pos = 0;
        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos)) pos = i;
            if (--map[s.charAt(i)-'a'] == 0) break;
        }
        return s.charAt(pos)+removeDuplicateLetters(s.substring(pos+1).replaceAll(""+s.charAt(pos), ""));
    }
}
分享到

python数据规整_分组_聚合

Dev
python, 数据分析

数据合并

DataFrame合并
1
2
3
4
import pandas as pd
from pandas import DataFrame,Series
import numpy as np
pd.merge(***)
merge方法
merge函数的参数
param explanation param explanation
left 左侧的DataFrame right 右侧的DataFrame
how 连接方式，inner、outer、left、right，默认为inner on 指定连接的列名
left_on 左侧DataFrame用于连接的键名 right_on 右侧DataFrame用于连接的键名
left_index 将左侧的行索引用作其连接键 right_index 将右侧的行索引用作其连接键
sort 对合并后的数据在连接键上排序，默认为True suffixes 重叠列名后缀，用于重复列名区分
copy 默认为True，设置为False可以避免将数据复制到结果数据结构中 ———— ————- 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
left1 = DataFrame({'key':['a','b','a','a','b','c'], 'value':range(6)})
$-> key  value
0   a      0
1   b      1
2   a      2
3   a      3
4   b      4
5   c      5

right1 = DataFrame({'group_val':[2,5]},index=['a','b'])
$-> group_val
a          2
b          5

pd.merge(left1, right1, left_on='key', right_index=True)
$-> key  value  group_val
0   a      0          2
2   a      2          2
3   a      3          2
1   b      1          5
4   b      4          5

层次化索引应当以列表的形式指明用作合并键的多个列

join方法
  • join方法可以更为方便地实现按索引合并
  • 可以合并多个带有相同或相似索引的DataFrame对象
1
2
3
4
5
6
# on指定调用者的连接键
left.join(right, how='', on='')

# 多个DataFrame合并
another = DataFrame(....)
left2.join([right2, another])
concat方法

concat方法用于轴向连接、绑定、堆叠操作
numpy有一个合并原始NumPy数组的concatenate的函数

1
2
3
arr = np.arange(12).reshape((3,4))
# axis=1水平连接，axis=0垂直连接
np.concatenate([arr, arr], axis=1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
s1 = Series([0,1], index=['a', 'b'])
s2 = Series([2,3,4], index=['c','d', 'e'])
s3 = Series([5,6], index=['f', 'g'])
# 默认 axis=0
pd.concat([s1, s2, s3])
$-> a    0
    b    1
    c    2
    d    3
    e    4
    f    5
    g    6
    dtype: int64

pd.concat([s1, s2, s3], axis=1)
$-> 0    1    2
a  0.0  NaN  NaN
b  1.0  NaN  NaN
c  NaN  2.0  NaN
d  NaN  3.0  NaN
e  NaN  4.0  NaN
f  NaN  NaN  5.0
g  NaN  NaN  6.0
concat函数的参数
param explanation param explanation
objs 参与连接的pandas对象的列表或字典，必需参数 axis 指明连接轴向，默认为0，参考上面示例
join 连接方式，inner、outer，默认为outer join_axes 指明其他n-1条轴的索引，不执行并集、交集运算
keys 用于形成连接轴上的层次化索引 levels 指定层次化索引上各级别的索引
names 用于创建分层级别的索引，如果设置了keys和levels的话 verify_integrity 检查结果对象新轴上的重复对象
ignore_index 不保留连接轴上的索引，产生新索引range() ——- ———————-

重塑层次化索引

  • stack 将数据的列‘旋转’为行
  • unstack 将数据的行‘旋转’为列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
data = DataFrame(np.arange(6).reshape((2,3)), index=pd.Index(['Ohio','Colorado'],name='state'), columns=pd.Index(['one','two','three'],name='number'))
$-> data
number    one  two  three
state
Ohio        0    1      2
Colorado    3    4      5

result = data.stack()
result
$-> state     number
    Ohio      one       0
                two       1
              three     2
    Colorado  one       3
              two       4
              three     5
    dtype: int32

result.unstack()
$-> number    one  two  three
    state
    Ohio        0    1      2
    Colorado    3    4      5

# unstack(和stack一样)默认操作的是最内层地址，给函数传入层次级别的编号或者名称即可在不同级别操作。
result.unstack(0)
$-> state   Ohio  Colorado
    number
    one        0         3
    two        1         4
    three      2         5
result.unstack('state')  # 效果同上

unstack操作可能会产生缺失值，而stack操作默认会过滤缺失值，可以设置参数dropna=False取消。

数据转换

去重
  • DataFrame的duplicated()方法返回一个bool型Series实例，指示每一行是否是重复行
  • DataFrame的drop_duplicates()方法返回一个移除重复行的DataFrame
  • drop_duplicates()默认保留第一个出现的值组合，设置take_last=True则保留最后一个
  • 指定部分列进行重复项判断，drop_duplicates([‘a1’, ‘a2’])
替换
  • Series中的replace函数可以进行替换操作
  • data.replace(a, b)
  • data.replace([a1, a2], b)
  • data.replace([a1, a2], [b1, b2])
映射
  • Series的map方法接受一个函数，或者含有映射关系的字典对象，返回一个映射后的Series对象
  • data.map(str.lower)
  • data.map(lambda x : str.lower(x))
离散化与bin划分
  • cut函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
ages = [20,22,25,27,21,23,37,31,61,45,41,32]
bins = [18, 25, 35, 60 ,100]

# 将ages按照bins划分进行切割
# 直接切割得到的区间是左开右闭的，设置right=False可以得到左闭右开区间
# 设置参数labels=['a1','a2',...,'an']可以更改区间名称
# 也可以不传入bins，直接传入整数n表示分成n个区间，函数会根据最值等间距划分

cats = pd.cut(ages, bins)
cats
$-> [(18, 25], (18, 25], (18, 25], (25, 35], (18, 25], ..., (25, 35], (
      60, 100], (35, 60], (35, 60], (25, 35]]
    Length: 12
    Categories (4, object): [(18, 25] < (25, 35] < (35, 60] < (60, 100]
    ]

cats.codes   #每个数据的标签
$-> array([0, 0, 0, 1, 0, 0, 2, 1, 3, 2, 2, 1], dtype=int8)
cats.categories  #区间信息
$-> Index([u'(18, 25]', u'(25, 35]', u'(35, 60]', u'(60, 100]'], dtype='object')

# 简单统计
pd.value_count(cats)
$-> (18, 25]     5
    (35, 60]     3
    (25, 35]     3
    (60, 100]    1
    dtype: int64
  • qcut函数根据样本分位数对样本进行划分，可以使得每个bin中的数据数量比较接近
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
data = np.random.rand(1000)
# 5分位数
cats = pd.qcut(data, 5)
pd.value_counts(cats)
$-> (0.813, 1]           200
    (0.628, 0.813]       200
    (0.421, 0.628]       200
    (0.223, 0.421]       200
    [0.000386, 0.223]    200

# 自定义的分位数
cats = pd.qcut(data, [0, 0.1, 0.5, 0.9, 1.0])
pd.value_counts(cats)
$-> (0.539, 0.901]       400
    (0.127, 0.539]       400
    (0.901, 1]           100
    [0.000386, 0.127]    100
    dtype: int64
检测和过滤异常值
1
2
3
4
5
6
7
8
9
data = DataFrame(np.random.randn(1000,4))
col = data[3]
# 找出某一列中绝对值大于3的值
col[np.abs(col) > 3]
# 找出data中全部大于3的值
data[(np.abs(data) > 3).any(1)]

# 替换异常值
data[np.abs(data) > 3] = 1
排列和随机采样
1
2
3
np.random.permutation(5)
# 整数采样，从[0,5)区间上采，样本空间为20
np.random.randint(0,5,20)
计算指示变量、哑变量

本节的作用是将分类变量转换为‘哑变量矩阵’（dummy matrix）或‘指示变量矩阵0-1’（indicator matrix）.如果DataFrame中的某一列有k个不同的值，则可以派生出一个k列矩阵或DataFrame

1
2
3
4
5
6
7
8
9
10
data = DataFrame({'key':['a','b','a','c','d'],'value':range(5)})
pd.get_dummies(data['key'])
$-> a    b    c    d
0  1.0  0.0  0.0  0.0
1  0.0  1.0  0.0  0.0
2  1.0  0.0  0.0  0.0
3  0.0  0.0  1.0  0.0
4  0.0  0.0  0.0  1.0
# 为新生成的列名添加前缀
pd.get_dummies(data['key'], prefix='new_')

字符串操作
python内置的字符串库
  • strip() 修剪空白符、换行符
  • split(‘xx’) 字符串分割
  • a.join(list): 在字符串a后面接上列表list（或元组）里所有的元素
  • str.index(‘,’) 在字符串str中找到’,’的位置，如果找不到则抛出异常
  • str.find(‘,’) 在字符串str中找’,’，找到返回第一个位置，找不到返回-1
  • str.rfind(‘,’) 在字符串str中找’,’，找到返回最后一个位置，找不到返回-1
  • str.count(‘,’) 统计str中’,’的个数
  • str.replace(‘aa’,’a’) 替换
  • str.lower(), upper() 大小写转换
  • str.ljust(n), rjust(n) 用空白字符填充以满足最小长度n
正则表达式

  • 正则表达式是用于处理字符串的强大工具，拥有自己独特的语法以及一个独立的处理引擎，效率上可能不如str自带的方法，但功能十分强大。得益于这一点，在提供了正则表达式的语言里，正则表达式的语法都是一样的，区别只在于不同的编程语言实现支持的语法数量不同。下图展示了使用正则表达式进行匹配的流程：

    ![](http://ww4.sinaimg.cn/mw690/9bcfe727jw1f6unc8s9fzj20d605w0ue.jpg)

  • 下图列出了Python支持的正则表达式元字符和语法：

    ![](http://ww3.sinaimg.cn/mw690/9bcfe727jw1f6unc85kmxj20m71brniv.jpg)

  • 正则表达式通常用于在文本中查找匹配的字符串。Python里数量词默认是贪婪的（在少数语言里也可能是默认非贪婪），总是尝试匹配尽可能多的字符；非贪婪的则相反，总是尝试匹配尽可能少的字符。例如：正则表达式”ab*”如果用于查找”abbbc”，将找到”abbb”。

  • 与大多数编程语言相同，正则表达式里使用”\”作为转义字符，这就可能造成反斜杠困扰。假如你需要匹配文本中的字符”\”，那么使用编程语言表示的正则表达式里将需要4个反斜杠”\\\\”：前两个和后两个分别用于在编程语言里转义成反斜杠，转换成两个反斜杠后再在正则表达式里转义成一个反斜杠。Python里的原生字符串很好地解决了这个问题，这个例子中的正则表达式可以使用r”\\”表示。同样，匹配一个数字的”\\d”可以写成r”\d”。

  • re模块。Python通过re模块提供对正则表达式的支持。使用re的一般步骤是先将正则表达式的字符串形式编译为Pattern实例，然后使用Pattern实例处理文本并获得匹配结果（一个Match实例），最后使用Match实例获得信息，进行其他的操作。

1
import re

  1. compile
    re.compile(strPattern[, flag])
    用于将字符串形式的正则表达式编译为Pattern对象,第二个参数flag是匹配模式，取值可以使用按位或运算符’|’表示同时生效。flag的可选值有：
    re.I(re.IGNORECASE): 忽略大小写（括号内是完整写法，下同）
    M(MULTILINE): 多行模式，改变’^’和’$’的行为（参见上图）
    S(DOTALL): 点任意匹配模式，改变’.’的行为
    L(LOCALE): 使预定字符类 \w \W \b \B \s \S 取决于当前区域设定
    U(UNICODE): 使预定字符类 \w \W \b \B \s \S \d \D 取决于unicode定义的字符属性
    X(VERBOSE): 详细模式。这个模式下正则表达式可以是多行，忽略空白字符，并可以加入注释

  2. match
    match(string[, pos[, endpos]]) | re.match(pattern, string[, flags])
    这个方法将从string的pos下标处起尝试匹配pattern；如果pattern结束时仍可匹配，则返回一个Match对象；如果匹配过程中pattern无法匹配，或者匹配未结束就已到达endpos，则返回None。
    pos和endpos的默认值分别为0和len(string)；re.match()无法指定这两个参数，参数flags用于编译pattern时指定匹配模式。 注意：这个方法并不是完全匹配。当pattern结束时若string还有剩余字符，仍然视为成功。想要完全匹配，可以在表达式末尾加上边界匹配符’$’。

  3. split
    split(string[, maxsplit]) | re.split(pattern, string[, maxsplit])
    按照能够匹配的子串将string分割后返回列表。maxsplit用于指定最大分割次数，不指定将全部分割。
  4. findall
    findall(string[, pos[, endpos]]) | re.findall(pattern, string[, flags])
    搜索string，以列表形式返回全部能匹配的子串
  5. finditer
    finditer(string[, pos[, endpos]]) | re.finditer(pattern, string[, flags])
    搜索string，返回一个顺序访问每一个匹配结果（Match对象）的迭代器
  6. sub
    sub(repl, string[, count]) | re.sub(pattern, repl, string[, count])
    使用repl替换string中每一个匹配的子串后返回替换后的字符串。
    当repl是一个字符串时，可以使用\id或\g、\g引用分组，但不能使用编号0。
    当repl是一个方法时，这个方法应当只接受一个参数（Match对象），并返回一个字符串用于替换（返回的字符串中不能再引用分组）。
    count用于指定最多替换次数，不指定时全部替换。
  7. subn
    subn(repl, string[, count]) |re.sub(pattern, repl, string[, count])
    返回 (sub(repl, string[, count]), 替换次数)

原文地址与示例

pandas中矢量化的字符串操作

通过Series的str方法获取Series中值得字符串内容，函数示例

  • data.str.constins(‘hello’), 返回一个bool型的Series对象
  • data.str.findall(pattern,flags=re.IGNORECASE)
  • matches = data.str.match(pattern, flags=re.IGNORECASE)
  • matches.str.get(1) 矢量化元素获取
  • matches.str[1] 矢量化元素获取(效果和上一个一致),也支持分片操作
矢量化的字符串方法
method explanation method explanation
cat 元素级的字符串连接操作，可指定分隔符 contains 返回各字符串是否包含指定模式的bool数组
count 模式出现的次数 endswith,startswith 各元素是否以指定的模式开头、结尾，返回bool数组
findall 计算各字符串的模式列表 get 获取各元素的第i个字符
join 根据指定的分隔符将各元素的字符串连接起来 len 计算各字符串的长度
lower,upper 大小写转换 match 根据给定模式，执行re.match()
pad 在字符串左边/右边或两边添加空白符 center 相当于pad(side=’both’)
repeat 重复操作，在字符串上就是多个相同的拼接 replace 替换指定模式
slice 对各个字符串进行子串分片操作 split 根据指定模式，对字符串切割
strip,rstrip,lstrip 去空白符，换行符

数据聚合

1
2
3
4
5
6
7
df
$->   data1     data2 key1 key2
0  2.128648  0.552487    a  one
1  2.040146 -0.974248    a  two
2 -1.442976 -0.404534    b  one
3  1.796789 -1.413561    b  two
4  0.429355  0.604959    a  one
GroupBy
  • groupby用于DataFrame上，假定要按‘key’进行分组，并计算‘value’列的值，默认在axis=0上分组
  • grouped = df[‘value’].groupby(df[‘key’]) grouped是一个GroupBy对象，只包含一些有关分组建的中间数据
  • 上面的等价语法为：df.groupby(df[‘key’])[‘value’]或者df.groupby(df[‘key’])[[‘value’]]
  • grouped.mean() 使用GroupBy的方法进行计算
  • 分组键可以不止一个，groupby(df[‘key1’,’key2’])，得到层次索引结果
  • 分组键可是任意长度适当的数组，可以是字符串、数字或其他python对象，比如’key1’，也可以按照列的类型dtype进行分组: df.groupby(df.dtypes, axis=1)
  • df.groupby(df[‘key’]).mean() 对df的所有数值列求值，非数值列自动忽略
  • df.groupby(df[‘key’]).size() 返回含有分组大小的Series
  • grouped.describe()等方法也是可以用在这里的
分组迭代
  • GroupBy对象支持迭代，可以产生一组二元分组（由分组名和数据块组成）
  • for name,group in df.groupby(df[‘key’]) 将返回df[‘key’]每一种可能的值以及其对应的df行集合
  • for (k1, k2),group in df.groupby(df[‘key1’, ‘key2’])

groupby对象字典化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
grouped = df.groupby('key1')

glist = list(grouped)  # glist中包含的是(分组名, 数据块)组成的元组
$-> [('a',
        data1     data2 key1 key2
  0  2.128648  0.552487    a  one
  1  2.040146 -0.974248    a  two
  4  0.429355  0.604959    a  one),
     ('b',
        data1     data2 key1 key2
  2 -1.442976 -0.404534    b  one
  3  1.796789 -1.413561    b  two)]

gdict = dict(glist)  # 字典化
$-> {'a':       data1     data2 key1 key2
         0  2.128648  0.552487    a  one
         1  2.040146 -0.974248    a  two
         4  0.429355  0.604959    a  one,
     'b':       data1     data2 key1 key2
         2 -1.442976 -0.404534    b  one
         3  1.796789 -1.413561    b  two}

dict(list(df.groupby(df.dtypes, axis=1)))

分组
通过字典或者Series进行分组

比如说现在dataframe有列’a’,’b’,’c’,’d’,’e’，通过如下代码

1
2
3
4
5
6
7
8
mapping = {'a':'red','b':'blue','c':'red','d':'red','e':'blue'}
# 将字典传给groupby函数，设置axis=1（这是合并列）
by_column = df.groupby(mapping, axis=1)
by_column.sum()  # 对映射到相同名称的列求和，结果的列只有'red'和'blue'

# Series也有同样的功能
map_series(mapping)
df.groupby(map_series, axis=1).sum()

通过函数进行分组

比如说索引为字符串，若想按照字符串长度进行分组，则可以：

1
2
3
4
5
df.groupby(len).sum()

# 将函数跟数组、列表、字典等结合起来使用也可以
key_list = ['one','one','one','two','two']
df.groupby([len, key_list]).sum() # 得到一个层次化索引的结果

通过索引级别进行分组

通过level关键字传入级别编号或名称，按照索引级别进行分组

1
2
3
4
5
6
7
8
9
columns = pd.MultiIndex.from_arrays([['US','US','US','JP','JP'],[1,3,5,1,3]], names=['country','tenor'])
df = DataFrame(np.random.randn(4,5), columns=columns)
df.groupby(level='country', axis=1).count()
$->
country  JP  US
0         2   3
1         2   3
2         2   3
3         2   3

聚合方法

自定义聚合函数，将其传入agg或者aggregate方法即可

经过优化的groupby方法，可以传入函数名字符串进行调用
method explanation method explanation
count 分组中非NAN值的数量 sum 非NAN值的和
mean 非NAN值的均值 median 非NAN值的中值
std,var 无偏(分母n-1)标准差和方差 min,max 非NAN值的最值
prod 非NAN值的乘积 first,last 第一个、最后一个非NAN值
面向列的多函数应用
1
2
3
4
5
6
7
8
# 传入一个函数列表执行多个函数，每个函数的执行结果单成一列
grouped['data3'].agg(['mean', 'std', my_function])

# 传入由(name, function)元组组成的列表时，每个元组第一个元素成为结果DataFrame的列名，第二个元素是对应此列名上的函数
grouped.agg([('data1','mean'), ('data2','std')])

# 不同的列对应不同的函数，可传入字典
grouped.agg({'data1':['min','max'], 'data2':[np.max, 'std'])
聚合结果索引变换

python聚合返回结果时，向groupby函数传入: as_index=False 取消由分组键形成索引，而是将分组键变成列，把简单数字作为索引。对结果调用reset_index()也能得到这样的结果。

分组运算与转换

transform

transform函数接收一个函数，并将这个函数应用到各个分组，然后将每个分组的结果放置在这个分组对应的每一个元素上，最后显示它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
people
$->
               a         b         c         d         e
Joe    -0.338386  0.849100 -1.951048 -1.153923 -1.672975
Steve  -0.490588  0.408497 -0.692801 -0.100917  0.970808
Wes    -1.603786       NaN       NaN -0.534380  0.847692
Jim     0.309432  2.768331 -0.454094 -1.026735 -0.679794
Travis -1.400938 -0.865599 -0.190541 -0.835916  0.315975

key=['one','two','one','two','one']
people.groupby(key).mean()
$->      a         b         c         d         e
one -1.114370 -0.008250 -1.070794 -0.841406 -0.169769
two -0.090578  1.588414 -0.573447 -0.563826  0.145507

people.groupby(key).transform(np.mean)
$->         a         b         c         d         e
Joe    -1.114370 -0.008250 -1.070794 -0.841406 -0.169769
Steve  -0.090578  1.588414 -0.573447 -0.563826  0.145507
Wes    -1.114370 -0.008250 -1.070794 -0.841406 -0.169769
Jim    -0.090578  1.588414 -0.573447 -0.563826  0.145507
Travis -1.114370 -0.008250 -1.070794 -0.841406 -0.169769

# 传入自定义的函数也可以，需要注意的是自定义函数的输入参数是已经分好组的各个分组
def my_function(arr):
    return arr-arr.mean()

apply：拆分-应用-合并
  • apply 将待处理的对象拆成多个分段，然后对各分段调用传入的函数，最后尝试将各分段组合到一起
  • 分段组合需要用到pandas.concat函数
  • apply 传入函数名，这里传入的函数需要包括：分好组的DataFrame分段，也可以包括一些其他的参数
1
2
3
4
5
6
7
# 取列'tip_pct'排前五的记录
def top(df, n=5, col='tip_pct'):
    return df.sort_index(by=col)[-n:]
df.groupby('smoker').apply(top)

# 禁止分组键
df.groupby('smoker', group_keys=False).apply(top)
分位数和桶分析
  • pandas中面元划分、样本分位数划分的函数cut和qcut可以和groupby结合起来
  • 函数cut和qcut返回的对象可以作为groupby函数的参数
1
2
3
4
5
6
def get_status(group):
    return {'min':group.min, 'max':group.max, 'count':group.count}

factor = pd.cut(df.data1, 4) # labels=False，只获取分位数编号
grouped = df.data2.groupby(factor)
grouped.apply(get_status).unstack()
透视表与交叉表
透视表
  • 根据一个或多个键对数据进行聚合，并根据行和列上的分组键将数据分配到各个矩形区域中
  • DataFrame有个pivot_table函数
  • 顶级函数：pandas.pivot_table
pivot_table的参数
method explanation method explanation
values 待聚合列的名称，默认为所有数值列 rows 用于分组的列名或其他分组键，出现在结果透视图的行
cols 用于分组的列名或其他分组键，出现在结果透视图的列 aggfunc 聚合函数或函数列表，默认为mean。可以是任何对groupby有效的函数
fill_value 用于替换结果表中的缺失值 margin 添加行列小计，默认为False 
1
2
3
4
5
6
7
8
9
# 第一个参数是表格内容，如果不设置，则默认为pivot_table中的默认聚合类型
# 设置参数 rows，设置行内容和索引，
# 设置参数 cols，设置列内容和索引
tips.pivot_table(['tip_pct','size'], rows=['sex','day'], cols='smoker')

# 设置：margins=True，添加分项小计，默认为平均值
tips.pivot_table(['tip_pct','size'], rows=['sex','day'], cols='smoker', margins=True)
# 要使用其他小计函数，可以使用：aggfunc参数
tips.pivot_table(['tip_pct','size'], rows=['sex','day'], cols='smoker', margins=True,aggfunc='sum')
交叉表
  • 交叉表是一种用于计算分组频率的特殊透视表
  • pandas.crosstab函数可以统计交叉表
1
2
3
4
# param1: 用于分组的列名或其他分组键，出现在结果透视图的行
# param2: 用于分组的列名或其他分组键，出现在结果透视图的列
# margins=True：行、列小计
pd.crosstab(param1, param2, margins=True)
分享到

python时间序列分析

Algorithm
python, time_series_data

基础工具

基础工具类，datetime模块
type explanation
date 以公历形式存储日历日期
time 以时、分、秒、毫秒形式存储时间
datetime 存储如期和时间
timedelta 两个datetime之间的差
  • datetime以毫秒形式存储日期和时间，datetime.timedelta表示两个datetime对象之间的时间差
  • 可以给datetime加上、减去一个或者多个timedelta对象
1
2
3
4
5
6
7
8
9
10
11
from datetime import datetime, timedelta
now = datetime.now()
now.year, now.month, now.day
$-> datetime.datetime(2016, 8, 4, 15, 14, 36, 899000)

# timedelta只有days和seconds这两个成员
delta = datetime(2011,7,2)-datetime(2011,7,1,9)
delta.days, delta.seconds
$-> (0, 54000)

delta = datetime(2011,7,2)-2*timedelta(10)
字符串和datetime的相互转换

datetime -> string

  • str方法
  • strftime方法
1
2
3
4
5
stamp = datetime(2011,8,1)
str(stamp)
$-> '2011-08-01 00:00:00'
stamp.strftime('%Y-%m-%d')
$-> '2011-08-01'

string -> datetime

  • datetime.strptime
  • dateutil的parser.parse方法，dateutil几乎可以理解所有人类能够理解的日期格式
1
2
3
4
5
6
value = '2011-1-25'
# 返回一个datetime对象
datetime.strptime(value, '%Y-%m-%d')

from dateutil.parse import parse
parse('2011-03-12')
pandas中的时间数据处理
  • pandas处理成组的时间数据
  • 可以处理空值和非法值，用NaT表示
  • 可能会把一些不是日期的字符串变成日期
1
2
datestr = ['2011-04-12','2015-11-09']
pd.to_datetime(datestr)

时间序列基础

1
2
3
4
5
6
7
8
from datetime import datetime
dates = [datetime(2012,1,1), datetime(2012,1,2)]
# datetime对象放置在一个DatetimeIndex中，pandas会自动识别这个Series为时间序列数据
ts = Series(np.random.randn(2), index=dates)

# DatetimeIndex中的各个标量是pandas的TimeStamp对象
ts.index[0]
$-> Timestamp('2012-01-01 00:00:00')
索引与子集
1
2
3
4
5
6
7
8
9
10
11
12
13
# 可以传入被解释为日期的字符串来访问
ts['2012-01-01']

# 切片操作，可以传入‘年’或者‘年月’
# periods决定date_range的长度
longer_ts = Series(np.random.randn(1000), index=pd.date_range('1/1/2000',period=1000))

# 也可以像列表切片那样，可以传入字符串日期，datetime或TimeStamp对象
# 这样切片产生的是源数据的视图，与numpy数组的切片运算一致
ts[datetime(2011,1,7):] # 2011-1-7起的所有数据
ts['1/6/2011':'1/11/2011'] # 从[2011-1-6, 2011-1-11)的数据

ts.truncate(after='1/1/2011') # 也有类似的效果

在Series与DataFrame中均适用，只要设置index即可

日期范围
date_range
  • pandas.date_range(start=s, end=e, period=p, freq=f, normalize=True)
  • [s, e)：决定了初始时间和结束时间
  • p：周期值，决定日期长度
  • f：决定频率，默认为’D’,表示天。常用频率见下表，更详细的见书本314页
  • normalize：True表示产生规范化到午夜的时间戳
value explanation value explanation
D 每日历日 B 每工作日
H 每小时 T or min 每分钟
S 每秒钟 L or ms 每毫秒
U 每微秒 M 每月最后一个日历日
BM 每月最后一个工作日 MS 每月第一个日历日
W-MON,W-TUE,.. 从指定的星期几开始起的每一周 BMS 每月第一个工作日
Q-JAN,Q-FEB,.. 从起始时间开始，每个季度最后一个月的最后一个工作日 WOM-1MON,WOM-2MON,..WOM-1FRI.. 产生每月第x个星期几
日期偏移量
1
2
3
4
5
6
7
8
9
10
from pandas.tseries.offsets import Hour,Minute
hour = Hour(4)
# 也可以更加简洁地使用freq参数
# freq = '1h30min'
pd.date_range('1/1/2011', '1/2/2011', freq='4h')
$-> DatetimeIndex(['2011-01-01 00:00:00', '2011-01-01 04:00:00',
                   '2011-01-01 08:00:00', '2011-01-01 12:00:00',
                      '2011-01-01 16:00:00', '2011-01-01 20:00:00',
                      '2011-01-02 00:00:00'],
                  dtype='datetime64[ns]', freq='4H')
移动数据
  • Series和DataFrame都有一个shift方法用于移动数据
  • shift移动步长参数：正值后移，负值前移
  • shift也可以带有参数 freq，这种情况下，数据不变，索引移动(正值前移)
1
2
3
4
# 计算变化率
ts / ts.shift(1) - 1

ts.shift(2,freq='D')
  • 日期偏移量可以做用在datetime或TimeStamp对象上
  • 如果加的是锚点偏移量(如MonthEnd)，第一次会偏移到符合频率规则的下一日期
  • 通过锚点偏移量的rollforward和rollback方法
1
2
3
4
5
6
7
8
9
10
11
12
13
from pandas.tseries.offsets import Day, MonthEnd

now = datetime(2011,2,15)
now + MonthEnd()
$-> Timestamp('2011-02-28 00:00:00')
now + MonthEnd(2)
$-> Timestamp('2011-03-31 00:00:00')'

offset = MonthEnd()
offset.rollforward(now)
$-> Timestamp('2011-02-28 00:00:00')
offset.rollback(now)
$-> Timestamp('2011-01-31 00:00:00')
时区处理

时间序列、日期范围和时间戳都可以从naive型转化为本地化时区意识型，也可以从一个时区转化为另一个时区

1
2
3
4
5
import pytz
# 常用时区列表
pytz.common_timezones
# 获取时区对象
tz = pytz.timezone('UTC')

默认情况下，pandas中的时区是naive的，其索引的tz字段为None
所以在生成日期范围的时候可以加上一个时区信息,设置tz参数。也可以直接使用tz_localize方法

1
2
3
4
5
6
7
8
9
10
11
12
13
pd.date_range('1/1/2001',period=10,tz='UTC')
# 完成本地化操作
ts_utc = ts.tz_localize('UTC')

# 时区转化
ts_utc.tz_convert('US/Eastern')

# 时间戳转换
stamp = pd.TimeStamp('2011-03-12 04:00')
stamp_utc = stamp.tz_localize('UTC')
stamp_eu = stamp.tz_convert('Europe/Moscow')

stamp_moscow = pd.TimeStamp('2011-03-12 04:00', tz='Europe/Moscow')

合并两个时间序列数据，时区不同时，结果自动转化为UTC时间。

时期Period及其算术运算
  • 时期Period表示的是时间区间，如数日、数月、数季、数年等，包含在pandas中
  • 构造函数需要一个字符串或者整数，以及freq参数
  • pandas.period_range函数，pandas.PeriodIndex函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 这个Period表示的是从2007-1-1到2007-12-31日之间的整段时间
# 可以被看成一个被划分成多个月度时期的时间段中的游标
p = pd.Period(2007,freq='A-DEC')
# 与整数直接进行加、减法运算
p + 5
$-> Period('2012', 'A-DEC')

# Period对象之间的加、减法运算
# freq不同时会抛出异常
pd.Period('2014', freq='A-DEC') - p
$-> 7L

# 创建时期范围
pd.period_range('1/1/2000', '6/30/2000', freq='M')

values = ['2001Q3', '2002Q2', '2003Q1']
index = pd.PeriodIndex(values, freq='Q-DEC')
index $-> PeriodIndex(['2001Q3', '2002Q2', '2003Q1'], dtype='int64', freq='Q-DEC')
时期的频率转换

Period和PeriodIndex对象都可以通过其asfreq方法被转换到其他频率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
p = pd.Period('2007', freq='A-DEC')
p.asfreq('M',how='start')
$-> Period('2007-01','M')
p.asfreq('M',how='end')
$-> Period('2007-12','M')
P.asfreq('B',how='start')
$-> Period('2007-01-01', 'B')

# 高频率转化为低频率
p = pd.Period('2007-08', 'M')
p.asfreq('A-JUN')
# 在频率A-JUN中，2007-08实际上是属于2008年
$-> Period('2008','A-JUN')

# 按季度计算的时期频率
# 频率为 Q-JAN,Q-FEB,Q-MAR,....Q-DEC, JAN starts from feb
p = pd.Period('2012Q4', freq='Q-JAN')
# 2012年Q4是从2011-11-01到2012-01-31
p.asfreq('D', 'start')
$-> Period('2011-11-01', 'D')
p.asfreq('D','e')
$-> Period('2012-01-31', 'D')

# TimeStamp和Period的相互转换
# to_timestamp()和to_period('freq')方法
ts = Series(np.random.randn(3), index=pd.date_range('1/1/2000',periods=3,freq='M'))
ts  $->
2000-01-31    2.375484
2000-02-29    0.726024
2000-03-31   -0.328938
Freq: M, dtype: float64

pts = ts.to_period()
pts $->
2000-01    2.375484
2000-02    0.726024
2000-03   -0.328938
Freq: M, dtype: float64

pts.to_timestamp(how='end')
$->
2000-01-31    2.375484
2000-02-29    0.726024
2000-03-31   -0.328938
Freq: M, dtype: float64

通过数组创建PeriodIndex
固定频率的数据集通常会将时间信息分开存放在多个列中，将这些数据以及频率传入PeriodIndex中就可以将它们合并成一个DataFrame索引

1
2
# quarter表示季度
pd.PeriodIndex(year=data.year, quarter=data.quarter, freq='Q-DEC')

重采样及频率转换
  • 重采样指的是将时间序列从一个频率转换到另一个频率的处理过程
  • 低频到高频称为升采样，反之为降采样
  • pandas对象都有一个resample方法
param explanation param explanation
freq 表示重采样频率的字符串或DataOffset,’M’,’5min’,Second(15) how=’mean’ 产生聚合的函数名或数组函数，默认为mean，还有’first’,’last’,’ohlc’,’min’
axis=0 采样轴，默认为axis=0 fill_method=None 升采样时的插值方式，可取’ffill’或’bfill’
closed=’right’ 降采样中，时间段哪一端是闭合的 label=’right’ 降采样中聚合值的标签
loffset=None 面元标签的时间校正值，-1s(Second(-1))将时间调早1s limit=None 向前、向后填充时，允许填充的最大时期数
kind=None 聚合到时期或时间戳，默认聚合到时间序列的索引类型 convention=None 重采样时期，低频到高频所采用的约定(‘start’/‘end’)，默认为’end’
降采样
1
2
3
4
# 聚合到5min范围，聚合函数为'sum'求和
ts.resample('5min', how='sum')

ts.resample('5min', how='sum', closed='left', label='left', loffset='-1s')

OHLC重采样

  • 经常应用于金融数据的采样方法，计算各面元的四个值，分别是第一个值（open/开盘）、最后一个值（close/收盘）、最大值（high/最高）、最小值（low/最低）
  • 传入how=’ohlc’即可得到含有这四种聚合值的DataFrame
  • ts.resample(‘5min’, how=’ohlc’)
  • 也可以通过groupby进行重采样
  • ts.groupby(lambda x: x.month).mean()
  • ts.groupby(lambda x: x.weekday).mean()
升采样
  • 升采样过程中，不需要聚合，需要插值
  • 既不是降采样也不是升采样的采样，需要传入新的频率 frame.resample(‘W-MON’,fill_method=’ffill’)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
frame = DataFrame(np.random.randn(2,4),index=pd.date_range('1/1/2000',periods=2,freq='W-WED'),columns=['a','b','c','d'])
frame
$->               a         b         c         d
2000-01-05 -0.550387 -1.294863  0.274911  0.330741
2000-01-12  2.512896 -1.719330  0.090617  0.329635

# 设置fill_method为ffill或者bfill，不设置时，引入缺失值
# 如果设置limit值，则只填充limit行
frame.resample('D', fill_method='ffill', limit=4)
$->                a         b         c         d
2000-01-05 -0.550387 -1.294863  0.274911  0.330741
2000-01-06 -0.550387 -1.294863  0.274911  0.330741
2000-01-07 -0.550387 -1.294863  0.274911  0.330741
2000-01-08 -0.550387 -1.294863  0.274911  0.330741
2000-01-09 -0.550387 -1.294863  0.274911  0.330741
2000-01-10       NaN       NaN       NaN       NaN
2000-01-11       NaN       NaN       NaN       NaN
2000-01-12  2.512896 -1.719330  0.090617  0.329635
绘图中的移动窗口函数
  • 移动窗口上计算的各种函数也是一类常见于时间序列的数组变换，称之为移动窗口函数
  • 它们接受TimeSeries或DataFrame对象，以及一个窗口长度。它们是pandas的函数
移动窗口和指数加权函数
function explanation function explanation
rolling_count 各窗口非NA观测值的数量 rolling_sum 窗口和
rolling_mean 窗口均值 rolling_median 窗口中位数
rolling_var,rolling_std 窗口无偏方差、标准差(n-1) rolling_skew,rolling_kurt 窗口三阶矩(偏度)、四阶矩(峰度)
rolling_min,rolling_max 窗口的最值 rolling_quantile 窗口制定百分数、分位数位置的值
rolling_corr,rolling_cov 窗口的相关系数和协方差 rolling_apply 对窗口应用普通数组函数
ewma 指数加权移动平均 ewmvar,ewmstd 指数加权移动方差和标准差
ewmcorr,ewmcov 指数加权移动相关系数和协方差

这些函数均不考虑NA值，bottlenect则是NA友好的窗口移动函数集。

1
2
3
4
5
6
# 窗口长度为250
pd.rooling_mean(data['col1'], 250, min_periods=10).plot()

# 将rolling_mean()函应用到所有列上,画出所有列对应的数据
expanding = lambda x : rolling_mean(x, len(x), min_periods=1)
pd.rolling_mean(data, 60).plot(logy=True)

指数加权函数
  • 通过定义一个衰减因子，decay factor，使得近期的观测值拥有更大的权重
  • 衰减因子定义可以使用：时间间隔span，兼容于窗口大小等于时间间隔的简单移动窗口函数
  • 具有较强的适应性
1
2
pd.ewma(data['col1'], span=60).plot()
# ewmvar, ewmstd的使用同理
二元移动窗口函数
  • 作用在两个个序列上的函数，比如相关性计算和协方差计算
1
2
3
4
pd.rolling_corr(series1, series2, 100, min_periods=100).plot()
# 计算一个序列与DataFrame的各个列的相关关系时
data = DataFrame(...)
pd.rolling_corr(data, series, 100, min_periods=100).plot()
用户定义的移动窗口函数
  • 使用rolling_apply()函数，需要自定义函数作为参数输入
  • 自定义函数要求：能从数组的各个片段中产生单个值
1
2
3
4
# percentileofscore(x,y)可用于计算样本x中特定值y的百分等级
from scipy.stats import percentileofscore
score_at_2percent = lambda x: percentileofscore(x, 0.02)
pd.rolling_apply(data['col'], 200, score_at_2percent)
分享到

NumPy进阶

Dev
numpy, python
数组重塑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import numpy as np
from numpy.random import randn

# reshape函数
arr = np.arange(8)
arr.reshape((4, 2)).sahpe
$-> (4, 2)
arr.reshape((5,-1))

# 扁平化函数
# flatten函数返回数据副本，ravel则不是
# 这些函数可以带有指示顺序的参数：{'C':行有限, 'F':列优先}
arr = np.arange(15).reshape((5, 3))
arr.ravel()
$-> array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14])
arr.flatten()
$-> array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14])
arr.ravel('F')
$-> array([ 0,  3,  6,  9, 12,  1,  4,  7, 10, 13,  2,  5,  8, 11, 14])

# 拆分合并
arr1 = np.array([[1,2,3],[4,5,6]])
arr2 = np.array([[7,8,9],[10,11,12]])
np.concatenate([arr1, arr2], axis=0)
$-> array([[ 1,  2,  3],
              [ 4,  5,  6],
           [ 7,  8,  9],
           [10, 11, 12]])

np.concatenate([arr1, arr2], axis=1)
$-> array([[ 1,  2,  3,  7,  8,  9],
           [ 4,  5,  6, 10, 11, 12]])

# vstack(垂直方向的连接), hstack(水平方向的连接)
# 里面的圆括号也可以换成方括号
np.vstack((arr1, arr2))
$-> array([[ 1,  2,  3],
           [ 4,  5,  6],
           [ 7,  8,  9],
           [10, 11, 12]])

np.hstack([arr1, arr2])
$-> array([[ 1,  2,  3,  7,  8,  9],
           [ 4,  5,  6, 10, 11, 12]])

# split
arr = randn(5, 2)
first, second, third = np.split(arr,[1,3])
first
$-> array([[-0.28435497,  0.71298716]])
second
$-> array([[ 0.48442513, -0.84460369],
           [-0.38289692, -1.11166995]])
third
$-> array([[-0.44724781,  0.52083756],
           [-0.39584687,  0.14325106]])
数组连接函数
method explanation
concatenate 沿一条轴连接一组数组
vstack,hstack 垂直、水平连接
row_stack 按行连接，相当于vstack
column_stack 按列连接，相当于hstack
dstack 以面向‘深度’的方式堆叠，沿轴2
split 沿指定轴的指定位置拆分
hsplit,vsplit,dsplit 分别沿轴0、1、2切分

元素重复操作
tile and repeat函数
tile沿指定轴向堆叠数组的副本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
arr = np.arange(3)
arr.repeat(3)
$-> array([0, 0, 0, 1, 1, 1, 2, 2, 2])
arr.repeat([2,3,4])
$-> array([0, 0, 1, 1, 1, 2, 2, 2, 2])

arr = np.arange(4).reshape((2,2))
arr.repeat([2,3], axis=0)
$-> array([[0, 1],
             [0, 1],
          [2, 3],
          [2, 3],
          [2, 3]])

np.tile(arr, 2)
$-> array([[0, 1, 0, 1],
           [2, 3, 2, 3]])

广播
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
np.arange(4) + 3
$-> array([3, 4, 5, 6])

# 每一行减去均值时，直接减
# 每一列减时需要维度变化
arr = np.arange(12).reshape((3,4))
# 参数为0计算每列的均值，1则计算每行的均值
arr.mean(0)
$-> array([ 4.,  5.,  6.,  7.])

arr - arr.mean(0)
$-> array([[-4., -4., -4., -4.],
           [ 0.,  0.,  0.,  0.],
           [ 4.,  4.,  4.,  4.]])

# arr - arr.mean(1)报错
# 沿其他轴广播，较小数组的‘广播维’必须为1，所以需要reshape()，把n变成(n,1)
arr - arr.mean(1).reshape((4,1))
$-> array([[-1.5, -0.5,  0.5,  1.5],
           [-1.5, -0.5,  0.5,  1.5],
           [-1.5, -0.5,  0.5,  1.5]])

# 一般解决方法是：专门为广播添加一个新轴
# 通过np.newaxis属性及全切片完成
arr = randn(3,4,5)
depth_mean = arr.mean(2)
demean = arr - depth_mean[:,np.newaxis,:]
demean.mean(2)
# 结果基本为0
$-> array([[  0.00000000e+00,  -2.22044605e-17,   1.11022302e-17,
              8.88178420e-17],
           [ -2.22044605e-17,  -1.11022302e-17,  -7.77156117e-17,
              2.77555756e-17],
           [  2.22044605e-17,  -5.55111512e-18,  -3.33066907e-17,
             -6.66133815e-17]])

# 通过广播设置数组的值
arr = randn(3,4)
arr[:] = 5
arr $->
array([[ 5.,  5.,  5.,  5.],
       [ 5.,  5.,  5.,  5.],
       [ 5.,  5.,  5.,  5.]])
ufunc高级应用
ufunc方法
method explanation
reduce(x) 通过连续执行原始运算的方式对值进行聚合
accumulate(x) 聚合值，保留所有局部聚合结果
reduceat(x,bin) 局部约简。约简数据的各个切片以产生聚合型数组
outer(x,y) 对x、y中的每个元素应用原始运算
自定义ufunc
  • numpy.frompyfunc()函数接受一个python函数，以及两个分别表示输入输出参数数量的整数
  • numpy.vectorize()函数用法类似
  • 这两个函数速度较慢
1
2
3
4
5
6
7
8
9
10
def add_elements(x, y):
    return x+y
# add_elements函数接受两个参数，返回一个参数
add_them = np.frompyfunc(add_elements, 2, 1)
add_them(np.arange(6), np.arange(6))
$-> array([0, 2, 4, 6, 8, 10], dtype=object)

add_them = np.vectorize(add_elements)
add_them(np.arange(6), np.arange(6))
$-> array([ 0,  2,  4,  6,  8, 10])
更多的排序
  • ndarray的排序是就地排序
  • numpy.sort产生一个排好序的副本
  • 两个函数都可以接受axis参数，0：对列排序，1：对行排序
间接排序

对多个键排序时，可以使用这两个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
values = np.array([5,0,1,3,2])
index = values.argsort()
index
$-> array([1, 2, 4, 3, 0])
values[index]
$-> array([0, 1, 2, 3, 5])

first = np.array(['a','b','c','d','e'])
last = np.array(['z','y','x','v','u'])
# 键的应用是从后往前，先last，再first
sorter = np.lexsort((first, last))
sorter $-> array([4, 3, 2, 1, 0])

zip(last[sorter], first[sorter])
$-> [('u', 'e'), ('v', 'd'), ('x', 'c'), ('y', 'b'), ('z', 'a')]

排序算法的kind参数
param speed stability space complexity worst complexity
quicksort 1 no 0 O(n^2)
mergesort 2 yes n/2 O(nlogn)
heapsort 3 no 0 O(nlogn)
numpy.searchsorted
  • 有序数组中的查找，使用二分查找
  • 存在待查找的元素，返回其序号，否则返回插入该元素后该元素的序号
1
2
3
4
5
6
7
8
9
10
11
12
arr = np.array([1,2,4,5,6,8,9])
arr.searchsorted(5)
$-> 3
arr.searchsorted(7)
$-> 5

arr = np.array([0,0,0,1,1,1])
arr.searchsorted([0,1])
$-> array([0, 3])
# 从右边数
arr.searchsorted([0,1], side='right')
$-> array([3, 6])
NumPy的matrix类
  • np.matrix()接受参数：二维数组，构建一个矩阵对象
  • 支持使用直接的 * 运算
  • X.I返回矩阵X的逆
  • 可用X.asarray将其转化为正规的ndarray对象
输出输入
内存映像文件
  • 内存映像文件是一种将磁盘上的非常大的二进制文件当作文件中的数组进行处理的方式，实际上就是放在磁盘上的ndarray
  • NumPy中的memmap对象允许将大文件分成小段进行读写
  • np.memmap()函数接受(文件路径,数据类型,文件模式,模式)
  • 对memmap对象切片会返回磁盘上的数据视图，如果对这些视图赋值，数据会被存储在内存中，调用flush就可以写入磁盘
  • 如果某个内存映像超出作用域，他就会被垃圾回收器回收，之前的修改都会被写入磁盘
1
2
3
4
5
6
mmap = memmap('mymmap', dtype='float64', mode='w+', shape=(10000,10000))
section = mmap[:5]
section[:] = randn(5,10000)

mmap.flush()
del mmap
HDF5
  • PyTables和h5py用于处理高效、可压缩的HDF5格式的数据
  • PyTables提供了一些用于结构化数组的高级查询功能
性能加速
  • 避免复制
  • 使用广播
  • 使用ufunc方法
  • 使用连续内存
  • Cython加速
1
2
3
arr_c = np.ones((1000,1000), order='C')
arr_f = np.ones((1000,1000), order='F')
# 对前者的操作要快于后者的操作，前者数据按照C语言的连续方式存储
分享到

Count Complete Tree Nodes

OJ
Binary Tree, LeetCode

Problem

count the total number of Binary Complete Tree nodes

Solution

  • traverse tree skill is not acceptable.

  • The height of a tree can be found by just going left. Let a single node tree have height 0. Find the height h of the whole tree. If the whole tree is empty, i.e., has height -1, there are 0 nodes.

  • Otherwise check whether the height of the right subtree is just one less than that of the whole tree, meaning left and right subtree have the same height.

  • If yes, then the last node on the last tree row is in the right subtree and the left subtree is a full tree of height h-1. So we take the 2^h-1 nodes of the left subtree plus the 1 root node plus recursively the number of nodes in the right subtree.

  • If no, then the last node on the last tree row is in the left subtree and the right subtree is a full tree of height h-2. So we take the 2^(h-1)-1 nodes of the right subtree plus the 1 root node plus recursively the number of nodes in the left subtree.

  • Since I halve the tree in every recursive step, I have O(log(n)) steps. Finding a height costs O(log(n)). So overall O(log(n)^2).

recursive version:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    int height(TreeNode root) {
        return root == null ? -1 : 1 + height(root.left);
    }
    public int countNodes(TreeNode root) {
        int h = height(root);
        return h < 0 ? 0 :
               height(root.right) == h-1 ? (1 << h) + countNodes(root.right)
                                         : (1 << h-1) + countNodes(root.left);
    }
}

iterative version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        int num=1;
        TreeNode *curR(root->left), *curL(root->left);
        // curR is the rightmost edge, which has a height equal to or less than the leftmost edge
        while(curR) {
            curL = curL->left;
            curR = curR->right;
            num = num<<1;
        }
        return  num + ( (!curL)?countNodes(root->right):countNodes(root->left) );
    }
};

分享到