• 关于 相似度计算函数 的搜索结果

问题

两两比较问题

lifubang 2019-12-01 20:20:16 854 浏览量 回答数 1

问题

Scala Spark中两个稀疏向量的余弦相似性

社区小助手 2019-12-01 19:29:00 1087 浏览量 回答数 1

回答

聚类分析计算方法主要有: 层次的方法(hierarchical method)、划分方法(partitioning method)、基于密度的方法(density-based method)、基于网格的方法(grid-based method)、基于模型的方法(model-based method)等。其中,前两种算法是利用统计学定义的距离进行度量。 k-means 算法的工作过程说明如下:首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然 后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。 其流程如下: (1)从 n个数据对象任意选择 k 个对象作为初始聚类中心; (2)根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分; (3)重新计算每个(有变化)聚类的均值(中心对象); (4)循环(2)、(3)直到每个聚类不再发生变化为止(标准测量函数收敛)。 优点: 本算法确定的K 个划分到达平方误差最小。当聚类是密集的,且类与类之间区别明显时,效果较好。对于处理大数据集,这个算法是相对可伸缩和高效的,计算的复杂度为 O(NKt),其中N是数据对象的数目,t是迭代的次数。一般来说,K< 缺点: 1. K 是事先给定的,但非常难以选定;2. 初始聚类中心的选择对聚类结果有较大的影响。

珍宝珠 2019-12-02 03:14:10 0 浏览量 回答数 0

新用户福利专场,云服务器ECS低至102元/年

新用户专场,1核2G 102元/年起,2核4G 699.8元/年起

回答

选择一门编程语言,例如C之类的。如果不想学编程,就尝试下Excel里面的公式。-------------------------算法的定义 算法(Algorithm)是一系列解决问题的清晰指令,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列,并且这样的步骤和序列可以解决一类问题。 一个算法应该具有以下五个重要的特征: 1、有穷性: 一个算法必须保证执行有限步之后结束; 2、确切性: 算法的每一步骤必须有确切的定义; 3、输入:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定除了初始条件; 4、输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的; 5、可行性: 算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。 计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法= 程序》,可见算法在计算机科学界与计算机应用界的地位。 [编辑本段]算法的复杂度 同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 时间复杂度 算法的时间复杂度是指算法需要消耗的时间资源。一般来说,计算机算法是问题规模n 的函数f(n),算法的时间复杂度也因此记做 T(n)=Ο(f(n)) 因此,问题的规模n 越大,算法执行的时间的增长率与f(n) 的增长率正相关,称作渐进时间复杂度(Asymptotic Time Complexity)。 空间复杂度 算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。 详见百度百科词条"算法复杂度" [编辑本段]算法设计与分析的基本方法 1.递推法 递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步,找出相邻几步的关系,从而达到目的,此方法称为递推法。 2.递归 递归指的是一个过程:函数不断引用自身,直到引用的对象已知 3.穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。 4.贪婪法 贪婪法是一种不追求最优解,只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不要回溯。 5.分治法 把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 6.动态规划法 动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础,被广泛应用于计算机科学和工程领域。 7.迭代法 迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题(一般是解方程或者方程组)的过程,为实现这一过程所使用的方法统称为迭代法。 [编辑本段]算法分类 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法。 算法可以宏泛的分为三类: 有限的,确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务,但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。 有限的,非确定算法 这类算法在有限的时间内终止。然而,对于一个(或一些)给定的数值,算法的结果并不是唯一的或确定的。 无限的算法 是那些由于没有定义终止定义条件,或定义的条件无法由输入的数据满足而不终止运行的算法。通常,无限算法的产生是由于未能确定的定义终止条件。 [编辑本段]举例 经典的算法有很多,如:"欧几里德算法,割圆术,秦九韶算法"。 [编辑本段]算法经典专著 目前市面上有许多论述算法的书籍,其中最著名的便是《计算机程序设计艺术》(The Art Of Computer Programming) 以及《算法导论》(Introduction To Algorithms)。 [编辑本段]算法的历史 “算法”即演算法的大陆中文名称出自《周髀算经》;而英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi,因为al-Khwarizmi在数学上提出了算法这个概念。“算法”原为"algorism",意思是阿拉伯数字的运算法则,在18世纪演变为"algorithm"。欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序,因此Ada Byron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机,这个算法未能在巴贝奇分析机上执行。 因为"well-defined procedure"缺少数学上精确的定义,19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要作用的。

马铭芳 2019-12-02 01:19:58 0 浏览量 回答数 0

回答

对象检测任务中,你希望能够同时定位对象,所以如果实际边界框是这样的,你的算法给出这个紫色的边界框,那么这个结果是好还是坏?所以交并比(loU)函数做的是计算两个边界框交集和并集之比。两个边界框的并集是这个区域,就是属于包含两个边界框区域(绿色阴影表示区域),而交集就是这个比较小的区域(橙色阴影表示区域),那么交并比就是交集的大小,这个橙色阴影面积,然后除以绿色阴影的并集面积。 一般约定,在计算机检测任务中,如果,就说检测正确,如果预测器和实际边界框完美重叠,loU就是1,因为交集就等于并集。但一般来说只要,那么结果是可以接受的,看起来还可以。一般约定,0.5是阈值,用来判断预测的边界框是否正确。一般是这么约定,但如果你希望更严格一点,你可以将loU定得更高,比如说大于0.6或者更大的数字,但loU越高,边界框越精确。 所以这是衡量定位精确度的一种方式,你只需要统计算法正确检测和定位对象的次数,你就可以用这样的定义判断对象定位是否准确。再次,0.5是人为约定,没有特别深的理论依据,如果你想更严格一点,可以把阈值定为0.6。有时我看到更严格的标准,比如0.6甚至0.7,但很少见到有人将阈值降到0.5以下。 人们定义loU这个概念是为了评价你的对象定位算法是否精准,但更一般地说,loU衡量了两个边界框重叠地相对大小。如果你有两个边界框,你可以计算交集,计算并集,然后求两个数值的比值,所以这也可以判断两个边界框是否相似,我们将在下一个视频中再次用到这个函数,当我们讨论非最大值抑制时再次用到。

因为相信,所以看见。 2020-05-20 18:07:29 0 浏览量 回答数 0

回答

逻辑回归 逻辑回归实际上是一种分类算法。我怀疑它这样命名是因为它与线性回归在学习方法上很相似,但是成本和梯度函数表述不同。特别是,逻辑回归使用了一个sigmoid或“logit”激活函数,而不是线性回归的连续输出。 首先导入和检查我们将要处理的数据集。 import numpy as np import pandas as pd import matplotlib.pyplot as plt %matplotlib inline import os path = os.getcwd() + '\data\ex2data1.txt' data = pd.read_csv(path, header=None, names=['Exam 1', 'Exam 2', 'Admitted']) data.head() 在数据中有两个连续的自变量——“Exam 1”和“Exam 2”。我们的预测目标是“Admitted”的标签。值1表示学生被录取,0表示学生没有被录取。我们看有两科成绩的散点图,并使用颜色编码来表达例子是positive或者negative。 positive = data[data['Admitted'].isin([1])] negative = data[data['Admitted'].isin([0])] fig, ax = plt.subplots(figsize=(12,8)) ax.scatter(positive['Exam 1'], positive['Exam 2'], s=50, c='b', marker='o', label='Admitted') ax.scatter(negative['Exam 1'], negative['Exam 2'], s=50, c='r', marker='x', label='Not Admitted') ax.legend() ax.set_xlabel('Exam 1 Score') ax.set_ylabel('Exam 2 Score') 从这个图中我们可以看到,有一个近似线性的决策边界。它有一点弯曲,所以我们不能使用直线将所有的例子正确地分类,但我们能够很接近。现在我们需要实施逻辑回归,这样我们就可以训练一个模型来找到最优决策边界,并做出分类预测。首先需要实现sigmoid函数。 def sigmoid(z): return 1 / (1 + np.exp(-z)) 这个函数是逻辑回归输出的“激活”函数。它将连续输入转换为0到1之间的值。这个值可以被解释为分类概率,或者输入的例子应该被积极分类的可能性。利用带有界限值的概率,我们可以得到一个离散标签预测。它有助于可视化函数的输出,以了解它真正在做什么。 nums = np.arange(-10, 10, step=1) fig, ax = plt.subplots(figsize=(12,8)) ax.plot(nums, sigmoid(nums), 'r') 我们的下一步是写成本函数。成本函数在给定一组模型参数的训练数据上评估模型的性能。这是逻辑回归的成本函数。 def cost(theta, X, y): theta = np.matrix(theta) X = np.matrix(X) y = np.matrix(y) first = np.multiply(-y, np.log(sigmoid(X * theta.T))) second = np.multiply((1 - y), np.log(1 - sigmoid(X * theta.T))) return np.sum(first - second) / (len(X)) 注意,我们将输出减少到单个标量值,该值是“误差”之和,是模型分配的类概率与示例的真实标签之间差别的量化函数。该实现完全是向量化的——它在语句(sigmoid(X * theta.T))中计算模型对整个数据集的预测。 测试成本函数以确保它在运行,首先需要做一些设置。 # add a ones column - this makes the matrix multiplication work out easier data.insert(0, 'Ones', 1) # set X (training data) and y (target variable) cols = data.shape[1] X = data.iloc[:,0:cols-1] y = data.iloc[:,cols-1:cols] # convert to numpy arrays and initalize the parameter array theta X = np.array(X.values) y = np.array(y.values) theta = np.zeros(3) 检查数据结构的形状,以确保它们的值是合理的。这种技术在实现矩阵乘法时非常有用 X.shape, theta.shape, y.shape ((100L, 3L), (3L,), (100L, 1L)) 现在计算初始解的成本,将模型参数“theta”设置为零。 cost(theta, X, y) 0.69314718055994529 我们已经有了工作成本函数,下一步是编写一个函数,用来计算模型参数的梯度,以找出改变参数来提高训练数据模型的方法。在梯度下降的情况下,我们不只是在参数值周围随机地jigger,看看什么效果最好。并且在每次迭代训练中,我们通过保证将其移动到减少训练误差(即“成本”)的方向来更新参数。我们可以这样做是因为成本函数是可微分的。这是函数。 def gradient(theta, X, y): theta = np.matrix(theta) X = np.matrix(X) y = np.matrix(y) parameters = int(theta.ravel().shape[1]) grad = np.zeros(parameters) error = sigmoid(X * theta.T) - y for i in range(parameters): term = np.multiply(error, X[:,i]) grad[i] = np.sum(term) / len(X) return grad 我们并没有在这个函数中执行梯度下降——我们只计算一个梯度步骤。在练习中,使用“fminunc”的Octave函数优化给定函数的参数,以计算成本和梯度。因为我们使用的是Python,所以我们可以使用SciPy的优化API来做同样的事情。 import scipy.optimize as opt result = opt.fmin_tnc(func=cost, x0=theta, fprime=gradient, args=(X, y)) cost(result[0], X, y) 0.20357134412164668 现在我们的数据集里有了最优模型参数,接下来我们要写一个函数,它使用我们训练过的参数theta来输出数据集X的预测,然后使用这个函数为我们分类器的训练精度打分。 def predict(theta, X): probability = sigmoid(X * theta.T) return [1 if x >= 0.5 else 0 for x in probability] theta_min = np.matrix(result[0]) predictions = predict(theta_min, X) correct = [1 if ((a == 1 and b == 1) or (a == 0 and b == 0)) else 0 for (a, b) in zip(predictions, y)] accuracy = (sum(map(int, correct)) % len(correct)) print 'accuracy = {0}%'.format(accuracy) accuracy = 89% 我们的逻辑回归分类器预测学生是否被录取的准确性可以达到89%,这是在训练集中的精度。我们没有保留一个hold-out set或使用交叉验证来获得准确的近似值,所以这个数字可能高于实际的值。 正则化逻辑回归 既然我们已经有了逻辑回归的工作实现,我们将通过添加正则化来改善算法。正则化是成本函数的一个条件,使算法倾向于更简单的模型(在这种情况下,模型会减小系数),原理就是帮助减少过度拟合和帮助模型提高通用化能力。我们使用逻辑回归的正则化版本去解决稍带挑战性的问题, 想象你是工厂的产品经理,你有一些芯片在两种不同测试上的测试结果。通过两种测试,你将会决定那种芯片被接受或者拒绝。为了帮助你做这个决定,你将会有以往芯片的测试结果数据集,并且通过它建立一个逻辑回归模型。 现在可视化数据。 path = os.getcwd() + '\data\ex2data2.txt' data2 = pd.read_csv(path, header=None, names=['Test 1', 'Test 2', 'Accepted']) positive = data2[data2['Accepted'].isin([1])] negative = data2[data2['Accepted'].isin([0])] fig, ax = plt.subplots(figsize=(12,8)) ax.scatter(positive['Test 1'], positive['Test 2'], s=50, c='b', marker='o', label='Accepted') ax.scatter(negative['Test 1'], negative['Test 2'], s=50, c='r', marker='x', label='Rejected') ax.legend() ax.set_xlabel('Test 1 Score') ax.set_ylabel('Test 2 Score') 这个数据看起来比以前的例子更复杂,你会注意到没有线性决策线,数据也执行的很好,处理这个问题的一种方法是使用像逻辑回归这样的线性技术,就是构造出由原始特征多项式派生出来的特征。我们可以尝试创建一堆多项式特性以提供给分类器。 degree = 5 x1 = data2['Test 1'] x2 = data2['Test 2'] data2.insert(3, 'Ones', 1) for i in range(1, degree): for j in range(0, i): data2['F' + str(i) + str(j)] = np.power(x1, i-j) * np.power(x2, j) data2.drop('Test 1', axis=1, inplace=True) data2.drop('Test 2', axis=1, inplace=True) data2.head() 现在我们需要去修改成本和梯度函数以包含正则项。在这种情况下,将正则化矩阵添加到之前的计算中。这是更新后的成本函数。 def costReg(theta, X, y, learningRate): theta = np.matrix(theta) X = np.matrix(X) y = np.matrix(y) first = np.multiply(-y, np.log(sigmoid(X * theta.T))) second = np.multiply((1 - y), np.log(1 - sigmoid(X * theta.T))) reg = (learningRate / 2 * len(X)) * np.sum(np.power(theta[:,1:theta.shape[1]], 2)) return np.sum(first - second) / (len(X)) + reg 我们添加了一个名为“reg”的新变量,它是参数值的函数。随着参数越来越大,对成本函数的惩罚也越来越大。我们在函数中添加了一个新的“learning rate”参数。 这也是等式中正则项的一部分。 learning rate为我们提供了一个新的超参数,我们可以使用它来调整正则化在成本函数中的权重。 接下来,我们将在梯度函数中添加正则化。 def gradientReg(theta, X, y, learningRate): theta = np.matrix(theta) X = np.matrix(X) y = np.matrix(y) parameters = int(theta.ravel().shape[1]) grad = np.zeros(parameters) error = sigmoid(X * theta.T) - y for i in range(parameters): term = np.multiply(error, X[:,i]) if (i == 0): grad[i] = np.sum(term) / len(X) else: grad[i] = (np.sum(term) / len(X)) + ((learningRate / len(X)) * theta[:,i]) return grad 与成本函数一样,将正则项加到最初的计算中。与成本函数不同的是,我们包含了确保第一个参数不被正则化的逻辑。这个决定背后的直觉是,第一个参数被认为是模型的“bias”或“intercept”,不应该被惩罚。 我们像以前那样测试新函数 # set X and y (remember from above that we moved the label to column 0) cols = data2.shape[1] X2 = data2.iloc[:,1:cols] y2 = data2.iloc[:,0:1] # convert to numpy arrays and initalize the parameter array theta X2 = np.array(X2.values) y2 = np.array(y2.values) theta2 = np.zeros(11) learningRate = 1 costReg(theta2, X2, y2, learningRate) 0.6931471805599454 我们能使用先前的最优代码寻找最优模型参数。 result2 = opt.fmin_tnc(func=costReg, x0=theta2, fprime=gradientReg, args=(X2, y2, learningRate)) result2 (数组([ 0.35872309, -3.22200653, 18.97106363, -4.25297831, 18.23053189, 20.36386672, 8.94114455, -43.77439015, -17.93440473, -50.75071857, -2.84162964]), 110, 1) 最后,我们可以使用前面应用的相同方法,为训练数据创建标签预测,并评估模型的性能。 theta_min = np.matrix(result2[0]) predictions = predict(theta_min, X2) correct = [1 if ((a == 1 and b == 1) or (a == 0 and b == 0)) else 0 for (a, b) in zip(predictions, y2)] accuracy = (sum(map(int, correct)) % len(correct)) print 'accuracy = {0}%'.format(accuracy) 准确度 = 91%

珍宝珠 2019-12-02 03:22:33 0 浏览量 回答数 0

回答

计算机的算法具有可行性,有穷性、输入\输出、确定性。 计算机算法特点 1.有穷性。一个算法应包含有限的操作步骤,而不能是无限的。事实上“有穷性”往往指“在合理的范围之内”。如果让计算机执行一个历时1000年才结束的算法,这虽然是有穷的,但超过了合理的限度,人们不把他视为有效算法。 2. 确定性。算法中的每一个步骤都应当是确定的,而不应当是含糊的、模棱两可的。算法中的每一个步骤应当不致被解释成不同的含义,而应是十分明确的。也就是说,算法的含义应当是唯一的,而不应当产生“歧义性”。 3. 有零个或多个输入、所谓输入是指在执行算法是需要从外界取得必要的信息。 4. 有一个或多个输出。算法的目的是为了求解,没有输出的算法是没有意义的。 5.有效性。 算法中的每一个 步骤都应当能有效的执行。并得到确定的结果。 拓展资料: 重要算法 A*搜寻算法 俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样,可以找到一条最短路径;也像BFS一样,进行启发式的搜索。 Beam Search 束搜索(beam search)方法是解决优化问题的一种启发式方法,它是在分枝定界方法基础上发展起来的,它使用启发式方法估计k个最好的路径,仅从这k个路径出发向下搜索,即每一层只有满意的结点会被保留,其它的结点则被永久抛弃,从而比分枝定界法能大大节省运行时间。束搜索于20 世纪70年代中期首先被应用于人工智能领域,1976 年Lowerre在其称为HARPY的语音识别系统中第一次使用了束搜索方法。他的目标是并行地搜索几个潜在的最优决策路径以减少回溯,并快速地获得一个解。 二分取中查找算法 一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。这种搜索算法每一次比较都使搜索范围缩小一半。 Branch and bound 分支定界(branch and bound)算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同,分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树,并且,在分支定界算法中,每一个活结点只有一次机会成为扩展结点。 数据压缩 数据压缩是通过减少计算机中所存储数据或者通信传播中数据的冗余度,达到增大数据密度,最终使数据的存储空间减少的技术。数据压缩在文件存储和分布式系统领域有着十分广泛的应用。数据压缩也代表着尺寸媒介容量的增大和网络带宽的扩展。 Diffie–Hellman密钥协商 Diffie–Hellman key exchange,简称“D–H”,是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。 Dijkstra’s 算法 迪科斯彻算法(Dijkstra)是由荷兰计算机科学家艾兹格·迪科斯彻(Edsger Wybe Dijkstra)发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说,如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离,迪科斯彻算法可以用来找到两个城市之间的最短路径。 动态规划 动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础,被广泛应用于计算机科学和工程领域。比较著名的应用实例有:求解最短路径问题,背包问题,项目管理,网络流优化等。这里也有一篇文章说得比较详细。 欧几里得算法 在数学中,辗转相除法,又称欧几里得算法,是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》(第VII卷,命题i和ii)中,而在中国则可以追溯至东汉出现的《九章算术》。 最大期望(EM)算法 在统计计算中,最大期望(EM)算法是在概率(probabilistic)模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法观测的隐藏变量(Latent Variable)。最大期望经常用在机器学习和计算机视觉的数据聚类(Data Clustering)领域。最大期望算法经过两个步骤交替进行计算,第一步是计算期望(E),利用对隐藏变量的现有估计值,计算其最大似然估计值;第二步是最大化(M),最大化在 E 步上求得的最大似然值来计算参数的值。M 步上找到的参数估计值被用于下一个 E 步计算中,这个过程不断交替进行。 快速傅里叶变换(FFT) 快速傅里叶变换(Fast Fourier Transform,FFT),是离散傅里叶变换的快速算法,也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用,如数字信号处理、计算大整数乘法、求解偏微分方程等等。 哈希函数 HashFunction是一种从任何一种数据中创建小的数字“指纹”的方法。该函数将数据打乱混合,重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中,不抑制冲突来区别数据,会使得数据库记录更难找到。 堆排序 Heapsort是指利用堆积树(堆)这种数据结构所设计的一种排序算法。堆积树是一个近似完全二叉树的结构,并同时满足堆积属性:即子结点的键值或索引总是小于(或者大于)它的父结点。 归并排序 Merge sort是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 RANSAC 算法 RANSAC 是”RANdom SAmpleConsensus”的缩写。该算法是用于从一组观测数据中估计数学模型参数的迭代方法,由Fischler and Bolles在1981提出,它是一种非确定性算法,因为它只能以一定的概率得到合理的结果,随着迭代次数的增加,这种概率是增加的。该算法的基本假设是观测数据集中存在”inliers”(那些对模型参数估计起到支持作用的点)和”outliers”(不符合模型的点),并且这组观测数据受到噪声影响。RANSAC 假设给定一组”inliers”数据就能够得到最优的符合这组点的模型。 RSA加密演算法 这是一个公钥加密算法,也是世界上第一个适合用来做签名的算法。今天的RSA已经专利失效,其被广泛地用于电子商务加密,大家都相信,只要密钥足够长,这个算法就会是安全的。 并查集Union-find 并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。 Viterbi algorithm 寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states)。 参考资料:计算机算法

游客886 2019-12-02 01:17:57 0 浏览量 回答数 0

回答

softmax用于多分类过程中最后一层,将多个神经元的输出,映射到(0, 1)区间内,可以看成概率来理解,从而来进行多分类! softmax函数如下: 更形象的如下图表示: softmax 直白来说就是讲原来输出是 3, 1, -3 通过 softmax 函数一作用,就映射成为(0, 1)的值,而这些值的累和为1,那么我们就可以将其理解成概率,在最后选取输出节点的时候,我们可以选取概率最大的节点,作为我们的预测目标! Python代码实现: # _*_coding:utf-8_*_ import tensorflow as tf import numpy as np import math # softmax函数,或称归一化指数函数 def softmax(x, axis=1): # 为了避免求 exp(x) 出现溢出的情况,一般需要减去最大值 # 计算每行的最大值 row_max = x.max(axis=axis) # 每行元素都需要减去对应的最大值,否则求exp(x)会溢出,导致INF情况 row_max = row_max.reshpae(-1, 1) x = x - row_max x_exp = np.exp(x) # 如果是列向量,则axis=0 x_sum = np.sum(x_exp, axis=1, keepdims=True) s = x_exp / x_sum return s # 简单一些 def softmax(x): """Compute softmax values for each sets of scores in x.""" e_x = np.exp(x - np.max(x)) return e_x / e_x.sum() # 使用 tf的softmax函数 with tf.Session() as sess: tf_s2 = tf.nn.softmax(x, axis=axis) s2 = sess.run(tf_s2)   下面我们分析一下,减去最大值和不减去最大值是否有必要吗?首先看代码: import numpy as np def softmax(x): """Compute softmax values for each sets of scores in x.""" e_x = np.exp(x - np.max(x)) return e_x / e_x.sum() def softmax1(x): """Compute softmax values for each sets of scores in x.""" return np.exp(x) / np.sum(np.exp(x), axis=0) scores = [3.0, 1.0, 0.2] print(softmax(scores)) print(softmax1(scores)) ''' 结果输出如下: [0.8360188 0.11314284 0.05083836] [0.8360188 0.11314284 0.05083836] ''' 其实两个结果输出是一样的,即使第一个实现了每列和最大值的差异,然后除以总和,但是问题来了,实现在代码和时间复杂度方面是否相似?哪一个更有效率? 当然,他们都是正确的,但是从数值稳定性的角度来看,第一个是正确的,因为我们避免了求 exp(x) 出现溢出的情况,这里减去了最大值。我们推导一下: # 转化公式: a ^(b – c)=(a ^ b)/(a ^ c) e ^ (x - max(x)) / sum(e^(x - max(x)) = e ^ x / (e ^ max(x) * sum(e ^ x / e ^ max(x))) = e ^ x / sum(e ^ x)

珍宝珠 2019-12-02 03:22:24 0 浏览量 回答数 0

问题

动态规划的实际应用:图片压缩算法 6月15日 【今日算法】

游客ih62co2qqq5ww 2020-06-17 02:16:53 12 浏览量 回答数 1

回答

HI,tsvector,tsquery 的相似度计算用到的这个函数。Datum rum_ts_distance_tt(PG_FUNCTION_ARGS) { TSVector txt = PG_GETARG_TSVECTOR(0); TSQuery query = PG_GETARG_TSQUERY(1); float4 res; res = calc_score(weights, txt, query, DEF_NORM_METHOD); PG_FREE_IF_COPY(txt, 0); PG_FREE_IF_COPY(query, 1); if (res == 0) PG_RETURN_FLOAT4(get_float4_infinity()); else PG_RETURN_FLOAT4(1.0 / res); } static float4 calc_score(float4 *arrdata, TSVector txt, TSQuery query, int method) { DocRepresentation *doc; uint32 len, doclen = 0; double Wdoc = 0.0; QueryRepresentation qr; qr.query = query; qr.map_item_operand = NULL; qr.operandexist = (bool *) palloc0(sizeof(bool) * query->size); qr.lenght = query->size; doc = get_docrep(txt, &qr, &doclen); if (!doc) { pfree(qr.operandexist); return 0.0; } Wdoc = calc_score_docr(arrdata, doc, doclen, &qr, method); if ((method & RANK_NORM_LOGLENGTH) && txt->size > 0) Wdoc /= log((double) (count_length(txt) + 1)); if (method & RANK_NORM_LENGTH) { len = count_length(txt); if (len > 0) Wdoc /= (double) len; } if ((method & RANK_NORM_UNIQ) && txt->size > 0) Wdoc /= (double) (txt->size); if ((method & RANK_NORM_LOGUNIQ) && txt->size > 0) Wdoc /= log((double) (txt->size + 1)) / log(2.0); pfree(doc); pfree(qr.operandexist); return (float4) Wdoc; }

德哥 2019-12-01 23:40:16 0 浏览量 回答数 0

问题

10个迷惑新手的Cocoa,Objective-c开发难点和问题? 400 报错

爱吃鱼的程序员 2020-05-31 00:44:29 0 浏览量 回答数 1

问题

【分享】WeX5的正确打开方式(3)——绑定机制

小太阳1号 2019-12-01 21:23:54 5393 浏览量 回答数 3

问题

【精品问答】110+数据挖掘面试题集合

珍宝珠 2019-12-01 21:56:45 2713 浏览量 回答数 3

回答

在云栖社区的问答区,有一位网友提到有一个问题: 表里相似数据太多,想删除相似度高的数据,有什么办法能实现吗? 例如: 银屑病怎么治? 银屑病怎么治疗? 银屑病怎么治疗好? 银屑病怎么能治疗好? 等等 解这个问题的思路 .1. 首先如何判断内容的相似度,PostgreSQL中提供了中文分词,pg_trgm(将字符串切成多个不重复的token,计算两个字符串的相似度) . 对于本题,我建议采取中文分词的方式,首先将内容拆分成词组。 .2. 在拆分成词组后,首先分组聚合,去除完全重复的数据。 .3. 然后自关联生成笛卡尔(矩阵),计算出每条记录和其他记录的相似度。相似度的算法很简单,重叠的token数量除以集合的token去重后的数量。 .4. 根据相似度,去除不需要的数据。 这里如果数据量非常庞大,使用专业的分析编程语言会更好例如 PL/R。 实操的例子: 首先要安装PostgreSQL 中文分词插件 (阿里云AliCloudDB PostgreSQL已包含这个插件,用法参考官方手册) git clone https://github.com/jaiminpan/pg_jieba.git mv pg_jieba $PGSRC/contrib/ export PATH=/home/digoal/pgsql9.5/bin:$PATH cd $PGSRC/contrib/pg_jieba make clean;make;make install git clone https://github.com/jaiminpan/pg_scws.git mv pg_jieba $PGSRC/contrib/ export PATH=/home/digoal/pgsql9.5/bin:$PATH cd $PGSRC/contrib/pg_scws make clean;make;make install 创建插件 psql # create extension pg_jieba; # create extension pg_scws; 创建测试CASE create table tdup1 (id int primary key, info text); create extension pg_trgm; insert into tdup1 values (1, '银屑病怎么治?'); insert into tdup1 values (2, '银屑病怎么治疗?'); insert into tdup1 values (3, '银屑病怎么治疗好?'); insert into tdup1 values (4, '银屑病怎么能治疗好?'); 这两种分词插件,可以任选一种。 postgres=# select to_tsvector('jiebacfg', info),* from tdup1 ; to_tsvector | id | info ---------------------+----+---------------------- '治':3 '银屑病':1 | 1 | 银屑病怎么治? '治疗':3 '银屑病':1 | 2 | 银屑病怎么治疗? '治疗':3 '银屑病':1 | 3 | 银屑病怎么治疗好? '治疗':4 '银屑病':1 | 4 | 银屑病怎么能治疗好? (4 rows) postgres=# select to_tsvector('scwscfg', info),* from tdup1 ; to_tsvector | id | info -----------------------------------+----+---------------------- '治':2 '银屑病':1 | 1 | 银屑病怎么治? '治疗':2 '银屑病':1 | 2 | 银屑病怎么治疗? '好':3 '治疗':2 '银屑病':1 | 3 | 银屑病怎么治疗好? '好':4 '治疗':3 '能':2 '银屑病':1 | 4 | 银屑病怎么能治疗好? (4 rows) 创建三个函数, 计算2个数组的集合(去重后的集合) postgres=# create or replace function array_union(text[], text[]) returns text[] as $$ select array_agg(c1) from (select c1 from unnest($1||$2) t(c1) group by c1) t; $$ language sql strict; CREATE FUNCTION 数组去重 postgres=# create or replace function array_dist(text[]) returns text[] as $$ select array_agg(c1) from (select c1 from unnest($1) t(c1) group by c1) t; $$ language sql strict; CREATE FUNCTION 计算两个数组的重叠部分(去重后的重叠部分) postgres=# create or replace function array_share(text[], text[]) returns text[] as $$ select array_agg(unnest) from (select unnest($1) intersect select unnest($2) group by 1) t; $$ language sql strict; CREATE FUNCTION 笛卡尔结果是这样的: regexp_split_to_array((regexp_replace(to_tsvector('jiebacfg',info)::text,'(:d+)', '', 'g')),' ') 用于将info转换成数组。 postgres=# with t(c1,c2,c3) as (select id,info,array_dist(regexp_split_to_array((regexp_replace(to_tsvector('jiebacfg',info)::text,'(:\d+)', '', 'g')),' ')) from tdup1) select * from (select t1.c1 t1c1,t2.c1 t2c1,t1.c2 t1c2,t2.c2 t2c2,t1.c3 t1c3,t2.c3 t2c3,round(array_length(array_share(t1.c3,t2.c3),1)::numeric/array_length(array_union(t1.c3,t2.c3),1),2) simulate from t t1,t t2) t; t1c1 | t2c1 | t1c2 | t2c2 | t1c3 | t2c3 | simulate ------+------+----------------------+----------------------+-------------------+-------------------+---------- 1 | 1 | 银屑病怎么治? | 银屑病怎么治? | {'银屑病','治'} | {'银屑病','治'} | 1.00 1 | 2 | 银屑病怎么治? | 银屑病怎么治疗? | {'银屑病','治'} | {'银屑病','治疗'} | 0.33 1 | 3 | 银屑病怎么治? | 银屑病怎么治疗好? | {'银屑病','治'} | {'银屑病','治疗'} | 0.33 1 | 4 | 银屑病怎么治? | 银屑病怎么能治疗好? | {'银屑病','治'} | {'银屑病','治疗'} | 0.33 2 | 1 | 银屑病怎么治疗? | 银屑病怎么治? | {'银屑病','治疗'} | {'银屑病','治'} | 0.33 2 | 2 | 银屑病怎么治疗? | 银屑病怎么治疗? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 2 | 3 | 银屑病怎么治疗? | 银屑病怎么治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 2 | 4 | 银屑病怎么治疗? | 银屑病怎么能治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 3 | 1 | 银屑病怎么治疗好? | 银屑病怎么治? | {'银屑病','治疗'} | {'银屑病','治'} | 0.33 3 | 2 | 银屑病怎么治疗好? | 银屑病怎么治疗? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 3 | 3 | 银屑病怎么治疗好? | 银屑病怎么治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 3 | 4 | 银屑病怎么治疗好? | 银屑病怎么能治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 4 | 1 | 银屑病怎么能治疗好? | 银屑病怎么治? | {'银屑病','治疗'} | {'银屑病','治'} | 0.33 4 | 2 | 银屑病怎么能治疗好? | 银屑病怎么治疗? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 4 | 3 | 银屑病怎么能治疗好? | 银屑病怎么治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 4 | 4 | 银屑病怎么能治疗好? | 银屑病怎么能治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 (16 rows) 以上生成的实际上是一个矩阵,simulate就是矩阵中我们需要计算的相似度: 我们在去重计算时不需要所有的笛卡尔积,只需要这个矩阵对角线的上部分或下部分数据即可。 所以加个条件就能完成。 postgres=# with t(c1,c2,c3) as (select id,info,array_dist(regexp_split_to_array((regexp_replace(to_tsvector('jiebacfg',info)::text,'(:\d+)', '', 'g')),' ')) from tdup1) select * from (select t1.c1 t1c1,t2.c1 t2c1,t1.c2 t1c2,t2.c2 t2c2,t1.c3 t1c3,t2.c3 t2c3,round(array_length(array_share(t1.c3,t2.c3),1)::numeric/array_length(array_union(t1.c3,t2.c3),1),2) simulate from t t1,t t2 where t1.c1<>t2.c1 and t1.c1<t2.c1) t; t1c1 | t2c1 | t1c2 | t2c2 | t1c3 | t2c3 | simulate ------+------+--------------------+----------------------+-------------------+-------------------+---------- 1 | 2 | 银屑病怎么治? | 银屑病怎么治疗? | {'银屑病','治'} | {'银屑病','治疗'} | 0.33 1 | 3 | 银屑病怎么治? | 银屑病怎么治疗好? | {'银屑病','治'} | {'银屑病','治疗'} | 0.33 1 | 4 | 银屑病怎么治? | 银屑病怎么能治疗好? | {'银屑病','治'} | {'银屑病','治疗'} | 0.33 2 | 3 | 银屑病怎么治疗? | 银屑病怎么治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 2 | 4 | 银屑病怎么治疗? | 银屑病怎么能治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 3 | 4 | 银屑病怎么治疗好? | 银屑病怎么能治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 (6 rows) 开始对这些数据去重,去重的第一步,明确simulate, 例如相似度大于0.5的,需要去重。 postgres=# with t(c1,c2,c3) as (select id,info,array_dist(regexp_split_to_array((regexp_replace(to_tsvector('jiebacfg',info)::text,'(:\d+)', '', 'g')),' ')) from tdup1) select * from (select t1.c1 t1c1,t2.c1 t2c1,t1.c2 t1c2,t2.c2 t2c2,t1.c3 t1c3,t2.c3 t2c3,round(array_length(array_share(t1.c3,t2.c3),1)::numeric/array_length(array_union(t1.c3,t2.c3),1),2) simulate from t t1,t t2 where t1.c1<>t2.c1 and t1.c1<t2.c1) t where simulate>0.5; t1c1 | t2c1 | t1c2 | t2c2 | t1c3 | t2c3 | simulate ------+------+--------------------+----------------------+-------------------+-------------------+---------- 2 | 3 | 银屑病怎么治疗? | 银屑病怎么治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 2 | 4 | 银屑病怎么治疗? | 银屑病怎么能治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 3 | 4 | 银屑病怎么治疗好? | 银屑病怎么能治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 (3 rows) 去重第二步,将t2c1列的ID对应的记录删掉即可。 delete from tdup1 where id in (with t(c1,c2,c3) as (select id,info,array_dist(regexp_split_to_array((regexp_replace(to_tsvector('jiebacfg',info)::text,'(:\d+)', '', 'g')),' ')) from tdup1) select t2c1 from (select t1.c1 t1c1,t2.c1 t2c1,t1.c2 t1c2,t2.c2 t2c2,t1.c3 t1c3,t2.c3 t2c3,round(array_length(array_share(t1.c3,t2.c3),1)::numeric/array_length(array_union(t1.c3,t2.c3),1),2) simulate from t t1,t t2 where t1.c1<>t2.c1 and t1.c1<t2.c1) t where simulate>0.5); 例如 : postgres=# insert into tdup1 values (11, '白血病怎么治?'); INSERT 0 1 postgres=# insert into tdup1 values (22, '白血病怎么治疗?'); INSERT 0 1 postgres=# insert into tdup1 values (13, '白血病怎么治疗好?'); INSERT 0 1 postgres=# insert into tdup1 values (24, '白血病怎么能治疗好?'); INSERT 0 1 postgres=# postgres=# with t(c1,c2,c3) as (select id,info,array_dist(regexp_split_to_array((regexp_replace(to_tsvector('jiebacfg',info)::text,'(:\d+)', '', 'g')),' ')) from tdup1) select * from (select t1.c1 t1c1,t2.c1 t2c1,t1.c2 t1c2,t2.c2 t2c2,t1.c3 t1c3,t2.c3 t2c3,round(array_length(array_share(t1.c3,t2.c3),1)::numeric/array_length(array_union(t1.c3,t2.c3),1),2) simulate from t t1,t t2 where t1.c1<>t2.c1 and t1.c1<t2.c1) t where simulate>0.5; t1c1 | t2c1 | t1c2 | t2c2 | t1c3 | t2c3 | simulate ------+------+--------------------+----------------------+-------------------+-------------------+---------- 2 | 3 | 银屑病怎么治疗? | 银屑病怎么治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 2 | 4 | 银屑病怎么治疗? | 银屑病怎么能治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 3 | 4 | 银屑病怎么治疗好? | 银屑病怎么能治疗好? | {'银屑病','治疗'} | {'银屑病','治疗'} | 1.00 22 | 24 | 白血病怎么治疗? | 白血病怎么能治疗好? | {'治疗','白血病'} | {'治疗','白血病'} | 1.00 13 | 22 | 白血病怎么治疗好? | 白血病怎么治疗? | {'治疗','白血病'} | {'治疗','白血病'} | 1.00 13 | 24 | 白血病怎么治疗好? | 白血病怎么能治疗好? | {'治疗','白血病'} | {'治疗','白血病'} | 1.00 (6 rows) postgres=# begin; BEGIN postgres=# delete from tdup1 where id in (with t(c1,c2,c3) as postgres(# (select id,info,array_dist(regexp_split_to_array((regexp_replace(to_tsvector('jiebacfg',info)::text,'(:\d+)', '', 'g')),' ')) from tdup1) postgres(# select t2c1 from (select t1.c1 t1c1,t2.c1 t2c1,t1.c2 t1c2,t2.c2 t2c2,t1.c3 t1c3,t2.c3 t2c3,round(array_length(array_share(t1.c3,t2.c3),1)::numeric/array_length(array_union(t1.c3,t2.c3),1),2) postgres(# simulate from t t1,t t2 where t1.c1<>t2.c1 and t1.c1<t2.c1) t where simulate>0.5); DELETE 4 postgres=# select * from tdup1 ; id | info ----+-------------------- 1 | 银屑病怎么治? 2 | 银屑病怎么治疗? 11 | 白血病怎么治? 13 | 白血病怎么治疗好? (4 rows) 用数据库解会遇到的问题, 因为我们的JOIN filter是<>和<,用不上hashjoin。 数据量比较大的情况下,耗时会非常的长。 postgres=# explain delete from tdup1 where id in (with t(c1,c2,c3) as (select id,info,array_dist(regexp_split_to_array((regexp_replace(to_tsvector('jiebacfg',info)::text,'(:\d+)', '', 'g')),' ')) from tdup1) select t2c1 from (select t1.c1 t1c1,t2.c1 t2c1,t1.c2 t1c2,t2.c2 t2c2,t1.c3 t1c3,t2.c3 t2c3,round(array_length(array_share(t1.c3,t2.c3),1)::numeric/array_length(array_union(t1.c3,t2.c3),1),2) simulate from t t1,t t2 where t1.c1<>t2.c1 and t1.c1<t2.c1) t where simulate>0.5); QUERY PLAN ---------------------------------------------------------------------------------------------------------------------- Delete on tdup1 (cost=10005260133.58..10005260215.84 rows=2555 width=34) -> Hash Join (cost=10005260133.58..10005260215.84 rows=2555 width=34) Hash Cond: (tdup1.id = "ANY_subquery".t2c1) -> Seq Scan on tdup1 (cost=0.00..61.10 rows=5110 width=10) -> Hash (cost=10005260131.08..10005260131.08 rows=200 width=32) -> HashAggregate (cost=10005260129.08..10005260131.08 rows=200 width=32) Group Key: "ANY_subquery".t2c1 -> Subquery Scan on "ANY_subquery" (cost=10000002667.20..10005252911.99 rows=2886838 width=32) -> Subquery Scan on t (cost=10000002667.20..10005224043.61 rows=2886838 width=4) Filter: (t.simulate > 0.5) CTE t -> Seq Scan on tdup1 tdup1_1 (cost=0.00..2667.20 rows=5110 width=36) -> Nested Loop (cost=10000000000.00..10005113119.99 rows=8660513 width=68) Join Filter: ((t1.c1 <> t2.c1) AND (t1.c1 < t2.c1)) -> CTE Scan on t t1 (cost=0.00..102.20 rows=5110 width=36) -> CTE Scan on t t2 (cost=0.00..102.20 rows=5110 width=36) (16 rows) 其他更优雅的方法,使用PLR或者R进行矩阵运算,得出结果后再进行筛选。 PLR R 或者使用MPP数据库例如Greenplum加上R和madlib可以对非常庞大的数据进行处理。 MADLIB MPP 小结 这里用到了PG的什么特性? .1. 中文分词 .2. 窗口查询功能 (本例中没有用到,但是如果你的数据没有主键时,则需要用ctid和row_number来定位到一条唯一记录)

德哥 2019-12-02 01:43:06 0 浏览量 回答数 0

回答

mport de.zbit.jcmapper.distance.DistanceTanimotoimport de.zbit.jcmapper.distance.IDistanceMeasureimport de.zbit.jcmapper.fingerprinters.EncodingFingerprintimport de.zbit.jcmapper.fingerprinters.features.FeatureMapimport de.zbit.jcmapper.fingerprinters.features.IFeatureimport de.zbit.jcmapper.fingerprinters.topological.Encoding2DAllShortestPathimport de.zbit.jcmapper.fingerprinters.topological.Encoding2DCATSimport de.zbit.jcmapper.fingerprinters.topological.Encoding2DECFPimport de.zbit.jcmapper.io.reader.RandomAccessMDLReaderimport de.zbit.jcmapper.io.writer.ExporterFullFingerprintCSVimport de.zbit.jcmapper.io.writer.ExporterFullFingerprintTABUnfoldedimport de.zbit.jcmapper.io.writer.ExporterLinearimport de.zbit.jcmapper.io.writer.ExporterSDFPropertyimport java.io.FileWriterimport java.util.Listimport java.io.File val similarity: IDistanceMeasure = new DistanceTanimoto()val fingerprinter: Encoding2DAllShortestPath = new Encoding2DAllShortestPath()val rawFeatures2: List[IFeature] = fingerprinter.getFingerprint(reader.getMol(0))val rawFeatures: List[IFeature] = fingerprinter.getFingerprint(reader.getMol(1))def getSimilarity( id1:Int, id2:Int ) : Double = { val featureMaps: List[FeatureMap] = new ArrayList[FeatureMap]() featureMaps.add(new FeatureMap(rawFeatures)) featureMaps.add(new FeatureMap(rawFeatures2)) val temp: Double = similarity.getSimilarity(featureMaps.get(0), featureMaps.get(1)) return temp val func = combinations.map(x => { getSimilarity(0, 1) }).take(5) Name: org.apache.spark.SparkExceptionMessage: Task not serializableStackTrace: at org.apache.spark.util.ClosureCleaner$.ensureSerializable(ClosureCleaner.scala:345) at org.apache.spark.util.ClosureCleaner$.org$apache$spark$util$ClosureCleaner$$clean(ClosureCleaner.scala:335) at org.apache.spark.util.ClosureCleaner$.clean(ClosureCleaner.scala:159) at org.apache.spark.SparkContext.clean(SparkContext.scala:2292) at org.apache.spark.rdd.RDD$$anonfun$map$1.apply(RDD.scala:371) at org.apache.spark.rdd.RDD$$anonfun$map$1.apply(RDD.scala:370) at org.apache.spark.rdd.RDDOperationScope$.withScope(RDDOperationScope.scala:151) at org.apache.spark.rdd.RDDOperationScope$.withScope(RDDOperationScope.scala:112) at org.apache.spark.rdd.RDD.withScope(RDD.scala:363) at org.apache.spark.rdd.RDD.map(RDD.scala:370) ... 48 elidedCaused by: java.io.NotSerializableException: de.zbit.jcmapper.io.reader.RandomAccessMDLReader` 我读了其他线程并理解我必须将变量和函数放在一个对象中以使其可序列化。但是,如果我这样做,我遇到了空指针异常错误: object Holder{val reader:RandomAccessMDLReader = new RandomAccessMDLReader(new File("datasets/internal.sdf"))val similarity: IDistanceMeasure = new DistanceTanimoto()val fingerprinter: Encoding2DAllShortestPath = new Encoding2DAllShortestPath()val rawFeatures2: List[IFeature] = fingerprinter.getFingerprint(reader.getMol(0))val rawFeatures: List[IFeature] = fingerprinter.getFingerprint(reader.getMol(1))def getSimilarity( id1:Int, id2:Int ) : Double = { val featureMaps: List[FeatureMap] = new ArrayList[FeatureMap]() featureMaps.add(new FeatureMap(rawFeatures)) featureMaps.add(new FeatureMap(rawFeatures2)) val temp: Double = similarity.getSimilarity(featureMaps.get(0), featureMaps.get(1)) return temp } val func = combinations.map(x => {Holder.getSimilarity(0, 1)}).take(5) Name: org.apache.spark.SparkExceptionMessage: Job aborted due to stage failure: Task 0 in stage 0.0 failed 4 times, most recent failure: Lost task 0.3 in stage 0.0 (TID 3, ip-10-245-2-223.ec2.internal, executor 1): java.lang.NullPointerException at de.zbit.jcmapper.io.reader.RandomAccessMDLReader.setRanges(Unknown Source) at de.zbit.jcmapper.io.reader.RandomAccessMDLReader.<init>(Unknown Source) at $line49.$read$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$Holder$.<init>(<console>:78) at $line49.$read$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw.Holder$lzycompute(<console>:77) at $line49.$read$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw.Holder(<console>:77) at $line57.$read$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$anonfun$1.apply(<console>:85) at $line57.$read$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$anonfun$1.apply(<console>:84) at scala.collection.Iterator$$anon$11.next(Iterator.scala:409) at scala.collection.Iterator$$anon$10.next(Iterator.scala:393) at scala.collection.Iterator$class.foreach(Iterator.scala:893) at scala.collection.AbstractIterator.foreach(Iterator.scala:1336) at scala.collection.generic.Growable$class.$plus$plus$eq(Growable.scala:59) at scala.collection.mutable.ArrayBuffer.$plus$plus$eq(ArrayBuffer.scala:104) at scala.collection.mutable.ArrayBuffer.$plus$plus$eq(ArrayBuffer.scala:48) at scala.collection.TraversableOnce$class.to(TraversableOnce.scala:310) at scala.collection.AbstractIterator.to(Iterator.scala:1336) at scala.collection.TraversableOnce$class.toBuffer(TraversableOnce.scala:302) at scala.collection.AbstractIterator.toBuffer(Iterator.scala:1336) at scala.collection.TraversableOnce$class.toArray(TraversableOnce.scala:289) at scala.collection.AbstractIterator.toArray(Iterator.scala:1336)` 对于阅读部分,我可以使用巨大的LinkedHashMap并存储所有化合物。但是,我必须使用getSimilarity()函数来使用第三方jar计算相似度。因此,即使我只使用getSimilarity()函数,如果我把它放在一个对象中,我也有空指针异常。如果我把它放在对象之外,那我的任务就不是可序列化的问题。因此,我有几个问题,我无法找到一个好的答案: Spark是否支持将第三方Jar映射到每个执行程序?在读者文件中,Spark是否将读取器类分发到每个执行器中并单独读取文件或作为整体读取文件,然后将文件分发到每个执行器上的小块中?为什么它显示空指针异常问题?似乎该对象确实解决了序列化问题,但没有解决空指针异常。

社区小助手 2019-12-02 01:46:28 0 浏览量 回答数 0

问题

我也想写点什么

猥琐屯公爵 2019-12-01 21:55:06 6158 浏览量 回答数 2

问题

【今日算法】5月18日-编辑距离

游客ih62co2qqq5ww 2020-05-19 07:57:13 5 浏览量 回答数 1

问题

【精品问答】python技术1000问(2)

问问小秘 2019-12-01 22:03:02 68 浏览量 回答数 0

问题

算法工程师必知必会10大基础算法! 6月23日 【今日算法】

游客ih62co2qqq5ww 2020-06-23 13:36:00 6 浏览量 回答数 1

问题

【教程免费下载】信息物理融合系统(CPS)设计

玄学酱 2019-12-01 22:08:06 1332 浏览量 回答数 1

回答

敢用自己的名字做软件名字的,都有非常强大的自信。比如,垠语言什么的。 awk的命名得自于它的三个创始人姓别的首字母,都是80来岁的老爷爷了。当然也有四个人的组合:流行的GoF设计模式。但对于我这游戏爱好者来说,想到的竟然是三位一体,果然是不争气啊。 它长的很像C,为什么这么有名,除了它强大的功能,我们姑且认为a这个字母比较靠前吧。awk比sed简单,它更像一门编程语言。 打印某一列 下面,这几行代码的效果基本是相同的:打印文件中的第一列。 这可能是awk最常用的功能了:打印文件中的某一列。它智能的去切分你的数据,不管是空格,还是TAB,大概率是你想要的。 对于csv这种文件来说,分隔的字符是,。AWK使用-F参数去指定。以下代码打印csv文件中的第1和第2列。 awk -F "," '{print $1,$2}' file 由此,我们可以看出一个基本的awk命令的组成部分。 一般的开发语言,数组下标是以0开始的,但awk的列$是以1开始的,而0指的是原始字符串。 网络状态统计 本小节,采用awk统计netstat命令的一些网络状态,来看一下awk语言的基本要素。netstat的输出类似于: 其中,第6列,标明了网络连接所处于的网络状态。我们先给出awk命令,看一下统计结果。 netstat -ant | awk ' \ BEGIN{print "State","Count" } \ /^tcp/ \ { rt[$6]++ } \ END{ for(i in rt){print i,rt[i]} }' 输出结果为: State Count LAST_ACK 1 LISTEN 64 CLOSE_WAIT 43 ESTABLISHED 719 SYN_SENT 5 TIME_WAIT 146 下面这张图会配合以上命令详细说明,希望你能了解awk的精髓。 乍一看,好吓人的命令,但是很简单。awk和我们通常的程序不太一样,它分为四个部分。 1、BEGIN 开头部分,可选的。用来设置一些参数,输出一些表头,定义一些变量等。上面的命令仅打印了一行信息而已。 2、END 结尾部分,可选的。用来计算一些汇总逻辑,或者输出这些内容。上面的命令,使用简单的for循环,输出了数组rt中的内容。 3、Pattern 匹配部分,依然可选。用来匹配一些需要处理的行。上面的命令,只匹配tcp开头的行,其他的不进入处理。 4、Action 模块。主要逻辑体,按行处理,统计打印,都可以。 注意点 1、awk的主程序部分使用单引号‘包围,而不能是双引号 2、awk的列开始的index是0,而不是1 例子 我们从几个简单的例子,来看下awk的作用。 1、输出Recv-Q不为0的记录 netstat -ant | awk '$2 > 0 {print}' 2、外网连接数,根据ip分组 netstat -ant | awk '/^tcp/{print $4}' | awk -F: '!/^:/{print $1}' | sort | uniq -c 3、打印RSS物理内存占用 top -b -n 1 | awk 'NR>7{rss+=$6}END{print rss} 4、过滤(去掉)空白行 awk 'NF' file 5、打印奇数行 awk 'a=!a' file 6、输出行数 awk 'END{print NR}' file 这些命令,是需要了解awk的一些内部变量的,接下来我们来介绍。 内置变量 FS 下面的两个命令是等价的 。 awk -F ':' '{print $3}' file awk 'BEGIN{FS=":"}{print $3}' file BEGIN块中的FS,就是内部变量,可以直接指定或者输出。如果你的文件既有用,分隔的,也有用:分割的,FS甚至可以指定多个分隔符同时起作用。 FS="[,:|]" 其他 OFS 指定输出内容的分割符,列数非常多的时候,简化操作。相似命令: awk -F ':' '{print $1,"-",$2,"-",$4}' file awk 'BEGIN{FS=":";OFS="-"}{print $1,$2,$4}' file NF 列数。非常有用,比如,过滤一些列数不满足条件的内容。 awk -F, '{if(NF==3){print}}' file NR 行号,例如,下面两个命令是等价的。 cat -n file awk '{print NR,$0}' file RS 记录分隔标志 ORS 指定记录输出的分隔标志 FILENAME 当前处理的文件名称,在一次性处理多个文件时非常有用 编程语言特性 数学运算 从上面的代码可以看出,awk可以做一些简单的运算。它的语言简洁,不需要显示的定义变量的类型。 比如上面的rt[$6]++,就已经默认定义了一个叫做rt的hash(array?),里面的key是网络状态,而value是可以进行运算的(+-*/%)。 包含一些内置的数学运算(有限) int log sqrt exp sin cos atan2 rand srand 字符串操作 类似其他语言,awk也内置了很多字符串操作函数。它本来就是处理字符串的,所以必须强大。 length(str) #获取字符串长度 split(input-string,output-array,separator) substr(input-string, location, length) 语言特性 awk是个小型的编程语言,看它的基本语法,如果你需要复杂一点的逻辑,请自行深入了解,包括一些时间处理函数: # logic if(x=a){} if(x=a){}else{} while(x=a){break;continue;} do{}while(x=a) for(;;){} # array arr[key] = value for(key in arr){arr[key]} delete arr[key] asort(arr) #简单排序 据说,awk可以胜任所有的文本操作。因为它本身就是一门语言啊。 End 曾经使用awk编写过复杂的日志处理和统计程序。虽然比写sed舒畅了很多,但还是备受煎熬。更加上现在有各种nawk,gawk版本之间的区别,所以业务复杂度一增长,就习惯性的转向更加简洁、工具更全的python。 awk处理一些简单的文本还是极其方便的,最常用的还是打印某一列之类的,包括一些格式化输出。对于awk,要简单的滚瓜烂熟,复杂的耳熟能详,毕竟有些大牛,就喜欢写这种脚本呢。 注明:转载于小姐妹养的狗

剑曼红尘 2020-04-01 11:18:23 0 浏览量 回答数 0

问题

最大限度利用 JavaScript 和 Ajax 性能:报错

kun坤 2020-06-05 22:56:50 0 浏览量 回答数 1

回答

HashMap HashMap 底层是基于 数组 + 链表 组成的,不过在 jdk1.7 和 1.8 中具体实现稍有 不同 其实1.7一个很明显需要优化的地方就是: 当 Hash 冲突严重时,在桶上形成的链表会变的越来越长,这样在查询时的效 率就会越来越低;时间复杂度为 O(N)。 因此 1.8 中重点优化了这个查询效率。 1.8 HashMap 结构图 JDK 1.8 对 HashMap 进行了修改: 最大的不同就是利用了红黑树,其由数组+链表+红黑树组成。 JDK 1.7 中,查找元素时,根据 hash 值能够快速定位到数组的具体下标, 但之后需要顺着链表依次比较才能查找到需要的元素,时间复杂度取决于链 表的长度,为 O(N)。 为了降低这部分的开销,在 JDK 1.8 中,当链表中的元素超过 8 个以后,会 将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。 JDK 1.8 使用 Node(1.7 为 Entry) 作为链表的数据结点,仍然包含 key, value,hash 和 next 四个属性。 红黑树的情况使用的是 TreeNode。 根据数组元素中,第一个结点数据类型是 Node 还是 TreeNode 可以判断该位 置下是链表还是红黑树。 核心成员变量于 1.7 类似,增加了核心变量,如下表。 属性说明TREEIFY_THRESHOLD用于判断是否需要将链表转换为红黑树的阈值,默认 为 8。 put步骤: 判断当前桶是否为空,空的就需要初始化(resize 中会判断是否进行初始 化)。 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空,为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。 如果当前桶有值( Hash 冲突),那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等,相等就赋值给 e,在第 8 步的时候会统一进 行赋值及返回。 如果当前桶为红黑树,那就要按照红黑树的方式写入数据。 如果是个链表,就需要将当前的 key、value 封装成一个新节点写入到当前桶的 后面(形成链表)。 接着判断当前链表的大小是否大于预设的阈值,大于时就要转换为红黑树。 如果在遍历过程中找到 key 相同时直接退出遍历。 如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。 后判断是否需要进行扩容. get 方法看起来就要简单许多了。 首先将 key hash 之后取得所定位的桶。 如果桶为空则直接返回 null 。 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key,是 就直接返回 value。 如果第一个不匹配,则判断它的下一个是红黑树还是链表。 红黑树就按照树的查找方式返回值。 不然就按照链表的方式遍历匹配返回值。 从这两个核心方法(get/put)可以看出 1.8 中对大链表做了优化,修改为红黑树之 后查询效率直接提高到了 O(logn)。 但是 HashMap 原有的问题也都存在,比如在并发场景下使用时容易出现死循环。 但是为什么呢?简单分析下。 看过上文的还记得在 HashMap 扩容的时候会调用 resize() 方法,就是这里的并 发操作容易在一个桶上形成环形链表;这样当获取一个不存在的 key 时,计算出的 index 正好是环形链表的下标就会出现死循环。 如下图: HashTable HashTable 容器使用 synchronized来保证线程安全,但在线程竞争激烈的情况下 HashTable 的效 率非常低下。 当一个线程访问 HashTable 的同步方法时,其他线程访问 HashTable 的同步方 法可能会进入阻塞或轮询状态。 HashTable 容器在竞争激烈的并发环境下表现出效率低下的原因,是因为所有 访问它的线程都必须竞争同一把锁,假如容器里有多把锁,每一把锁用于锁容 器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就 不会存在锁竞争,从而可以有效的提高并发访问效率,这就是 ConcurrentHashMap(JDK 1.7) 使用的 锁分段技术。 ConcurrentHashMap 将数据分成一段一段的存储,然后给每一段数据配一把 锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他 线程访问。 有些方法需要跨段,比如 size() 和 containsValue(),它们可能需要锁定整个表 而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所 有段的锁。 按顺序 很重要,否则极有可能出现死锁,在 ConcurrentHashMap 内部,段数 组是 final 的,并且其成员变量实际也是 final 的,但是,仅仅是将数组声明为 final 的并不保证数组成员也是 final 的,需要实现上的保证。这可以确保不会 出现死锁,因为获得锁的顺序是固定的。 HashTable 的迭代器是强一致性的,而 ConcurrentHashMap 是弱一致的。 ConcurrentHashMap 的 get,clear,iterator 方法都是弱一致性的。 初识ConcurrentHashMap Concurrent翻译过来是并发的意思,字面理解它的作用是处理并发情况的 HashMap。 通过前面的学习,我们知道多线程并发下 HashMap 是不安全的(如死循环),更普遍 的是多线程并发下,由于堆内存对于各个线程是共享的,而 HashMap 的 put 方法 不是原子操作,假设Thread1先 put 值,然后 sleep 2秒(也可以是系统时间片切换失 去执行权),在这2秒内值被Thread2改了,Thread1“醒来”再 get 的时候发现已经不 是原来的值了,这就容易出问题。 那么如何避免这种多线程出错的情况呢? 常规思路就是给 HashMap 的 put 方法加锁(synchronized),保证同一个时刻只允 许一个线程拥有对 hashmap 有写的操作权限即可。然而假如线程1中操作耗时,其 他需要操作该 hashmap 的线程就需要在门口排队半天,严重影响用户体验, HashTable 就是这样子做的。 举个生活中的例子,很多银行除了存取钱,还支持存取贵重物品,贵重物品都放在 保险箱里,把 HashMap 和 HashTable 比作银行,结构: 把线程比作人,对应的情况如下: 多线程下用 HashMap 不确定性太高,有破产的风险,不能选;用 HashTable 不会 破产,但是用户体验不太好,那么怎样才能做到多人存取既不影响他人存值,又不 用排队呢? 有人提议搞个「银行者联盟」,多开几个像HashTable 这种「带锁」的银行就好 了,有多少人办理业务,就开多少个银行,一对一服务,这个区都是大老板,开银 行的成本都是小钱,于是「银行者联盟」成立了。 接下来的情况是这样的:比如用户A和用户B一起去银行存各自的项链,这个「银行 者联盟」操作后,然后对用户A说,1号银行现在没人你可以去那存,不用排队,然 后用户A就去1号银行存项链,1号银行把用户A接进门,马上拉闸,然后把用户A的 项链放在第x行第x个保险箱,等用户A办妥离开后,再开闸;对于用户B同理。此时 不管用户A和用户B在各自银行里面待多久都不会影响到彼此,不用担心自己的项链 被人偷换了。这就是ConcurrentHashMap的设计思路,用一个图来理解 从上图可以看出,此时锁的是对应的单个银行,而不是整个「银行者联盟」。分析 下这种设计的特点: 多个银行组成的「银行者联盟」 当有人来办理业务时,「银行者联盟」需要确定这个人去哪个银行 当此人去到指定银行办理业务后,该银行上锁,其他人不能同时执行修改操作,直 到此人离开后解锁. ConcurrentHashMap源码解析 ConcurrentHashMap 同样也分为 1.7 、1.8 版,两者在实现上略有不同。 先来看看 1.7 的实现,下面是结构图: 如图所示,是由 Segment 数组、HashEntry 组成,和 HashMap 一样,仍然是数组 加链表。主要是通过分段锁实现的。 关于分段锁 段Segment继承了重入锁ReentrantLock,有了锁的功能,每个锁控制的是一段, 当每个Segment越来越大时,锁的粒度就变得有些大了。 分段锁的优势在于保证在操作不同段 map 的时候可以并发执行,操作同段 map 的时候,进行锁的竞争和等待。这相对于直接对整个map同步 synchronized是有优势的。 缺点在于分成很多段时会比较浪费内存空间(不连续,碎片化); 操作map时竞争 同一个分段锁的概率非常小时,分段锁反而会造成更新等操作的长时间等待; 当 某个段很大时,分段锁的性能会下降。 1.7 已经解决了并发问题,并且能支持 N 个 Segment 这么多次数的并发,但依然存 在 HashMap 在 1.7 版本中的问题。 那就是查询遍历链表效率太低。 因此 1.8 做了一些数据结构上的调整。 首先来看下底层的组成结构: 其实和 1.8 HashMap 结构类似,当链表节点数超过指定阈值的话,也是会转换成红 黑树的,大体结构也是一样的。 那么 JDK 1.8 ConcurrentHashMap 到底是如何实现线程安全的? 答案:其中抛弃了原有的Segment 分段锁,而采用了 CAS + synchronized 来保证 并发安全性。(cas:比较并替换) **① 基本组成 ** 抛弃了 JDK 1.7 中原有的 Segment 分段锁,而采用了 CAS + synchronized 来 保证并发安全性。 将JDK 1.7 中存放数据的 HashEntry 改为 Node,但作用是相同的。、 我们来看看 ConcurrentHashMap 的几个重要属性. 重要组成元素 Node:链表中的元素为 Node 对象。他是链表上的一个节点,内部存储了 key、 value 值,以及他的下一 个节点的引用。这样一系列的 Node 就串成一串,组成一 个链表。 ForwardingNode:当进行扩容时,要把链表迁移到新的哈希表,在做这个操作 时,会在把数组中的头节点替换为 ForwardingNode 对象。ForwardingNode 中不 保存 key 和 value,只保存了扩容后哈希表 (nextTable)的引用。此时查找相应 node 时,需要去 nextTable 中查找。 TreeBin:当链表转为红黑树后,数组中保存的引用为 TreeBin,TreeBin 内部不保 存 key/value,他保存了 TreeNode 的 list 以及红黑树 root。 TreeNode:红黑树的节点。 **② put 方法过程 ** 存储结构定义了容器的 “形状”,那容器内的东西按照什么规则来放呢?换句话讲, 某个 key 是按 照什么逻辑放入容器的对应位置呢? 我们假设要存入的 key 为对象 x,这个过程如下 : 1、通过对象 x 的 hashCode () 方法获取其 hashCode; 2、将 hashCode 映射到数组的某个位置上; 3、把该元素存储到该位置的链表中。 put 方法用来把一个键值对存储到 map 中。代码如下: 实际调用的是 putVal 方 法,第三个参数传入 false,控制 key 存在时覆盖原来的值。 请先看完代码注释,有个大致的了解,然后我们更加详细的学习一下: 判断存储的 key、value 是否为空,若为空,则抛出异常,否则,进入步骤 2。 计算 key 的 hash 值,随后进入自旋,该自旋可以确保成功插入数据,若 table 表为空或者长度为 0,则初始化 table 表,否则,进入步骤 3。 根据 key 的 hash 值取出 table 表中的结点元素,若取出的结点为空(该桶为 空),则使用 CAS 将 key、value、hash 值生成的结点放入桶中。否则,进入 步骤 4。 若该结点的的 hash 值为 MOVED(-1),则对该桶中的结点进行转移,否则, 进入步骤 5。 5 . 对桶中的第一个结点(即 table 表中的结点)进行加锁,对该桶进行遍历,桶中 的结点的 hash 值与 key 值与给定的 hash 值和 key 值相等,则根据标识选择是 否进行更新操作(用给定的 value 值替换该结点的 value 值),若遍历完桶仍 没有找到 hash 值与 key 值和指定的 hash 值与 key 值相等的结点,则直接新生 一个结点并赋值为之前后一个结点的下一个结点。进入步骤 6。 若 binCount 值达到红黑树转化的阈值,则将桶中的结构转化为红黑树存储, 后,增加 binCount 的值。 如果桶中的第一个元素的 hash 值大于 0,说明是链表结构,则对链表插入或者 更新。 如果桶中的第一个元素是 TreeBin,说明是红黑树结构,则按照红黑树的方式进 行插入或者更新。 在锁的保护下,插入或者更新完毕后,如果是链表结构,需要判断链表中元素 的数量是否超过 8(默认),一旦超过,就需要考虑进行数组扩容,或者是链表 转红黑树。 扩容 什么时候会扩容? 使用put()添加元素时会调用addCount(),内部检查sizeCtl看是否需要扩容。 tryPresize()被调用,此方法被调用有两个调用点: 链表转红黑树(put()时检查)时如果table容量小于64(MIN_TREEIFY_CAPACITY),则会 触发扩容。 调用putAll()之类一次性加入大量元素,会触发扩容。 addCount() addCount()与tryPresize()实现很相似,我们先以addCount()分析下扩容逻辑: **1.链表转红黑树 ** 首先我们要理解为什么 Map 需要扩容,这是因为我们采用哈希表存储数据,当固定 大小的哈希表存 储数据越来越多时,链表长度会越来越长,这会造成 put 和 get 的 性能下降。此时我们希望哈希表中多一些桶位,预防链表继续堆积的更长。 ConcurrentHashMap 有链表转红黑树的操作,以提高查找的速度,红黑树时间复 杂度为 O (logn),而链表是 O (n/2),因此只在 O (logn)<O (n/2) 时才会进行转换, 也就是以 8 作为分界点。 接下来我们分析 treeifyBin 方法代码,这个代码中会选择是把此时保存数据所在的 链表转为红黑树,还是对整个哈希表扩容。 treeifyBin 不一定就会进行红黑树转换,也可能是仅仅做数组扩容。 构造完TreeBin这个空节点之后,就开始构造红黑树,首先是第一个节点,左右 子节点设置为空,作为红黑树的root节点,设置为黑色,父节点为空。 然后在每次添加完一个节点之后,都会调用balanceInsertion方法来维持这是一 个红黑树的属性和平衡性。红黑树所有操作的复杂度都是O(logn),所以当元素量比 较大的时候,效率也很高。 **数组扩容 ** 我们大致了解了 ConcurrentHashMap 的存储结构,那么我们思考一个问题,当数 组中保存的链表越来越多,那么再存储进来的元素大概率会插入到现有的链表中, 而不是使用数组中剩下的空位。 这样会造成数组中保存的链表越来越长,由此导致 哈希表查找速度下降,从 O (1) 慢慢趋近于链表 的时间复杂度 O (n/2),这显然违背 了哈希表的初衷。 所以 ConcurrentHashMap 会做一个操作, 称为扩容。也就是把数组长度变大,增 加更多的空位出来,终目的就是预防链表过长,这样查找的时间复杂度才会趋向于 O (1)。扩容的操作并不会在数组没有空位时才进行,因为在桶位快满时, 新保存元 素更大的概率会命中已经使用的位置,那么可能后几个桶位很难被使用,而链表却 越来 越长了。ConcurrentHashMap 会在更合适的时机进行扩容,通常是在数组中 75% 的位置被使用 时。 其实以上内容和 HashMap 类似,ConcurrentHashMap 此外提供了线程安全的保 证,它主要是通 过 CAS 和 Synchronized 关键字来实现,我们在源码分析中再详细 来看。 我们做一下总结: 1、ConcurrentHashMap 采用数组 + 链表 + 红黑树的存储结构; 2、存入的 Key 值通过自己的 hashCode 映射到数组的相应位置; 3、ConcurrentHashMap 为保障查询效率,在特定的时候会对数据增加长度,这个 操作叫做扩容; 4、当链表长度增加到 8 时,可能会触发链表转为红黑树(数组长度如果小于 64, 优先扩容,具体 看后面源码分析)。 接下来,我们的源码分析就从 ConcurrentHashMap 的构成、保存元素、哈希算 法、扩容、查找数 据这几个方面来进行 扩容后数组容量为原来的 2 倍。 **数据迁移( 扩容时的线程安全) ** ConcurrentHashMap 的扩容时机和 HashMap 相同,都是在 put 方法的后一步 检查是否需要扩容,如果需要则进行扩容,但两者扩容的过程完全不同, ConcurrentHashMap 扩容的方法叫做 transfer,从 put 方法的 addCount 方法进 去,就能找到 transfer 方法,transfer 方法的主要思路是: 首先需要把老数组的值全部拷贝到扩容之后的新数组上,先从数组的队尾开始 拷贝; 拷贝数组的槽点时,先把原数组槽点锁住,保证原数组槽点不能操作,成功拷 贝到新数组时,把 原数组槽点赋值为转移节点; 这时如果有新数据正好需要 put 到此槽点时,发现槽点为转移节点,就会一直 等待,所以在扩容完成之前,该槽点对应的数据是不会发生变化的; 从数组的尾部拷贝到头部,每拷贝成功一次,就把原数组中的节点设置成转移 节点; 直到所有数组数据都拷贝到新数组时,直接把新数组整个赋值给数组容器,拷 贝完成 putTreeVal()与此方法遍历方式类似不再介绍。  ④ get 方法过程 ConcurrentHashMap 读的话,就比较简单,先获取数组的下标,然后通过判断数 组下标的 key 是 否和我们的 key 相等,相等的话直接返回,如果下标的槽点是链表 或红黑树的话,分别调用相应的 查找数据的方法,整体思路和 HashMap 很像,源 码如下: 计算 hash 值。 根据 hash 值找到数组对应位置: (n – 1) & h。 根据该位置处结点性质进行相应查找。 如果该位置为 null,那么直接返回 null。 如果该位置处的结点刚好就是需要的,返回该结点的值即可。 如果该位置结点的 hash 值小于 0,说明正在扩容,或者是红黑树。 如果以上 3 条都不满足,那就是链表,进行遍历比对即可。 ** 初始化数组 ** 数组初始化时,首先通过自旋来保证一定可以初始化成功,然后通过 CAS 设置 SIZECTL 变量的值,来保证同一时刻只能有一个线程对数组进行初始化,CAS 成功 之后,还会再次判断当前数组是否已经初始化完成,如果已经初始化完成,就不会 再次初始化,通过自旋 + CAS + 双重 check 等 手段保证了数组初始化时的线程安 全,源码如下: 里面有个关键的值 sizeCtl,这个值有多个含义。 1、-1 代表有线程正在创建 table; 2、-N 代表有 N-1 个线程正在复制 table; 3、在 table 被初始化前,代表 根据构造函数传入的值计算出的应被初始化的大小; 4、在 table 被初始化后,则被 设置为 table 大小 的 75%,代表 table 的容量(数组容量)。 initTable 中使用到 1 和 4,2 和 3 在其它方法中会有使用。下面我们可以先看下 ConcurrentHashMap 的构造方法,里面会使用上面的 3 最后来回顾总结下HashMap和ConcurrentHashMap对比 ConcurrentHashMap 和 HashMap 两者的相同之处: 1.数组、链表结构几乎相同,所以底层对数据结构的操作思路是相同的(只是思路 相同,底层实现 不同); 2.都实现了 Map 接口,继承了 AbstractMap 抽象类,所以大多数的方法也都是相 同的, HashMap 有的方法,ConcurrentHashMap 几乎都有,所以当我们需要从 HashMap 切换到 ConcurrentHashMap 时,无需关心两者之间的兼容问题 不同点: 1.红黑树结构略有不同,HashMap 的红黑树中的节点叫做 TreeNode,TreeNode 不仅仅有属 性,还维护着红黑树的结构,比如说查找,新增等等; ConcurrentHashMap 中红黑树被拆分成 两块,TreeNode 仅仅维护的属性和查找 功能,新增了 TreeBin,来维护红黑树结构,并负责根 节点的加锁和解锁; 2.新增 ForwardingNode (转移)节点,扩容的时候会使用到,通过使用该节点, 来保证扩容时的线程安全。

剑曼红尘 2020-03-25 11:21:44 0 浏览量 回答数 0

回答

92题 一般来说,建立INDEX有以下益处:提高查询效率;建立唯一索引以保证数据的唯一性;设计INDEX避免排序。 缺点,INDEX的维护有以下开销:叶节点的‘分裂’消耗;INSERT、DELETE和UPDATE操作在INDEX上的维护开销;有存储要求;其他日常维护的消耗:对恢复的影响,重组的影响。 需要建立索引的情况:为了建立分区数据库的PATITION INDEX必须建立; 为了保证数据约束性需要而建立的INDEX必须建立; 为了提高查询效率,则考虑建立(是否建立要考虑相关性能及维护开销); 考虑在使用UNION,DISTINCT,GROUP BY,ORDER BY等字句的列上加索引。 91题 作用:加快查询速度。原则:(1) 如果某属性或属性组经常出现在查询条件中,考虑为该属性或属性组建立索引;(2) 如果某个属性常作为最大值和最小值等聚集函数的参数,考虑为该属性建立索引;(3) 如果某属性经常出现在连接操作的连接条件中,考虑为该属性或属性组建立索引。 90题 快照Snapshot是一个文件系统在特定时间里的镜像,对于在线实时数据备份非常有用。快照对于拥有不能停止的应用或具有常打开文件的文件系统的备份非常重要。对于只能提供一个非常短的备份时间而言,快照能保证系统的完整性。 89题 游标用于定位结果集的行,通过判断全局变量@@FETCH_STATUS可以判断是否到了最后,通常此变量不等于0表示出错或到了最后。 88题 事前触发器运行于触发事件发生之前,而事后触发器运行于触发事件发生之后。通常事前触发器可以获取事件之前和新的字段值。语句级触发器可以在语句执行前或后执行,而行级触发在触发器所影响的每一行触发一次。 87题 MySQL可以使用多个字段同时建立一个索引,叫做联合索引。在联合索引中,如果想要命中索引,需要按照建立索引时的字段顺序挨个使用,否则无法命中索引。具体原因为:MySQL使用索引时需要索引有序,假设现在建立了"name,age,school"的联合索引,那么索引的排序为: 先按照name排序,如果name相同,则按照age排序,如果age的值也相等,则按照school进行排序。因此在建立联合索引的时候应该注意索引列的顺序,一般情况下,将查询需求频繁或者字段选择性高的列放在前面。此外可以根据特例的查询或者表结构进行单独的调整。 86题 建立索引的时候一般要考虑到字段的使用频率,经常作为条件进行查询的字段比较适合。如果需要建立联合索引的话,还需要考虑联合索引中的顺序。此外也要考虑其他方面,比如防止过多的所有对表造成太大的压力。这些都和实际的表结构以及查询方式有关。 85题 存储过程是一组Transact-SQL语句,在一次编译后可以执行多次。因为不必重新编译Transact-SQL语句,所以执行存储过程可以提高性能。触发器是一种特殊类型的存储过程,不由用户直接调用。创建触发器时会对其进行定义,以便在对特定表或列作特定类型的数据修改时执行。 84题 存储过程是用户定义的一系列SQL语句的集合,涉及特定表或其它对象的任务,用户可以调用存储过程,而函数通常是数据库已定义的方法,它接收参数并返回某种类型的值并且不涉及特定用户表。 83题 减少表连接,减少复杂 SQL,拆分成简单SQL。减少排序:非必要不排序,利用索引排序,减少参与排序的记录数。尽量避免 select *。尽量用 join 代替子查询。尽量少使用 or,使用 in 或者 union(union all) 代替。尽量用 union all 代替 union。尽量早的将无用数据过滤:选择更优的索引,先分页再Join…。避免类型转换:索引失效。优先优化高并发的 SQL,而不是执行频率低某些“大”SQL。从全局出发优化,而不是片面调整。尽可能对每一条SQL进行 explain。 82题 如果条件中有or,即使其中有条件带索引也不会使用(要想使用or,又想让索引生效,只能将or条件中的每个列都加上索引)。对于多列索引,不是使用的第一部分,则不会使用索引。like查询是以%开头。如果列类型是字符串,那一定要在条件中将数据使用引号引用起来,否则不使用索引。如果mysql估计使用全表扫描要比使用索引快,则不使用索引。例如,使用<>、not in 、not exist,对于这三种情况大多数情况下认为结果集很大,MySQL就有可能不使用索引。 81题 主键不能重复,不能为空,唯一键不能重复,可以为空。建立主键的目的是让外键来引用。一个表最多只有一个主键,但可以有很多唯一键。 80题 空值('')是不占用空间的,判断空字符用=''或者<>''来进行处理。NULL值是未知的,且占用空间,不走索引;判断 NULL 用 IS NULL 或者 is not null ,SQL 语句函数中可以使用 ifnull ()函数来进行处理。无法比较 NULL 和 0;它们是不等价的。无法使用比较运算符来测试 NULL 值,比如 =, <, 或者 <>。NULL 值可以使用 <=> 符号进行比较,该符号与等号作用相似,但对NULL有意义。进行 count ()统计某列的记录数的时候,如果采用的 NULL 值,会被系统自动忽略掉,但是空值是统计到其中。 79题 HEAP表是访问数据速度最快的MySQL表,他使用保存在内存中的散列索引。一旦服务器重启,所有heap表数据丢失。BLOB或TEXT字段是不允许的。只能使用比较运算符=,<,>,=>,= <。HEAP表不支持AUTO_INCREMENT。索引不可为NULL。 78题 如果想输入字符为十六进制数字,可以输入带有单引号的十六进制数字和前缀(X),或者只用(Ox)前缀输入十六进制数字。如果表达式上下文是字符串,则十六进制数字串将自动转换为字符串。 77题 Mysql服务器通过权限表来控制用户对数据库的访问,权限表存放在mysql数据库里,由mysql_install_db脚本初始化。这些权限表分别user,db,table_priv,columns_priv和host。 76题 在缺省模式下,MYSQL是autocommit模式的,所有的数据库更新操作都会即时提交,所以在缺省情况下,mysql是不支持事务的。但是如果你的MYSQL表类型是使用InnoDB Tables 或 BDB tables的话,你的MYSQL就可以使用事务处理,使用SET AUTOCOMMIT=0就可以使MYSQL允许在非autocommit模式,在非autocommit模式下,你必须使用COMMIT来提交你的更改,或者用ROLLBACK来回滚你的更改。 75题 它会停止递增,任何进一步的插入都将产生错误,因为密钥已被使用。 74题 创建索引的时候尽量使用唯一性大的列来创建索引,由于使用b+tree做为索引,以innodb为例,一个树节点的大小由“innodb_page_size”,为了减少树的高度,同时让一个节点能存放更多的值,索引列尽量在整数类型上创建,如果必须使用字符类型,也应该使用长度较少的字符类型。 73题 当MySQL单表记录数过大时,数据库的CRUD性能会明显下降,一些常见的优化措施如下: 限定数据的范围: 务必禁止不带任何限制数据范围条件的查询语句。比如:我们当用户在查询订单历史的时候,我们可以控制在一个月的范围内。读/写分离: 经典的数据库拆分方案,主库负责写,从库负责读。垂直分区: 根据数据库里面数据表的相关性进行拆分。简单来说垂直拆分是指数据表列的拆分,把一张列比较多的表拆分为多张表。水平分区: 保持数据表结构不变,通过某种策略存储数据分片。这样每一片数据分散到不同的表或者库中,达到了分布式的目的。水平拆分可以支撑非常大的数据量。 72题 乐观锁失败后会抛出ObjectOptimisticLockingFailureException,那么我们就针对这块考虑一下重试,自定义一个注解,用于做切面。针对注解进行切面,设置最大重试次数n,然后超过n次后就不再重试。 71题 一致性非锁定读讲的是一条记录被加了X锁其他事务仍然可以读而不被阻塞,是通过innodb的行多版本实现的,行多版本并不是实际存储多个版本记录而是通过undo实现(undo日志用来记录数据修改前的版本,回滚时会用到,用来保证事务的原子性)。一致性锁定读讲的是我可以通过SELECT语句显式地给一条记录加X锁从而保证特定应用场景下的数据一致性。 70题 数据库引擎:尤其是mysql数据库只有是InnoDB引擎的时候事物才能生效。 show engines 查看数据库默认引擎;SHOW TABLE STATUS from 数据库名字 where Name='表名' 如下;SHOW TABLE STATUS from rrz where Name='rrz_cust';修改表的引擎alter table table_name engine=innodb。 69题 如果是等值查询,那么哈希索引明显有绝对优势,因为只需要经过一次算法即可找到相应的键值;当然了,这个前提是,键值都是唯一的。如果键值不是唯一的,就需要先找到该键所在位置,然后再根据链表往后扫描,直到找到相应的数据;如果是范围查询检索,这时候哈希索引就毫无用武之地了,因为原先是有序的键值,经过哈希算法后,有可能变成不连续的了,就没办法再利用索引完成范围查询检索;同理,哈希索引也没办法利用索引完成排序,以及like ‘xxx%’ 这样的部分模糊查询(这种部分模糊查询,其实本质上也是范围查询);哈希索引也不支持多列联合索引的最左匹配规则;B+树索引的关键字检索效率比较平均,不像B树那样波动幅度大,在有大量重复键值情况下,哈希索引的效率也是极低的,因为存在所谓的哈希碰撞问题。 68题 decimal精度比float高,数据处理比float简单,一般优先考虑,但float存储的数据范围大,所以范围大的数据就只能用它了,但要注意一些处理细节,因为不精确可能会与自己想的不一致,也常有关于float 出错的问题。 67题 datetime、timestamp精确度都是秒,datetime与时区无关,存储的范围广(1001-9999),timestamp与时区有关,存储的范围小(1970-2038)。 66题 Char使用固定长度的空间进行存储,char(4)存储4个字符,根据编码方式的不同占用不同的字节,gbk编码方式,不论是中文还是英文,每个字符占用2个字节的空间,utf8编码方式,每个字符占用3个字节的空间。Varchar保存可变长度的字符串,使用额外的一个或两个字节存储字符串长度,varchar(10),除了需要存储10个字符,还需要1个字节存储长度信息(10),超过255的长度需要2个字节来存储。char和varchar后面如果有空格,char会自动去掉空格后存储,varchar虽然不会去掉空格,但在进行字符串比较时,会去掉空格进行比较。Varbinary保存变长的字符串,后面不会补\0。 65题 首先分析语句,看看是否load了额外的数据,可能是查询了多余的行并且抛弃掉了,可能是加载了许多结果中并不需要的列,对语句进行分析以及重写。分析语句的执行计划,然后获得其使用索引的情况,之后修改语句或者修改索引,使得语句可以尽可能的命中索引。如果对语句的优化已经无法进行,可以考虑表中的数据量是否太大,如果是的话可以进行横向或者纵向的分表。 64题 建立索引的时候一般要考虑到字段的使用频率,经常作为条件进行查询的字段比较适合。如果需要建立联合索引的话,还需要考虑联合索引中的顺序。此外也要考虑其他方面,比如防止过多的所有对表造成太大的压力。这些都和实际的表结构以及查询方式有关。 63题 存储过程是一些预编译的SQL语句。1、更加直白的理解:存储过程可以说是一个记录集,它是由一些T-SQL语句组成的代码块,这些T-SQL语句代码像一个方法一样实现一些功能(对单表或多表的增删改查),然后再给这个代码块取一个名字,在用到这个功能的时候调用他就行了。2、存储过程是一个预编译的代码块,执行效率比较高,一个存储过程替代大量T_SQL语句 ,可以降低网络通信量,提高通信速率,可以一定程度上确保数据安全。 62题 密码散列、盐、用户身份证号等固定长度的字符串应该使用char而不是varchar来存储,这样可以节省空间且提高检索效率。 61题 推荐使用自增ID,不要使用UUID。因为在InnoDB存储引擎中,主键索引是作为聚簇索引存在的,也就是说,主键索引的B+树叶子节点上存储了主键索引以及全部的数据(按照顺序),如果主键索引是自增ID,那么只需要不断向后排列即可,如果是UUID,由于到来的ID与原来的大小不确定,会造成非常多的数据插入,数据移动,然后导致产生很多的内存碎片,进而造成插入性能的下降。总之,在数据量大一些的情况下,用自增主键性能会好一些。 60题 char是一个定长字段,假如申请了char(10)的空间,那么无论实际存储多少内容。该字段都占用10个字符,而varchar是变长的,也就是说申请的只是最大长度,占用的空间为实际字符长度+1,最后一个字符存储使用了多长的空间。在检索效率上来讲,char > varchar,因此在使用中,如果确定某个字段的值的长度,可以使用char,否则应该尽量使用varchar。例如存储用户MD5加密后的密码,则应该使用char。 59题 一. read uncommitted(读取未提交数据) 即便是事务没有commit,但是我们仍然能读到未提交的数据,这是所有隔离级别中最低的一种。 二. read committed(可以读取其他事务提交的数据)---大多数数据库默认的隔离级别 当前会话只能读取到其他事务提交的数据,未提交的数据读不到。 三. repeatable read(可重读)---MySQL默认的隔离级别 当前会话可以重复读,就是每次读取的结果集都相同,而不管其他事务有没有提交。 四. serializable(串行化) 其他会话对该表的写操作将被挂起。可以看到,这是隔离级别中最严格的,但是这样做势必对性能造成影响。所以在实际的选用上,我们要根据当前具体的情况选用合适的。 58题 B+树的高度一般为2-4层,所以查找记录时最多只需要2-4次IO,相对二叉平衡树已经大大降低了。范围查找时,能通过叶子节点的指针获取数据。例如查找大于等于3的数据,当在叶子节点中查到3时,通过3的尾指针便能获取所有数据,而不需要再像二叉树一样再获取到3的父节点。 57题 因为事务在修改页时,要先记 undo,在记 undo 之前要记 undo 的 redo, 然后修改数据页,再记数据页修改的 redo。 Redo(里面包括 undo 的修改) 一定要比数据页先持久化到磁盘。 当事务需要回滚时,因为有 undo,可以把数据页回滚到前镜像的状态,崩溃恢复时,如果 redo log 中事务没有对应的 commit 记录,那么需要用 undo把该事务的修改回滚到事务开始之前。 如果有 commit 记录,就用 redo 前滚到该事务完成时并提交掉。 56题 redo log是物理日志,记录的是"在某个数据页上做了什么修改"。 binlog是逻辑日志,记录的是这个语句的原始逻辑,比如"给ID=2这一行的c字段加1"。 redo log是InnoDB引擎特有的;binlog是MySQL的Server层实现的,所有引擎都可以使用。 redo log是循环写的,空间固定会用完:binlog 是可以追加写入的。"追加写"是指binlog文件写到一定大小后会切换到下一个,并不会覆盖以前的日志。 最开始 MySQL 里并没有 InnoDB 引擎,MySQL 自带的引擎是 MyISAM,但是 MyISAM 没有 crash-safe 的能力,binlog日志只能用于归档。而InnoDB 是另一个公司以插件形式引入 MySQL 的,既然只依靠 binlog 是没有 crash-safe 能力的,所以 InnoDB 使用另外一套日志系统,也就是 redo log 来实现 crash-safe 能力。 55题 重做日志(redo log)      作用:确保事务的持久性,防止在发生故障,脏页未写入磁盘。重启数据库会进行redo log执行重做,达到事务一致性。 回滚日志(undo log)  作用:保证数据的原子性,保存了事务发生之前的数据的一个版本,可以用于回滚,同时可以提供多版本并发控制下的读(MVCC),也即非锁定读。 二进 制日志(binlog)    作用:用于主从复制,实现主从同步;用于数据库的基于时间点的还原。 错误日志(errorlog) 作用:Mysql本身启动,停止,运行期间发生的错误信息。 慢查询日志(slow query log)  作用:记录执行时间过长的sql,时间阈值可以配置,只记录执行成功。 一般查询日志(general log)    作用:记录数据库的操作明细,默认关闭,开启后会降低数据库性能 。 中继日志(relay log) 作用:用于数据库主从同步,将主库发来的bin log保存在本地,然后从库进行回放。 54题 MySQL有三种锁的级别:页级、表级、行级。 表级锁:开销小,加锁快;不会出现死锁;锁定粒度大,发生锁冲突的概率最高,并发度最低。 行级锁:开销大,加锁慢;会出现死锁;锁定粒度最小,发生锁冲突的概率最低,并发度也最高。 页面锁:开销和加锁时间界于表锁和行锁之间;会出现死锁;锁定粒度界于表锁和行锁之间,并发度一般。 死锁: 是指两个或两个以上的进程在执行过程中。因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去。 死锁的关键在于:两个(或以上)的Session加锁的顺序不一致。 那么对应的解决死锁问题的关键就是:让不同的session加锁有次序。死锁的解决办法:1.查出的线程杀死。2.设置锁的超时时间。3.指定获取锁的顺序。 53题 当多个用户并发地存取数据时,在数据库中就会产生多个事务同时存取同一数据的情况。若对并发操作不加控制就可能会读取和存储不正确的数据,破坏数据库的一致性(脏读,不可重复读,幻读等),可能产生死锁。 乐观锁:乐观锁不是数据库自带的,需要我们自己去实现。 悲观锁:在进行每次操作时都要通过获取锁才能进行对相同数据的操作。 共享锁:加了共享锁的数据对象可以被其他事务读取,但不能修改。 排他锁:当数据对象被加上排它锁时,一个事务必须得到锁才能对该数据对象进行访问,一直到事务结束锁才被释放。 行锁:就是给某一条记录加上锁。 52题 Mysql是关系型数据库,MongoDB是非关系型数据库,数据存储结构的不同。 51题 关系型数据库优点:1.保持数据的一致性(事务处理)。 2.由于以标准化为前提,数据更新的开销很小。 3. 可以进行Join等复杂查询。 缺点:1、为了维护一致性所付出的巨大代价就是其读写性能比较差。 2、固定的表结构。 3、高并发读写需求。 4、海量数据的高效率读写。 非关系型数据库优点:1、无需经过sql层的解析,读写性能很高。 2、基于键值对,数据没有耦合性,容易扩展。 3、存储数据的格式:nosql的存储格式是key,value形式、文档形式、图片形式等等,文档形式、图片形式等等,而关系型数据库则只支持基础类型。 缺点:1、不提供sql支持,学习和使用成本较高。 2、无事务处理,附加功能bi和报表等支持也不好。 redis与mongoDB的区别: 性能:TPS方面redis要大于mongodb。 可操作性:mongodb支持丰富的数据表达,索引,redis较少的网络IO次数。 可用性:MongoDB优于Redis。 一致性:redis事务支持比较弱,mongoDB不支持事务。 数据分析:mongoDB内置了数据分析的功能(mapreduce)。 应用场景:redis数据量较小的更性能操作和运算上,MongoDB主要解决海量数据的访问效率问题。 50题 如果Redis被当做缓存使用,使用一致性哈希实现动态扩容缩容。如果Redis被当做一个持久化存储使用,必须使用固定的keys-to-nodes映射关系,节点的数量一旦确定不能变化。否则的话(即Redis节点需要动态变化的情况),必须使用可以在运行时进行数据再平衡的一套系统,而当前只有Redis集群可以做到这样。 49题 分区可以让Redis管理更大的内存,Redis将可以使用所有机器的内存。如果没有分区,你最多只能使用一台机器的内存。分区使Redis的计算能力通过简单地增加计算机得到成倍提升,Redis的网络带宽也会随着计算机和网卡的增加而成倍增长。 48题 除了缓存服务器自带的缓存失效策略之外(Redis默认的有6种策略可供选择),我们还可以根据具体的业务需求进行自定义的缓存淘汰,常见的策略有两种: 1.定时去清理过期的缓存; 2.当有用户请求过来时,再判断这个请求所用到的缓存是否过期,过期的话就去底层系统得到新数据并更新缓存。 两者各有优劣,第一种的缺点是维护大量缓存的key是比较麻烦的,第二种的缺点就是每次用户请求过来都要判断缓存失效,逻辑相对比较复杂!具体用哪种方案,可以根据应用场景来权衡。 47题 Redis提供了两种方式来作消息队列: 一个是使用生产者消费模式模式:会让一个或者多个客户端监听消息队列,一旦消息到达,消费者马上消费,谁先抢到算谁的,如果队列里没有消息,则消费者继续监听 。另一个就是发布订阅者模式:也是一个或多个客户端订阅消息频道,只要发布者发布消息,所有订阅者都能收到消息,订阅者都是平等的。 46题 Redis的数据结构列表(list)可以实现延时队列,可以通过队列和栈来实现。blpop/brpop来替换lpop/rpop,blpop/brpop阻塞读在队列没有数据的时候,会立即进入休眠状态,一旦数据到来,则立刻醒过来。Redis的有序集合(zset)可以用于实现延时队列,消息作为value,时间作为score。Zrem 命令用于移除有序集中的一个或多个成员,不存在的成员将被忽略。当 key 存在但不是有序集类型时,返回一个错误。 45题 1.热点数据缓存:因为Redis 访问速度块、支持的数据类型比较丰富。 2.限时业务:expire 命令设置 key 的生存时间,到时间后自动删除 key。 3.计数器:incrby 命令可以实现原子性的递增。 4.排行榜:借助 SortedSet 进行热点数据的排序。 5.分布式锁:利用 Redis 的 setnx 命令进行。 6.队列机制:有 list push 和 list pop 这样的命令。 44题 一致哈希 是一种特殊的哈希算法。在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n 个关键字重新映射,其中K是关键字的数量, n是槽位数量。然而在传统的哈希表中,添加或删除一个槽位的几乎需要对所有关键字进行重新映射。 43题 RDB的优点:适合做冷备份;读写服务影响小,reids可以保持高性能;重启和恢复redis进程,更加快速。RDB的缺点:宕机会丢失最近5分钟的数据;文件特别大时可能会暂停数毫秒,或者甚至数秒。 AOF的优点:每个一秒执行fsync操作,最多丢失1秒钟的数据;以append-only模式写入,没有任何磁盘寻址的开销;文件过大时,不会影响客户端读写;适合做灾难性的误删除的紧急恢复。AOF的缺点:AOF日志文件比RDB数据快照文件更大,支持写QPS比RDB支持的写QPS低;比RDB脆弱,容易有bug。 42题 对于Redis而言,命令的原子性指的是:一个操作的不可以再分,操作要么执行,要么不执行。Redis的操作之所以是原子性的,是因为Redis是单线程的。而在程序中执行多个Redis命令并非是原子性的,这也和普通数据库的表现是一样的,可以用incr或者使用Redis的事务,或者使用Redis+Lua的方式实现。对Redis来说,执行get、set以及eval等API,都是一个一个的任务,这些任务都会由Redis的线程去负责执行,任务要么执行成功,要么执行失败,这就是Redis的命令是原子性的原因。 41题 (1)twemproxy,使用方式简单(相对redis只需修改连接端口),对旧项目扩展的首选。(2)codis,目前用的最多的集群方案,基本和twemproxy一致的效果,但它支持在节点数改变情况下,旧节点数据可恢复到新hash节点。(3)redis cluster3.0自带的集群,特点在于他的分布式算法不是一致性hash,而是hash槽的概念,以及自身支持节点设置从节点。(4)在业务代码层实现,起几个毫无关联的redis实例,在代码层,对key进行hash计算,然后去对应的redis实例操作数据。这种方式对hash层代码要求比较高,考虑部分包括,节点失效后的代替算法方案,数据震荡后的自动脚本恢复,实例的监控,等等。 40题 (1) Master最好不要做任何持久化工作,如RDB内存快照和AOF日志文件 (2) 如果数据比较重要,某个Slave开启AOF备份数据,策略设置为每秒同步一次 (3) 为了主从复制的速度和连接的稳定性,Master和Slave最好在同一个局域网内 (4) 尽量避免在压力很大的主库上增加从库 (5) 主从复制不要用图状结构,用单向链表结构更为稳定,即:Master <- Slave1 <- Slave2 <- Slave3...这样的结构方便解决单点故障问题,实现Slave对Master的替换。如果Master挂了,可以立刻启用Slave1做Master,其他不变。 39题 比如订单管理,热数据:3个月内的订单数据,查询实时性较高;温数据:3个月 ~ 12个月前的订单数据,查询频率不高;冷数据:1年前的订单数据,几乎不会查询,只有偶尔的查询需求。热数据使用mysql进行存储,需要分库分表;温数据可以存储在ES中,利用搜索引擎的特性基本上也可以做到比较快的查询;冷数据可以存放到Hive中。从存储形式来说,一般情况冷数据存储在磁带、光盘,热数据一般存放在SSD中,存取速度快,而温数据可以存放在7200转的硬盘。 38题 当访问量剧增、服务出现问题(如响应时间慢或不响应)或非核心服务影响到核心流程的性能时,仍然需要保证服务还是可用的,即使是有损服务。系统可以根据一些关键数据进行自动降级,也可以配置开关实现人工降级。降级的最终目的是保证核心服务可用,即使是有损的。而且有些服务是无法降级的(如加入购物车、结算)。 37题 分层架构设计,有一条准则:站点层、服务层要做到无数据无状态,这样才能任意的加节点水平扩展,数据和状态尽量存储到后端的数据存储服务,例如数据库服务或者缓存服务。显然进程内缓存违背了这一原则。 36题 更新数据的时候,根据数据的唯一标识,将操作路由之后,发送到一个 jvm 内部队列中。读取数据的时候,如果发现数据不在缓存中,那么将重新读取数据+更新缓存的操作,根据唯一标识路由之后,也发送同一个 jvm 内部队列中。一个队列对应一个工作线程,每个工作线程串行拿到对应的操作,然后一条一条的执行。 35题 redis分布式锁加锁过程:通过setnx向特定的key写入一个随机值,并同时设置失效时间,写值成功既加锁成功;redis分布式锁解锁过程:匹配随机值,删除redis上的特点key数据,要保证获取数据、判断一致以及删除数据三个操作是原子的,为保证原子性一般使用lua脚本实现;在此基础上进一步优化的话,考虑使用心跳检测对锁的有效期进行续期,同时基于redis的发布订阅优雅的实现阻塞式加锁。 34题 volatile-lru:当内存不足以容纳写入数据时,从已设置过期时间的数据集中挑选最近最少使用的数据淘汰。 volatile-ttl:当内存不足以容纳写入数据时,从已设置过期时间的数据集中挑选将要过期的数据淘汰。 volatile-random:当内存不足以容纳写入数据时,从已设置过期时间的数据集中任意选择数据淘汰。 allkeys-lru:当内存不足以容纳写入数据时,从数据集中挑选最近最少使用的数据淘汰。 allkeys-random:当内存不足以容纳写入数据时,从数据集中任意选择数据淘汰。 noeviction:禁止驱逐数据,当内存使用达到阈值的时候,所有引起申请内存的命令会报错。 33题 定时过期:每个设置过期时间的key都需要创建一个定时器,到过期时间就会立即清除。该策略可以立即清除过期的数据,对内存很友好;但是会占用大量的CPU资源去处理过期的数据,从而影响缓存的响应时间和吞吐量。 惰性过期:只有当访问一个key时,才会判断该key是否已过期,过期则清除。该策略可以最大化地节省CPU资源,却对内存非常不友好。极端情况可能出现大量的过期key没有再次被访问,从而不会被清除,占用大量内存。 定期过期:每隔一定的时间,会扫描一定数量的数据库的expires字典中一定数量的key,并清除其中已过期的key。该策略是前两者的一个折中方案。通过调整定时扫描的时间间隔和每次扫描的限定耗时,可以在不同情况下使得CPU和内存资源达到最优的平衡效果。 32题 缓存击穿,一个存在的key,在缓存过期的一刻,同时有大量的请求,这些请求都会击穿到DB,造成瞬时DB请求量大、压力骤增。如何避免:在访问key之前,采用SETNX(set if not exists)来设置另一个短期key来锁住当前key的访问,访问结束再删除该短期key。 31题 缓存雪崩,是指在某一个时间段,缓存集中过期失效。大量的key设置了相同的过期时间,导致在缓存在同一时刻全部失效,造成瞬时DB请求量大、压力骤增,引起雪崩。而缓存服务器某个节点宕机或断网,对数据库服务器造成的压力是不可预知的,很有可能瞬间就把数据库压垮。如何避免:1.redis高可用,搭建redis集群。2.限流降级,在缓存失效后,通过加锁或者队列来控制读数据库写缓存的线程数量。3.数据预热,在即将发生大并发访问前手动触发加载缓存不同的key,设置不同的过期时间。 30题 缓存穿透,是指查询一个数据库一定不存在的数据。正常的使用缓存流程大致是,数据查询先进行缓存查询,如果key不存在或者key已经过期,再对数据库进行查询,并把查询到的对象,放进缓存。如果数据库查询对象为空,则不放进缓存。一些恶意的请求会故意查询不存在的 key,请求量很大,对数据库造成压力,甚至压垮数据库。 如何避免:1:对查询结果为空的情况也进行缓存,缓存时间设置短一点,或者该 key 对应的数据 insert 了之后清理缓存。2:对一定不存在的 key 进行过滤。可以把所有的可能存在的 key 放到一个大的 Bitmap 中,查询时通过该 bitmap 过滤。 29题 1.memcached 所有的值均是简单的字符串,redis 作为其替代者,支持更为丰富的数据类型。 2.redis 的速度比 memcached 快很多。 3.redis 可以持久化其数据。 4.Redis支持数据的备份,即master-slave模式的数据备份。 5.Redis采用VM机制。 6.value大小:redis最大可以达到1GB,而memcache只有1MB。 28题 Spring Boot 推荐使用 Java 配置而非 XML 配置,但是 Spring Boot 中也可以使用 XML 配置,通过spring提供的@ImportResource来加载xml配置。例如:@ImportResource({"classpath:some-context.xml","classpath:another-context.xml"}) 27题 Spring像一个大家族,有众多衍生产品例如Spring Boot,Spring Security等等,但他们的基础都是Spring的IOC和AOP,IOC提供了依赖注入的容器,而AOP解决了面向切面的编程,然后在此两者的基础上实现了其他衍生产品的高级功能。Spring MVC是基于Servlet的一个MVC框架,主要解决WEB开发的问题,因为 Spring的配置非常复杂,各种xml,properties处理起来比较繁琐。Spring Boot遵循约定优于配置,极大降低了Spring使用门槛,又有着Spring原本灵活强大的功能。总结:Spring MVC和Spring Boot都属于Spring,Spring MVC是基于Spring的一个MVC框架,而Spring Boot是基于Spring的一套快速开发整合包。 26题 YAML 是 "YAML Ain't a Markup Language"(YAML 不是一种标记语言)的递归缩写。YAML 的配置文件后缀为 .yml,是一种人类可读的数据序列化语言,可以简单表达清单、散列表,标量等数据形态。它通常用于配置文件,与属性文件相比,YAML文件就更加结构化,而且更少混淆。可以看出YAML具有分层配置数据。 25题 Spring Boot有3种热部署方式: 1.使用springloaded配置pom.xml文件,使用mvn spring-boot:run启动。 2.使用springloaded本地加载启动,配置jvm参数-javaagent:<jar包地址> -noverify。 3.使用devtools工具包,操作简单,但是每次需要重新部署。 用

游客ih62co2qqq5ww 2020-03-27 23:56:48 0 浏览量 回答数 0

问题

不搞清这8大算法思想,刷再多题效果也不好的 7月23日 【今日算法】

游客ih62co2qqq5ww 2020-07-29 11:10:09 3 浏览量 回答数 1

问题

干货分享:DBA专家门诊一期:索引与sql优化问题汇总

xiaofanqie 2019-12-01 21:24:21 74007 浏览量 回答数 38

回答

回2楼啊里新人的帖子 在日常的业务开发中,常见使用到索引的地方大概有两类: 第一类.做业务约束需求,比如需要保证表中每行的单个字段或者某几个组合字段是唯一的,则可以在表中创建唯一索引; 比如:需要保证test表中插入user_id字段的值不能出现重复,则在设计表的时候,就可以在表中user_id字段上创建一个唯一索引: CREATE TABLE `test` (   `id` int(11) NOT NULL AUTO_INCREMENT,   `user_id` int(11) NOT NULL,   `gmt_create` datetime DEFAULT NULL,   PRIMARY KEY (`id`),   UNIQUE KEY `uk_userid` (`user_id`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8 ; 第二类.提高SQL语句执行速度,可以根据SQL语句的查询条件在表中创建合适的索引,以此来提升SQL语句的执行速度; 此过程好比是去图书找一本书,最慢的方法就是从图书馆的每一层楼每一个书架一本本的找过去;快捷一点的方法就是先通过图书检索来确认这一本书在几楼那个书架上,然后直接去找就可以了;当然创建这个索引也需要有一定的代价,需要存储空间来存放,需要在数据行插入,更新,删除的时候维护索引: 例如: CREATE TABLE `test_record` (   `id` int(11) NOT NULL AUTO_INCREMENT,   `user_id` int(11) NOT NULL,   `gmt_create` datetime DEFAULT NULL,   PRIMARY KEY (`id`) ) ENGINE=InnoDB AUTO_INCREMENT=5635996 DEFAULT CHARSET=utf8 该表有500w的记录,我需要查询20:00后插入的记录有多少条记录: mysql> select count(*) from test_record where gmt_create>'2014-12-17 20:00:00'; +----------+ | count(*) | +----------+ |        1 | +----------+ 1 row in set (1.31 sec) 可以看到查询耗费了1.31秒返回了1行记录,如果我们在gmt_create字段上添加索引: mysql> alter table test_record add index ind_gmt_create(gmt_create); Query OK, 0 rows affected (21.87 sec) Records: 0  Duplicates: 0  Warnings: 0 mysql> select count(*) from test_record where gmt_create>'2014-12-17 20:00:00'; +----------+ | count(*) | +----------+ |        1 | +----------+ 1 row in set (0.01 sec) 查询只消耗了0.01秒中就返回了记录. 总的来说,为SQL语句(select,update,delete)创建必要的索引是必须的,这样虽然有一定的性能和空间消耗,但是是值得,尤其是在大并发的请求下,大量的数据被扫描造成系统IO和CPU资源消耗完,进而导致整个数据库不可服务. ------------------------- 怎么学好数据库是一个比较大题目,数据库不仅仅是写SQL那么简单,即使知道了SQL怎么写,还需要很清楚的知道这条SQL他大概扫描了多少数据,返回多少数据,是否需要创建索引。至于SQL优化是一个比较专业的技术活,但是可以通过学习是可以掌握的,你可以把一条sql从执行不出来优化到瞬间完成执行,这个过程的成就感是信心满满的。学习的方法可以有以下一些过程:1、自己查资料,包括书本,在线文档,google,别人的总结等等,试图自己解决2、多做实验,证明自己的想法以及判断3、如果实在不行,再去论坛问,或者问朋友4、如果问题解决了,把该问题的整个解决方法记录下来,以备后来的需要5、多关注别人的问题,或许以后自己就遇到了,并总是试图去多帮助别人6、习惯从多个方面去考虑问题,并且养成良好的总结习惯 下面是一些国内顶级数据库专家学习数据库的经验分享给大家: http://www.eygle.com/archives/2005/08/ecinieoracleouo.html 其实学习任何东西都是一样,没有太多的捷径可走,必须打好了坚实的基础,才有可以在进一步学习中得到快速提高。王国维在他的《人间词话》中曾经概括了为学的三种境界,我在这里套用一下: 古今之成大事业、大学问者,罔不经过三种之境界。"昨夜西风凋碧树。独上高楼,望尽天涯路。"此第一境界也。"衣带渐宽终不悔,为伊消得人憔悴。"此第二境界也。"众里寻他千百度,蓦然回首,那人却在灯火阑珊处。"此第三境界也。 学习Oracle,这也是你必须经历的三种境界。 第一层境界是说,学习的路是漫漫的,你必须做好充分的思想准备,如果半途而废还不如不要开始。 这里,注意一个"尽"字,在开始学习的过程中,你必须充分阅读Oracle的基础文档,概念手册、管理手册、备份恢复手册等(这些你都可以在http://tahiti.oracle.com 上找到);OCP认证的教材也值得仔细阅读。打好基础之后你才具备了进一步提升的能力,万丈高楼都是由地而起。 第二层境界是说,尽管经历挫折、打击、灰心、沮丧,也都要坚持不放弃,具备了基础知识之后,你可以对自己感兴趣或者工作中遇到的问题进行深入的思考,由浅入深从来都不是轻而易举的,甚至很多时候你会感到自己停滞不前了,但是不要动摇,学习及理解上的突破也需要时间。 第三次境界是说,经历了那么多努力以后,你会发现,那苦苦思考的问题,那百思不得其解的算法原理,原来答案就在手边,你的思路豁然开朗,宛如拨云见月。这个时候,学习对你来说,不再是个难题,也许是种享受,也许成为艺术。 所以如果你想问我如何速成,那我是没有答案的。 不经一番寒彻骨,哪得梅花扑鼻香。 当然这三种境界在实际中也许是交叉的,在不断的学习中,不断有蓦然回首的收获。 我自己在学习的过程中,经常是采用"由点及面法"。 当遇到一个问题后,一定是深入下去,穷究根本,这样你会发现,一个简单的问题也必定会带起一大片的知识点,如果你能对很多问题进行深入思考和研究,那么在深处,你会发现,这些面逐渐接合,慢慢的延伸到oracle的所有层面,逐渐的你就能融会贯通。这时候,你会主动的去尝试全面学习Oracle,扫除你的知识盲点,学习已经成为一种需要。 由实践触发的学习才最有针对性,才更能让你深入的理解书本上的知识,正所谓:" 纸上得来终觉浅,绝知此事要躬行"。实践的经验于我们是至为宝贵的。 如果说有,那么这,就是我的捷径。 想想自己,经常是"每有所获,便欣然忘食", 兴趣才是我们最好的老师。 Oracle的优化是一门学问,也是一门艺术,理解透彻了,你会知道,优化不过是在各种条件之下做出的均衡与折中。 内存、外存;CPU、IO...对这一切你都需要有充分的认识和相当的了解,管理数据库所需要的知识并不单纯。 作为一个数据库管理人员,你需要做的就是能够根据自己的知识以及经验在各种复杂情况下做出快速正确的判断。当问题出现时,你需要知道使用怎样的手段发现问题的根本;找到问题之后,你需要运用你的知识找到解决问题的方法。 这当然并不容易,举重若轻还是举轻若重,取决于你具备怎样的基础以及经验积累。 在网络上,Howard J. Rogers最近创造了一个新词组:Voodoo Tuning,用以形容那些没有及时更新自己的知识技能的所谓的Oracle技术专家。由于知识的陈旧或者理解的肤浅,他们提供的很多调整建议是错误的、容易使人误解的,甚至是荒诞的。他们提供的某些建议在有些情况下也许是正确的,如果你愿意回到Oracle5版或者6版的年代;但是这些建议在Oracle7.0,8.0 或者 Oracle8i以后往往是完全错误的。 后来基于类似问题触发了互联网内Oracle顶级高手的一系列深入讨论,TOM、Jonathan Lewis、HJR等人都参与其中,在我的网站上(www.eygle.com )上对这些内容及相关链接作了简要介绍,有兴趣的可以参考。 HJR给我们提了很好的一个提示:对你所需要调整的内容,你必须具有充分的认识,否则你做出的判断就有可能是错误的。 这也是我想给自己和大家的一个建议: 学习和研究Oracle,严谨和认真必不可少。 当然 你还需要勤奋,我所熟悉的在Oracle领域有所成就的技术人员,他们共同的特点就是勤奋。 如果你觉得掌握的东西没有别人多,那么也许就是因为,你不如别人勤奋。 要是你觉得这一切过于复杂了,那我还有一句简单的话送给大家: 不积跬步,无以至千里。学习正是在逐渐积累过程中的提高。 现在Itpub给我们提供了很好的交流场所,很多问题都可以在这里找到答案,互相讨论,互相学习。这是我们的幸运,我也因此非常感谢这个网络时代。 参考书籍: 如果是一个新人可以先买一些基本的入门书籍,比如MySQL:《 深入浅出MySQL——数据库开发、优化与管理维护 》,在进阶一点的就是《 高性能MySQL(第3版) 》 oracle的参考书籍: http://www.eygle.com/archives/2006/08/oracle_fundbook_recommand.html 最后建议不要在数据库中使用外键,让应用程序来保证。 ------------------------- Re:回 9楼(千鸟) 的帖子 我有一个问题想问问,现在在做一个与图书有关的项目,其中有一个功能是按图书书名搜索相似图书列表,问题不难,但是想优化一下,有如下问题想请教一下: 1、在图书数据库数据表的书名字段里,按图书书名进行关键字搜索,如何快速搜索相关的图书?   现在由于数据不多,直接用的like模糊查找验证功能而已; 如果数据量不大,是可以在数据库中完成搜索的,可以在搜索字段上创建索引,然后进行搜索查询: CREATE TABLE `book` (   `book_id` int(11) NOT NULL AUTO_INCREMENT,   `book_name` varchar(100) NOT NULL,   .............................   PRIMARY KEY (`book_id`),   KEY `ind_name` (`book_name`) ) ENGINE=InnoDB select book.*  from book , (select book_id from book where book_name like '%算法%')  book_search_id  where book.book_id=book_search_id.book_id; 但是当数据量变得很大后,就不在适合了,可以采用一些其他的第三方搜索技术比如sphinx; 2、如何按匹配的关键度进行快速排序?比如搜索“算法”,有一本书是《算法》,另一本书是《算法设计》,要求前者排在更前面。 现在的排序是根据数据表中的主键序号id进行的排序,没有达到想要的效果。 root@127.0.0.1 : test 15:57:12> select book_id,book_name from book_search where book_name like '%算%' order by book_name; +---------+--------------+ | book_id | book_name    | +---------+--------------+ |       2 | 算法       | |       1 | 算法设计 | ------------------------- 回 10楼(大黑豆) 的帖子 模糊查询分为半模糊和全模糊,也就是: select * from book where name like 'xxx%';(半模糊) select * from book where name like '%xxx%';(全模糊) 半模糊可以可以使用到索引,全模糊在上面场景是不能使用到索引的,但可以进行一些改进,比如: select book.*  from book , (select book_id from book where book_name like '%算法%')  book_search_id   where book.book_id=book_search_id.book_id; 注意这里book_id是主键,同时在book_name上创建了索引 上面的sql语句可以利用全索引扫描来完成优化,但是性能不会太好;特别在数据量大,请求频繁的业务场景下不要在数据库进行模糊查询; 非得使用数据库的话 ,建议不要在生产库进行查询,可以在只读节点进行查询,避免查询造成主业务数据库的资源消耗完,导致故障. 可以使用一些开源的搜索引擎技术,比如sphinx. ------------------------- 回 11楼(蓝色之鹰) 的帖子 我想问下,sql优化一般从那几个方面入手?多表之间的连接方式:Nested Loops,Hash Join 和 Sort Merge Join,是不是Hash Join最优连接? SQL优化需要了解优化器原理,索引的原理,表的存储结构,执行计划等,可以买一本书来系统的进行学习,多多实验; 不同的数据库优化器的模型不一样,比如oracle支持NL,HJ,SMJ,但是mysql只支持NL,不通的连接方式适用于不同的应用场景; NL:对于被连接的数据子集较小的情况,嵌套循环连接是个较好的选择 HJ:对于列连接是做大数据集连接时的常用方式 SMJ:通常情况下散列连接的效果都比排序合并连接要好,然而如果行源已经被排过序,在执行排序合并连接时不需要再排序了,这时排序合并连接的性能会优于散列连接 ------------------------- Re:回 19楼(原远) 的帖子 有个问题:分类表TQueCategory,问题表TQuestion(T-SQL) CREATE TABLE TQueCategory ( ID INT IDENTITY(1,1) PRIMARY KEY,        --问题分类ID NAME VARCHAR(20)        --问题分类名称 ) CREATE TABLE TQuestion ( ID INT IDENTITY(1,1) PRIMARY KEY,        --问题ID CateID INT NOT NULL,        --问题分类ID TITLE VARCHAR(50),        --问题标题 CONTENT VARCHAR(500)        --问题内容 ) 当前要统计某个分类下的问题数,有两种方式: 1.每次统计,在TQuestion通过CateID进行分组统计 SELECT CateID,COUNT(1) AS QueNum FROM TQuestion GROUP BY CateID WHERE 1=1 2.在TQueCategory表增加字段QueNum,用于标识该分类下的问题数量 ALTER TABLE TQueCategory ADD QueNum INT SELECT CateID,QueNum FROM TQueCategory 问:在哪种业务应用场景下采用上面哪种方式性能比较好,为什么? ############################################################################################### 方案 一 需要对 TQuestion 的 CateID字段 进行分组 ,可以在 CateID上创建一个索引,这样就可以索引扫描来完成查询; 方案 二 需要对 TQueCategory 进行扫描就可以得出结果,但是必须在问题表有插入,删除的时候维护quenum数量; 单单从SQL的性能来看, 分类表的数量应该是远远小于问题表的数量的,所以方案二的性能会比较好; 但是如果 TQuestion 的插入非常频繁的话,会带来对 TQueCategory的频繁更新,一次 TQuestion 的 insert或deleted就会带来一次 TQueCategory 的update,这个代价其实是蛮高的; 如果这个分类统计的查询不是非常频繁的话,建议还是使用方案一; 同时还可能还会其他的业务逻辑统计需求(例如: CateID +时间),这个时候在把逻辑放到 TQueCategory就不合适了。 ------------------------- 回 20楼(原远) 的帖子 经验之谈,仅供参考 使用外键在开发上确实省去了很多功夫,但是把业务逻辑交由数据库来完成,对后期的维护来说是很麻烦的事情,不利于维护. ------------------------- 回 21楼(玩站网) 的帖子 无关技术方面: 咨询一下,现在mysql新的版本,5.5.45后貌似修改了开源协议。 是否意味着今后我们商业化使用mysql将受到限制? 如果甲骨文真周到那一步,rds是否会受到影响? 一个疑惑: 为什么很少见到有人用mysql正则匹配?性能不好还是什么原因? ######################################## MySQL有商业版 和 社区版,RDS的MySQL采用开源的社区版进行改进,由专门的RDS MySQL源码团队来维护,国内TOP 10的mysql源码贡献者大部分都在RDS,包括了@丁奇 ,@彭立勋 ,@印风 等; 不在数据库中做业务计算,是保证数据库运行稳定的一个好的设计经验; 是否影响性能与你的sql的执行频率,需要参与的计算数据量相关,当然了还包括数据库所在主机的IO,cpu,内存等资源,离开了这些谈性能是没有多大意义的; ------------------------- 回 22楼(比哥) 的帖子 分页该怎么优化才行??? ######################### 可以参考这个链接,里面有很多的最佳实践,其中就包括了分页语句的优化: http://bbs.aliyun.com/read/168647.html?spm=5176.7114037.1996646101.1.celwA1&pos=1 普通写法: select  *  from t where sellerid=100 limit 100000,20 普通limit M,N的翻页写法,往往在越往后翻页的过程中速度越慢,原因 mysql会读取表中的前M+N条数据,M越大,性能就越差: 优化写法: select t1.* from  t t1,             (select id from t  sellerid=100 limit 100000,20) t2 where t1.id=t2.id; 优化后的翻页写法,先查询翻页中需要的N条数据的主键id,在根据主键id 回表查询所需要的N条数据,此过程中查询N条数据的主键ID在索引中完成 注意:需要在t表的sellerid字段上创建索引 create index ind_sellerid on t(sellerid); 案例: user_A (21:42:31): 这个sql该怎么优化,执行非常的慢: | Query   |   51 | Sending data | select id, ... from t_buyer where sellerId = 765922982 and gmt_modified >= '1970-01-01 08:00:00' and gmt_modified <= '2013-06-05 17:11:31' limit 255000, 5000 SQL改写:selectt2.* from (selectid from t_buyer where sellerId = 765922982   andgmt_modified >= '1970-01-01 08:00:00'   andgmt_modified <= '2013-06-05 17:11:31' limit255000, 5000)t1,t_buyer t2 where t1.id=t2.id index:seller_id,gmt_modified user_A(21:58:43): 好像很快啊。神奇,这个原理是啥啊。牛!!! user_A(21:59:55): 5000 rows in set (4.25 sec), 前面要90秒。 ------------------------- 回 27楼(板砖大叔) 的帖子 这里所说的索引都是普通的b-tree索引,mysql,sqlserver,oracle 的关系数据库都是默认支持的; ------------------------- 回 32楼(veeeye) 的帖子 可以详细说明一下“最后建议不要在数据库中使用外键,让应用程序来保证。 ”的原因吗?我们公司在项目中经常使用外键,用程序来保证不是相对而言更加复杂了吗? 这里的不建议使用外键,主要考虑到 : 第一.维护成本上,把一些业务逻辑交由数据库来保证,当业务需求发生改动的时候,需要同时考虑应用程序和数据库,有时候一些数据库变更或者bug,可能会导致外键的失效;同时也给数据库的管理人员带来维护的麻烦,不便于管理。 第二.性能上考虑,当大量数据写入的时候,外键肯定会带来一定的性能损耗,当出现这样的问题时候,再来改造去除外键,真的就不值得了; 最后,不在数据库中参与业务的计算(存储过程,函数,触发器,外键),是保证数据库运行稳定的一个好的最佳实践。 ------------------------- 回 33楼(优雅的固执) 的帖子 ReDBA专家门诊一期:索引与sql优化 十分想请大师分享下建立索引的经验 我平时简历索引是这样的 比如订单信息的话 建立 订单号  唯一聚集索引 其他的比如   客户编号 供应商编号 商品编号 这些建立非聚集不唯一索引   ################################################## 建立索引,需要根据你的SQL语句来进行创建,不是每一个字段都需要进行创建,也不是一个索引都不创建,,可以把你的SQL语句,应用场景发出来看看。 索引的创建确实是一个非常专业的技术活,需要掌握:表的存储方式,索引的原理,数据库的优化器,统计信息,最后还需要能够读懂数据库的执行计划,以此来判断索引是否创建正确; 所以需要进行系统的学习才能掌握,附件是我在2011年的时候的一次公开课的ppt,希望对你有帮助,同时可以把你平时遇到的索引创建的疑惑发到论坛上来,大家可以一起交流。 ------------------------- 回 30楼(几几届) 的帖子 我也是这样,简单的会,仔细写也会写出来,但是就是不知道有没有更快或者更好的 #################################################### 多写写SQL,掌握SQL优化的方法,自然这些问题不在话下了。 ------------------------- 回 40楼(小林阿小林) 的帖子 mysql如何查询需要优化的语句,比如慢查询的步奏,如何找出需要通知程序员修改或者优化的sql语句 ############################################################ 可以将mysql的慢日志打开,就可以记录执行时间超过指定阀值的慢SQL到本地文件或者数据库的slow_log表中; 在RDS中默认是打开了慢日志功能的:long_query_time=1,表示会记录执行时间>=1秒的慢sql; 如何快速找到mysql瓶颈: 简单一点的方法,可以通过监控mysql所在主机的性能(CPU,IO,load等)以及mysql本身的一些状态值(connections,thread running,qps,命中率等); RDS提供了完善的数据库监控体系,包括了CPU,IOPS,Disk,Connections,QPS,可以重点关注cpu,IO,connections,disk 4个 指标; cpu,io,connections主要体现在了性能瓶颈,disk主要体现了空间瓶颈; 有时候一条慢sql语句的频繁调用,也可能导致整个实例的cpu,io,connections达到100%;也有可能一条排序的sql语句,消耗大量的临时空间,导致实例的空间消耗完。 ------------------------- 下面是分析一个cpu 100%的案例分析:该实例的cpu已经到达100% 查看当前数据库的活动会话信息:当前数据库有较多的活跃线程在数据库中执行查看当前数据库正在执行的sql: 可以看到这条sql执行的非常缓慢:[tr=rgb(100, 204, 255)]delete from task_process where task_id='1801099' 查看这个表的索引: CREATE TABLE `task_process` (  `id` int(11) NOT NULL AUTO_INCREMENT,    ................  `task_id` int(11) NOT NULL DEFAULT '0' COMMENT '??????id',   ................  PRIMARY KEY (`id`),  KEY `index_over_task` (`is_over`,`task_id`),  KEY `index_over` (`is_over`,`is_auto`) USING BTREE,  KEY `index_process_sn` (`process_sn`,`is_over`) USING BTREE) ENGINE=InnoDB AUTO_INCREMENT=32129710; 可以看到这个表有3KW的数据,但是没有task_id字段开头的索引,导致该sql语句删除需要进行全表扫描: 在我们的诊断报告中已经将该sql语句捕获到,同时给你提出该怎样进行索引的添加。 广告:诊断报告将会在1月底发布到控制台,到时候用户可以直接查看诊断建议,来完成你的数据库优化。 ------------------------- 回 45楼(dentrite) 的帖子 datetime和int都是占用数据库4个字节,所以在空间上没有什么差别;但是为了可读性,建议还是使用datetime数据类型。 ------------------------- 回 48楼(yuantel) 的帖子 麻烦把ecs_brand和ecs_goods的表结构发出来一下看看 。 ------------------------- 回 51楼(小林阿小林) 的帖子 普通的 ECS服务器上目前还没有这样的慢SQL索引建议的工具。 不过后续有IDBCloud将会集成这样的sql诊断功能,使用他来管理ECS上的数据库就可以使用这样的功能了 。

玄惭 2019-12-02 01:16:11 0 浏览量 回答数 0
阿里云大学 云服务器ECS com域名 网站域名whois查询 开发者平台 小程序定制 小程序开发 国内短信套餐包 开发者技术与产品 云数据库 图像识别 开发者问答 阿里云建站 阿里云备案 云市场 万网 阿里云帮助文档 免费套餐 开发者工具 SQL审核 小程序开发制作 视频内容分析 企业网站制作 视频集锦 代理记账服务 2020阿里巴巴研发效能峰会 企业建站模板 云效成长地图 高端建站 人工智能 阿里云云栖号 云栖号案例 云栖号直播