精华内容
下载资源
问答
  • JS中简单算法和数据结构的复杂性 (The complexity of simple algorithms and data structures in JS) In the previous article “A Step Towards Computing as a Science: Simple Algorithms &am...

    数据结构中复杂度的算法

    by Yung L. Leung

    梁永良

    JS中简单算法和数据结构的复杂性 (The complexity of simple algorithms and data structures in JS)

    In the previous article “A Step Towards Computing as a Science: Simple Algorithms & Data Structures in JS,” we discussed simple algorithms (linear & binary searches; bubble, selection & insertion sorts) & data structures (array & key-value paired objects). Here, I continue with the concept of complexity and its application to these algorithms & data structures.

    在上一篇文章“ 迈向科学计算的一步:JS中的简单算法和数据结构”中 ,我们讨论了简单算法(线性和二进制搜索;冒泡,选择和插入排序)和数据结构(数组和键值对对象) )。 在这里,我继续复杂性的概念及其在这些算法和数据结构中的应用。

    复杂 (Complexity)

    Complexity is a factor involved in a complex process. Regarding algorithms & data structures, this can be the time or space (meaning computing memory) required to perform a specific task (search, sort or access data) on a given data structure. The efficiency of performing a task is dependent on the number of operations required to complete a task.

    复杂性是复杂过程中涉及的一个因素。 关于算法和数据结构,这可以是在给定数据结构上执行特定任务(搜索,排序或访问数据)所需的时间空间 (即计算内存)。 执行任务的效率取决于完成任务所需的操作数。

    Taking out the trash may require 3 steps (tying up a garbage bag, bringing it outside & dropping it into a dumpster). Taking out the trash may be simple, but if you are taking out the trash after a long week of renovation, you may find yourself unable to complete the task due to a lack of space in the dumpster.

    取出垃圾可能需要3个步骤(绑好垃圾袋,将其带到室外然后放入垃圾箱)。 取出垃圾可能很简单,但是如果经过漫长的整修后要取出垃圾,您可能会发现由于垃圾箱空间不足而无法完成任务。

    Vacuuming a room can require many repetitive steps (turning it on, repeatedly sweeping the vacuum head across a floor & turning it off). The larger a room, the more times you will have to sweep a vacuum head across its floor. Thus, the longer the time it will take to vacuum the room.

    对房间进行吸尘可能需要许多重复步骤(将其打开,反复将吸尘头扫过地板并关闭)。 房间越大,您将需要越多次扫除地板上的真空头。 因此,吸尘室所需的时间越长

    So, there is a direct causal relationship between the number of operations performed and the number of elements that are performed on. Having a lot of trash (elements) requires taking it out many times. This can lead to a problem of space complexity. Having a lot of square footage (elements) requires sweeping a vacuum head across a floor many times over. This can lead to a problem of time complexity.

    因此,执行的操作数与执行的元素数之间存在直接因果关系。 有很多垃圾(元素)需要将其清除很多次。 这可能导致空间复杂性问题。 拥有大量平方英尺(元素)需要多次将真空头扫过地板。 这可能导致时间复杂性问题。

    Whether you are taking out the trash or vacuuming a room, you might say that the operation count (O) increases exactly with the number of elements (n). If I have 1 trash bag, I have to take out the trash once. If I had 2 trash bags, I have to perform the same task twice, assuming you physically cannot lift more than one bag at a time. So, the Big-O of these chores is O = n or O = function(n) or O(n). This is a linear complexity (a straight line with a 1 operation: 1 element correspondence). So, 30 operations are performed on 30 elements (yellow line on graph).

    无论您是 垃圾还是在给房间打扫灰尘 ,您都可以说操作数( O )元素数( n )的增加而增加。 如果我有1个垃圾袋,则必须将垃圾取出一次。 如果我有2个垃圾袋,假设您一次只能举起一个垃圾袋,则我必须执行两次相同的任务。 因此,这些琐事的Big-O为O = n或O = function(n)或O(n) 。 这是线性复杂度(带有1个运算的直线:1个元素对应)。 因此,对30个元素(图形上的黄线)执行了30次操作。

    This is similar to what happens when considering algorithms & data structures.

    这类似于考虑算法和数据结构时发生的情况。

    搜索次数 (Searches)

    The best case for searching an item in an ordered list, one after another, is a constant O(1), assuming it is the 1st item in your list. So, if the item you are searching for is always listed first, regardless of your list size, you will find your item in an instant. The complexity of your search is constant with the list size. The average to the worst case of this kind of search is a linear complexity or O(n). In other words, for n items, I have to look n times, before I find my item, hence linear search.

    假设有序列表中的第一个项目,一个接一个地搜索项目的最佳情况是常数O(1) 。 因此,无论列表大小如何,如果始终要首先列出要搜索的项目,那么您将立即找到您的项目。 搜索的复杂度与列表大小相同。 这种搜索的最坏情况平均值是线性复杂度或O(n)。 换一种说法, 对于n个项目,我必须先查找n次,然后才能找到我的项目,因此需要进行线性搜索。

    For a binary search, the best case is O(1), meaning the item of your search is located at the midpoint. The worst & average case is log base 2 of n or:

    对于二进制搜索, 最好的情况是O(1),这意味着搜索的项位于中点。 最坏且平均的情况是n的对数底数2或:

    Logarithm or log is a way of expressing an exponent for a given base. So, if there were 16 elements (n = 16), then it would take, at worse case, 4 steps to find the number 15 (exponent = 4).

    对数或对数是一种表示给定底数的指数的方式。 因此,如果有16个元素(n = 16),那么在更坏的情况下,将需要4个步骤才能找到数字15(指数= 4)。

    Or simply: O(log n)

    或者简单地: O(log n)

    排序 (Sorts)

    泡沫 (Bubble)

    In bubble sort, every item is compared to the rest of the collection to determine the highest value to bubble up. For this reason, on average to worst case, its complexity is O(n²). Think a loop nested within another loop.

    在冒泡排序中,将每个项目与其余集合进行比较,以确定冒泡的最高价值。 因此, 平均到最坏的情况 ,其复杂度为O(n²) 。 考虑一个嵌套在另一个循环中的循环。

    So, for each item, you are comparing it to the rest of your collection. This amounts to 16 comparisons (or operations) for 4 elements (4² = 16). The best case is if your collection is almost sorted, except for a single item. This would amount to a single round of comparisons. That is, four comparisons are required to bubble up a member of a four-item collection, which is a complexity of O(n).

    因此,对于每个项目,您都将其与其他产品进行比较。 这相当于对4个元素(4²= 16)进行16个比较(或操作)。 最好的情况是,除单个项目外,您的集合几乎已排序。 这相当于单轮比较。 也就是说,需要四次比较才能使四项集合的成员冒泡,这是O(n)的复杂性。

    选拔 (Selection)

    Unlike bubble sort, instead of bubbling up the highest value, selection sort selects the lowest value to swap it to the earliest positions. But, because it requires comparing each item to the rest of the collection, it also has a complexity of O(n²).

    冒泡排序不同, 选择排序不会冒出最高值,而是选择最低值以将其交换到最早的位置。 但是,由于需要将每个项目与集合的其余部分进行比较,因此它的复杂度也为O(n²)

    插入 (Insertion)

    Unlike the bubble & selection sorts, insertion sort inserts the item into its correct position. But, like the previous sorts, this also requires comparing each item to the rest of the collection, therefore, it has an average to worst case complexity of O(n²). Like the bubble sort, if there is only one item left to sort, it only requires a single round of comparisons to insert the item into its correct position. That is, it has the best case complexity of O(n).

    冒泡选择排序不同插入排序会将项目插入正确的位置。 但是,像以前的排序一样,这也需要将每个项目与集合的其余部分进行比较,因此,其平均复杂度为O(n²) 。 像冒泡排序一样,如果只剩下一个要排序的项目,则只需进行一轮比较即可将该项目插入正确的位置。 也就是说,它具有O(n)最佳情况复杂度。

    数据结构 (Data Structures)

    数组 (Arrays)

    Because it takes a single step to access an item of an array via its index, or add/remove an item at the end of an array, the complexity for accessing, pushing or popping a value in an array is O(1). Whereas, linearly searching through an array via its index, as seen before, has a complexity of O(n).

    由于通过其索引访问数组的一项或在数组的末尾添加/删除一项仅需一步,因此访问推入弹出数组中的值的复杂度为O(1) 。 而如前所述,通过数组索引线性搜索数组的复杂度为O(n)

    Also, because a shift or unshift of a value to or from the front of an array requires reindexing each element that follows it (i.e. removing an element at index 0 requires relabelling element at index 1 as index 0, and so forth), they have a complexity of O(n). The relabelling is carried through from the start to the end of the array.

    此外,因为一个值的到或从阵列的前部的移位不印字需要重新索引每个跟随它元件(即,在索引0移除元素需要在索引1重新标号的要素索引0,等等),它们具有O(n)的复杂度。 重新标记从数组的开始到结尾进行。

    键-值配对对象 (Key — Value Paired Objects)

    Accessing, inserting or removing a value by using a key is instantaneous, and so, they have a complexity of O(1). Searching through each “deposit box” for a specific item by using every available key is essentially a linear search. And so, it has a complexity of O(n).

    使用键访问插入删除值是瞬时的,因此它们的复杂度为O(1) 。 通过使用每个可用键在每个“保管箱”中搜索特定项目实质上是线性搜索 。 因此,它的复杂度为O(n)

    结论 (Conclusion)

    Complexity is more than just a topic for discussing established algorithms & data structures. If used wisely, it can be a useful tool for gauging the efficiency of the work you do and the code you create to solve your problems.

    复杂性不仅仅是讨论已建立的算法和数据结构的主题。 如果使用得当,它可能是衡量您所做工作的效率以及为解决问题而创建的代码的有用工具。

    参考: (Reference:)

    https://www.udemy.com/js-algorithms-and-data-structures-masterclass/

    https://www.udemy.com/js-algorithms-and-data-structures-masterclass/

    翻译自: https://www.freecodecamp.org/news/the-complexity-of-simple-algorithms-and-data-structures-in-javascript-11e25b29de1e/

    数据结构中复杂度的算法

    展开全文
  • 用LiquidHaskell(功能性Pearl)证明摊销的复杂性 这是我正在进行的工作,有关直接在使用LiquidHaskell实现数据结构的Haskell代码上证明摊销的复杂性
  • 摘要本文介绍了CPython中数据结构的关键操作的Big-O表示法。 big-o标记本质上是一种衡量操作时间复杂度的方法。 本文还说明了列表,集合和字典的许多常用操作。为算法设计和选择正确的数据结构至关重要。希望能帮助...

    摘要

    本文介绍了CPython中数据结构的关键操作的Big-O表示法。 big-o标记本质上是一种衡量操作时间复杂度的方法。 本文还说明了列表,集合和字典的许多常用操作。

    为算法设计和选择正确的数据结构至关重要。

    希望能帮助到你。

    为什么我们需要知道时间复杂性?

    对于数据科学家程序员而言,为工作选择正确的数据结构至关重要。 特别是,如果算法需要大量计算,例如训练机器学习模型的算法或处理大量数据的算法,那么确保选择合适的数据结构时要特别小心。

    选择正确的数据类型通常会被忽略,并且最终会严重影响应用程序的性能。

    文章目的

    本文介绍了CPython中数据结构的关键操作的Big-O表示法。 big-O表示法是一种衡量操作时间复杂度的方法。

    d4f70d91edd7210c43d0307b2032d7c8.jpeg-wh_651x-s_1084368465.jpeg

    1.让我们了解大O符号的含义是什么?

    在算法中执行许多操作。 这些操作可能包括遍历集合,复制项目或整个集合,将项目追加到集合中,在集合的开始或结尾处插入项目,删除项目或更新集合中的项目。

    Big-O衡量算法运算的时间复杂度。 它测量算法计算所需运算所需的时间。 尽管我们也可以测量空间复杂度(算法占用多少空间),但本文将重点介绍时间复杂度。

    用最简单的术语来说,Big O表示法是一种基于输入大小(称为n)来衡量操作性能的方法。

    2. Big O表示法有何不同?

    我们需要熟悉许多常见的Big O符号。

    让我们考虑n为输入集合的大小。 就时间复杂度而言:

    O(1):无论您的集合有多大,执行操作所花费的时间都是恒定的。 这是恒定的时间复杂度符号。 这些操作尽可能快。 例如,检查集合内部是否有任何项目的操作是O(1)操作。

    O(log n):当集合的大小增加时,执行操作所花费的时间对数增加。 这是对数时间复杂度表示法。 潜在优化的搜索算法为O(log n)。

    O(n):执行操作所需的时间与集合中的项目数成线性正比。 这是线性时间复杂度符号。 就性能而言,这介于两者之间或中等。 作为一个实例,如果我们想对一个集合中的所有项目求和,那么我们将不得不遍历该集合。 因此,集合的迭代是O(n)操作。

    (n log n):执行某项操作的性能是集合中项目数量的拟线性函数。 这称为准线性时间复杂度表示法。 优化排序算法的时间复杂度通常为n(log n)。

    O(n平方):执行操作所需的时间与集合中项目的平方成正比。 这称为二次时间复杂度表示法。

    (n!):当在操作中计算集合的每个单个排列时,因此执行操作所需的时间取决于集合中项目的大小。 这称为阶乘时间复杂度表示法。 非常慢。

    该图像概述了Big-O符号。

    3aaedc6c3f924a60228290f0808ecc16.jpeg

    O(1)很快。 O(n平方)很慢。 O(n!)非常慢。

    大O符号是相对的。 大O表示法与机器无关,忽略常量,并且被包括数学家,技术人员,数据科学家等在内的广泛读者所理解。

    最佳,平均,最差情况

    当我们计算操作的时间复杂度时,我们可以根据最佳,平均或最坏情况产生复杂度。

    2296da0556b7ddf05308c72543f7186d.jpeg

    最佳情况方案:顾名思义,这是当数据结构和集合中的项目以及参数处于最佳状态时的方案。 例如,假设我们要在集合中找到一个项目。 如果该项目恰好是集合的第一项,那么这是该操作的最佳情况。

    平均情况是根据输入值的分布定义复杂度。

    最坏的情况是可能需要一种操作,该操作需要在大型集合(例如列表)中找到位于最后一个项目的项目,并且算法会从第一个项目开始对集合进行迭代。

    Python集合和时间复杂度

    在本文的这一部分中,我将记录CPython中的常见集合,然后概述它们的时间复杂性。

    我将特别关注平均情况。

    1.List

    List是迄今为止Python中最重要的数据结构之一。 我们可以将列表用作堆栈(添加的最后一项是第一项)或队列(添加的第一项是第一项)。 列表是有序且可变的集合,因为我们可以随意更新项目。

    让我们回顾一下常见列表操作及其Big-O表示法

    插入:Big-O表示法是O(n)

    获取项目:Big-O表示法为O(1)

    删除项目:Big-O表示法是O(n)

    迭代:Big-O表示法是O(n)

    获得长度:Big-O表示法为O(1)

    3a63f6d71636bc5f86ebef71f2f80c25.jpeg

    Joshua Sortino在Unsplash上拍摄的照片

    2.Set

    集合也是Python中使用最广泛的数据集合之一。 集合本质上是无序集合。 集合不允许重复,因此集合中的每个项目都是唯一的。 集合支持许多数学运算,例如联合,差,集合的交集等。

    让我们回顾一下通用Set操作

    检查集合中的项目:Big-O表示法是O(1)

    集合A与集合B的区别:大O表示法是O(A的长度)

    集A和B的交集:大O表示法是O(A或B的长度的最小值)

    集A和B的并集:相对于长度(A)+长度(B),它的Big-O表示法是O(N)

    668b9edcbf8dc317448ad7abef6a88f7.jpeg

    fabio在Unsplash上的照片

    3.Dict 字典

    最后,我想提供字典数据收集的概述。 字典是键值对集合。 键在字典中是唯一的,以防止项目冲突。 这是非常有用的数据收集。

    字典由键索引,其中键可以是字符串,数字甚至是带有字符串,数字或元组的元组。

    我们可以对字典执行许多操作,例如存储键的值,或基于键检索项目,或遍历项目等。

    让我们回顾一下常见的词典时间复杂度:

    在这里,我们认为该密钥用于获取,设置或删除项目。

    获取项目:Big-O表示法为O(1)

    设定项目:Big-O表示法是O(1)

    删除项目:Big-O表示法是O(1)

    遍历字典:Big-O表示法是O(n)

    fc084b0a3a5e3d0a944355a373edd29e.jpeg

    NASA在Unsplash上拍摄的照片

    【编辑推荐】

    【责任编辑:未丽燕 TEL:(010)68476606】

    点赞 0

    展开全文
  • 数据科学项目中使用Python编程语言的每个人的重要文章在Medium上,这个主题没有很好地介绍,因此我决定以一种易于理解的方式概述Python数据结构的时间复杂性。为什么我们需要知道时间复杂性?对于数据科学家程序员而...

    数据科学项目中使用Python编程语言的每个人的重要文章

    在Medium上,这个主题没有很好地介绍,因此我决定以一种易于理解的方式概述Python数据结构的时间复杂性。

    为什么我们需要知道时间复杂性?

    对于数据科学家程序员而言,为工作选择正确的数据结构至关重要。 特别是,如果算法需要大量计算,例如训练机器学习模型的算法或处理大量数据的算法,那么确保选择合适的数据结构时要特别小心。

    选择正确的数据类型通常会被忽略,并且最终会严重影响应用程序的性能。

    文章目的

    本文介绍了CPython中数据结构的关键操作的Big-O表示法。 big-O表示法是一种衡量操作时间复杂度的方法。

    fde04992f8bcb7d656c7776becdfc1e9.png

    1.让我们了解大O符号的含义是什么?

    在算法中执行许多操作。 这些操作可能包括遍历集合,复制项目或整个集合,将项目追加到集合中,在集合的开始或结尾处插入项目,删除项目或更新集合中的项目。

    Big-O衡量算法运算的时间复杂度。 它测量算法计算所需运算所需的时间。 尽管我们也可以测量空间复杂度(算法占用多少空间),但本文将重点介绍时间复杂度。

    用最简单的术语来说,Big O表示法是一种基于输入大小(称为n)来衡量操作性能的方法。

    2. Big O表示法有何不同?

    我们需要熟悉许多常见的Big O符号。

    让我们考虑n为输入集合的大小。 就时间复杂度而言:

    • O(1):无论您的集合有多大,执行操作所花费的时间都是恒定的。 这是恒定的时间复杂度符号。 这些操作尽可能快。 例如,检查集合内部是否有任何项目的操作是O(1)操作。
    • O(log n):当集合的大小增加时,执行操作所花费的时间对数增加。 这是对数时间复杂度表示法。 潜在优化的搜索算法为O(log n)。
    • O(n):执行操作所需的时间与集合中的项目数成线性正比。 这是线性时间复杂度符号。 就性能而言,这介于两者之间或中等。 作为一个实例,如果我们想对一个集合中的所有项目求和,那么我们将不得不遍历该集合。 因此,集合的迭代是O(n)操作。
    • (n log n):执行某项操作的性能是集合中项目数量的拟线性函数。 这称为准线性时间复杂度表示法。 优化排序算法的时间复杂度通常为n(log n)。
    • O(n平方):执行操作所需的时间与集合中项目的平方成正比。 这称为二次时间复杂度表示法。
    • (n!):当在操作中计算集合的每个单个排列时,因此执行操作所需的时间取决于集合中项目的大小。 这称为阶乘时间复杂度表示法。 非常慢。

    该图像概述了Big-O符号。

    08ba4a3c155acd308f1bd596080a175a.png

    O(1)很快。 O(n平方)很慢。 O(n!)非常慢。

    大O符号是相对的。 大O表示法与机器无关,忽略常量,并且被包括数学家,技术人员,数据科学家等在内的广泛读者所理解。

    最佳,平均,最差情况

    当我们计算操作的时间复杂度时,我们可以根据最佳,平均或最坏情况产生复杂度。

    aa6d58db3b0489b440cfe787d84ba39d.png
    • 最佳情况方案:顾名思义,这是当数据结构和集合中的项目以及参数处于最佳状态时的方案。 例如,假设我们要在集合中找到一个项目。 如果该项目恰好是集合的第一项,那么这是该操作的最佳情况。
    • 平均情况是根据输入值的分布定义复杂度。
    • 最坏的情况是可能需要一种操作,该操作需要在大型集合(例如列表)中找到位于最后一个项目的项目,并且算法会从第一个项目开始对集合进行迭代。

    Python集合和时间复杂度

    在本文的这一部分中,我将记录CPython中的常见集合,然后概述它们的时间复杂性。

    我将特别关注平均情况。

    1.List

    List是迄今为止Python中最重要的数据结构之一。 我们可以将列表用作堆栈(添加的最后一项是第一项)或队列(添加的第一项是第一项)。 列表是有序且可变的集合,因为我们可以随意更新项目。

    让我们回顾一下常见列表操作及其Big-O表示法

    1. 插入:Big-O表示法是O(n)
    2. 获取项目:Big-O表示法为O(1)
    3. 删除项目:Big-O表示法是O(n)
    4. 迭代:Big-O表示法是O(n)
    5. 获得长度:Big-O表示法为O(1)
    ec9ab92342c671634c9665c37a62917d.png

    Joshua Sortino在Unsplash上拍摄的照片

    2.Set

    集合也是Python中使用最广泛的数据集合之一。 集合本质上是无序集合。 集合不允许重复,因此集合中的每个项目都是唯一的。 集合支持许多数学运算,例如联合,差,集合的交集等。

    让我们回顾一下通用Set操作

    1. 检查集合中的项目:Big-O表示法是O(1)
    2. 集合A与集合B的区别:大O表示法是O(A的长度)
    3. 集A和B的交集:大O表示法是O(A或B的长度的最小值)
    4. 集A和B的并集:相对于长度(A)+长度(B),它的Big-O表示法是O(N)
    0bd2f56c5c8bd7133b26cc531ff3d72f.png

    fabio在Unsplash上的照片

    3.Dict 字典

    最后,我想提供字典数据收集的概述。 字典是键值对集合。 键在字典中是唯一的,以防止项目冲突。 这是非常有用的数据收集。

    字典由键索引,其中键可以是字符串,数字甚至是带有字符串,数字或元组的元组。

    我们可以对字典执行许多操作,例如存储键的值,或基于键检索项目,或遍历项目等。

    让我们回顾一下常见的词典时间复杂度:

    在这里,我们认为该密钥用于获取,设置或删除项目。

    1. 获取项目:Big-O表示法为O(1)
    2. 设定项目:Big-O表示法是O(1)
    3. 删除项目:Big-O表示法是O(1)
    4. 遍历字典:Big-O表示法是O(n)
    709426ae32b807b23d7c50fa305e98a6.png

    NASA在Unsplash上拍摄的照片

    摘要

    本文介绍了CPython中数据结构的关键操作的Big-O表示法。 big-o标记本质上是一种衡量操作时间复杂度的方法。 本文还说明了列表,集合和字典的许多常用操作。

    为算法设计和选择正确的数据结构至关重要。

    希望能帮助到你。

    (本文翻译自Farhad Malik的文章《Time Complexities Of Python Data Structures》)

    展开全文
  • 首先考察数据结构的复杂性的特点。在这里以微软的演示数据库 nwind.mdb为例子进行分析,现在要出订单明细报表,则涉及到的数据结构如图所示 可以发现这5张表的数据组成了一个3层的树状结构。第一...
    现在的信息系统越来越复杂,它们的数据库中的数据结构也越来越复杂,表和字段变多了,表间关系也越来越多。面对如此复杂的数据结构,各大报表工具各显神通,想尽一切办 法誓要从中获得数据。

        首先考察数据结构的复杂性的特点。在这里以微软的演示数据库 nwind.mdb为例子进行分析,现在要出订单明细报表,则涉及到的数据结构如图所示
    可以发现这5张表的数据组成了一个3层的树状结构。第一层是Customers的数据,第二层是Orders,Employees组成的数据,第三层是OrderDetails,Products组成的。其意思就是说 数据库中存在好几个客户,一个客户有多个订单,一个订单有多个货物。

        面对这种比较复杂的数据,传统的报表工具由于采用两层的数据源模型,因此需要一次性获取数据,采用眉毛胡子一起抓的思想,这就导致可能需要编写复杂的SQL语句,例如对于 订单明细报表,SQL语句可以为"SELECT Customers.CompanyName, Customers.ContactName, Customers.Phone,
    OrderDetails.*, Orders.OrderDate,
    Products.ProductName, Employees.FirstName, Employees.LastName
    FROM ((Orders 
    INNER JOIN (OrderDetails 
    INNER JOIN Products ON OrderDetails.ProductID = Products.ProductID) 
    ON Orders.OrderID = OrderDetails.OrderID) 
    INNER JOIN Customers ON Orders.CustomerID = Customers.CustomerID) 
    INNER JOIN Employees ON Orders.EmployeeID = Employees.EmployeeID
    ",如此复杂的SQL语句我是写不出,也不想写,个人认为复杂SQL语句坏处多多,尤其是JOIN 子语句,应尽量避免。SQL语句写出来后,在报表模板中还需要进行多次分组才能组织出报表样式。

       若采用多层报表数据源模型,则采用了眉毛胡子分别抓的指导思想,处理起来从容不迫,此时获取数据的原理如图所示

    dbdatasource.gif

    其详细步骤为

    1. 对于Customers节点,执行SQL语句"Select CompanyName , ContactName , CustomerID , Phone From Customers"获得客户列表 ,将查询所得的栏目分别分配到CompanyName,ContactName , 订单列表 , Phone 数据源子节点。
    2. Customers节点遍历所有的查询所得的记录行时,每处理一行,都递归调用子节点处理数据的过程。对于订单列表 节点,它有子节点,因此其处理数据的过程是,首先执行SQL语句"Select Orders.OrderID , Orders.OrderDate , Orders.EmployeeID , Employees.EmployeeID , Employees.FirstName , Employees.LastName From Orders , Employees where orders.employeeid = Employees.EmployeeID and orders.CustomerID= 当前处理的CustomerID栏目的值",例如Customers节点处理CustomerID为“1234”的记录时,订单列 表执行的SQL语句为"Select ... From From Orders , Employees where orders.employeeid = Employees.EmployeeID and orders.CustomerID=1234" , 也就时说订单列表节点出执行的SQL语句是根据当前节点的值而改变的。订单列表节点查询成功后,然后将查询所得的栏目分配到 OrderID , OrderData 等子节点,其中 栏目 Orders.OrderID分配给了 订单详细内容 子节点 。
    3. 类似的,对于订单详细内容,执行的SQL语句为"Select OrderDetails.ProductID , OrderDetails.UnitPrice , OrderDetails.Discount , Products.ProductName , OrderDetails.Quantity ,( OrderDetails.UnitPrice * OrderDetails.Quantity * ( 1 - OrderDetails.Discount )) as TotalCount From  OrderDetails , Products where OrderDetails.ProductID = Products.ProductID And OrderDetails.OrderID = 当前处理的订单号",查询所得的栏目分别分配到了它的子节点,其中 TotalCount 栏目分配到了总金额子节点。

    执行的SQL语句依次可能为,此处字段列表用 ...表示

    1. Select ... From Customers
    2. Select ... From Orders , Employees where orders.employeeid = Employees.EmployeeID and orders.CustomerID='1234'
    3. Select ... From  OrderDetails , Products where OrderDetails.ProductID = Products.ProductID And OrderDetails.OrderID = 100
    4. Select ... From  OrderDetails , Products where OrderDetails.ProductID = Products.ProductID And OrderDetails.OrderID = 101
    5. Select ... From Orders , Employees where orders.employeeid = Employees.EmployeeID and orders.CustomerID='5678'
    6. Select ... From  OrderDetails , Products where OrderDetails.ProductID = Products.ProductID And OrderDetails.OrderID = 201
    7. Select ... From  OrderDetails , Products where OrderDetails.ProductID = Products.ProductID And OrderDetails.OrderID = 202

        如此看出,这种多层数据源的使用有利有弊。好处有

    1. 处理过程符合一般的编程逻辑,便于对数据源结构的理解和设计。
    2. 提供了充分的自由度,可以不依赖外部编程来处理大部分复杂的数据库结构。
    3. 此过程中使用的SQL语句简单可靠,很容易理解,而且执行效率高。
    4. 这种多层的数据源结构很大程度上就反映了数据库中的数据结构。数据源树状结构直接映射了数据库中各条记录组成的树状结构,只要了解数据结构就可以很自然的套这这 种结构来编制报表数据源。某种程度上可以进行数据源结构和数据结构的相互检查。

        当然弊端还是有的,最大的就是大大增加了执行SQL语句的次数,影响报表执行效率。当数据源结构层数越多,执行的SQL语句个数将以指数方式增长,因此实际应用中数据源层数 必须有所限制,而且设计良好的数据库数据结构有助于控制数据源层数。

        面对多层数据源的好处和弊端,这需要权衡,个人认为大部分情况下利大于弊,主要原因有

    1. 随着计算机硬件和基础软件的发展,数据库查询速度越来越快,这可以一定程度上弥补SQL语句数量增加的影响。
    2. 随着信息系统规模不断膨胀,复杂的数据结构也是越来越多,若采用传统模式获得报表数据,则程序中分布了很多复杂难懂的SQL语句,这非常不利于系统的开发和维护。相 对于一般的程序代码,SQL语句没有源代码控制,没有编写规范,注释和文档也很少,其含义也更抽象难懂,而且少数的数据库高手才能编写和维护复杂的SQL语句,因此使用大量 复杂SQL语句是不明智的。
    3. 多层数据源结构符合一般的编程逻辑,也反映了数据库的数据结构,因此比较容易编制和理解,知道了解数据库结构就会理解多层数据源结构,可以让很多有基础的经过培 训的人来编制和维护数据源结构,因此可以让普通群众编制大部分报表数据源而不必惊动高手,降低报表编制成本。
    4. 多层数据源结构提供了充分的自由度,可以处理大部分数据结构而无需编程,这就为开发报表模块而无需编程打下了坚实的基础。

       多层数据源模型是本人刚刚提出来的,其思想还不成熟不完善,希望大家多多指点。

    XDesigner 软件工作室 2006-8-31

    转载于:https://www.cnblogs.com/xdesigner/archive/2006/08/31/491636.html

    展开全文
  • 数据科学项目中使用Python编程语言的每个人的重要文章在Medium上,这个主题没有很好地介绍,因此我决定以一种易于理解的方式概述Python数据结构的时间复杂性。为什么我们需要知道时间复杂性?对于数据科学家程序员而...
  • 数组>...我们可以通过将元素设置为某个特定值来象征地删除元素,例如-1,0等,具体取决于我们要求>类似地,对于数组插入基本上如开头所述设置ArrayList:>添加:摊销O(1)>删除:O(n)&...
  • 前端时间复习了一段c语言, 现在开始数据结构的学习, 数据结构是和算法相呼应的, 而算法的关键 就在于时间复杂性和空间复杂性, 这些是很关键的, 又和数学有很的的关系, 拿下一段的学习就该是微积分了吧.
  • 我想着就是数据结构的目的吧。 1,函数在运行时候的机器内存结构 一段编译过后函数在计算机的运行时分为:指令空间,数据空间和环境栈。 指令空间:顾名思义编译生成的指令代码在计算机内存的空间。 数据...
  • 在线法官和一些基本知识 Descrição: ... 使用电子法官,OO基础知识,数据结构/复杂性。 更多关于 : 使用在线法官,例如Urionlinejudge,CD-MOJ和Codeforce。 以提高技能为原则,例如错误处理。
  • 数据结构窦延平版讲义--1_时间复杂性;1算法和算法分析;1算法和算法分析;1算法和算法分析;1算法和算法分析;1算法和算法分析;1算法和算法分析;1算法和算法分析;1算法和算法分析;1算法和算法分析;此课件下载可自行...
  • 1算法和算法分析 1算法和算法分析 1算法和算法分析 1...数据结构与程序设计考研复习大纲_SJTU 1算法一个算法就是有穷规则集合其中规则规定了一个解决某一个特定问题运算 序列 2算法时间复杂性和空间复杂性
  • 因此,每当需要修改数据结构的内容时,都会随之创建一个具有更新值的新实例。随着数据结构越来越复杂,创建副本就越来越繁琐。 为了简化这一过程,技术人员设计了一组通常名为Optics的函数,以便简单地访问或修改...
  • 数据结构 第2讲 算法复杂性

    千次阅读 2017-09-11 09:12:29
    该内容来源于本人著作《趣学算法》在线章节:http://www.epubit.com.cn/book/details/4825如果说数学是皇冠上...多年来,我有一个梦想,希望每一位提到算法人,不再立即紧皱眉头,脑海闪现枯燥公式、冗长代码...
  • Python中的数据结构和算法 此存储库包含Python中数据结构和算法所有实现,具有最佳时间和空间复杂性,并带有源代码和完整文档 内容 链表
  • 2.数据结构的重要 编程就是和数据打交道,计算机程序总是在接受数据,操作数据或返回数据。所有的小程序或者软件都运行在数据结构之上。数据结构不只是用于组织数据,还极大地影响着代码的运行速度。因为数据结构...
  • 程序空间复杂性是指运行完一个程序所需要内存大小。程序时间复杂性是指运行完该程序所需要时间。空间复杂性的组成:程序所需要空间主要由以下部分构成:指令空间:指令空间是指用来存储经过编译之后程序...
  • 2.4 矢量栅格一体化数据结构 一矢量栅格数据结构的优缺点 ?...矢量数据结构的复杂性导致了操作和算法的复杂化作为一种基于线和边界的编码方法不能有效地支持影像代数运算如不能有效地进行点集的集合运
  • 2.4矢量栅格一体化数据结构 一矢量栅格数据结构的优缺点 ...据的输出质量好精度高 矢量数据结构的复杂性导致了操作和算法的复杂化作为一种基于线和边 界的编码方法不能有效地支持影像代数运算如不能有效地进行点集的集
  • 常用大Ο大Θ大Ω就不说了,一般知道大Ο也就行了。...在一些应用中,数据结构是从属于一系列操作而不是一个操作,这时,我们分析最坏情况时就不能分析每一个操作最坏情况,然后认为整个操作序
  • 时间复杂性与空间复杂性的比较:  排序方法 最好情况 平均情况 最坏情况 辅助存储 稳定性 直接插入排序 O(n) O() O() O(1) √ 希尔排序 与增量序列有关 × 简单选择...
  • kotlin中算法和数据结构:一个Kotlin项目,其中包含常见算法解决方案以及它们时间和内存复杂性。 测试是用Spock编写
  • 数据结构是描述非数值计算再实体中的数学模型以及在计算机中的表示方法,以及这些模型进行的...数据结构的逻辑组织 线性结构:线性表(表、栈、队列、串等) 非线性结构: 树(二叉树,Huffman树,二叉索引树等)  
  • 在执行时比较结果,并显示在处理高维数据时并行计算相对于非并行数据结构的优越。 此外,该项目的目的是显示工作人员节点数与图形相关问题的计算时间之间的关系。 使用的数据集是标准大学的Twitch-Social-Network...
  • 复杂结构数据提交

    2015-12-03 14:32:00
    问题抛出 在前台需要一次保存结构复杂的数据组织,界面原型如下: 导致问题复杂的原因有2个: 1. 多实例 如界面原型所示,绿茶属于一个实例,白茶属于另一个实例。多实例下,需要保证实例之间属性隔离,以及...
  • 大数据技术与应用专业教学资源库 数据结构课程说课稿 数据结构期末...幻灯片 3 选择题的第1题 算法分析的主要目的是 A) 分析数据项的合理性 B) 分析数据结构的复杂性 C) 分析算法的时空效率以求改进 D) 研究算法的输入
  • 为了更加全面、动态地测量信息系统复杂度,提出了数据复杂性的概念,将数据复杂性分为数据结构、数据量和数据操作等三个维度,构建了基于数据复杂性的信息系统复杂度测量模型;然后,建立了数据复杂性三个子维度...
  • Gson是由Google自家...但当我们要解析一个复杂的数据结构时,比如说List<CardBean<E>>这种,泛型之中还有泛型数组结构,就比较麻烦了。下面我会给出一种方案,在此之前我还是先简单介绍一下Gson一些东西,如果

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,250
精华内容 3,300
关键字:

数据结构的复杂性

数据结构 订阅