缺失的第一个正数
41. 缺失的第一个正数 - 力扣(LeetCode) 空间复杂度o(n)很好想,但o(1)不好想,还是个408考研真题
注意O(n) == O(2n),即相较于边遍历边判断,还是遍历两次更加方便且不会有太多损失。类似思想:73. 矩阵置零 - 力扣(LeetCode)
41. 缺失的第一个正数 - 力扣(LeetCode) 空间复杂度o(n)很好想,但o(1)不好想,还是个408考研真题
注意O(n) == O(2n),即相较于边遍历边判断,还是遍历两次更加方便且不会有太多损失。类似思想:73. 矩阵置零 - 力扣(LeetCode)
ICL即In-contexting Learning。 ICL 包含三种分类: - Few-shot
learning,允许输入数条示例和一则任务说明; - One-shot
learning,只允许输入一条示例和一则任务说明; - Zero-shot
learning,不允许输入任何示例,只允许输入一则任务说明。
题目地址 # 思路 通过前缀和+哈希表,并有简单的数学变换。前缀和即 \(y[i]=y[i-1]+x[i]\) 类比于accumlate函数,注意前缀和思想也可以应用为“前缀积、后缀和、后缀积”等思想。238. 除自身以外数组的乘积 - 力扣(LeetCode) > 使用前缀和的方法可以解决这个问题,因为我们需要找到和为k的连续子数组的个数。通过计算前缀和,我们可以将问题转化为求解两个前缀和之差等于k的情况。 >假设数组的前缀和数组为prefixSum,其中prefixSum[i]表示从数组起始位置到第i个位置的元素之和。那么对于任意的两个下标i和j(i < j),如果prefixSum[j] - prefixSum[i] = k,即从第i个位置到第j个位置的元素之和等于k,那么说明从第i+1个位置到第j个位置的连续子数组的和为k。 通过遍历数组,计算每个位置的前缀和,并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中,我们检查是否存在prefixSum[j] - k的前缀和,如果存在,说明从某个位置到当前位置的连续子数组的和为k,我们将对应的次数累加到结果中。 这样,通过遍历一次数组,我们可以统计出和为k的连续子数组的个数,并且时间复杂度为O(n),其中n为数组的长度。 # 代码
题目地址 # 思路 通过前缀和+哈希表,并有简单的数学变换。前缀和即 \(y[i]=y[i-1]+x[i]\) 类比于accumlate函数,注意前缀和思想也可以应用为“前缀积、后缀和、后缀积”等思想。238. 除自身以外数组的乘积 - 力扣(LeetCode) > 使用前缀和的方法可以解决这个问题,因为我们需要找到和为k的连续子数组的个数。通过计算前缀和,我们可以将问题转化为求解两个前缀和之差等于k的情况。 >假设数组的前缀和数组为prefixSum,其中prefixSum[i]表示从数组起始位置到第i个位置的元素之和。那么对于任意的两个下标i和j(i < j),如果prefixSum[j] - prefixSum[i] = k,即从第i个位置到第j个位置的元素之和等于k,那么说明从第i+1个位置到第j个位置的连续子数组的和为k。 通过遍历数组,计算每个位置的前缀和,并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中,我们检查是否存在prefixSum[j] - k的前缀和,如果存在,说明从某个位置到当前位置的连续子数组的和为k,我们将对应的次数累加到结果中。 这样,通过遍历一次数组,我们可以统计出和为k的连续子数组的个数,并且时间复杂度为O(n),其中n为数组的长度。 # 代码
def find(x):
if (p[x] != x):
= find(p[x])
p[x] return p[x]
上面是y总的模板,实现了路径压缩。
与本主题的shortcode类似 类型有:note、abstract、info、tip、success、question、warning、failure、danger、bug、example、quote。
"当前文件: $TM_FILENAME",
"当前日期: $CURRENT_YEAR/$CURRENT_MONTH/$CURRENT_DATE"
只贴最核心的损失函数代码
def simcse_unsup_loss(y_pred, device, temp=0.05):
"""无监督的损失函数
y_pred (tensor): bert的输出, [batch_size * 2, 768] ,2为句子个数,即一个句子对
"""
# 得到y_pred对应的label, [1, 0, 3, 2, ..., batch_size-1, batch_size-2]
= torch.arange(y_pred.shape[0], device=device)
y_true
= (y_true - y_true % 2 * 2) + 1
y_true
# batch内两两计算相似度, 得到相似度矩阵(batch_size*batch_size)
= F.cosine_similarity(y_pred.unsqueeze(1), y_pred.unsqueeze(0), dim=-1)
sim
print(sim)
print(sim.shape)
# 将相似度矩阵对角线置为很小的值, 消除自身的影响
= sim - torch.eye(y_pred.shape[0], device=device) * 1e12
sim
# 相似度矩阵除以温度系数
= sim / temp
sim
# 计算相似度矩阵与y_true的交叉熵损失
# 计算交叉熵,每个case都会计算与其他case的相似度得分,得到一个得分向量,目的是使得该得分向量中正样本的得分最高,负样本的得分最低
= F.cross_entropy(sim, y_true)
loss
return torch.mean(loss)
"""
苏神keras源码
def simcse_loss(y_true, y_pred):
idxs = K.arange(0, K.shape(y_pred)[0]) #生成batch内句子的编码 [0,1,2,3,4,5]为例子
idxs_1 = idxs[None, :] # 给idxs添加一个维度,变成: [[0,1,2,3,4,5]]
idxs_2 = (idxs + 1 - idxs % 2 * 2)[:, None] # 这个意思就是说,如果一个句子id为奇数,那么和它同义的句子的id就是它的上一句,如果一个句子id为偶数,那么和它同义的句子的id就是它的下一句。 [:, None] 是在列上添加一个维度。初步生成了label。[[1], [0], [3], [2], [5], [4]]
y_true = K.equal(idxs_1, idxs_2) # equal会让idxs1和idxs2都映射到6*6,idxs1垂直,idxs2水平
y_true = K.cast(y_true, K.floatx()) # 生成label
y_pred = K.l2_normalize(y_pred, axis=1) # 对句向量各个维度做了一个L2正则,使其变得各项同性,避免下面计算相似度时,某一个维度影响力过大。
similarities = K.dot(y_pred, K.transpose(y_pred)) # 计算batch内每句话和其他句子的内积相似度。
similarities = similarities - tf.eye(K.shape(y_pred)[0]) * 1e12 # 将和自身的相似度变为0(后面的softmax之后)。
similarities = similarities * 20 # 将所有相似度乘以20,这个目的是想计算softmax概率时,更加有区分度。
loss = K.categorical_crossentropy(y_true, similarities, from_logits=True)
return K.mean(loss)
"""
def simcse_sup_loss(y_pred, device, lamda=0.05):
"""
有监督损失函数
"""
= F.cosine_similarity(y_pred.unsqueeze(0), y_pred.unsqueeze(1), dim=2)
similarities
= torch.arange(0, y_pred.shape[0], 3)
row
= torch.arange(0, y_pred.shape[0])
col
= col[col % 3 != 0]
col
= similarities[row, :]
similarities
= similarities[:, col]
similarities
= similarities / lamda
similarities
= torch.arange(0, len(col), 2, device=device)
y_true
= F.cross_entropy(similarities, y_true)
loss
return loss