摩尔投票的一般性方法

前言

本文将从特殊到一般地介绍摩尔投票算法。每个特殊案例以尽可能相似的口吻叙述,以求得最终的一般性方法。

二分之一

让我们从最简单的开始,如何求出数组中所有出现次数在二分之一以上的元素?

参考题目:多数元素I

首先,一个数组里面最多只能有一个出现次数大于总长度一半的数。因此,本题可能满足条件的元素最多只有一种。

1,若存在一种元素满足条件

我们设满足条件的元素为val,将数组分为两个集合,一个是由所有的val组成的集合A,另一个是由剩下的元素组成的集合B。

假设val的数量刚好占了1/2,则两个集合的数目相等,我们从集合A、B中分别拿出一个元素,让这两个元素消除,循环往复,这个数组将被消除的干干净净。

事实是,集合A的元素数量多于1/2,集合B的元素数量少于1/2,如果我们从集合A、B中各拿一个元素消除,循环往复,那么剩下的元素一定是集合A中的val。

因此,我们只需要每次从数组中拿出两个元素,保证其中一个是val,另一个不是val,然后让他们循环消除,最后剩下的就是我们要求的val了。

但是,我们并不知道集合A、B在数组中的位置,自然也不能准确地将他们拿出来,我们只能通过从前往后遍历的方式检测数组中的元素。

因此,我们暂时设val为数组中的第一个元素,这样我们就拿到了val,只需要找到一个与val不相等的元素,就可以完成一次消除了。

于是从前往后遍历,我们将这时的nums【i】分为两种情况:

  1. nums【i】与val相等。
  2. nums【i】与val不相等。

如果是第一种情况,显然不满足我们之前推导的两个元素消除的条件,但是,我们也不能无视当前的numsi。

因此,设变量num,统计val出现的次数。这时如果出现第一种情况,就让num+1,当val被消除时,可以补上一个相同的数,同时让num-1。

如果是第二种情况,就让num-1,一旦出现num等于0的情况,就代表当前的val已经被暂时消除干净了,需要马上更换一个val,同时将num设为1。

这时有同学就提出一个问题,更换的val并不一定最终的答案啊?

是这样没错,我们最开始设置的val,也不一定是最终的答案,那我们为什么要这样做呢?

因为,我们需要一个集合B中的元素才能进行一次消除,而集合B中的元素数量根本连1/2都达不到,所以val被消除的次数,不会超过1/2。而集合A的元素数量超过了1/2,所以当循环结束,集合A一定会有剩余。即使更换的val不一定是最终答案,后面“真正的”val也会将他们替换下来。

你可以这样理解,当并非最终答案的一个元素成为了val,那么“真正的”val就被归纳为集合B中的元素了,此时的集合B_plus,是原来的集合B与集合A之和,其数量绝对远远超过原来的集合B。况且,集合B中的元素并非全部相等,这个假冒的答案不一定有那么多的“同伙”来帮它撑num的数值,就算集合B元素全部相等,也依然没有真正的val的数量多,因此,这个假冒的元素一定会被真正的元素挤下来。

这时又有同学要问了,如果在数组遍历结束的最后一刻,val从最终答案变成别的数了怎么办?

首先,如果数组存在一个满足条件的元素,因为集合A的元素数量比C的多,这种情况一定不会发生,如果发生了,那就一定是接下来要讲的,不存在满足条件的元素的讨论。

2,若不存在元素满足条件

如果没有元素满足条件,解决方法很简单,只需要遍历一次就行了,统计这个val出现的次数,此时的时间复杂度依然是O(n)。

如果题目告诉你一定存在满足条件的数,那么直接返回val即可;如果题目告诉你不一定存在满足条件的数,遍历一遍即可。

代码实现

在这里我展示参考题目的提交通过代码,参考题目中已经规定数组中一定存在一个满足条件的元素,因此你可以省略下面的次数统计。

int majorityElement(int* nums, int numsSize)
{
    int val = 0;
    int num = 0;

    int i = 0;
    for (i = 0; i < numsSize; i++) 
    {
        if(num==0)
        {
            val=nums[i];
            num=1;
        }
        else if(val==nums[i])
        {
            num++;
        }
        else if(val!=nums[i])
        {
            num--;
        }
        
    }
    
    int count=0;//在参考题目中可以省略
    for(i=0;i<numsSize;i++)
    {
        if(nums[i]==val)
        {
            count++;
        }
    }
    if(count>numsSize/2)
        return val;
    else 
        return;
}

三分之一

参考题目:多数元素II

首先,2个大于1/3的数相加,其结果一定大于2/3,因此,这题里出现次数超过1/3的元素最多只有两种。

1,若存在两种元素满足条件

我们将这两种元素分别设为val1,val2,然后将数组分为三个集合,第一个是val1的集合A,第二个是val2的集合B,第三个是剩余元素的集合C。假设val1和val2都刚刚好占了1/3,那么我们从ABC中分别取出一个元素,然后将他们消除,循环往复,这个数组将被消除的干干净净。

事实是,集合A的元素数量大于1/3,集合B的元素数量也大于1/3,集合C的元素数量少于1/3,如果我们在ABC中各拿一个元素,循环消除,那么最先消除的集合一定是C。

因此,我们只需要每次在数组中拿出三个元素,保证其中一个是val1,一个是val2,另一个是集合C中的元素,然后让他们循环消除,最后剩下的元素一定就是我们要求的val1和val2。

但是,我们并不知道集合ABC在数组中的位置,自然也不能准确地将他们拿出来,我们只能通过从前往后遍历的方式检测数组中的元素。

因此,设val1为数组的第一个元素,val2是数组从前往后数第一个和val1不同的元素,这样我们就拿到了val1和val2,只需要找出第三个元素,于是从前往后遍历,假设数组为nums,遍历使用的工具变量设为i,我们将这时的nums【i】分为三种情况:

  1. nums【i】与val1相等。
  2. nums【i】与val2相等。
  3. nums【i】与val1和val2都不相等。

如果是第一种和第二种情况,显然不满足我们之前推导的三个元素消除的条件,但是,我们也不能无视当前的nums【i】。

因此,设num1、num2,分别统计val1、val2出现的次数。这时如果出现第一种或第二种情况,就让对应的num+1,这样当对应的val被消除时,可以补上一个相同的数,同时让对应的num-1。

如果是第三种情况,让num1和num2都各自-1,一旦出现num等于0的情况,就代表当前对应的val已经被暂时消除干净了,需要马上更换一个val,因为有两个val的存在,所以你在更换一个val的时候需要注意,新的val不能和另外一个val相等,同时将被更换的val的num设为1。

这时有同学就提出一个问题,更换的val并不一定最终的答案啊?

是这样没错,我们最开始设置的val1和val2,也不一定是最终的答案,那我们为什么要这样做呢?

因为,我们需要一个集合C中的元素才能进行一次消除,而集合C中的元素数量根本连1/3都达不到,所以val1和val2被消除的次数,不会超过1/3。而集合A和B的元素数量超过了1/3,所以当循环结束,集合A与B一定会有剩余。即使更换的val不一定是最终答案,后面“真正的”val也会将他们替换下来。

你可以这样理解,当并非最终答案的一个元素成为了val1,那么“真正的”val1就被归纳为集合C中的元素了,此时的集合C_plus,是原来的集合C与集合A之和,其数量绝对远远超过原来的集合C。况且,集合C中的元素并非全部相等,这个假冒的答案不一定有那么多的“同伙”来帮它撑num的数值,就算集合C元素全部相等,也依然没有真正的val1的数量多,因此,这个假冒的元素一定会被真正的元素挤下来。

这时又有同学要问了,如果在数组遍历结束的最后一刻,val从最终答案变成别的数了怎么办?

首先,如果在数组存在两种满足要求的元素,因为集合A和B的元素数量都比集合C的数量多,这种情况一定不会发生,如果发生了,那就一定是接下来要讲的,只存在一个或没有满足要求的元素的讨论。

2,若只存在一个或没有元素满足条件

我们假设val1满足条件,val2不满足条件,则上述情况的发生,是val2在遍历结束前被清除干净了,而val1因为数量超过了1/3,又因为消除次数小于1/3,所以依然保留。

又或者两个val都不满足条件,都被替换成了别的数。

对于这种情况,不必太过苦恼,解决方法很简单,遍历一次就行了,统计这两个数出现的次数,此时的时间复杂度依然是O(n)。

如果题目告诉你满足条件的数一定有两个,你可以直接返回这两个数;如果题目告诉你满足条件的数只有一个,你可以比较这两个数的大小,返回较大的数即可。

代码实现

对于三分之一的问题,代码实现时有一个特殊情况,即数组全部元素都等于val2的初始值,val1在进入循环时被赋为该值,num1的长度最终变为数组长度,此时val1与val2相等,需要在结束时判断两者是否相等。

在此我展示参考题目的通过代码。

int* majorityElement(int* nums, int numsSize, int* returnSize)
{
    int val1=0,val2=0;
    int num1=0,num2=0;

    int i=0;
    for(i=0;i<numsSize;i++)
    {
        if(num1==0&&nums[i]!=val2)
        {
            val1=nums[i];
            num1=1;
        }
        else if(num2==0&&nums[i]!=val1)
        {
            val2=nums[i];
            num2=1;
        }
        else if(nums[i]==val1)
        {
            num1++;
        }
        else if(nums[i]==val2)
        {
            num2++;
        }
        else 
        {
            num1--;
            num2--;
        }
    }

    int* arr=(int*)malloc(8);//开辟空间
    if(arr==NULL)
    {
        return -1;
    }

    if(val1==val2)//二者相等返回其一即可
    {
        arr[0]=val1;
        *returnSize=1;
        return arr;
    }
    int count1=0,count2=0;//统计次数
    for(i=0;i<numsSize;i++)
    {
        if(nums[i]==val1)
        {
            count1++;
        }
        if(nums[i]==val2)
        {
            count2++;
        }
    }


    int flag=0;
    int x=0;
    if(count1>numsSize/3)
    {
        arr[x]=val1;
        x++;
        flag++;
    }
    if(count2>numsSize/3)
    {
        arr[x]=val2;
        x++;
        flag++;
    }
    *returnSize=flag;
    return arr;
}

四分之一

参考题目:NULL

首先,3个大于1/4的数相加,其结果一定大于3/4,因此,这题里出现次数超过1/4的元素最多只有三种。

1,若存在三种元素满足条件

我们将这三种元素分别设为val1,val2,val3,然后将数组分为四个集合,第一个是val1的集合A,第二个是val2的集合B,第三个是val3的集合C,第四个是剩余元素的集合D。假设val1、val2、val3都刚刚好占了1/4,那么我们从ABCD中分别取出一个元素,然后将他们消除,循环往复,这个数组将被消除的干干净净。

事实是,集合A、B、C的元素数量都大于1/4,如果我们在ABCD中各拿一个元素,循环消除,那么最先消除的集合一定是D。

因此,我们只需要每次在数组中拿出四个元素,分别保证他们来自集合ABCD,然后让他们循环消除,最后剩下的元素一定就是我们要求的三个val。

因此,设val1为数组的第一个元素,val2是数组从前往后数第一个和val1不同的元素,val3是从前往后数第二个与val1的不同的元素,这样我们就拿到了val1、val2和val3,只需要找出第四个元素,于是从前往后遍历,假设数组为nums,遍历使用的工具变量设为i,我们将这时的nums【i】分为三种情况:

  1. nums【i】与val1相等。
  2. nums【i】与val2相等。
  3. nums【i】与val3相等。
  4. nums【i】与v这三者都不相等。

如果是第1、2、3种情况,显然不满足我们之前推导的四个元素消除的条件,但是,我们也不能无视当前的nums【i】。

因此,设num1、num2,num3分别统计val1、val2、val3出现的次数。这时如果出现第1、2、3种情况,就让对应的num+1,这样当对应的val被消除时,可以补上一个相同的数,同时让对应的num-1。

这时有同学就提出一个问题,更换的val并不一定最终的答案啊?

是这样没错,我们最开始设置的val1、val2、val3,也不一定是最终的答案,那我们为什么要这样做呢?

因为,我们需要一个集合D中的元素才能进行一次消除,而集合D中的元素数量根本连1/4都达不到,所以val1、val2、val3被消除的次数,不会超过1/4。而集合A、B、C的元素数量超过了1/4,所以当循环结束,集合A、B、C一定会有剩余。即使更换的val不一定是最终答案,后面“真正的”val也会将他们替换下来。

你可以这样理解,当并非最终答案的一个元素成为了val1,那么“真正的”val1就被归纳为集合D中的元素了,此时的集合D_plus,是原来的集合D与集合A之和,其数量绝对远远超过原来的集合D。况且,集合D中的元素并非全部相等,这个假冒的答案不一定有那么多的“同伙”来帮它撑num的数值,就算集合D元素全部相等,也依然没有真正的val1的数量多,因此,这个假冒的元素一定会被真正的元素挤下来。

这时又有同学要问了,如果在数组遍历结束的最后一刻,val从最终答案变成别的数了怎么办?

首先,如果在数组存在三种满足要求的元素,因为集合A、B、C的元素数量都比集合D的数量多,这种情况一定不会发生,如果发生了,那就一定是接下来要讲的,只存在1、2个或没有满足要求的元素的讨论。

2,若存在0、1、2个元素满足条件

只要有一个val不满足条件,就有val可能不是我们需要的答案,解决方法还是那样,遍历即可。

代码实现

与三分之一问题类比,在最后结束时需要判断三个val之间是否有相等的情况,如果有,只返回其中一个。

因为没有参考题目,我将展示未经系统评估的代码。

int answer1 = 0;
int answer2 = 0;
int answer3 = 0;
int count1 = 0, count2 = 0, count3 = 0;

haha(int* arr)
{
	int val1=0, val2=0, val3=0;
	int num1=0, num2=0, num3=0;
	int i = 0;
	for (i = 0; i < 12; i++)
	{
		if (num1 == 0 && arr[i] != val2 && arr[i] != val3)
		{
			val1 = arr[i];
			num1 = 1;
		}
		else if (num2 == 0 && arr[i] != val1 && arr[i] != val3)
		{
			val2 = arr[i];
			num2 = 1;
		}
		else if (num3 == 0 && arr[i] != val1 && arr[i] != val2)
		{
			val3 = arr[i];
			num3 = 1;
		}
		else if (arr[i] == val1)
		{
			num1++;
		}
		else if (arr[i] == val2)
		{
			num2++;
		}
		else if (arr[i] == val3)
		{
			num3++;
		}
		else
		{
			num1--;
			num2--;
			num3--;
		}
	}
	if (val1 == val2 == val3)
	{
		answer1 = val1;
	}
	else if (val1 == val2 && val2 != val3)
	{
		answer1 = val1;
		answer2 = val3;
	}
	else if (val1 == val3 && val3 != val2)
	{
		answer1 = val1;
		answer2 = val2;
	}
	else if (val2 == val3 && val3 != val1)
	{
		answer1 = val1;
		answer2 = val2;
	}
	else
	{
		answer1 = val1;
		answer2 = val2;
		answer3 = val3;
	}
	for (i = 0; i < 12; i++) 
	{
		if (arr[i] == answer1)
		{
			count1++;
		}
		else if (arr[i] == answer2)
		{
			count2++;
		}
		else if (arr[i] == answer3)
		{
			count3++;
		}
	}

}
int main()
{
	int arr[12] = { 0,0,0,0,0,0,0,0,0,0,1,2 };
	haha(arr);
	printf("%d %d %d\n", answer1, answer2, answer3);//三个可能的答案,超过n/4就返回即可
	printf("%d %d %d", count1, count2, count3);//查看出现的次数
	return 0;
}

N分之一

下面我们进行一般性的简易梳理。

三分之一及其以上的问题就具有了一定的一般性,随着N越来越大,代码也越来越冗杂。

将N-1种元素设为val1、val2、val3...,每个val各不相同,分别设置对应的num存储出现次数,对每个val赋值时注意不能与其他val相同,讨论特殊情况时,若遇相同,返回其一即可,详细请看代码:

int answer1 = 0;
int answer2 = 0;
int answer3 = 0;
int count1 = 0, count2 = 0, count3 = 0;

haha(int* arr)
{
	int val1=0, val2=0, val3=0;//共有N-1个变量
	int num1=0, num2=0, num3=0;
	int i = 0;
	for (i = 0; i < 12; i++)
	{
		if (num1 == 0 && arr[i] != val2 && arr[i] != val3)//复杂的判断
		{
			val1 = arr[i];
			num1 = 1;
		}
		else if (num2 == 0 && arr[i] != val1 && arr[i] != val3)
		{
			val2 = arr[i];
			num2 = 1;
		}
		else if (num3 == 0 && arr[i] != val1 && arr[i] != val2)
		{
			val3 = arr[i];
			num3 = 1;
		}
		else if (arr[i] == val1)
		{
			num1++;
		}
		else if (arr[i] == val2)
		{
			num2++;
		}
		else if (arr[i] == val3)
		{
			num3++;
		}
		else
		{
			num1--;
			num2--;
			num3--;
		}
	}
	if (val1 == val2 == val3)//有相等的只返回其一
	{
		answer1 = val1;
	}
	else if (val1 == val2 && val2 != val3)
	{
		answer1 = val1;
		answer2 = val3;
	}
	else if (val1 == val3 && val3 != val2)
	{
		answer1 = val1;
		answer2 = val2;
	}
	else if (val2 == val3 && val3 != val1)
	{
		answer1 = val1;
		answer2 = val2;
	}
	else
	{
		answer1 = val1;
		answer2 = val2;
		answer3 = val3;
	}
	for (i = 0; i < 12; i++) 
	{
		if (arr[i] == answer1)
		{
			count1++;
		}
		else if (arr[i] == answer2)
		{
			count2++;
		}
		else if (arr[i] == answer3)
		{
			count3++;
		}
	}

}
int main()
{
	int arr[12] = { 0,0,0,0,0,0,0,0,0,0,1,2 };
	haha(arr);
	printf("%d %d %d\n", answer1, answer2, answer3);//三个可能的答案,超过n/4就返回即可
	printf("%d %d %d", count1, count2, count3);//查看出现的次数
	return 0;
}

感谢你的阅读与耐心~

本文转载于网络 如有侵权请联系删除

相关文章

  • 数据库中的schema

    大家好,又见面了,我是你们的朋友全栈君。研究多租户的过程中涉及到了schema的概念,具体是什么呢?schema的官方定义为:Aschemaisacollectionofdatabaseobjects(usedbyauser.). Schemaobjectsarethelogicalstructuresthatdirectlyrefertothedatabase’sdata. Auserisanamedefinedinthedatabasethatcanconnecttoandaccessobjects. Schemasandusershelpdatabaseadministratorsmanagedatabasesecurity.从定义我们可以看出:schema就是数据库对象的集合,这个集合包含了各种对象如:表、视图、存储过程、索引等。为了区分不同的集合,就需要给不同的集合起不同的名字,默认情况下一个用户对应一个集合,用户的schema名等于用户名,并作为该用户缺省schema。所以schema集合看上去像用户名。 如果把database看作是一个仓库,仓库很多房间(schema),

  • 能让 JS 执行的 JavascriptCore ,到底是啥

    在这篇文章中我们知道,ISO版微信小程序逻辑层中的JavaScript代码运行在JavaScriptCore中,那么JavascriptCore到底有什么神奇的地方,能让JS在IOS中执行呢?Swift自2014年推出以来,人气飙升,但是JavaScript是一种与Swift完全相反的语言,比如Swift在编译时做了很多保障安全性的措施,而JavaScript则是一门弱类型语言,它只在执行时运行。可能它们两个也没想到有一天能够一起协作,制作一个流畅的iOS应用程序! 但是,你知道为什么JS能在IOS中运行吗?本篇文章,我们就来说说能让JS在IOS运行的JavascriptCore框架到底是什么。你将了解到以下知识点:JavaScriptCore框架的组成。如何从iOS/Swift代码中调用JavaScript。如何从JavaScript访问IOS/Swift代码。开始JavaScriptCore框架提供对WebKit的JavaScript引擎的访问。最初,该框架有一个仅限Mac的CAPI,但iOS7和OSX10.9附带了一个更好的Objective-C包装器。该框架能够使你的Swift

  • 可区分的质量多样性

    质量多样性(QD)是随机优化研究的一个日益增长的分支,它研究的是如何生成一个最大化给定目标函数的解决方案档案,但对于一组指定的度量函数也是多样的。然而,即使这些函数是可微的,QD算法将它们视为“黑盒”,忽略了梯度信息。我们提出了可微质量多样性(DQD)问题,这是QD的一个特例,其中目标函数和测度函数都是一阶可微的。然后,我们提出了map-eliteviaGradientArborescence(MEGA),这是一种DQD算法,利用梯度信息有效地探索目标函数和测度函数的联合范围。在两个QD基准域和StyleGAN的潜在空间搜索结果表明,MEGA算法显著优于先进的QD算法,突出了DQD在梯度信息可用时的高效质量多样性优化的前景。源代码可在https://github.com/icaros-usc/dqd上获得。原文题目:DifferentiableQualityDiversity原文:Qualitydiversity(QD)isagrowingbranchofstochasticoptimizationresearchthatstudiestheproblemofgeneratingana

  • 随机显示必应每日一图,API代码及调用方法

    主题有好多模板设置了分类的背景图,调用了第三方api但是最近第三方挂了,嗯嗯,这就是图省事不写代码的后果,一旦图片都失效,网站打开速度慢不说,图片的背景图还是灰蒙蒙一片,非常尴尬。。。百度了下必应每日api源代码有很多,但是随机显示的也都是调用人家自己的,这样就可能再次出现无法打开的情况,但是仅仅调用一张图片又略显单调(最烦我这种啥也不是,要求还多的人。。。),终于皇天不负有心人让我找到了一个随机显示必应图片的api调用方法,附上代码及适用教程。调用方法:(代码在下方)此API只支持https调用,所有参数均仅适用于以GET方式进行请求,可直接插入img标签中请求地址:(不要适用本站api代码,跨域)https://www.talklee.com/api/bing/复制调用参数:参数代码参数含义可用参数rand是否随机显示最近8天内的图片trueorfalseday显示指定的最近图片-1,0,1,2,3,4,5,6,7(0为今天,-1为昨天)size指定获取图片大小详见下方可用分辨率info获取图片基础信息(json格式)trueorfalse以上所有参数均非必要,默认参数为rand=

  • PyTorch入门笔记-增删张量的维度

    增加维度增加一个长度为1的维度相当于给原有的张量添加一个新维度的概念。由于增加的新维度长度为1,因此张量中的元素并没有发生改变,仅仅改变了张量的理解方式。比如一张大小的灰度图片保存为形状为的张量,在张量的头部增加一个长度为1的新维度,定义为通道数维度,此时张量的形状为。“图片张量的形状有两种约定: 通道在后的约定。TensorFlow将通道维度放在最后:;通道在前的约定。PyTorch将通道维度放在前面:”使用torch.unsqueeze(input,dim)可以在指定的dim维度前插入一个长度为1的新维度。>>>importtorch >>>#使用随机生成的正态分布模拟没有通道维度的图片张量 >>>input=torch.randn(28,28) >>>print(input.size()) torch.Size([28,28]) >>>#指定第0个维度前面插入新的维度 >>>image=torch.unsqueeze(input,dim=0) >>>p

  • 一篇文章弄懂Linux磁盘和磁盘分区

    前言Linux系统中所有的硬件设备都是通过文件的方式来表现和使用的,我们将这些文件称为设备文件,硬盘对应的设备文件一般被称为块设备文件。本文介绍磁盘设备在Linux系统中的表示方法以及如何创建磁盘分区。为什么要有多个分区?防止数据丢失:如果系统只有一个分区,那么这个分区损坏,用户将会丢失所的有数据。增加磁盘空间使用效率:可以用不同的区块大小来格式化分区,如果有很多1K的文件,而硬盘分区区块大小为4K,那么每存储一个文件将会浪费3K空间。这时我们需要取这些文件大小的平均值进行区块大小的划分。数据激增到极限不会引起系统挂起:将用户数据和系统数据分开,可以避免用户数据填满整个硬盘,引起的系挂起。磁盘分类比较常见的磁盘类型有服务器中使用的SCSI硬盘和消费类市场中的SATA硬盘,当然还有当下大热的各种固态硬盘。SCSI硬盘SCSI硬盘即采用SCSI接口的硬盘。它由于性能好、稳定性高,因此在服务器上得到广泛应用。同时其价格也不菲,正因它的价格昂贵,所以在普通PC上很少见到它的踪迹。SCSI硬盘使用50针接口,外观和普通硬盘接口有些相似(下图来自互联网):SATA硬盘SATA(SerialATA)

  • HDD机械硬盘的性能

    HDD机械硬盘的性能性能指标:IOPS=1000/(寻道时间AverageSeekTime+旋转延迟AverageLatency)复制寻道时间(AverageSeekTime)是指将读写磁头(DiskHead)移动至正确的磁道上所需要的时间。从公式可以得出,寻道时间越短,I/O操作越快,IOPS就越高。旋转延迟(AverageLatency)是指盘片旋转将请求数据所在扇区(Sector)移至读写磁头(DiskHead)下方所需要的时间。旋转延迟取决于磁盘转速,通常使用磁盘旋转一周所需时间的1/2表示。比如,7200RPM的磁盘平均旋转延迟大约为60*1000/7200/2=4.17ms,而转速为15000RPM的磁盘其平均旋转延迟为2ms。注:事实上还有一个传输时间(同样位于公式的分母),即完成传输所请求的数据所需要的时间,它取决于数据传输率,其值等于数据大小除以数据传输率。由于主流的SAS、SATA接口数据传输率的不断提升,数据传输时间通常远小于前两部分消耗时间,简单计算时可忽略。降低寻道时间想提高存储的IOPS性能,就要想办法减小分母上的数值。由于旋转延迟是固定的(除非购买更快转速

  • eFORGE v2.0:一个表观遗传研究的在线分析工具

    DNA甲基化(DNAm)是人类疾病研究中主要的表观遗传标记。Illumina公司开发的新型EPIC芯片可以检测超过85万个基因组位点的DNAm,将450k序列的启动子中心覆盖范围扩展到ENCODE和FANTOM5项目识别的增强子, 为表观基因组关联研究(EWAS)提供了一个强大而可靠的新工具。eFORGE的原始版本(PMID:27851974)采用多层表观遗传信息,包括开放染色质位点(DNaseI热点)和组蛋白标记(H3K4me1,H3K4me3,H3K27me3,H3K9me3和H3K36me3)的数据,以检测驱动EWAS信号的细胞类型。eFORGE的更新版扩展并增强了该工具,增加了新的功能,如跨15个染色质状态的同时分析,与EWAS信号相关的转录因子(TF)基序的检测,累积DNaseI足迹分析,EPIC阵列支持,以及用于分析EWAS基因座中TF占有率的浏览器。值得注意的是,我们将其中许多功能合并到新的基于Web的套件eFORGE-TF中,以帮助对TF相关的EWAS机制进行多级表征。的原始版本(Breeze等人,2016)采用多层表观遗传信息,包括开放染色质位点(DNaseI热点)和

  • 单例模式(Singleton)

    单例模式(Singleton)–单线程保证一个类仅有一个实例,并提供一个访问它的全局访问点,避免一个全局使用的类频繁的创建和销毁,节省系统资源,提高程序效率。怎么创建唯一的实例?Java是这么创建实例的Personp=newPerson();但是这么创建会创建多个实例,所以我们必须把构造器设为私有,这样其他类就不能使用new来实例化一个类。publicclassSingleton{ //定义一个属性,用来保存Singleton类对象的实例 privatestaticSingletoninstance; //私有构造器,该类不能被外部类使用new方式实例化 privateSingleton(){ } //外部通过该方法获取Singleton类的唯一实例 publicstaticSingletongetInstance(){ if(instance==null){ instance=newSingleton(); } returninstance; } }复制这种实现方式并不是线程安全的,当有多个线程同时调用Singleton.getInstance()方法时会产生多个实例。单例模

  • 真是跪了,谷歌无人驾驶你还能更牛逼一点吗?

    近六年,从谷歌的无人驾驶汽车在山景称的马路上“巡游”开始,居然发生各种事故14起,不得不让对这项技术的安全性产生担忧,甚至怀疑谷歌这一项目“代价太大,成效太低”。但深信这项技术无论安全性还是效率都高于传统人类驾驶的谷歌,不仅没有一丝动摇,而且还在不断努力让外界减轻这方面的担心。近日,谷歌无人驾驶项目负责人克里斯•厄姆森(ChrisUrmson)在伊斯兰提举行的自动车辆研讨会上,展示了一系列其无人驾驶测试车在总部山景城周围道路上遇到的路况和场景。其中一个场景是:一只鸭子在十字路口跌跌撞撞,后面跟着一位骑电动车的妇女在追赶。对于这种奇葩场景,厄姆森表示,这种场景几乎很难在现实中出现,而且对于汽车驾驶来说,这显然是毫无规则可循的意外事件,“即使是车管局也不会有针对这一情况的相关规定”。但谷歌的无人驾驶车辆在面对这一情况时需要知道,这种现象并非常规,需要做的就是冷静下来,等一切正常。对于这种特殊情况,驾车的传统驾驶员一般能够判断鸭子和妇女的行进路线,并且伺机开过去;谷歌汽车的做法则是停下来,等待汽车“大脑”来确认“前方没有障碍”,再决定是否行使。这表明,谷歌的无人驾驶汽车对各种哪怕现实生活很难

  • Python爬虫技术系列-02HTML解析-BS4

    Python爬虫技术系列-02HTML解析-BS42BeautifulSoup解析2.1BeautifulSoup概述2.1.1BeautifulSoup安装2.1.2BeautifulSoup4库内置对象2.2BS4案例2.2.1读取HTML案例2.2.2BS4常用语法1Tag节点2遍历节点3搜索方法1)find_all()2)find()3)CSS选择器2.3BS4综合案例2.3.1需求:爬取三国演义小说的所有章节和内容2.3.2爬取小说数据,并排错2BeautifulSoup解析参考连接: https://beautifulsoup.readthedocs.io/zh_CN/v4.4.0/# http://c.biancheng.net/python_spider/bs4.html2.1BeautifulSoup概述2.1.1BeautifulSoup安装BeautifulSoup简称BS4(其中4表示版本号)是一个Python第三方库,它可以从HTML或XML文档中快速地提取指定的数据。BeautifulSoup语法简单,使用方便,并且容易理解,因此您可以快速地学习并掌握它。本

  • FFmpegUtil

    这几天没事研究音频玩比如X配音app的配音功能录一段pcm或者wav格式的文件替换mp4指定位置的音频刚开始卡在pcm混合以及pcm指定位置插入。思路  一段段的视频进行切割   用到MP4Code和Android转码的一个依赖库后面附上地址能实现,但是每次都要切割感觉太耗性能了。后来反编译X配音的发现他是从pcm入手并没有做切割基于Mp4Parse一个依赖库进行封装完成的废话不多说直接上工具类。publicclassFFmpegUtil{privateFFmpegffmpeg;publicFFmpegUtil(Contextcontext){if(null==ffmpeg)ffmpeg=FFmpeg.getInstance(context);}/***指定位置合并录音文件支持AAC测试过*@paramtotalFile较长的文件*@paramtempFile要插入替换的文件*@paramdelayTiem延时插入的位置*@paramduration较长文件的时间*@paramoutputFile新的录音文件输出目录*/publicvoidmergeAudio(StringtotalF

  • 一个数如果恰好等于它的因子之和,这个数称为“完数”,如6的因子为 1,2,3,而1+2+3=6,因此6就是完数 提示: 判断一个数是否是完数,用穷举法:从1~n/2+1 逐个判断是否整除,如果整除则累加 如果累加结果与n 相等,则输出完数n; 如果完数个数为0,则输出NO 类似问题可以做1111号题目

    输入: 输入一个整数n(0<n<=1000) 输出: 输出2到n间的所有完数。注:如果有多个,输出在同一行,用空格隔开,如果没有,输出“NO”。如:输入3,输出:NO;输入8,输出:6;输入30,输出:628。 #include<stdio.h> main() { intn,i,j,sum=0,s=0; scanf("%d",&n); for(i=2;i<=n;i++) { for(j=1;j<i;j++) { if(i%j==0) { sum+=j; } } if(i==sum) { printf("%d",i); s++; } sum=0; } if(s==0) { printf("NO"); } }复制  

  • oracle如何去除字符串中的重复字符

    1createorreplacefunctionremove_rame_string(oldStrvarchar2,signvarchar2) 2returnvarchar2is 3 4/**************************************************** 5**Oracle去掉重复字符串 6**函数名称:RemoveSameStr 7**参数:【名称】【类型】【说明】 8**oldStrvarchar2要处理的字符串 9**signvarchar2字符串分隔符 10**返回值:Resultvarchar2不包含重复子串的记录 11****************************************************/ 12strvarchar2(2000); 13currentIndexnumber; 14startIndexnumber; 15endIndexnumber; 16 17typestr_typeistableofvarchar2(30)indexbybinary_integer; 18arrstr_type; 19

  • 认识Nginx,理解原理和功能

    前端工程师在理解Nginx之后,就能更好的与后端工程师沟通,为了能提高工作效率,这两天抽空读了《Nginx高性能Web服务器实战教程》。 一、Nginx Nginx是一款高性能的Web服务器软件,主要用于提供网上信息浏览服务,为高并发网站的应用场景而设计,可以在Linux、macOS和Windows等操作系统中运行,它的优点包括性能高、稳定性好、结构模块化、配置简单以及资源消耗非常低等。拥有HTTPS访问、gzip压缩、虚拟主机和URL重写等功能,不但可以搭配FastCGI程序处理动态请求,还可以用于代理、反向代理、负载均衡和缓存服务器等功能。P2 1)进程和访问控制 Nginx由一个主进程和多个工作进程组成,主进程接收客户端请求,再转交给工作进程处理,从而很好地利用多核心CPU的计算能力。P89       Nginx的访问控制是网络安全防范和保护的主要策略,其任务是保证网络资源不被非法访问。P93 2)日志记录功能 Nginx提供了一个非常灵活的日志记录功能,它可以使每个块的配置拥有各自独立的日志进行记录,并且根据记录内容的不同又分为访问日志和错误日志

  • RobotFrameowork+Python3环境部署

    1.安装Python3(笔者这里安装的Python3.6.5) 安装 robotframework:  pipinstallrobotframework-U pipinstallrobotframework-U复制 3.安装WxPython库 pipinstallwxpython复制 4.安装robotframwork pipinstallrobotframework复制 5.安装RobotFramework常用库 pipinstallrobotframework-selenium2library#(非常有用) pipinstallrobotframework-requests#(可选) pipinstallrobotframework-SSHLibrary#(可选) pipinstallrobotframework-ftplibrary#(可选) pipinstallrobotframework-appiumlibrary#(可选)复制 6.如果非要使用RF官方编辑器RIDE的话,我们继续安装robotframework-ride

  • CF1051F The Shortest Statement 题解

    题目 Youaregivenaweighedundirectedconnectedgraph,consistingofnverticesandmedges. Youshouldanswerqqueries,thei-thqueryistofindtheshortestdistancebetweenvertices\(u_i\)and\(v_i\). 输入格式 Thefirstlinecontainstwointegers\(n\)and\(m(1≤n,m≤105,m−n≤20)\)—thenumberofverticesandedgesinthegraph. Nextmlinescontaintheedges:thei-thedgeisatripleofintegers\(v_i,u_i,d_i(1≤u_i,v_i≤n,1≤d_i≤10^9,u_i≠v_i)\).Thistriplemeansthatthereisanedgebetweenverticesuiandviofweightdi.Itisguaranteedthatgraphcontainsnoself-loopsandmu

  • sqlyog存储过程

    存储过程定义:(摘自百度百科): 存储过程(StoredProcedure)是在大型数据库系统中,一组为了完成特定功能的SQL语句集,存储在数据库中,经过第一次编译后再次调用不需要再次编译,用户通过指定存储过程的名字并给出参数(如果该存储过程带有参数)来执行它。 我的需求: 想在数据库school的表student中插入1000条记录。 操作: sqlyog中新建一个存储过程: DELIMITER$$ CREATE PROCEDURE`school`.`test`() BEGIN DECLAREiINTDEFAULT0; WHILEi<1000DO INSERTINTOstudent(score)VALUES(i); SETi=i+1; ENDWHILE; END$$ DELIMITER;复制 如上,建立了一个存储过程,名为test,像执行一个普通sql脚本一下执行这段代码,即在数据库中建立了这个存储过程。 调用存储过程,即完成了插入数据操作: CALLtest();复制

  • 没什么卵用的 ICN 论文

    虽然没什么卵用,但还是要写,不然怎么毕业。 看资料的时候,从Information-CentricNetworking:SeeingtheForestfortheTrees跳到了 FindinganeedleinHaystack:Facebook’sphotostorage 译文(http://www.importnew.com/3292.html)   做科研,导师也不懂,糊里糊涂过了一年。沮丧太多,也是自己不努力。 按理说,NDN也是大牛提出来的,缓存对访问的提升效果有巨大的局限性这事儿,大牛不应该不知道啊。哎……某些科研真的就是大牛挖坑,渣渣灌水吧。 Anyway,跳转阅读到了经典论文,还是开心的。粘几句 Information-CentricNetworking:SeeingtheForestfortheTrees里形象生动说出我新生的神吐槽吧(自己真的是弱爆了,想吐槽都说不明白)。 Becausethereisnocommonframework,thefocusisoftenonlow-levelmechanisms.Asaresult,many

  • 王晋康 - 养蜂人&#183;王晋康科幻小说精选集1(2014年2月4日)

    《养蜂人·王晋康科幻小说精选集1》 作  者:王晋康 译  者: 系  列:王晋康科幻小说精选集 出  版:时代文艺出版社 字  数:214千字 阅读完成:2014年2月4日 作者:行一山人          出处:http://www.cnblogs.com/benbenkoala/ 本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

  • Vue学习笔记5

    列表渲染 用v-for把一个数组对应为一组元素 <divid="app"> <liv-for="iteminarray"> {{item.message}} </li> </div> <script> varapp=newVue({ el:'#app', data:{ array:[ {message:'vue1'}, {message:'vue2'}, {message:'vue3'} ] }, }) </script> 复制 <divid="app"> <liv-for="iteminarray"> {{item}} </li> </div> <script> varapp=newVue({ el:'#app', data:{ array:[ 'vue1', 'vue2', 'vue3' ] }, }) </script> 复制 结果: v-for还支持一个可选的第二个参数为当前项的索引。 <divid="app"> <

相关推荐

推荐阅读