精华内容
下载资源
问答
  • 分组
    千次阅读
    2020-12-03 14:48:00

    在日常数据分析时,经常会遇到需要按列分组 (groupby) 的任务,如计算某公司各部门的人数,计算各部门男女平均工资,计算不同年代的员工的平均工资等等。在进行这类运算时,Pandas 提供了 groupby 函数,大多数问题它都可以解决,但有一些问题使用 groupby 函数会略显麻烦,下面我们就这些问题展开细致的讨论。

    groupby 是 pandas 中非常重要的一个函数, 主要用于数据分类和聚合计算. 其思想是“split-apply-combine”(拆分 - 应用 - 合并),如下图:

    ..

    分组原理图

    一、单列分组聚合

    单列分组聚合是指把某一列作为键进行分组,然后对各组进行聚合运算。

    它是上述分组原理的最简单应用,比如根据员工信息数据,计算各部门员工数。

    问题分析:要计算各部门员工数,首先把部门作为键进行分组,然后对各组成员进行计数。

    部分员工信息数据如下:

    EIDNAMESURNAMEGENDERSTATEBIRTHDAYHIREDATEDEPTSALARY
    1RebeccaMooreFCalifornia1974/11/202005/3/11R&D7000
    2AshleyWilsonFNew York1980/7/192008/3/16Finance11000
    3RachelJohnsonFNew   Mexico1970/12/172010/12/1Sales9000
    4EmilySmithFTexas1985/3/72006/8/15HR7000
    5AshleySmithFTexas1975/5/132004/7/30R&D16000

    Python代码

    import pandas as   pd

    employee =   pd.read_csv("Employees.csv")

    dept_emp_num =   employee.groupby('DEPT')['DEPT'].count()

    print(dept_emp_num)

     

    读取数据

    分组计数

    讨论:groupby(‘DEPT’) 将数据按照部门分组, count() 函数进行计数。

    二、多列分组聚合

    多列分组聚合是指把多列的值同时作为键进行分组,然后对各组进行聚合运算。

    它和单列分组聚合类似,只是分组的键是多列组合而已。如根据员工信息数据,计算各部门男女员工的平均工资。

    继续使用上例中的员工信息数据

    问题分析:需要分组的键有两个,分别是部门和性别,只要把他们组合起来看作是一个键,然后当做单列分组聚合即可。

    Python 代码

    import pandas as pd

    employee = pd.read_csv("Employees.csv")

    dept_gender_salary =   employee.groupby(['DEPT','GENDER'],as_index=False).SALARY.mean()

    print(dept_gender_salary)

     

     

    多列分组再聚合

    讨论:groupby(['DEPT','GENDER']),分组的两列以列表的形式作为参数,as_index 表示是否把分组列作为索引,True 表示作为索引,这里使用 False 表示不作为索引。使用 mean() 函数计算工资的平均值。

    三、根据衍生列分组聚合

    根据衍生列分组聚合,是指需要分组的键并不直接在数据中,需要根据数据计算出一列新数据,把它作为键对数据进行分组。如计算不同年代的员工的平均工资。

    问题分析:员工信息数据中并没有年代这一列,因此需要根据员工的生日列计算出来,把它作为键对员工数据进行分组,然后再求工资均值。

    Python 代码

    import pandas as pd

    import numpy as np

    employee = pd.read_csv("Employees.csv")

    employee['BIRTHDAY']=pd.to_datetime(employee['BIRTHDAY'])

    years_salary =   employee.groupby(np.floor((employee['BIRTHDAY'].dt.year-1900)/10)).SALARY.mean()

    print(years_salary)

     

     

     

    生日列转换成日期格式

     

    计算衍生数组并按此数组分组,再计算平均工资

    讨论:年代数据在原数据中并不存在,使用 np.floor((employee['BIRTHDAY'].dt.year-1900)/10) 计算出衍生列表示年代,然后根据他分组并计算平均工资。

    四、多个聚合

    多个聚合,是指分组后对单列或者多列进行多种聚合。

    (一)   多列单聚合

    多列单聚合,指同时对多列聚合,但每列使用一种聚合方式。如:同时计算各部门员工的人数,平均工资。

    问题分析:求员工人数可以对 EID 计数,求平均工资需要对工资列求均值,两列聚合但每列只用一种聚合方式。

    Python 代码

    import pandas as pd

    employee = pd.read_csv("Employees.csv")

    dept_agg =   employee.groupby('DEPT',as_index=False).agg({'EID':'count','SALARY':'mean'})

    print(dept_agg.rename(columns={'EID':'NUM','SALARY':'AVG_SALARY'}))

     

     

    分组并对 EID 计数,对 SALARY 求平均

    重命名列名

    讨论:Pandas 的 agg()函数可以完成这类任务,各列以及各列的聚合方式以字典的形式作为参数传入 agg(),聚合的列作为字典的键,聚合方式作为字典的值,从而完成聚合运算。

    (二)   单列多聚合

    单列多聚合,指只对一列聚合,但聚合的方式有多种。如上述问题也可以直接对工资计数并求平均,此时是对工资进行了两种聚合——计数和平均。

    Python 代码

    import pandas as   pd

    employee =   pd.read_csv("Employees.csv")

    dept_agg = employee.groupby('DEPT').SALARY.agg(['count','mean']).reset_index()

    print(dept_agg.rename(columns={'count':'NUM','mean':'AVG_SALARY'}))

     

     

    对 SALARY 计数并求平均

    重命名列名

    讨论:如果是单列的不同聚合方式,则可以把聚合方式进行组合以列表的形式作为参数传入 agg()。

    (三)   多列多聚合

    多列多聚合,指对多列聚合同时也包含单列多聚合的组合聚合方式。聚合方式还可以是自己定义的函数,

    如:计算各部门员工人数,平均工资和最大年龄。

    问题分析:计算员工人数和平均工资,是对工资列计数并求平均(单列多聚合),求最大年龄,需对生日列使用自定义的函数计算出最大年龄。

    Python 代码

    import pandas as   pd

    import datetime

    def max_age(s):

        today = datetime. datetime.today().year

        age = today-s.dt.year

        return age.max()

    employee = pd.read_csv("Employees.csv")

    employee['BIRTHDAY']=pd.to_datetime(employee['BIRTHDAY'])

    dept_agg =   employee.groupby('DEPT').agg({'SALARY':['count','mean'],'BIRTHDAY':max_age})

     

     

     

    dept_agg.columns   = ['NUM','AVG_SALARY','MAX_AGE']

    print(dept_agg.reset_index())

     

     

    函数:求最大年龄

    年份

    求年龄

     

     

     

    按 DEPT 分组,根据 SALARY 计数和求均值,BIRTHDAY 使用 max_age 计算最大年龄

    修改列名

     

    讨论:这种情况,聚合列和聚合方式还是按照字典的方式传入,但当某一列需要多种聚合方式时,则需要将其组合,以列表的形式作为字典的值。

    五、分组聚合值复制

    分组聚合值复制,指把分组聚合的结果转换成与该组等长的列,相当于把聚合的结果复制到该组的所有行。如:为员工信息数据新增一列各部门的平均工资。

    问题分析:各部门的平均工资需要按照部门分组再对工资求平均,把平均工资的值添加到对应的组,并保持数据原序。

    Python 代码

    import pandas as pd

    employee = pd.read_csv("Employees.csv")

    employee['AVG_SALARY'] =   employee.groupby('DEPT').SALARY.transform('mean')

    print(employee)

     

     

    按照 DEPT 分组并对 SALARY 求平均

    讨论:按照部门分组后,对工资求均值。transform() 函数在组内求聚合值后会按照原索引的顺序返回结果,可以自动按照索引添加结果,从而保证原数据顺序不变。

    六、分组子集处理

    分组应用:指分组后对各组进行一些非聚合运算。比如分组排序,分组后不再关心聚合的结果,而是关心组内记录的顺序。如:将各部门按照入职时间从早到晚进行排序 。

    问题分析:按照部门分组后,不再关心分组后的聚合结果,而是关心员工的入职时间顺序。分组后,对各组进行循环同时对组内成员按照入职时间排序就可以了。

    Python 代码

    import pandas as pd

    employee = pd.read_csv("Employees.csv")

    employee['HIREDATE']=pd.to_datetime(employee['HIREDATE'])

    employee_new =   employee.groupby('DEPT',as_index=False).apply(lambda   x:x.sort_values('HIREDATE')).reset_index(drop=True)

    print(employee_new)

     

     

    修改入职时间格式

     

    按 DEPT 分组,并对各组按照 HIREDATE 排序,最后重置索引

     

    讨论:分组后需要对组内成员排序,可以使用 apply()函数结合 lambda 的方式,其中 lambda 表达式是对各组循环,使用 sort_values() 函数在组内部再排序,返回组内排序的结果。

    简单的运算使用 lambda 函数计算,但有时会遇到比较复杂的计算,如:计算各部门年龄最大的员工和年龄最小的员工的工资差。

    问题分析:首先需按照部门分组,分组后还需要找到年龄最大的员工和年龄最小的员工的记录,然后才能计算工资差。

    Python 代码

    import pandas as pd

    def salary_diff(g):

        max_age =   g['BIRTHDAY'].idxmin()

        min_age =   g['BIRTHDAY'].idxmax()

        diff =   g.loc[max_age]['SALARY']-g.loc[min_age]['SALARY']

        return diff

    employee = pd.read_csv("Employees.csv")

    employee['BIRTHDAY']=pd.to_datetime(employee['BIRTHDAY'])

    salary_diff = employee.groupby('DEPT').apply(salary_diff)

    print(salary_diff)

     

    函数:计算各组工资差

    年龄最大的索引

    年龄最小的索引

    计算工资差

     

     

     

    按 DEPT 分组并使用自定义函数计算

     

    讨论:使用 apply()结合自定义函数的方式。其中 apply() 会把分组的结果作为参数传入自定义函数。salary_diff() 函数是自定义函数,g 实质上就是 pandas 的 DataFrame 格式的数据框,这里是分组的结果。对它计算最大年龄和最小年龄的索引后,找到工资字段计算差即得到结果。

    思考:

    由上述讨论可见,熟练掌握 Pandas 的这些 groupby 方法对我们进行数据分析是特别有帮助的。

     

    下面我们以 stack overflow 网站上的一些实际问题来进一步了解 groupby。

    七、按位置分组

    按位置分组,指不以某列作为键分组,而是以记录的位置作为键来分组。比如将数据每三行分到相同组或者按照位置分成奇数位置一组,偶数位置一组等。举例如下:

    source: https://stackoverflow.com/questions/59110612/pandas-groupby-mode-every-n-rows

    数据片段如下:

    time                       a                       b

    0                          0.5                    -2.0

    1                          0.5                    -2.0

    2                          0.1                    -1.0

    3                          0.1                    -1.0

    4                          0.1                    -1.0

    5                          0.5                    -1.0

    6                          0.5                    -1.0

    7                          0.5                    -3.0

    8                          0.5                    -1.0

    希望每三行分成一组,并把众数作为该组的结果。理想的结果如下:

    time                       a                       b

    2                          0.5                    -2.0

    5                          0.1                    -1.0

    8                          0.5                    -1.0

    问题分析:该问题的分组与现有的列没有关系,只与位置相关,因此需要衍生出一列作为分组依据,按位置做整数乘法即得到衍生列,然后据此分组即可。

    Python 代码

    import pandas as pd

    import numpy as np

    data = pd.read_csv("group3.txt",sep='\t')

    res = data.groupby(np.arange(len(data)) //   3).agg(lambda x: x.mode().iloc[-1])

    print(res)

     

     

     

    按照衍生列分组,使用 agg 结合 lambda 的方式得到众数,取各组各列的最后 1 个众数作为结果

    讨论:衍生列计算方式为 np.arange(len(data)) // 3,其结果是 [0 0 0 1 1 1 2 2 2],把它作为键进行分组就可以把数据分成每三行一组。而 agg(lambda x: x.mode()) 则是将各组的各列分别求众数,如第一组 time 的众数为 [0,1,2] 而 a 和 b 的众数分别是 [0.5] 和[-2.0]分别取最后 1 个众数 iloc[-1]即得到想要的结果。

    八、值变化分组

    值变化分组,指在有序的数据中,发生数据变化时就分出一个新组。举例如下:

    source: https://stackoverflow.com/questions/41620920/groupby-conditional-sum-of-adjacent-rows-pandas

    数据片段如下:

          duration  location  user

    0        10    house    A

    1         5    house    A

    2         5      gym    A

    3         4      gym    B

    4        10     shop    B

    5         4      gym    B

    6         6      gym    B

    按照 user 分组后,各组当 location 连续相同时对 duration 进行求和,location 变化时则重新求和。理想结果如下:

       duration  location   user

            15    house    A

             5      gym    A

             4      gym    B

            10     shop    B

            10      gym    B

    问题分析:location 列的顺序很重要,连续相同时可以视为一组,当变化时则重新分一组,如 user=B 时,第 4 行 (索引为 3) 的 location 为 [gym,shop,gym,gym], 不可以把其中的 3 个 gym 分到 1 组,而应该把第一个 gym 单独作为 1 组,shop 与 gym 不同,值发生了变化,把 shop 分到下一组,后面两个 gym 没有值变化,可以分到同一组,分组的结果为[[gym],[shop],[gym,gym]],所以这里不可以使用 df.groupby(['user','location']).duration.sum() 来计算结果,而是要想办法生成一个衍生列作为分组依据。

    代码如下:

    import pandas as pd

    df = pd.DataFrame({'user' : ['A', 'A', 'A', 'B', 'B',   'B','B'],

                    'location' : ['house','house','gym','gym','shop','gym','gym'],

                    'duration':[10,5,5,4,10,4,6]})

    derive = (df.location !=   df.location.shift()).cumsum()

    res = df.groupby(['user', 'location', derive],   as_index=False, sort=False)['duration'].sum()

    print(res)

     

    生成数据

     

     

     

    创造衍生列

    按照 user,location 和衍生列分组,对 duraton 求和

     

    讨论:衍生列 derive 是当 location 与前者不同时进行累加,得到 [1 1 2 2 3 4 4]。然后按照 user,location 和该数列分组,再对 duration 求和。

    九、条件变化分组

    条件变化分组:指在有序的数据中,当满足某一条件时重新分组。举例如下:

    source: https://stackoverflow.com/questions/62461647/choose-random-rows-in-pandas-datafram

    数据片段如下:

    ID          code

    333_c_132   x

    333_c_132   n06

    333_c_132   n36

    333_c_132   n60

    333_c_132   n72

    333_c_132   n84

    333_c_132   n96

    333_c_132   n108

    333_c_132   n120

    999_c_133   x

    999_c_133   n06

    999_c_133   n12

    999_c_133   n24

    998_c_134   x

    998_c_134   n06

    998_c_134   n12

    998_c_134   n18

    998_c_134   n36

    997_c_135   x

    997_c_135   n06

    997_c_135   n12

    997_c_135   n24

    997_c_135   n36

    996_c_136   x

    996_c_136   n06

    996_c_136   n12

    996_c_136   n18

    996_c_136   n24

    996_c_136   n36

    995_c_137   x

    希望从 code 列的每两个 x 中间随机取一行

    理想结果形式如下:

    333_c_132   n06

    999_c_133   n12

    998_c_134   n18

    997_c_135   n36

    996_c_136   n18

    问题分析:取两个 x 之间的随机一条记录,可以转化成每当 code 等于 x 时开始新的一组,不等于 x 时分组不变,然后从该组中随机取一行。因此这里还是需要生成衍生列,把它作为键分组才能完成任务。

    代码如下:

    import pandas as pd

    df = pd.read_csv("data.txt")

    derive = df.code.eq('x').cumsum()

    res=df[df.code.ne('x')].groupby(derive).apply(lambda   x : x.sample(1))

    res=res.reset_index(level=0, drop=True)

    print(res) 

     

     

    生成衍生列

    根据衍生列分组,使用 apply 结合 lambda 的方式随机抽样

    重置索引

     

    讨论:code.eq(x) 表示 code 等于 x 时为 True,其余为 False,cumsum()表示对其累加,生成的衍生列为 [1 1 1 1 1 1 1 1 1 2 2…],过滤掉等于 x 的列再根据该列进行分组并抽样即可。

    思考:

    前面所有的例子都是将原集合根据某个条件,将数据划分成若干个子集,且满足以下两点:

    1)没有空子集

    2)原集合的任何成员都属于且只属于某一个子集

    我们称这种划分方式为完全划分。那么有没有不完全划分呢?

    来看下面这几个例子

    十、对位分组

    对位分组,指先罗列出一个基准集合,然后将待分组集合成员的某个属性(字段或表达式)与基准集合成员比较,相同者则分到一个子集中,最后拆分出来的子集数量和基准集合成员数是相同的。对位分组有三个特点:

    1)可能出现空子集(比如基准集合的某些成员在待分组集合中并不存在);

    2)可能有待分组集合成员未被分到任何子集(比如有些不重要的成员未被列入基准集合);

    3)每个成员最多只出现在一个子集中。

    (一)出现空子集

    公司统计各部门男女人数,如果某个部门没有男员工或者没有女员工,则将该部门的男员工人数或女员工人数填为 0。

    问题分析:如果直接按照部门和性别分组,则如果某个部门没有女员工或没有男员工时,该部门将只被分成 1 组,就会丢失掉缺少的性别的统计信息,因此不可以直接 groupby([‘DEPT’,’GENDER’])。很容易想到的方案就是,先按部门分组,罗列出 [男, 女] 的基准集合,使用左连接 (left join) 的方式与各组连接,再对连接后的结果按照性别分组,最后汇总结果,这样就能保证分组的结果总会有 [男, 女] 了。

    Python 代码

    import pandas as pd

    def align_group(g,l,by):

        d = pd.DataFrame(l,columns=[by])

        m =   pd.merge(d,g,on=by,how='left')

    return m.groupby(by,sort=False)

    employee = pd.read_csv("Employees.csv")

    l = ['M','F']

    res = employee.groupby('DEPT').apply(lambda   x:align_group(x, l, 'GENDER').apply(lambda s:s.EID.count()))

    print(res)

     

    函数,对位分组

    生成对照的 dataframe

    利用 merge 完成对位运算

    分组

     

    指定序列

    按 DEPT 分组,再对各组使用函数对位分组,对 EID 进行计数

     

    讨论:

    自定义函数 align_group,使用 merge()函数完成罗列集合与待分组集合的 left join,再按 merge 的列进行分组。按部门分组后,使用 apply() 结合 lambda 表达式的方式对每组使用自定义函数对位分组,最后对 EID 列计数得到最终结果。(注意:这里不可以对 GENDER 计数,因为 merge 时 GENDER 的成员都被保留了,如果有空子集时,对它计数结果将是 1,而其他列(比如 EID), 在 left join 时会是空值,所以对 EID 计数结果是 0)。

    (二)有待分组集合成员未被分到任何子集

    按指定的部门 ['Administration', 'HR', 'Marketing', 'Sales'] 分组,只查询这几个部门的人数且部门先后顺序保持不变。

    问题分析:与出现空子集的情况类似,此时也可以使用 left join 的方式,将不在预先罗列的集合成员排除掉,只保留罗列集合中的成员。

    代码如下:

    import pandas as pd

    def align_group(g,l,by):

        d =   pd.DataFrame(l,columns=[by])

        m =   pd.merge(d,g,on=by,how='left')

        return   m.groupby(by,sort=False)

    employee = pd.read_csv("Employees.csv")

    sub_dept = ['Administration', 'HR', 'Marketing',   'Sales']

    res =   align_group(employee,sub_dept,'DEPT').apply(lambda x:x.EID.count())

    print(res)

     

    函数,对位分组

     

     

     

     

    指定顺序的部门子集

    使用对位分组函数分组,再对 EID 计数

    讨论:Pandas 不直接支持对位分组的功能,因此完成起来成本就会比较高,而且使用 merge 函数也会导致运行效率低下。

    十一、枚举分组

    枚举分组:事先指定一组条件,将待分组集合的成员作为参数计算这批条件,条件成立者被划分到与该条件对应的一个子集中,结果集的子集和事先指定的条件一一对应。枚举分组的特点:允许集合成员重复出现在不同的子集中。

    举例如下:

    按在公司的工龄将员工分组统计每组的男女员工人数(分组条件重合时,列出所有满足条件的员工,分组的条件是 [工龄 <5 年,5 年 <= 工龄 <10 年,工龄 >=10 年,工龄 >=15 年])

    问题分析:工龄 >=10 年和工龄 >=15 年两个条件有重复的区间,即工龄大于 15 年的员工,其工龄也一定大于 10 年,这时如果使用构造衍生列的方式来完成,将无法使同一个成员重复出现在两个分组中,因此需要考虑每个条件都分一次组,然后找出满足条件的组,最后再汇总。

    import pandas as pd

    import datetime

    def eval_g(dd:dict,ss:str):

        return   eval(ss,dd)   

    emp_file = 'E:\\txt\\employee.txt'

    emp_info = pd.read_csv(emp_file,sep='\t')

    employed_list = ['Within five years','Five to ten   years','More than ten years','Over fifteen years']

    employed_str_list =   ["(s<5)","(s>=5) &   (s<10)","(s>=10)","(s>=15)"]

    today = datetime.datetime.today().year

    arr = pd.to_datetime(emp_info['HIREDATE'])

    employed = today-arr.dt.year

    emp_info['EMPLOYED']=employed

    dd = {'s':emp_info['EMPLOYED']}

    group_cond = []

    for n in range(len(employed_str_list)):

        emp_g =   emp_info.groupby(eval_g(dd,employed_str_list[n]))

        emp_g_index   = [index for index in emp_g.size().index]

        if True not   in emp_g_index:

              female_emp=0

              male_emp=0

        else:

            group =   emp_g.get_group(True)

            sum_emp   = len(group)

              female_emp = len(group[group['GENDER']=='F'])

              male_emp = sum_emp-female_emp

          group_cond.append([employed_list[n],male_emp,female_emp])

    group_df =   pd.DataFrame(group_cond,columns=['EMPLOYED','MALE','FEMALE'])

    print(group_df)

     

     

    函数,字符串转表达式

     

     

     

     

     

    分组条件

     

     

     

    计算入职时间

     

     

     

    循环分组条件

    按分组条件分组

    分组索引

    如果没有满足条件的成员

    男女员工数为 0

     

    满足条件

    获取分组

    计算男女员工人数

     

     

     

     

    汇总各个分组条件的计算结果

    讨论:EMPLOYED 是根据入职时间 HIREDATE 新增加的一列,表示工龄。自定义函数 eval_g(),是把分组的条件转换成表达式,比如当条件是 s<5 时,eval_g(dd,ss)的表达式就是 emp_info['EMPLOYED']<5,根据这个衍生列来对数据分组。对分组条件进行循环,按该衍生列分成两组,get_group(True) 表示取满足条件的组,最后把所有满足条件的结果使用 concat() 函数汇总。

    总结

    Python 在进行分组处理时,多数情况可以比较优雅的处理,但在处理有序分组时,如值变化分组、条件变化分组时则需要自己想办法生成满足分组条件的衍生列,略显麻烦。对位分组和枚举分组的两种情况更是糟糕,需要自己想办法去绕,要么使用 merge 运算,要么多次分组,使分组的成本变得很高,这样看来,Pandas 的分组运算还有其局限性。

    对于分组运算,相比之下,esProc SPL 处理的更完善。 esProc 是专业的数据计算引擎,SPL 提供了丰富的分组运算,可以方便的完成上述任务,代码风格的一致程度也更好。

    两个分组运算函数 groups()和 group(),分别实现分组聚合和分组子集,可以比 Python 更简洁地解决前面六个常规分组问题:

    问题SPL代码简单说明
    A.groups(DEPT;count(~):NUM)A是数据表,按 DEPT 分组,count() 计数
    A.groups(DEPT,GENDER;avg(SALARY):AVG_SALARY)按 DEPT,GENDER 分组,avg() 平均

    A.groups((year(BIRTHDAY)-

    1900)\10:years;avg(SALARY):AVG_SALARY)

    (year(BIRTHDAY)-1900)\10命名为 years,并分组

    A.groups(DEPT;count(EID):NUM,avg(SALARY):AVG_SAL

    ARY)

    多列单聚合

    A.groups(DEPT;count(SALARY):NUM,avg(SALARY):AVG_

    SALARY)

    单列多聚合

    A.groups(DEPT;count(SALARY):NUM,avg(SALARY):AVG_

    SALARY,max(age(BIRTHDAY)):MAX_AVG)

    多列多聚合

    B=A.derive(AVG_SALARY)

    >B.group(DEPT).((a=~.avg(SALARY),~.run(AVG_SALARY

    =a)))

    增加新列

    修改为分组的聚合值

    A.group(DEPT).conj(~.sort(HIREDATE))分组排序

    A.group(DEPT;(ma=~.minp(BIRTHDAY),mi=~.maxp(BIR

    THDAY),ma.SALARY-mi.SALARY):SALARY_DIF)

    分组子集运算

    对于这六个简单分组计算,Python 的分组计算方法同样方便。但涉及了很多其他函数,如 agg,transform,apply,lambda 表达式甚至是自定义函数等等,代码风格差别比较大。而 SPL 则基本保持了 groups(x;y) 或者是 group(x).(y) 这样统一的代码风格。

    对于问题七、八、九,Python 就略显烦琐,需想办法生成衍生列,而 SPL 本身基于有序集合设计,提供了有序分组的选项,仍可以优雅的保持简单运算时的代码风格。

    问题SPL代码简单说明
    A.groups@n((#-1)\3;y)每三行分 1 组,y 是聚合运算表达式
    A.groups@o(user,location;y)@o选项:值变化分组
    A.group@i(code==”x”).(y)@i选项:条件变化分组

    根据分组后直接聚合还是分组后针对子集计算,灵活选择 groups 和 group 函数。

    最后两个问题,对位分组和枚举分组,确实有点难为 Python 了,不过不管是使用 merge 函数绕还是多次分组,总算是完成了任务。而 SPL 提供了专门的对位分组函数 align()和枚举分组函数 enum(),可以继续优雅。

    问题SPL分组处理简单说明

    s=[“M”,”F”]

    A.group(DEPT).(~.align@a(s,GENDER).(y))

    可能出现空子集

    s=[“Administration”,   “HR”, “Marketing”, “Sales”]

    A.align@a(s,DEPT).(y)

    有待分组集合成员未被分到任何子集
    十一

    c=[“?<5”,”?>=5   && ?<10”,”?>=10”,”?>=15”]

    A.enum(c, EMPLOYED)

    有成员被分到不同子集

    需要提到的是,Python 还有一个致命缺点——大数据(无法一次性读入内存)分组,它涉及到外存读写和 hash 分组,对于非专业的程序员来说,使用 Python 完成这个任务几乎是不可能的。有兴趣可以参考以下文章:

    Python 如何处理大文件

    这里介绍了 Python 处理大数据存在的问题(包括大数据分组),也简单介绍了 esProc SPL 中的游标系统,其中 group 和 groupx() 函数仍然可以优雅的完成大数据分组任务。

    更多相关内容
  • 依靠gridcontrol强大的属性功能实现分组,并依据分组总计,平均统计等。本实例根据班级分组计算班级总分与平均分。
  • RecyclerView 分组 item实现不同布局
  • 新编密码学——分组密码

    千次阅读 2021-12-16 15:56:34
    一、分组密码的设计思想 1.1、分组密码的定义 分组密码是指对固定长度的一组明文进行加密的一种加密算法,这一固定长度称为分组长度。 1.2、分组密码的作用 消息加密 伪造伪随机数生成器(用于产生性能良好的随机数...

    一、分组密码的设计思想

    1.1、分组密码的定义

    分组密码是指对固定长度的一组明文进行加密的一种加密算法,这一固定长度称为分组长度。

    1.2、分组密码的作用

    • 消息加密
    • 伪造伪随机数生成器(用于产生性能良好的随机数)
    • 消息认证/数据完整性保护(通过用于构造消息认证码(MAC)来实现
    • 构造流密码
    • 构成其他密码协议的基本模块(如秘钥管理协议,身份认证协议)

    1.3、分组密码的五要素

    明文、密文、加密算法、解密算法、秘钥

    在这里插入图片描述

    1.4、分组密码的要求

    • 对于每一个k,Ek : {0,1}^n --> {0,1}^n 是一一映射的
    • 加密函数易记算
    • 从方程c = E(m,k) 或 m = D(c,k)中解出k是一个困难问题

    1.5、分组密码的设计原则

    1.5.1、安全性设计原则

    • 混淆原则(数据关系变复杂):明文、密文、密钥之间的依赖关系相当复杂,防止密码分享者利用统计分析方法进行破译攻击
    • 扩散原则(微小输入改变导致输出多位变化):
      • 密钥的每一个比特影响密文的每一个比特,以防止对密钥进行逐段破译
      • 明文的每一个比特影响密文的每一个比特,以便最充分地隐蔽明文的统计特性。

    1.5.2、迭代分组密码基本设计原则

    • 分组长度n要足够大:防止明文穷举攻击
    • 密钥长度l要足够大:尽可能不存在弱密钥和防止密钥穷举攻击
    • 加解密算法要足够复杂:实现混淆与扩散
    • 加解密运算简单:易于软硬件高速实现
    • 数据扩展:采用随机化加密等技术时,可引入。

    1.5.3、实现性设计原则

    • 软件实现的设计原则
      • 将分组n划分成若干字块。子块的数据长度能自然适应软件编程,如8,16,32比特
      • 选择简单的运算,如模加、移位、异或、乘等。
    • 硬件实现的设计原则
      • 硬件实现时,应该保证加密和解密的相似性,即 加密和解密可以便用同样的器件来实现

    1.6、分组密码设计思想

    • 直接构造密码学性质强的复杂函数(不常用)
    • 迭代型分组密码:构造密码学性质相对较弱的 简单函数,并且基于简单函数进行多次迭代(常用)

    1.6.1、分组迭代密码

    • 每一迭代称为一轮,相应的函数G称作轮函数
    • 每一轮输入都是前一轮输出的函数
    • 其中Ki是第i轮的字密钥,由秘密密钥K作为种子密钥通过密钥扩展算法生成。

    在这里插入图片描述

    1.6.2、分组密码的轮函数

    在这里插入图片描述

    1.6.3、轮函数G—S盒与P盒实现

    S盒:非线性部件,规模较小,局部混淆

    • 非线性关系:实现混淆
    • 规模:较小
      • DES(6进4出)
      • AES(8进8出)
      • SM4(8进8出)
    • 局部:各个S盒之间没有关联,混淆是在各个S盒之内进行的,是局部的。

    P盒:线性部件,整体扩散。

    1.6.4、迭代型密码的基本结构

    • Feistel结构(典型代表DES,SM4)
      • 加解密算法相同,只是轮密钥逆序使用
      • 结构保证可逆,但S盒不需要可逆
    • SPN结构(AES)
      • 加解密结构相似
      • S盒通常需要可逆
      • 扩散速度较Feistel快,因而轮数比Feistel少。

    二、DES(重点)

    DES是一个包含16个阶段的“替换—置换”的分组密码,以56位为分组对数据进行加密

    2.1、基本参数(重点)

    • 分组长度:64比特
    • 密钥长度:64比特。实际上用户只提供56位(通常是转换成ASCII位的7个字母单词作为密钥),其他的8位由算法提供,分别放在8,16,24,32,40,48,56,64)位上。添加的位是有选择的,使得每个8位的块都含有奇数个奇偶检验位(1的个数是奇数)。
    • 轮数:16
    • 结构:Feistel结构
    • 基本思想:利用乘积密码(顺序的执行两个或多个基 本密码系统,使得最后结 果的密码强度高每个基本 密码系统产生的结果)实现混淆和扩散。

    2.2、加密流程

    在这里插入图片描述

    2.3、加密过程详细说明

    2.3.1、初始置换

    简称IP置换,在第一轮运算之前执行。数组打乱

    2.3.2、密钥置换

    DES加密算法输入的初始密钥大小为8个字节,每个字节的第8位作为检验位,所以初始密钥不考虑每个字节的第8位。实际上是对56位先进行密钥置换(顺序打乱),再通过压缩置换选出48位字密钥。

    2.3.3、扩展变换(E—盒)

    也被称为E-盒,将64位输入序列的右半部分Ri扩展到48位。

    2.3.4、S-盒变换(重点)

    经过密钥置换得到的48位轮密钥和拓展变换得到的分组进行异或运算,得到48位结果序列,对这个序列进行替换运算。替换由8个替换盒(S-盒)。每个S-盒对应6位的输入序列,得到相应的4位输出序列。每个S盒大小为64.

    输入输出序列转换:

    输入b1,b2, b3, b4, b5, b6 ; b1b6表示行。b2,b3b4b5表示列

    0123456789101112131415
    01009146315511312711428
    11370934610285141211151
    21364981530111212510147
    31101306987415143115212

    例如输入101011 行:11 = 3,列0101 = 5 输出9 = 1001

    2.3.5、P-盒替换

    经S-盒替换运算得到的32位输出再进行置换,结果与本轮输入的64位分组的左半部分进行异或,得到本轮的右半部分;本轮加密输入序列的右半部分直接输出,作为本轮加密输出的左半部分。

    P-盒设计特点:

    • P盒的各输入组的4个比特都分配到不同的输出组之中
    • P盒的各输入组的4个比特都 分配到不同的输出组之中
    • P盒的各输入组的4个比特都 分配到不同的输出组之中

    2.3.6、逆初始置换

    初始置换的逆过程。

    2.3.7、DES解密

    解密过程是加密的逆过程。

    2.4、DES安全性分析

    2.4.1、互补性

    在这里插入图片描述

    2.4.2、弱密钥

    密钥k满足

    DESk(m) = DESk ^ -1 (m)

    四种弱密钥:

    • k = 01 01 01 01 01 01 01 01
    • k = 1F 1F 1F 1F 1F 1F 1F 1F
    • k = E0 E0 E0 E0 E0 E0 E0 E0
    • k = FE FE FE FE FE FE FE FE

    2.4.3、半弱密钥

    密钥k和k`满足:

    DESk(m) = DESk ^ -1 (m)。

    2.4.4、双重DES

    在这里插入图片描述

    2.4.5、三重DES

    在这里插入图片描述

    三、AES(重点)

    3.1、数学基础(重点)

    AES中的运算是按字节或4字节的字定义的,并把1字节看成系数在GF(2)上的次数小于8的多项式,即是GF(2^8)中的一个元素;把一个4字节的字看成系数在GF(2 ^8)上且次数小于4的多项式。

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    3.2、基本参数(重点)

    • 分组长度:128

    • 密钥长度及轮次

      AES-128AES-192AES-256
      密钥长度128192256
      轮数101214

    3.3、加密过程

    在这里插入图片描述

    四、IDEA,SM4,RC5

    4.1、IDEA

    4.1.1、基本参数

    • 密钥长度:128
    • 分组长度:64
    • 轮数:8
    • 结构:LAI-MASSEY

    4.1.2、加密流程

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    4.2、SM4

    4.2.1、基本参数

    • 密钥长度:128
    • 分组长度:128
    • 轮数:32
    • 结构:非平衡型FEISTEL

    4.3、RC5

    特点:

    • 简单、加解密速度快,因为只用基本计算机运算 (模加、异或、移位等)

    • 灵活:轮数可变,密钥位数可变

      参数定义取值范围
      wword (字长) 一次加密2个word16, 32, 64
      r加密轮数0~255
      b密钥大小对应的字节个数0~255

    五、分组密码的工作模式(记住五种模式名称)

    5.1、电码本模式(ECB)

    在这里插入图片描述

    5.2、密文分组链接模式(CBC)

    在这里插入图片描述

    在这里插入图片描述

    5.3、密文反馈模式(CFB)

    在这里插入图片描述

    5.4、输出反馈模式(OFB)

    在这里插入图片描述

    在这里插入图片描述

    5.5、计数器模式(CTR)

    在这里插入图片描述

    5.6、比较

    在这里插入图片描述

    展开全文
  • jdk8(java8),list 集合 分组,stream 流处理,groupingBy 使用 两种分组方式的代码 参考 Stream流使用groupingBy+mapping实现对分组之后的对象集合转化为对象的某个属性的集合 测试代码 import java.util....

    jdk8(java8),list 集合 分组,stream 流处理,groupingBy 使用
    为了实现 分组后排序,增加 sorted 使用,先排序在分组,就能保证 分组后排序的效果

    两种分组方式的代码

    参考
    Stream流使用groupingBy+mapping实现对分组之后的对象集合转化为对象的某个属性的集合

    测试代码

    import java.util.ArrayList;
    import java.util.List;
    import java.util.Map;
    import java.util.Set;
    import java.util.stream.Collectors;
    
    /**
     * Stream流使用groupingBy+mapping实现对分组之后的对象集合转化为对象的某个属性的集合
     *
     * @version v1.0
     * @date 2021/8/16
     */
    public class GroupListTest {
        public static void main(String[] args) {
            List<P> list = new ArrayList<>();
            list.add(new P().name("你").type("女"));
            list.add(new P().name("我").type("男"));
            list.add(new P().name("他").type("男"));
            list.add(new P().name("她").type("女"));
            System.out.println("源>:"+list);
            Map<String, List<P>> groupMap1 = list.stream()
                    .collect(Collectors.groupingBy(P::getType));
            System.out.println("简单分组>:"+groupMap1);
            Map<String, Set<String>> groupMap2 = list.stream()
                    .collect(Collectors.groupingBy(P::getType, Collectors.mapping(P::getName, Collectors.toSet())));
            System.out.println("指定字段分组>:"+groupMap2);
        }
        public static class P{
            private String name,type;
    
            public String getName() { return name; }
            public void setName(String name) { this.name = name; }
            public P name(String name) { this.name = name; return this; }
            public String getType() { return type; }
            public void setType(String type) { this.type = type; }
            public P type(String type) { this.type = type; return this; }
    
            @Override
            public String toString() {
                return "P{ name='" + name + "', type='" + type + "'}";
            }
        }
    }
    

    输出

    源>:[P{ name='你', type='女'}, P{ name='我', type='男'}, P{ name='他', type='男'}, P{ name='她', type='女'}]
    
    简单分组>:{女=[P{ name='你', type='女'}, P{ name='她', type='女'}], 男=[P{ name='我', type='男'}, P{ name='他', type='男'}]}
    
    指定字段分组>:{女=[你, 她], 男=[我, 他]}
    

    截图
    在这里插入图片描述

    增加排序后分组

    import java.util.*;
    import java.util.stream.Collectors;
    
    /**
     * Stream流使用groupingBy+mapping实现对分组之后的对象集合转化为对象的某个属性的集合
     * @author zy
     * @version v1.0
     * @date 2021/8/16
     */
    public class GroupListTest {
        public static void main(String[] args) {
            List<P> list = new ArrayList<>();
            list.add(new P().no(0).age(21).name("你").type("女"));
            list.add(new P().no(2).age(31).name("我").type("男"));
            list.add(new P().no(1).age(22).name("他").type("男"));
            list.add(new P().no(null).age(30).name("她").type("女"));
            list.add(new P().no(3).age(33).name("她1").type("女"));
            System.out.println("源>:"+list);
            Map<String, List<P>> groupMap1 = list.stream()
                    .collect(Collectors.groupingBy(P::getType));
            System.out.println("简单分组>:"+groupMap1);
            Map<String, Set<String>> groupMap2 = list.stream()
                    .collect(Collectors.groupingBy(P::getType, Collectors.mapping(P::getName, Collectors.toSet())));
            System.out.println("指定字段分组>:"+groupMap2);
            Map<String, List<P>> groupMap3 = list.stream()
                    .sorted(Comparator.comparing(P::getNo,Comparator.nullsLast(Integer::compareTo)))
                    .collect(Collectors.groupingBy(P::getType, Collectors.toList()));
            System.out.println("排序后指定字段分组>:"+groupMap3);
        }
        public static class P{
            private String name,type;
            private Integer no,age;
    
            public String getName() { return name; }
            public void setName(String name) { this.name = name; }
            public P name(String name) { this.name = name; return this; }
            public String getType() { return type; }
            public void setType(String type) { this.type = type; }
            public P type(String type) { this.type = type; return this; }
    
            public void setAge(Integer age) { this.age = age; }
            public Integer getAge() { return age; }
            public P age(Integer age) { this.age = age; return this; }
            public void setNo(Integer no) { this.no = no; }
            public Integer getNo() { return no; }
            public P no(Integer no) { this.no = no; return this; }
    
            @Override
            public String toString() {
                return "P{ no='" + no + "', name='" + name + "', age=" + age + ", type='" + type + "'}";
            }
        }
    }
    

    输出

    源>:[P{ no='0', name='你', age=21, type='女'}, P{ no='2', name='我', age=31, type='男'}, P{ no='1', name='他', age=22, type='男'}, P{ no='null', name='她', age=30, type='女'}, P{ no='3', name='她1', age=33, type='女'}]
    简单分组>:{女=[P{ no='0', name='你', age=21, type='女'}, P{ no='null', name='她', age=30, type='女'}, P{ no='3', name='她1', age=33, type='女'}], 男=[P{ no='2', name='我', age=31, type='男'}, P{ no='1', name='他', age=22, type='男'}]}
    指定字段分组>:{女=[你, 她1, 她], 男=[我, 他]}
    排序后指定字段分组>:{女=[P{ no='0', name='你', age=21, type='女'}, P{ no='3', name='她1', age=33, type='女'}, P{ no='null', name='她', age=30, type='女'}], 男=[P{ no='1', name='他', age=22, type='男'}, P{ no='2', name='我', age=31, type='男'}]}
    
    展开全文
  • 分组交换

    千次阅读 多人点赞 2020-10-31 12:23:22
    什么是分组交换? 电路交换 电路交换最早用于电话网络,两台电话之间用专有电线连接,一台电话只能和连在电线上的另一台电话通信。 但实际上,为了能和其他人通信,专有电线会连接到交换中心。在交换中心,操作员会...

    1、什么是分组交换?

    电路交换

    电路交换最早用于电话网络,两台电话之间用专有电线连接,一台电话只能和连在电线上的另一台电话通信。
    在这里插入图片描述
    但实际上,为了能和其他人通信,专有电线会连接到交换中心。在交换中心,操作员会手工将输入的专有电线连接到待连接的电话的专有电线上。这里的重点是电线从通话开始到结束都是专有的。
    在这里插入图片描述
    今天使用的电路交换网都是自动切换的。
    在这里插入图片描述
    容易想到,打一个电话要经过三个阶段。首先,我们拿起听筒并拨号,拨打的号码说明了我们要连接的地方。这样就形成了从一端到另一端到专有电路,这样一来,专有电路将遍历所有电路,系统告知了每段电路将输入线连接到输出线。每个电路交换机都要维持状态以将输入电路映射到正确的输出电路上。
    第二阶段,在大多数像电话一样的数字电话系统中,我们的声音在第一个交换机处被采样和数字化。然后,通过专有电路将其作为64Kb信道的语音发送。因此,我们的电话通信在整个通信过程中都有专用的电路或信道,电路不与其他人共享。
    最后,当我们挂断电话后,电路必须被移除,并且沿着路径上的交换机的状态也必须被移除。
    在这里插入图片描述
    实际上,在交换机间存在中继线,它们非常非常快,即很高的比特率。即使是最慢的也有2.5Gb/s,最快的有40甚至100Gb/s。如图所示,这个干线看起来很大,实际上它比头发还细,所有的电话呼叫都使用这条干线。但每个电话呼叫都有专用的64Kb/s的电路,不与他人共享。
    在这里插入图片描述

    总结

    • 每个电话呼叫都有自己的私有、有保证的、端到端的独立数据传输速率
    • 一次电话呼叫有三个阶段:
      1. 建立端到端的电路(拨号)
      2. 通话
      3. 关闭电路(拆卸)
    • 最初,电路是端到端的物理电线
    • 如今,电路就像一根虚拟的私人电线,实际使用的电线会与其他人共享,但在电线内部有自己的专用电路

    问题

    1. 效率低下。计算机通信往往是非常突发的。例如,通过ssh连接键入,或查看一系列网页。如果每个通信都有一个专用电路,它的使用效率将非常低。
    2. 不同的速率。计算机以许多不同的速率通信。例如,一个6Mb/s的流媒体视频服务器,或者我以每秒1个字符的速度打字。固定速率的电路用处不大。
    3. 状态管理。电路交换需要维护每一个通信的必须管理的状态。

    分组交换

    在这里插入图片描述
    在分组交换中没有专用的电路来传输数据。相反,我们可以通过添加一个标头,在数据准备好的任何时候发送一块数据,它就是分组或数据包(packet)。标头里包含了数据包的目标地址。
    在这里插入图片描述
    分组交换网络由终端、链路和分组交换机组成。
    在这里插入图片描述
    当我们发送数据包时,它从源被逐跳地路由到目的地。
    在这里插入图片描述
    沿途的每次分组交换都要在交换机的转发表中查找下一跳的地址。
    在互联网中,存在许多不同类型的分组交换机。其中一些称为路由器,因为它们处理的是因特网地址,并且其中的还包含我们办公桌上的小型路由器或大型配线间的大型路由器。还有一些称为以太网交换机。
    在这里插入图片描述
    分组交换机还有缓冲区。
    在这里插入图片描述
    如果两个包同时到达,交换机必须安置其中一个,因为无法同时发送它们,它只能一次发送一个。
    在这里插入图片描述
    缓冲区保留数据包:

    • 当两个或以上的数据包同时到达
    • 在拥塞期间

    总结

    在这里插入图片描述

    • 数据包通过在路由器本地的转发表中查找地址来独立路由
    • 所有数据包共享链路的全部容量
    • 路由器不维护每个通信的状态

    为什么互联网使用分组交换

    有效利用昂贵的链路

    • 链路被认为是昂贵和稀缺的
    • 分组交换允许很多突发流有效地共享同一链路
    • “电路交换很少用于数据网,…因为网络的使用效率很低” —— Bertsekas/Gallager

    对链路和路由器的故障具有弹性

    • “为了高可靠性,…互联网将成为数据报子网,因此,如果某些线路或路由器被破坏,则信息很容易被重新路由。“ —— Tanenbaum

    互联网最初被设计为现有网络的互连。那时,几乎所有广泛使用的通信网络使用的是分组交换,所以互联网也需要设计为分组交换网。

    2、端到端时延

    传播时延

    在这里插入图片描述

    包装时延(传输时延)

    在这里插入图片描述
    注意:示例2中,1kbit为1024bit,1kb/s为1000bit/s

    端到端时延

    在这里插入图片描述

    在这里插入图片描述
    当来自不同链路上的数据包同时进入一个交换机并都想从同一条链路出去时,某些数据包必须在路由器的队列中等待。队列也被称为数据包缓冲区。通常,队列是先进先服务的。数据包缓冲区可以防止数据包被丢弃,每个交换机都有自己的数据包缓冲区,它们是分组交换的基础。如果没有数据包缓冲区,每当两个数据包同时出现时,我们都不得不丢弃其中一个。
    但是数据包缓冲区改变了端到端时延的表达式。如果我们的数据包到了,队列里还有一些数据包,它将延迟转发到下一条链路的时间,因为它不得不等待它前面的数据包先离开。
    在这里插入图片描述
    这里要注意的是,除了排队时延,其它时延都是确定的。
    下面是从斯坦福大学ping普林斯顿大学和清华大学的累计分布关于RTT的函数图。
    在这里插入图片描述
    斯坦福大学距离普林斯顿大学约4000公里,距离清华大学约10000公里,因此对于前者,传播时延更低。同时可以注意到图中圈住的部分,到普林斯顿的RTT区间范围比到清华大学要小,前者大约为100-200,后者约为320-500。这是因为随着通信距离变长,途中的排队时延也增加的缘故。排队时延可能占了整个端到端时延的一半。

    总结

    端到端时延由三个主要部分组成:

    • 沿链路的传播时延(固定)
    • 将数据包放到链路上的包装时延(固定)
    • 路由器数据包缓冲区中的排队时延(不定)

    3、播放缓冲区

    问题描述

    有一些应用程序必须关心排队时延,特别是例如流视频和语音等实时应用程序。基本上,因为这些应用程序无法确切地知道数据包何时出现,所以它们不能确定能否及时提供语音或视频样本给用户。因此,它们在所谓的播放缓冲区中积累了很多数据包。通过预先积累数据包,可以防止某些数据包没有及时到达而影响体验的情况。
    在这里插入图片描述
    在设计播放缓冲区的时候,必须考虑缓冲区能走多远。
    在这里插入图片描述
    假设我们使用下图中右边的笔记本观看来自左边服务器上的视频。为了方便,服务器的传输速率(单位时间内被送到链路上的比特数)为1Mb/s,路径上只有3个路由器。下面的函数图中,自变量为时间,因变量为累计的字节数。左边的函数为服务器随时间发送的字节数,因为传输速率恒定,所以显然是线性函数。右边的曲线为笔记本累计接收到的字节数,由于排队时延的不定性,因此函数呈无规则曲线状。
    两曲线间的水平距离表示每个特定的字节从它被发送到它被接收的总时延。由于排队时延的不定性,因此总时延也是不定的。两曲线间的竖直距离表示还在传输路径上的字节数。
    从图中我们还可以获取很多有用的信息。首先,端到端的总时延不能小于分组时延和传播时延,因此两曲线间的水平距离有一个下限。然后,它还有一个上限。因为每个路由器的缓冲区都是有限大小的,所以可以假设一个数据包经过每一个路由器时都排了最长的队,将这些最大值添加到总时延中就得到了上限。但是上限没什么用,因为它通常非常非常大。最后,对于右边的接收曲线,它每一点的斜率都为正且不应超过最后一个路由器到笔记本之间的链路的数据率。
    在这里插入图片描述
    最右边的直线表示随时间播放的字节数。中间的黄线表示的是一个特定字节从开始发送到开始播放之间的时延。
    在这里插入图片描述
    下图的水平黄线表示的是一个特定字节已缓冲的时间。
    在这里插入图片描述
    同理,竖直黄线表示的是当前缓冲区中的使用量。从图中可以看出,一开始缓冲区里的字节一直在积累,然后随着视频开始播放,积累的字节数开始减少,缓冲区甚至差点空了,幸运的是缓冲区里的字节数又开始增多了,最终一切顺利。
    在这里插入图片描述
    粗略地看一下客户端的内部,playback point指向的是已到达的位置,它就是视频播放器中进度条上的点。从播放缓冲区中取出字节后,将它们交给视频解码器,最终在屏幕上播放。
    在这里插入图片描述
    下面看一个糟糕的情况。如果我们在播放第一个字节前没有等待足够长的时间,就会导致缓冲区生产的速度低于消费的速度,缓冲区变空,意味着我们没有要解码并在屏幕上播放的字节。
    在这里插入图片描述
    在这里插入图片描述
    客户端要怎么做呢?它必须让缓冲区更大一些,并重新缓存。为了做到这一点,屏幕会被“冻结”,等待一些字节积累,然后它才能继续播放。
    在这里插入图片描述

    总结

    • 在分组交换中,端到端的延迟是可变的
    • 我们使用播放缓冲区来吸收这种变化
    • 我们可以把播放缓冲区设得很大,但是这也会导致我们等待缓冲区被填充的时间变长,也就是我们不得不延迟我们开始观看视频的时间
    • 因此,应用程序会估计延迟,设置延迟缓冲区,并在延迟改变时调整缓冲区大小。

    4、队列模型

    简单的确定性队列模型

    在这里插入图片描述
    A(t):到时间t为止累计到达的字节数
    Q(t):t时刻队列中的字节数
    D(t):到时间t为止累计离开的字节数
    如图,这就像一个水桶,上面有水流入,下面有水流出,中间的部分就是累计量,即队列。
    在这里插入图片描述
    上图使用的是存储转发模型。
    在这里插入图片描述
    看一个例子:
    在这里插入图片描述
    上图中的平均值计算可以用积分,结果是一样的。

    小型数据包减少了端到端的延迟

    在这里插入图片描述
    上图右边的表达式的第二项严格来讲应该为 ( M P − 1 ) ∗ r 3 (\frac{M}{P}-1)*r_3 (PM1)r3,因为第1个数据包已经计算在第一项中了,不过这里不影响理解。从左图中可以看出,如果整个报文以一个数据包发出,在开始第2段链路传输时,必须等待所有比特到达;而如果分成更小的数据包,那么每个数据包都是独立传输,不必等待其它数据包,这样就形成了流水线的效果,增强了并行性,减少了端到端延迟。

    统计复用

    如图,如果所有链路都以全速率R运行,那么输出链路将不堪重负,并且很快开始丢弃数据包。实际上,将有NR的速率输入,而只有R的输出速率。但由于统计复用和到达的突发性,如果平均速率较低,我们有可能避免这种情况。
    在这里插入图片描述
    下面有两条不同的链路输入同一个路由器,其中一个的比特率为A,另一个为B,输出链路的比特率为C。从图中可以看出,两峰重叠的时刻是很少的。
    在这里插入图片描述
    将两者的速率相加,因为峰值没有重叠,所以加起来的和小于两曲线的最值和。注意这里我们没利用缓冲区的存在这一条件。
    在这里插入图片描述
    下图考虑R‘,这时,输出顶不住输入的压力,会讲多的部分放入缓冲区中。
    在这里插入图片描述

    总结

    • 通常,我们可以使用简单的确定性队列模型来理解网络中的包动态
    • 我们将消息分成数据包,因为它允许我们通过流水线传输消息,并减少端到端的延迟
    • 统计复用使我们能够在一个链路上高效地传输多个流

    5、有用的队列特性

    通常情况下,到达过程是复杂的,所以我们通常使用随机过程来建模。
    研究具有随机到达过程的队列称为排队论
    具有随机到达过程的队列有一些有趣的特性。

    队列随时间的变化

    在这里插入图片描述
    蓝色箭头表示一个数据包到达,红色箭头表示离开,队列的占用情况由最下方的Q(t)和数字表示。图中的虚线红箭头表示队列为空时不能发送数据包。

    队列属性1:突发性到达会增加延迟

    在这里插入图片描述
    假设这是一个均匀到达的数据包序列,如图,每1秒到达一个数据包,在这种情况下,队列占用为0或1,即小于等于1,平均占用情况介于0和1。
    在这里插入图片描述
    和刚刚类似,到达链路和输出链路的数据率都不变,不过这一次是每N秒会有来自N个不同链路上的N个数据包同时到达(突发性),队列的占用情况Q(t)如图所示。可以看到,范围变大了,为0-5,并且整个过程一直在变化,均值和方差都变大了。
    总的来说,突发性到达会增加延迟,虽然这个简单的例子不能真正证明这一点,但我们也可以从直观上了解到它。

    队列属性2:确定性使延迟最小化

    这和第1个属性是刚好平衡的。随机到达的平均等待时间比简单的周期性到达要长。

    队列属性3:Little’s Result

    在这里插入图片描述
    λ为平均到达速率,L为平均队列长度,d为平均排队延迟。上面看似简单的结论适用于任何没有客户丢失或被丢弃的队列。

    泊松过程

    在这里插入图片描述
    泊松是许多独立随机事件的集合,例如

    • 新到达电话交换机的电话呼叫
    • 许多独立核粒子的衰变
    • 电路中的散粒噪声

    它使数学变得容易

    警示

    1. 网络流量非常具有突发性
    2. 数据包到达不是泊松分布的
    3. 但它很好地模拟了新流量的到来

    M/M/1队列

    在这里插入图片描述
    第1个M:Markovian arrival process(马尔可夫到达过程),在这里是泊松过程
    第2个M:Markovian service process(马尔可夫服务过程),在这里是指数过程
    1:1个服务者,即图中为队列服务的输出链路
    这个模型很简单,但也经常用来模拟各种复杂的排队系统。
    平均排队延迟: d = 1 μ − λ d=\frac{1}{μ-λ} d=μλ1
    可以看出,随着负载的增加,即 λ u \frac{λ}{u} uλ越趋近于1,平均延迟会越来越大
    由Little’s Result, L = λ d L=λd L=λd,所以 L = λ u − λ = λ u 1 − λ u L=\frac{λ}{u-λ}=\frac{\frac{λ}{u}}{1-\frac{λ}{u}} L=uλλ=1uλuλ,当λ逐渐增加越趋近于u,队列就越来越长,延迟就越来越大。
    因此,尽管M/M/1永远不可能是实际排队系统的队列占用率或平均延迟的性能度量,但它仍为我们提供了很好的直观感受。

    总结

    队列特性

    • 突发性到达会使延迟增加
    • Little’s Result L = λ d L=λd L=λd

    数据包的到达不是泊松的,但一些事件是,例如web请求和和一些新流量到达
    M/M/1队列是一个简单的队列模型

    6、分组交换机的工作方式(1)

    通用分组交换机

    在这里插入图片描述
    一个数据包到达后,先通过转发表查询目的地址对应的输出链路,然后可能要更新数据包的头信息(例如,对于互联网路由器,TTL要减1,然后重新计算校验和),接下来可能要在缓冲区中排队,轮到它后才被发送到输出链路。

    下面看看多个数据包的情况。
    在这里插入图片描述
    如图,红色的数据包会选择从红色圆点出去,蓝色数据包会从蓝色圆点出去,圆点表示链路。
    在这里插入图片描述
    如图,蓝色数据包被送出,红色数据包的一个被送出,另一个进入缓冲区排队。
    在这里插入图片描述
    一旦前面的数据包离开了,它就可以继续向前传输了。

    以太网交换机

    1. 检查每个到达帧的报头
    2. 如果以太网目标地址在转发表中,则转发帧到正确的输出端口
    3. 如果以太网目标地址不在表中,则广播帧到所有端口(帧到达的端口除外)
    4. 表中的条目是通过检查到达包的以太网源地址

    互联网路由器

    1. 如果到达帧的以太网目的地址(MAC地址)属于路由器,接受帧;否则丢弃
    2. 检查数据报的IP版本号和长度
    3. 减少TTL,更新IP报头校验和
    4. 检查TTL是否为0
    5. 如果IP目的地址在转发表中,则转发到下一跳的输出端口
    6. 找到下一跳路由器的以太网目的地址(ARP协议)
    7. 创建一个新的以太网帧并发送它

    基本操作

    1. 查找地址:在转发表中如何查找地址?
    2. 交换:如何将数据包发送到正确的输出端口?

    查找地址:以太网

    完全匹配:
    在这里插入图片描述

    查找地址:IP

    最长前缀匹配:
    在这里插入图片描述
    在这里插入图片描述

    最长前缀匹配的实现1:Trie树

    在这里插入图片描述
    这有点像哈夫曼树,0往左走,1往右走,可以到达唯一的叶节点。如果我们到达一个叶子结点发现那里为空,则回退到最近的匹配点

    最长前缀匹配的实现2:TCAM

    在这里插入图片描述
    连续X前面的位表示需要匹配的前缀,X表示表示无需匹配。掩码用来说明这一点。用这个实现的匹配是暴力匹配,即和表中的每一项都要去匹配。

    查找地址:通用

    现在的分组交换机被设计为可以完成不同层上的转发任务。
    在这里插入图片描述

    总结

    分组交换机执行两种基本操作:

    • 在转发表中查找地址
    • 切换到正确的输出端口

    在高层次上,以太网交换机和因特网路由器执行类似的操作
    地址查找在交换机和路由器中表现得非常不同

    7、分组交换机的工作方式(2)

    输出队列的分组交换

    如图,在每个输出链路上都有缓冲区,当发生拥塞时数据包被缓存在此。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    当前面的数据包离开后它才能离开。(FIFO)
    在这里插入图片描述
    考虑非常糟糕的情况,所有链路上同时到达的数据包都想从同一条链路输出。
    在这里插入图片描述
    假设所有链路的数据率均为R,则对于队列来说,输入速率为NR,输出速率为R,对于这块内存来说,它的总运行速率就要为(N+1)R。当N可能非常非常大时,建立可伸缩的队列内存是极为困难的。我们期望的总速率应该是2R,即输入R,输出R。

    输入队列的分组交换

    解决上述问题的一种方法是将队列移动到输入中。
    在这里插入图片描述
    和刚刚一样的例子:
    在这里插入图片描述
    另一个红色数据包被缓存:
    在这里插入图片描述
    当前面的包离开后,它才能继续:
    在这里插入图片描述
    这里的好处在于,同一时间队列中只会有一个数据包(不可能有多个数据包同时从一条链路上到达),这样一来输入的速率为R,输出速率为R,那么总速率就从(N+1)R减少为了我们期望的2R。
    但这个办法同样有问题。

    队头阻塞

    如图为所有链路的输入队列情况,此时所有队列的队头数据包都想要从红色链路输出。
    1.
    在这里插入图片描述
    2.
    在这里插入图片描述
    3.
    在这里插入图片描述
    尽管队列中有要发送到其它链路的数据包,但由于队头元素的阻塞,导致这一轮发不出去。

    虚拟输出队列

    解决队头阻塞的一个办法是使用虚拟输出队列,其中每个输入为每个输出维护一个单独的队列。
    在这里插入图片描述
    如图,三个输入,三个输出,因此在每个输入中有三个队列。
    在这里插入图片描述
    如图,对每个输入中的数据包,根据要输出的链路分别安排在对应的队列中。
    在这里插入图片描述
    这样一来,就不会发生队头阻塞了。
    在这里插入图片描述
    虚拟输出队列实际上在生活中很常见,如图,左转车道的车在对面有车过来时不能通行,即被阻塞,而右边的直行车道和右转车道上的车都不受影响。
    在这里插入图片描述

    总结

    分组交换机执行两种基本操作:

    • 在转发表中查找地址
    • 切换到正确的输出端口

    最简单和最慢的交换机使用输出队列,这将使数据包延迟最小化
    高性能交换机通常使用输入队列,通过虚拟输出队列来最大化吞吐量

    8、严格的优先级和有保证的流量率

    展开全文
  • // 更新使用(配合spring的@Validated功能分组使用) public interface Update{}​ // 删除使用(配合spring的@Validated功能分组使用) public interface Delete{}​ // 属性必须有这两个分组的才验证(配合spring的@...
  • 1-02、试简述分组交换的要点.答:在分组交换网络中,采用存储转发方式工作,数据以短的分组形式传送.如 果一个源站有一个长的报文要发送, 该报文就会被分割成一系列的分组. 每个分 组包含用户数据的一部分加上一些控制...
  • 分组密码模式

    千次阅读 2022-03-30 13:58:58
    分组密码是一种加密方法,它应用确定性算法和对称密钥来加密文本块。 分组密码的一些不同操作模式包括 ECB(电子密码本)、CBC(密码分组链)、CFB(密码反馈)、OFB(输出反馈模式)、CTR(计数器)。 0x01 ...
  • 分组密码算法与DES算法

    千次阅读 2022-02-14 19:56:59
    1 分组密码的含义 1.1 分组密码介绍 分组密码(block cipher)是现代密码学中的重要体制之一,也是应用最广泛、影响最大的一种密码体质,其主要任务是提供数据保密性,也可以用到再许多方面,如构造伪随机数生成器...
  • 分组密码总结

    千次阅读 2021-12-15 17:35:16
    代换: 明文分组到密文分组的可逆变换为代换。 扩散和混淆: 扩散和混淆是Shannonon提出的设计密码系统的两个基本方法,目的是抗击敌手对密码系统的统计分析。扩散是将明文的统计特性散布到密文中,使密文中的每一位...
  • stream进行分组统计

    千次阅读 2022-04-12 16:04:23
    // //groupingBy分组 // Map<Integer, Long> map = houseList.stream().collect(Collectors.groupingBy(House::getBuildId, Collectors.counting())); // //控制台输出map // map.forEach((k,v)->{ // ...
  • ORACLE分组查询和统计等

    千次阅读 2020-12-19 02:37:36
    oracle分组查询 分组函数 在分组函数中,如果有一个查找项分组,其他项必须也分组,比如下面的语句会报错,因为sal分组了,而ename没有分组: 1.显示工资最高的员工: 2.显示所有员工的平均工资: 2.1使用系统函 ... oracle...
  • Mysql:分组查询

    千次阅读 2020-11-15 20:00:25
    分组查询 1、分组查询是对数据按照某个或多个字段进行分组,在MYSQL中使用GROUP BY关键字对数据进行分组 2、GROUP BY关键字可以将查询结果按照某个字段或多个字段进行分组。字段中值相等的为一组 ⑴分组的核心是...
  • RecyclerView 实现分组展示;与iOS 类似的展示方式,可以随意调节数据多少,不仅限于只添加head和footer
  • pandas数据分析之分组聚合

    千次阅读 2022-02-12 09:31:53
    在数据分析过程中,经常会需要根据某一列或多列把数据划分为不同的组别,然后再对其进行数据分析。本文将介绍pandas的数据分组分组后的应用如对数据进行聚合、转换和过滤。
  • 数据聚合与分组操作(数据分析)

    千次阅读 2022-03-23 14:03:22
    第10章 数据聚合与分组操作 对数据集进行分类,并在每一组上应用一个聚合函数或转换函数,这通常是数据分析工作流中的一个重要部分。在载入、合并、准备数据集之后,你可能需要计算分组统计或者数据透视表用于报告...
  • jqGrid表格自带group分组功能,包括表头Header分组和表格内容分组功能,本文讨论表格行如何实现分组统计;表格行新增、删除时如何自动更新分组统计;表格行汇总列单元格编辑室如何更新分组统计;如何动态实现分组...
  • wpf仿QQ好友分组

    热门讨论 2014-03-20 17:12:16
    采用Expander和ListView来实现,运用了DataTemplate,具体请下载了查看代码
  • 文章目录 Pre 需求 实现三部曲 Step1 定义分组接口 Step2 给参数分配分组 Step3 指定分组 Step4 验证 源码 Pre SpringBoot - 优雅的实现【参数校验】高级进阶 SpringBoot - 优雅的实现【自定义参数校验】高级进阶 ...
  • STATA学习笔记:分组统计和分组回归

    万次阅读 多人点赞 2021-03-05 21:57:59
    STATA学习笔记:分组统计和分组回归 1. 分组统计 (1)对一个类别变量进行统计时 tabulate命令 tabulate oneway //for one-way tables of frequencies tabulate twoway //for two-way tables of frequencies ...
  • 实验六-线性分组码的MATLAB实现

    千次阅读 2021-07-06 23:53:03
    线性分组码的MATLAB实现一、线性分组码原理介绍二级目录三级目录二、线性分组码编码实例三、代码展示及运行结果四、程序自评价 一、线性分组码原理介绍 二级目录 三级目录 二、线性分组码编码实例 三、代码展示及...
  • 【计算机网络】分组交换技术

    千次阅读 2021-06-29 10:05:52
    存储转发交换又可以分为两类:报文存储转发交换(简称为报文交换)与报文分组存储转发交换(简称为分组交换);分组交换又可以进一步分为数据报交换与虚电路交换。线路交换方式与电话交换的工作方式类似。两台计算机通过...
  • Mybatis之分组查询

    千次阅读 2022-04-11 17:04:44
    在应用开发中,分组统计是非常经典的需求,在springboot+mybatis+mysql中实现分组统计。 学生信息统计场景,学生包含姓名、性别、年龄、地址等属性。 按性别分组统计数量 按地址分组统计数量 按地址、性别分组统计...
  • 什么是分组交换

    千次阅读 2021-06-18 05:29:23
    分组交换(Packed Switching)也称为包交换(Packet Switching),同样也属于存储-转发方式,是现代计算机网络的技术基础。分组交换网的出现标志着现代电信时代的开始。分组交换技术的出现克服了报文交换中传输延迟大的...
  • Java Lambda 多级分组

    千次阅读 2022-03-17 11:36:51
    Java Lambda 多级分组 public class Menu { /** * 菜品名称 */ private String name; /** * 菜品单价 */ private Double price; /** * 菜品斤数 */ private Double kilo; /** * 菜品类型:...
  • Stream流分组

    千次阅读 2022-03-24 19:04:12
    java Stream流分组案例
  • DataTables行分组的展开与折叠功能的实现
  • 分组密码

    千次阅读 2018-06-02 22:05:42
    一个分组的比特数就称为分组长度(block lenght)。 例如 DES和3DES的分组长度都是64比特。AES的分组长度为128比特。 流密码(stream cipher)是对数据流进行连续处理的一类密码算法。流密码中一般以1比...
  • Stream流-分组操作

    万次阅读 多人点赞 2020-07-11 22:21:05
    Stream流-分组操作 文章目录Stream流-分组操作方法1,`groupingBy(Function)`方法2,`groupingBy(Function,Collector)`方法3:`groupingBy(Function,Supplier,Collector)` Collectors.groupingBy()3个方法的使用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 961,327
精华内容 384,530
关键字:

分组

友情链接: Arme By BaF.rar