“糟糕的程序员会考虑代码。优秀的程序员会考虑数据结构及其关系,” Linux的创建者Linus Torvalds。
我们通常认为,对编程中任何问题的解决方案都取决于选择正确的数据结构。这个公理可以证明,但是它很长一段时间,而本文则是关于另一个的。今天,我们将讨论最简单的理论对之一。一对是一种数据结构,它本身存储任何两个数据元素,这意味着我们希望以某种方式将它们逻辑地组合为一个。它恰好解决了这个问题,即 如果有一些数据元素,
并且b
我们需要以形式呈现b
,则可以成对实现此设计。如果您认为自己从未遇到过或不会遇到这样的事情,那么事实并非如此。这是VUE文档中计算属性的最简单示例:var vm = new Vue({
el: '#demo',
data: {
firstName: 'Foo',
lastName: 'Bar'
},
computed: {
fullName: function () {
return this.firstName + ' ' + this.lastName
}
}
})
从理论上看,fullName
这是一对夫妇。在技术和现实世界中,有无数此类示例,我们经常使用程序代码对其进行建模。您可以正确地注意到我们可以在逻辑上组合任意数量的元素,您将是正确的。这给我们带来了一个更复杂的复合数据结构概念,其中之一就是一对。我们将在稍后处理复合数据,现在我们将重点介绍这对数据。该理论告诉我们,对具有以下属性:- , .. - , , . , ( - . , )
- . . . , , , , , .
:
pair = { a, b }
如果在调用代码中我们将以这种方式直接使用该对:pair.a
那么更改该对的实现时,无论对该对的调用出现在哪里,我们都将不得不重写该调用代码。这不是很好!
一对是一个抽象(甚至是一个低级),因此直接使用其组件是错误的。使用任何抽象的组件时,我们必须使用抽象接口,否则代码将变得混乱(它将变得更难阅读,更容易犯错误,但最重要的是更难更改,因为必须在代码的不同部分进行更改)。
配对可以以非常不同的方式实现。在任何一种编程语言中,都有不止一种机会来实现这种数据结构。例如,您可以为任意数据类型实现一对:
const pair = (first, second) => (elementType) => {
switch(elementType) {
case 'first':
return first;
case 'second':
return second;
}
};
const getFirstElement = (pair) => (pair('first'));
const getSecondElement = (pair) => (pair('second'));
这种工作方式称为发送消息。奇怪的是,但是实体之间的这种交互方式在C / C ++之前曾被称为OOP。我们必须使用设计switch
吗?当然不一定。这些是技术实施的细节,并且可以有很多实施!最重要的是使这对夫妻变得可变!例如,您可以使用地图实现相同的功能
const pair = (first, second) => (
new Map([
['first', first],
['second', second],
])
);
const getFirst = (pair) => (pair.get('first'));
const getSecond = (pair) => (pair.get('second'));
注意,第一种实现可以很容易地用第二种替换。第二到第一!调用代码不会更改。这是抽象的重要优点。我们可以轻松地在程序中更改抽象的实现,但是使用此抽象的代码将不知道这些更改。如果我们想更改抽象本身的实现,则无需编辑与这些抽象一起使用的代码。这很重要,因为节省客户资金并提高开发人员奖金。顺便说一句,假设我们不了解js中Mapov的存在,但是我们可以使用对象。
const pair = (first, second) => (
Object.freeze({
'first': first,
'second': second,
})
);
const getFirst = (pair) => (pair.first);
const getSecond = (pair) => (pair.second);
您可以很容易地猜到,这两个以前的实现也都可以用第三个实现替换,并且这不会改变(实际上,有一些区别。当尝试直接更改属性时,映射不会抛出异常,但是它们会抛出“冻结对象” TypeError: Cannot assign to read only property
。)但是,在本文的上下文中重要)。为什么我们需要理论数据结构的知识?
如果我们从鸟瞰的角度来看程序员的工作,我们会发现实际上他正在从事这一工作。这会创建可操纵某些数据集的工具。因此,我们经常需要为数据选择某种存储结构,并想出使用这些存储结构的方法或为混乱的数据集指定特定的结构。了解典型的数据结构使我们能够为不同的典型任务拥有一套现成的解决方案,并且只需为特定任务选择最方便的方式。让我们分析一个示例:“实现一种处理分数的机制。分数应以通常的格式存储。那些。以1/2的形式。还必须执行基本操作(加法,减法,乘法,除法)。需要提供规范化。”让我们弄清楚问题的状况!我们需要为某些数学实体实现抽象,因此参考原始资料是合理的。当然,如果有经验的程序员阅读本文,那么他们一定会立即想到代码中的解决方案,而无需阅读有关数学分数的文章,但是我们会假设。我们微弱地想象分数是如何工作的,并说明整个推理过程。维基百科的资料告诉我们,分数是普通(1/4)和十进制(0.1)。显然,根据问题的情况,我们需要使用常规表示形式的分数。我们还看到普通分数是两个的逻辑联合数字(分子和分母),这是关于需要使用一对作为此任务的数据结构的最确定的信号。在代码中,我们可以将这种结构描述如下:
const makeRational = (num, denom) => (
new Map([
['num', num],
['denom', denom],
])
);
const getNumer = (rat) => (rat.get('num'));
const getDenom = (rat) => (rat.get('denom'));
接下来,我们应该用8 / 4、6 / 9计划的一部分来分析情况。任务的条件表明需要提供规范化。分数的归一化是从其中移除最大公约数(GCD)。我们实现了一个搜索GCD两个数字的功能:
const getGcd = (a, b) => ((a % b) ? getGcd(b, a % b) : Math.abs(b));
如果您不清楚该函数的文本,那么建议您阅读有关递归的内容。要归一化分数,我们需要将其分子和分母除以GCD。我们编写标准化函数:const normalize = (n1, n2) => {
const commonDivisor = getGcd(n1, n2);
return [n1 / commonDivisor, n2 / commonDivisor];
};
将规范化置于makeRational构造函数中以在创建分数时始终规范化数据是合乎逻辑的。const makeRational = (num, denom) => {
const [normalizeNum, normalizeDenom] = normalize(num, denom);
return new Map([
['num', normalizeNum],
['denom', normalizeDenom],
]);
};
接下来,我们将在操作界面上进行操作。1)加法要添加两个普通分数,应将它们带到一个公分母。然后添加分子,并使分母保持不变。
const add = (rat1, rat2) => (
makeRational(
getNumer(rat1) * getDenom(rat2) + getNumer(rat2) * getDenom(rat1),
getDenom(rat1) * getDenom(rat2),
));
2)减法为了得到分数的差,还需要将它们简化为一个公分母,然后减去分子,分母应保持不变。
const sub = (rat1, rat2) => (
makeRational(
getNumer(rat1) * getDenom(rat2) - getNumer(rat2) * getDenom(rat1),
getDenom(rat1) * getDenom(rat2),
));
3)乘法要对两个普通分数相乘,您需要将其分子和分母相乘。const multi = (rat1, rat2) => (
makeRational(
getNumer(rat1) * getNumer(rat2),
getDenom(rat1) * getDenom(rat2),
));
4)除法为了将一个普通分数除成另一个,您需要将第一个分数乘以第二个分数的倒数。逆数被称为分数,其分子等于原始数的分母,而分母是原始数的分子。const div = (rat1, rat2) => (
makeRational(
getNumer(rat1) * getDenom(rat2),
getDenom(rat1) * getNumer(rat2),
));
如您所见,在每个操作中,我们都会创建一个新实体。这是不变性规则的结果。请注意,在数学运算中,请勿更改原始数字,而是创建新的:1 + 2 = 3
。要注意。我们可以将实现更改为makeRational
其他任何实现,但是调用代码将不知道该实现并将继续运行。这是由于我们正确地实现了抽象并通过接口而不是直接通过接口使用其组件这一事实的结果。用户以通常的方式获取数据也很重要,因此我们引入了一项附加功能。const ratToString = (rat) => `${getNumer(rat)}/${getDenom(rat)}`;
我将附上测试清单:describe('normalize', () => {
test('should work', () => {
expect(normalize(21, 6)).toEqual([7, 2]);
expect(normalize(2, 3)).toEqual([2, 3]);
});
});
describe('rational', () => {
test('getters', () => {
const rat1 = makeRational(3, 9);
expect(getNumer(rat1)).toBe(1);
expect(getDenom(rat1)).toBe(3);
const rat3 = makeRational(-4, 16);
expect(getNumer(rat3)).toBe(-1);
expect(getDenom(rat3)).toBe(4);
});
test('add&sub', () => {
const rat1 = makeRational(3, 9);
const rat2 = makeRational(10, 3);
expect(add(rat1, rat2)).toEqual(makeRational(11, 3));
expect(sub(rat1, rat2)).toEqual(makeRational(-3, 1));
const rat4 = makeRational(12, 5);
const rat3 = makeRational(-4, 16);
expect(add(rat3, rat4)).toEqual(makeRational(43, 20));
expect(sub(rat3, rat4)).toEqual(makeRational(-53, 20));
const rat5 = makeRational(1, 15);
const rat6 = makeRational(4, 25);
expect(add(rat5, rat6)).toEqual(makeRational(17, 75));
expect(sub(rat5, rat6)).toEqual(makeRational(-7, 75));
});
test('multi&div', () => {
const rat1 = makeRational(1, 2);
const rat2 = makeRational(2, 3);
expect(multi(rat1, rat2)).toEqual(makeRational(2, 6));
const rat3 = makeRational(1, 3);
const rat4 = makeRational(1, 2);
expect(div(rat3, rat4)).toEqual(makeRational(2, 3));
});
test('ratToString', () => {
const rat1 = makeRational(3, 9);
const rat3 = makeRational(-4, 16);
expect(ratToString(rat1)).toBe('1/3');
expect(ratToString(rat3)).toBe('-1/4');
});
});
结论
原来的案文非常多,但我希望它清楚。总结一下:- 每当需要逻辑组合两个不相关的值时,我们都可以使用Steam数据结构
- 这对夫妻一定要免疫
- 这对夫妇必须提供一个使用其组件的接口
如果文章对某人似乎超载,我事先表示歉意。我主要关注不太有经验的开发人员,因此我尝试以这样一种方式编写代码,使我的推理逻辑以及该解决方案或该解决方案的选择都非常清楚。如果文章对社区感兴趣。那么典型数据结构的方向将继续。下一个主题是相关列表。