• 开源镜像
  • 开源沙龙
  • 媛宝
  • 猿帅
  • 注册
  • 登录
  • 息壤开源生活方式平台
  • 加入我们

开源日报

  • 开源日报第754期:《保持学习 til》

    21 4 月, 2020
    开源日报 每天推荐一个 GitHub 优质开源项目和一篇精选英文科技或编程文章原文,坚持阅读《开源日报》,保持每日学习的好习惯。
    今日推荐开源项目:《保持学习 til》
    今日推荐英文原文:《How I’ve adjusted my work-from-home habits》

    今日推荐开源项目:《保持学习 til》传送门:GitHub链接
    推荐理由:该项目为作者每天通过各种语言和技术学习的记录。你我各有一种思想,相互交换,就都有了两种思想。
    今日推荐英文原文:《How I’ve adjusted my work-from-home habits》作者:Will Kelly
    原文链接:https://opensource.com/article/20/4/healthy-remote-work-habits
    推荐理由:有人说家是一个需要常回但是不能久待的地方,但是看来我们还要与病毒斗争很久。在家,学习与工作中找到平衡。

    How I’ve adjusted my work-from-home habits

    WFH newbs and veterans alike have to adjust to self-quarantine; here’s how to maintain some balance.

    (Image by : Opensource.com) I’ve been a remote worker during various chapters in my career, and have tried to carry those lessons into each new remote work experience. At the end of last year, I switched to a job that lets me work from home. Fast forward to the COVID-19 outbreak; even though I was no WFH novice, I found myself having to adapt just like the many other workers who’ve been suddenly thrust into remote work.

    In hopes of easing that transition, here are some healthy remote work habits to adapt during a pandemic.

    Keep exercising even if your gym is closed

    I watched the crowd in my gym dwindle the week before my state government issued its stay at home orders. Whether I’ve been working in an office or at home, going to the gym helps me vent stress, plus it acts as a logical break in my daily routine because I put down my phone and keyboard to clear my head.

    Fortunately, my gym put some training activities online that I plan to use. I already have a stability ball and Bosu ball in my home office that I began using on day three after the pandemic closed all the offices, schools, and later gyms in my local area. As I write this article, I’m entering week 4 of COVID-19-mandated remote work, and I’m still trying to get back to the exercise dedication and momentum I had before this all happened.

    Dress (and groom) yourself for work

    I’ve worked from home on and off during my career. When I started my new job, I decided not to repeat some mistakes I made during the last time I worked from home. One mistake I made was not shaving every day. I also stopped getting dressed for work.

    When you dress and groom yourself for work every day, it can help put you in focus for work. You don’t have to be too strict; it is a pandemic after all. I’m still debating on sweatpants Fridays during this crisis.

    Eat meals away from your desk

    It’s too easy to just eat meals at your desk when you work at home. Many even do it at the office. I recommend as you get through your COVID-19-enforced remote working that you use eating as a natural break in the ebbs and flows of your day. For example, unless a deadline was calling, I would go out to lunch to break up my remote working days. These days I get up from my desk, walk outside to get a breath of fresh air and have lunch in my living room.

    Keep a schedule and track your progress

    It’s easy to sleep in when you don’t have to go to the office. I recommend trying to keep to your regular schedule as much as possible. It’s admittedly easy for me to say that because I live alone. If you’re home with children, work with your employer to time-shift your schedule to accommodate the added responsibilities and other challenges you’re facing right now. It may take a few iterations to get the right schedule, but you’ll appreciate the consistency.

    Another word about keeping a schedule—you might add important work meetings to your personal calendar or as reminders on your mobile device, so you have another reminder as you adjust to the new normal of COVID-19.

    The open source community has a lot of great scheduling and project management tools that you can use to track your own time and progress. There are project management tools for agile development teams. You can also find open source alternatives to Google Calendar available on Android.

    Put backup communications channels in place

    Even companies with robust telework programs may see some communications outages. It may not even be their CIO’s fault, such as the Microsoft Teams outage that happened in Europe early on during the COVID-19 pandemic.

    Having problems dialing into a conference bridge or your employer’s group chat having sporadic issues will surprise nobody right now; most understand that workers are in a period of transition, and not everything will run smoothly. However, you still need to have backup channels in place to make that communication happen, even if it’s just coworkers exchanging cell numbers so they can text or call each other as needed.

    There are some fully-featured open source Slack alternatives available that are worth exploring if your organization is lacking in chat applications or if you want to give your team a backup channel to your official corporate application. (Whether you do it with the approval of your corporate IT department is up to you).

    You should also consider installing implementing MediaWiki or Twiki to improve collaboration or to give your team an accessible document repository.

    Pivot on communications when needed

    Every company where I’ve been an employee or contractor has had its own communications style. Remote working at scale during the COVID-19 epidemic will challenge those communication styles.

    Be prepared to shake up your communication style, whether you’re a newb or long term remote worker. That could mean writing more detailed emails instead of the terse ones you normally send to becoming more of a power user with your company’s group chat tool. There are also the open source wikis I mentioned earlier that can provide you a centralized platform for any long-form writing you need to do to help communicate project requirements and changes.

    I also extend this advice to your personal communications during the workday. For example, a friend and I video conference during the day. We never did that pre-COVID-19.

    Final thoughts

    Lots of people will evolve and rethink their remote work habits. It’s only healthy that you prepare yourself for adjusting your own remote working habits. What worked for me pre-COVID-19 doesn’t necessarily work right now, so I’m adjusting my remote work habits weekly as I see fit so I can maximize my productivity during the current crisis.

    How are you adjusting your remote work habits during self-quarantine?


    下载开源日报APP:https://opensourcedaily.org/2579/
    加入我们:https://opensourcedaily.org/about/join/
    关注我们:https://opensourcedaily.org/about/love/
  • 开源日报第753期:《道上的规矩 project-guidelines》

    20 4 月, 2020
    开源日报 每天推荐一个 GitHub 优质开源项目和一篇精选英文科技或编程文章原文,坚持阅读《开源日报》,保持每日学习的好习惯。
    今日推荐开源项目:《道上的规矩 project-guidelines》
    今日推荐英文原文:《The Best Thing You Can Do Is Keep Going》

    今日推荐开源项目:《道上的规矩 project-guidelines》传送门:GitHub链接
    推荐理由:JS 项目当然有很多人搞过,既然如此自然也有无数人踩过各种各样的坑,这个项目总结了 JS 项目中应有的实践策略来规避这样那样的问题。一个人的项目自然想怎么玩怎么玩,有不少坑都不会真正造成影响,但是如果与他人进行协作,这些坏习惯就会把你的队友作宝搞——如果不想被队友毒打的话,在项目开始前应当检查一下有没有疏忽这个实践策略列表中的某项。
    今日推荐英文原文:《The Best Thing You Can Do Is Keep Going》作者:Eileen Pollack
    原文链接:https://humanparts.medium.com/the-best-thing-you-can-do-is-keep-going-7c7d090554f4
    推荐理由:只要一直没有忘记要去做的话,总有一天回过头来就能发现自己的成果

    The Best Thing You Can Do Is Keep Going

    Don’t worry about being productive right now. Just be aware.

    Dear Draft,

    For the life of me, I can’t figure out how to be creative now that I’m suddenly working full-time from home while caring for my kids and supervising their schoolwork. How can I think clearly amid so many distractions? I don’t feel in control of my immediate surroundings, let alone the horrors of the larger world barraging me on the news.

    Signed,
    Too Harried to Think of a Pseudonym

    Dear Harried,

    I might not be qualified to answer this particular question. I live alone. I am used to working from my apartment, and my freelance editing jobs have all dried up.

    But, like most people my age, I can look back on periods of my life that I don’t know how I managed to survive. In my forties, after I got divorced, I found myself teaching full time, trying to publish another book before I came up for tenure, and running a creative writing program while raising my son, keeping our house and yard in a reasonable state of repair, and caring for a neurotic greyhound. These tasks were made more difficult by a host of undiagnosed medical problems, one of which caused me to bleed internally so profusely I almost died, the other a spinal cord injury that led me to become slowly paralyzed.

    At the same time, my father was dying of cancer, and my mother was suffering from heart disease and Parkinson’s, so my siblings and I needed to fly down to Florida every few weeks to care for them.

    How did I get through those crises? I kept waking up in the morning and doing what I needed to do that day, as well as I could, given the constraints. I found pleasure where I could. I lay down on my office floor when I needed to recover. I didn’t give up.

    I don’t mean to minimize what you are going through, Harried. Tens of thousands of people are dying. You and your partner are being asked to take on a Herculean task, hunkering down in a tiny apartment while working on your laptops and trying to homeschool your kids. But a day can hold only so much craziness. Once you’ve reached that limit, whatever lies beyond doesn’t matter. You will make it through this terrible time. Then, like me, you will look back and marvel at how you did it.

    The first rule is: Let everything go that’s not essential. I was raised by compulsively neat and orderly parents, so even when I am overwhelmed, my apartment remains neat and orderly. But I clean that apartment — by which I mean dusting, vacuuming, mopping the counters and floors — only once every six weeks (if that). When I was cooking for my son, we got by on Annie’s mac and cheese (“bunny pasta,” we used to call it), frozen peas, and bagels. My son wouldn’t eat anything else anyway. And yet, he grew up to be six foot two, healthy, smart, successful, and kind.

    My students seem to have been programmed to obsess about their grades and job prospects, which, given the economy in which they grew up, is understandable. But I am also amazed by how much time and care they are willing to devote to curating their wardrobe and appearance, planning elaborate proposals, engagement parties, bachelor parties, weddings, gender-reveal parties, baby showers, birthday parties for their children, significant others, and friends, worrying about what their children eat and wear and play with, how well those children do in school and what activities they pursue after hours. If I had devoted half as much attention to any of those details, I would never have been able to fulfill my obligations to my job, let alone continue writing.

    You probably don’t need to worry as much as you might be worrying about being the perfect homeschooler. The children suffering the most from this pandemic are the ones who were lagging behind before it started — the kids with special needs that weren’t being met, the kids whose parents couldn’t afford the laptop and Wi-Fi that would enable them to sign in to their classes now. Most middle-class teenagers will continue learning on their own or make up for lost time later. And younger kids? As someone who has earned degrees in both the sciences and humanities, I can assure you that as long as you help your child learn to read and write and achieve a basic facility for math, nothing else really matters.

    So, Harried, do the best you can. Accomplish what absolutely must be accomplished in a given day. But don’t worry about the rest. If you can’t concentrate on your novel because you’re worrying about catching the virus, losing your job, or losing your grandparents, don’t make your existence harder by berating yourself for not finding time to be creative.

    If a war hit, if a nuclear disaster showered your city with radiation, if a famine or flood caused you to pack up and flee, would you worry about your productivity? Most of us grew up in a statistically unlikely bubble in which we suffered very few threats to our way of life. Even Boomers like me managed to survive the polio epidemic of the 1950s, and, except for the riots, protests, and assassinations of the 1960s and the aftershocks of 9/11, avoided any real catastrophes that tested our resilience.

    We wondered if we were soft. Secretly, we longed for a challenge that might test our character. What if, like our parents, we had needed to survive the Great Depression, the Holocaust, or WWII? I think younger generations feel this longing even more acutely. How else to explain all the movies, novels, and video games about ordinary human beings scrabbling to survive in a post-apocalyptic world? Or all those extreme sports that require courage and discipline if the athlete is to avoid serious injury or even death? Well, this is the chance for all of us to prove our ability to endure hardship in real life, without complaining (too much), without putting our own needs first, and perhaps even by helping others.

    The lie we all grew up on is that we’re able to achieve everything we want to achieve, to be happy, fulfilled, and creative all the time — and if we don’t manage to be successful, at everything, the fault is ours. Pandemic or not, most people live precarious existences, working jobs that bore them, stifle their potential, strain their backs, cause them to contract diseases, yet leave them far too little money to pay their bills or enough time to worry about their children’s welfare. The one lesson I have learned by reading my students’ essays for so many decades is that even relatively fortunate young people often lose a parent or a sibling, suffer terrible abuse, or come down with a debilitating physical or mental illness.

    The lie is that most people have it easy, a lie our government reinforces because to acknowledge otherwise would be to admit the need for social welfare programs that corporations refuse to pay taxes to support. From an early age, we are groomed to perform the high-wire act of leading a perfect life without a safety net to catch us. But most of us do fall. Multiple times. Sometimes, we get pushed by circumstances beyond our control. Other times, we trip over our own feet. Or we despair and leap off the edge. If anything, this pandemic should teach us that falling is usually not our fault, and even if it is, our failures need not be lethal.

    No matter how little time you find for writing now, Harried, you are growing as a writer. Being creative doesn’t mean making stuff up; it means being sensitive and alive to what is going on around you, acutely aware of what you and your neighbors are experiencing. If you can, keep track of the minutiae of your daily life in quarantine, the emotions you are surprised to notice, the effects the pandemic is having on your spouse and kids. Imagine if you were a fighter in the French Resistance or a soldier in Vietnam. You wouldn’t have time to write. But you would want to keep track of all you witnessed. Then, after the battles ended and you were safe, you could turn those notes into a novel or a poem.

    That said, maybe your circumstances aren’t quite as dire as you are painting them. Maybe you are afraid to make claims for your creative work because writing a story or a poem right now seems frivolous. If that’s the case, don’t feel selfish asking your partner to mind the kids for an hour so you can lock yourself in the bedroom and write. Maybe all you can focus on is jotting a description of the sounds you and your neighbors emit from your windows every night to express gratitude to the first responders, or the dialogue that transpired between your kids at lunch.

    You might be shocked at what you can dash off in an hour. When I was in college, one of my classmates complained he could write only if he were alone and had the entire day to concentrate. “I used to think that, too,” our professor said. “But then I found myself as a war correspondent in the Pacific theater, and I found I could write even when sitting on the floor of a freezing-cold cargo plane, wearing gloves, with a manual typewriter on my lap. You would be amazed what you can accomplish when you have no choice.”

    If that’s not possible, Harried, be generous to yourself. Use all you are learning about life right now to become a better writer later. I am ridiculously competitive, disciplined, and ambitious. But I know when my sanity or the well-being of the people I love are more important than my own achievements. At times like these, I remember the woman whose grave I once discovered in New Hampshire. The engraving on her tombstone read: SHE DONE ALL SHE COULD. That woman is my hero. She did all any of us can be asked to do, especially in the middle of a pandemic.
    下载开源日报APP:https://opensourcedaily.org/2579/
    加入我们:https://opensourcedaily.org/about/join/
    关注我们:https://opensourcedaily.org/about/love/
  • 开源日报第752期:《go语言百度客户端: BaiduPCS-Go》

    19 4 月, 2020
    开源日报 每天推荐一个 GitHub 优质开源项目和一篇精选英文科技或编程文章原文,坚持阅读《开源日报》,保持每日学习的好习惯。
    今日推荐开源项目:《go语言百度客户端: BaiduPCS-Go》
    今日推荐英文原文:《Three Signs You Need Technical Agile Coaching》

    今日推荐开源项目:《go 语言百度客户端:BaiduPCS-Go》传送门:GitHub链接
    推荐理由:多平台支持, 支持 Windows, macOS, linux, 移动设备等.百度帐号多用户支持;通配符匹配网盘路径和 Tab 自动补齐命令和路径
    今日推荐英文原文:《Three Signs You Need Technical Agile Coaching》作者:Emily Bache
    原文链接:http://coding-is-like-cooking.info/2020/02/three-signs-you-need-technical-agile-coaching/
    推荐理由:敏捷技术辅导帮助开发人员改变他们的工作方式。开发人员学会提高产品中代码的质量,并且作为一个团队更有效地工作。

    Three Signs You Need Technical Agile Coaching

    How your team actually writes its code is very important if your organization is trying to build products in an Agile way. This post considers the risks associated with insufficiently Agile coding practices and explains how to identify them before they become major issues.

    Nearly every software organization has high ambitions for increasing their agility and yours is probably one of them. It’s common to bring in experienced coaches to help teams operate with more agility and to discover ways of delivering more value. But, if you’re working on software products, you’ll find it’s hard to realize some of the benefits of Agile without changing the behaviour of developers in the codebase. Too many coaching efforts place little or no emphasis there.

    Agile Coaching helps your business to become more successful by improving the way you plan and deliver software. Technical Agile Coaching specifically focuses on how people write code. How do you know if you need Technical Agile Coaching? Here are three signs.

    You spend more time fixing bugs than building new features

    Look at all the tasks you work on each week. Ask yourself how much time is being spent on innovative new features, and how much on fixing defects in existing features? For some teams the answer can be as little as 5% of time spent on proactive new work. Now ask yourself – how much more money would our organization make if we spent less time on fixes and more on delivering new features?

    Turning this situation around is about increasing the quality of your work so that fewer fixes are needed, resulting in more time for innovation. Often, the root cause of defects is technical debt and code that is hard to understand and change.

    You can mitigate against this by training your developers to build in quality from the start. Technical Agile Coaching helps teams to improve automated tests and reduce technical debt by demonstrating various techniques and practices for evolving design safely.

    Delivery of new features is delayed, sometimes more than once

    Are your new features around 80% done for long periods and then take forever to be actually ready for release? Often this is the biggest complaint from customers and other stakeholders. How much would it be worth to your organization for new functionality to be available reliably and on time?

    Late deliveries are often caused by developers not collaborating effectively in the code. To build a new feature they need to bring the whole team’s expertise to bear, and integrate their work seamlessly. Typically, the coding work is not divided up in a way that makes collaboration easy, and changes are not integrated until late in the process.

    Technical Agile Coaching helps developers to deliver on time: reliable automated regression tests promote better collaboration with a shared view of the current status; teams learn to divide up the coding work and integrate changes far more frequently than the interval between external deliveries; developers learn to use their tools better and to communicate effectively within the team so they can complete tasks more reliably.

    Developers complain the code is so bad they need to re-write the whole thing

    Sometimes developers ask for a hiatus in new feature development for several months, even a year, so they can start over by rebuilding the same functionality using new tools and frameworks. This is a significant cost to your business, and a large risk. A more staged approach carries far less risk and allows you to build better functionality with much more manageable cost.

    Usually, an organization arrives in this situation after many years of accumulated technical debt. The technologies chosen originally become outdated and are not upgraded in a timely way. Developers make design decisions and then leave without fully documenting or otherwise transferring design knowledge to new team members. New features are added that were not anticipated in the original design. Gradually the code quality declines and it becomes harder and harder to work with.

    Technical Agile Coaching helps developers gain better control over existing code, so they can continue working with it and building new features. Teams learn to migrate code to newer technologies in a series of smaller, less risky steps, adding new functionality as they go. Developers learn to pay off technical debt and to communicate better about design decisions.

    Benefits of Technical Agile Coaching

    Technical Agile Coaching helps developers to change the way they work, day to day, minute by minute, in their codebase. They learn to increase the quality of the code in their product and work more effectively as a team. The coach works closely with the developers while they are writing code to remind, reinforce, teach, and demonstrate Agile practices. With Technical Agile Coaching you should expect to see the following benefits:

    • Reductions in technical debt
    • Better automated regression tests
    • Improved communication between developers within the team
    • Smaller, safer changes integrated often and documented well
    • Improved effectiveness using team development tools and IDEs.

      Technical Agile Coaching helps a team to improve how they write code, and begin to use more effective agile development practices together.

    下载开源日报APP:https://opensourcedaily.org/2579/
    加入我们:https://opensourcedaily.org/about/join/
    关注我们:https://opensourcedaily.org/about/love/

  • 开源日报第751期:《老古董 pong》

    18 4 月, 2020
    开源日报 每天推荐一个 GitHub 优质开源项目和一篇精选英文科技或编程文章原文,坚持阅读《开源日报》,保持每日学习的好习惯。
    今日推荐开源项目:《老古董 pong》
    今日推荐英文原文:《Complexity Theory for Algorithms》

    今日推荐开源项目:《老古董 pong》传送门:GitHub链接
    推荐理由:这款制作于1972年的游戏《pong》大概最古老的电子游戏之一。
    今日推荐英文原文:《Complexity Theory for Algorithms》作者:Cody Nicholson
    原文链接:https://medium.com/better-programming/complexity-theory-for-algorithms-fabd5691260d
    推荐理由:关于算法的复杂度理论以及如何优化时间复杂度,毕竟谁都不想用冒泡。

    Complexity Theory for Algorithms

    How we measure the speed of our algorithms

    Complexity theory is the study of the amount of time taken by an algorithm to run as a function of the input size. It’s very useful for software developers to understand so they can write code efficiently. There are two types of complexities:

    Space complexity: How much memory an algorithm needs to run.
    Time complexity: How much time an algorithm needs to run.

    We usually worry more about time complexity than space complexity because we can reuse the memory an algorithm needs to run, but we can’t reuse the time it takes to run. It’s easier to buy memory than it is to buy time. If you need more memory — you can rent server space from providers like Amazon, Google, or Microsoft. You could also buy more computers to add more memory without renting server space. The remainder of this article will cover how we can optimize time complexity.

    How Do We Measure Time Complexity?

    A new computer will usually be faster than an old computer, and desktops will usually be faster than smartphones — so how do we really know the absolute time an algorithm takes?

    To measure the absolute time, we consider the number of operations the algorithm performs. The building blocks of any algorithm are if-statements and loops. They answer the questions: (1) When should we do operations? (2) How many times should we do them? We want to write code using as few if-statements and loops as possible for maximum efficiency on any machine.

    For analyzing algorithms, we consider the input size n — the number of input items. We want to make a good guess on how the algorithm’s running time relates to the input size n. This is the order of growth: how the algorithm will scale and behave given the input size n.
    1. Input 10 items -> 10 ms
    2. Input 100 items -> 100 ms (Good, linear growth)
    3. Input 1,000 items -> 10,000 ms (Bad, exponential growth)
    
    In the above example, when we input 10 items, it takes 10 ms to run. When we input 100 items, it takes 100 ms — which is good since the growth of our input increased proportionally to the runtime.

    However, on the next step, we input 1,000 items, and it takes 10,000 ms. We’re now taking 10 times longer to run relative to the increase in our input size n. Now we have exponential growth of our runtime instead of linear growth. To better understand the different orders of growth, we’ll cover the Big-O notation.

    Big-O Complexity Chart

    The big-o notation describes the limiting behavior of an algorithm when the runtime tends toward a particular value or infinity. We use it to classify algorithms by how they respond to changes in input size. We denote our input size as n and the number of operations performed on our inputs as N. My examples will be coded in Python.

    We prefer algorithms that have an order of growth that’s linearithmic in terms of input or faster because slower algorithms can’t scale to large input sizes. Here’s a list of the runtime complexities from lowest to highest:
    • O(1) : Constant Time Complexity
    • O(log(n)) : Logarithmic Complexity
    • O(n) : Linear Complexity
    • O(n * log(n)) : Linearithmic Complexity
    • O(n^k) : Polynomial Complexity (Where k > 1)
    • O(c^n) : Exponential Complexity (Where c is a constant)
    • O(n!) : Factorial Complexity

    Constant Time Complexity: O(1)

    An algorithm runs in constant time if the runtime is bounded by a value that doesn’t depend on the size of the input.

    The first example of a constant-time algorithm is a function to swap two numbers. If we changed the function definition to take a million numbers as input and we left the function body the same, it’d still only perform the same three operations plus a return statement. The runtime doesn’t change based on the input size.
    def swapNums(num1, num2):
       temp = num1
       num1 = num2
       num2 = temp
       return (num1, num2)
    
    In this second example, we’ll first check if the input message is “Hello World!” and change the message to another value if it is. After, it’ll loop three times, executing another loop that’ll print the message 100 times — meaning the message will be printed 300 times total. Despite all those operations — since the function won’t perform more operations based on the input size — this algorithm still runs in constant time.
    def printMessage300Times(message):
       if(message == "Hello World!")
          message = "Pick something more original!"
       for x in range(0, 3):
          for x in range(0, 100):
             print(message)
    

    Logarithmic Time Complexity: O(log(n))

    A logarithmic algorithm is very scalable because the ratio of the number of operations N to the size of the input n decreases when the input size n increases. This is because logarithmic algorithms don’t access all elements of their input — as we’ll see in the binary-search algorithm.

    In binary search, we try to find our input number, num, in a sorted list, num_list. Our input size n is the length of num_list.

    Since our list is sorted, we can compare the num we’re searching for to the number in the middle of our list. If num is greater than the midpoint number, we know that our num could only be in the greater side of the list — so we can discard the lower end of the list entirely and save time by not needing to process over it.

    We can then repeat this process recursively (which behaves much like a loop) on the greater half of the list, discarding half of our remaining num_list every time we iterate. This is how we can achieve logarithmic time complexity.
    def binarySearch(num_list, left_i, right_i, num):
       if right_i >= left_i:
          midpoint = left_i + (right_i - left_i)/2
          if num_list[midpoint] == num:
             return midpoint
          elif num_list[midpoint] > num:
             return binarySearch(num_list, left_i, midpoint-1, num)
          else:
             return binarySearch(num_list, midpoint+1, right_i, num)
       else:
          return "Number not in collection"
    

    Linear Time Complexity: O(n)

    An algorithm runs in linear time when the running time increases at most proportionally with the size of the input n. If we multiply the input by 10, the runtime should also multiply by 10 or less. This is because in a linear-time algorithm, we typically run operations on every element of the input.

    Finding the maximum value in an unsorted collection of numbers is an algorithm we could create to run in linear time since we have to check every element in our input once in order to solve the problem:
    def findMaxNum(list_of_nums):
       max = list_of_nums[0]
       for i in range(1, len(list_of_nums.length)):
          if(list_of_nums[i] > max):
             max = list_of_nums[i]
       return max
    
    In the for loop, we iterate over every element in our input n, updating our maximum value if needed before returning the max value at the end. More examples of linear-time algorithms include checking for duplicates in an unordered list or finding the sum of a list.

    Linearithmic Time Complexity: O(n * log(n))

    Linearithmic-time algorithms are slightly slower than those of linear time and are still scaleable.

    It’s a moderate complexity that floats around linear time until input reaches a large enough size. The most popular examples of algorithms that run in linearithmic time are sorting algorithms like mergeSort, quickSort, and heapSort. We’ll look at mergeSort:
    def mergeSort(num_list): 
        if len(num_list) > 1: 
            midpoint = len(arr)//2
            L = num_list[:midpoint] # Dividing "n"  
            R = num_list[midpoint:] # into 2 halves 
    
            mergeSort(L) # Sort first half 
            mergeSort(R) # Sort second half 
    
            i = j = k = 0
    
            # Copy data to temp arrays L[] and R[] 
            while i < len(L) and j < len(R): 
                if L[i] < R[j]: 
                    num_list[k] = L[i] 
                    i+=1
                else: 
                    num_list[k] = R[j] 
                    j+=1
                k+=1
    
            # Checking if any element was left in L
            while i < len(L): 
                num_list[k] = L[i] 
                i+=1
                k+=1
            # Checking if any element was left in R
            while j < len(R): 
                num_list[k] = R[j] 
                j+=1
                k+=1
    

    ‘mergeSort’ works by:

    • Dividing the num_list recursively until the elements are two or less
    • Sorting each of those pairs of items iteratively
    • Merging our resulting arrays iteratively
    With this approach, we can achieve linearithmic time because the entire input n must be iterated over, and this must occur O(log(n)) times (the input can only be halved O(log(n)) times). Having n items iterated over log(n) times results in the runtime O(n * log(n)), also known as linearithmic time.

    Polynomial Time Complexity: O(n^c) where c > 1

    An algorithm runs in polynomial time if the runtime increases by the same exponent c for all input sizes n.

    This time complexity and the ones that follow don’t scale! This means that as your input size grows, your runtime will eventually become too long to make the algorithm viable. Sometimes we have problems that can’t be solved in a faster way, and we need to get creative with how we limit the size of our input so we don’t experience the long processing time polynomial algorithms will create. An example polynomial algorithm is bubbleSort:

    def bubbleSort(num_list):
        n = len(num_list)
        for i in range(n):
            # Last i elements are already in place
            for j in range(0, n-i-1):
                # Swap if the element found is greater
                # than the next element
                if num_list[j] > num_list[j+1] :
                    temp = num_list[j]
                    num_list[j] = num_list[j+1]
                    num_list[j+1] = temp
    
    bubbleSort will iterate over all elements in our list over and over, swapping adjacent numbers when it finds they’re out of order. It only stops when it finds all the numbers are in the correct order.

    In the below picture, we only have seven items, and it’s able to iterate over the whole set three times to sort the numbers — but if it was 100 numbers, it’s easy to see how the runtime could become very long. This doesn’t scale.

    Exponential Time Complexity: O(c^n) Where c Is a Constant

    An algorithm runs in exponential time when the runtime doubles with each addition to the input dataset. Calculating the Fibonacci numbers recursively is an example of an exponential-time algorithm:
    def fibonacci(n): 
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else: 
            return fibonacci(n-1) + fibonacci(n-2) 
    
    This algorithm calls itself twice on the last line — once with n-1 and once with n-2. This means if we started with n=7, we’d call the function a total of 25 times! It’s very expensive to run as the input grows.

    Factorial Time Complexity: O(n!)

    Lastly, an algorithm runs in factorial time if it iterates over the input n a number of times equal to n multiplied by all positive integer numbers less than n. It’s the slowest time complexity we’ll discuss in this article, and it’s primarily used to calculate permutations of a collection:
    def getListPermutation(items_list):
       results = []
       i = 0
       l = len(items_list)
       while i < l:
          j, k = i, i + 1
          while k <= l:
             results.append(" ".join(items_list[j:k]))    
             k = k + 1
          i = i + 1
       print results
    

    Conclusion

    Thanks for reading! I’d love to hear your feedback or take any questions you have.


    下载开源日报APP:https://opensourcedaily.org/2579/
    加入我们:https://opensourcedaily.org/about/join/
    关注我们:https://opensourcedaily.org/about/love/
←上一页
1 … 70 71 72 73 74 … 262
下一页→

Proudly powered by WordPress