ARTS-Week-14

ARTS-Week-14

ARTS 是耗叔发起的一项活动,每周完成以下内容:

Algorithm - 至少做一个 LeetCode 上的算法题
Review - 阅读并点评至少一篇英文技术文章
Tip - 学习至少一个技术技巧
Share - 至少分享一篇有观点和思考的技术文章

Algorithm

LeetCode Problems 703 - Kth Largest Element in a Stream

Kth Largest Element in a Stream

Difficulty: Easy

Solution

第一种解法:暴力解法

将数组排序后,维护 k 个较大元素的数组
如果新加入的元素小于所维护数组的最小值,那么直接返回这个最小值
如果新加入的元素大于所维护数组的最小值,将该元素加入所维护数组重新排序并截取前 k 个元素,返回该数组最小值

# Python

class KthLargest(object):

    def __init__(self, k, nums):
        nums.sort(reverse=True)
        self.nums = nums[0:k]
        self.k = k

    def add(self, val):
        if len(self.nums) == self.k and val < self.nums[-1]:
            return self.nums[-1]
        else:
            self.nums.append(val)
            self.nums.sort(reverse=True)
            self.nums = self.nums[0:self.k]
            return self.nums[-1]

复杂度

  • Time complexity: O(N * k * logk);

运行结果

Python:
Runtime: 1612 ms.
Your runtime beats 12.92 % of python3 submissions.
Memory Usage: 16.1 MB

第二种解法:二分查找

此方法依然需要维护 k 个较大元素的排序数组。所不同的是,将新元素增加到所维护数组的过程中,使用二分查找的思想找到需要插入的位置,而不是直接重新排序。所以时间复杂度更优。

# Python

class KthLargest(object):

    def __init__(self, k, nums):
        nums.sort(reverse=True)
        self.nums = nums[0:k]
        self.k = k

    def add(self, val):
        if len(self.nums) == self.k and val <= self.nums[-1]:
            return self.nums[-1]

        left, right = 0, len(self.nums)
        while left < right:
            mid = (left + right) // 2
            if val > self.nums[mid]:
                right = mid
            else:
                left = mid + 1

        self.nums.insert(left, val)
        if len(self.nums) > self.k:
            self.nums.pop()

        return self.nums[-1]

复杂度

  • Time complexity: O(k * logk);

运行结果

Python:
Runtime: 200 ms.
Your runtime beats 21.79 % of python3 submissions.
Memory Usage: 15.9 MB

第三种解法:优先队列

维护一个元素个数为 k 的最小堆,堆顶即为第 k 大的元素。
需要做的是每次加入新元素时,维护好这个最小堆即可。

# Python

import heapq

class KthLargest(object):

    def __init__(self, k, nums):
        self.pool = nums
        self.k = k
        heapq.heapify(self.pool)
        while len(self.pool) > k:
            heapq.heappop(self.pool)

    def add(self, val):
        if len(self.pool) < self.k:
            heapq.heappush(self.pool, val)
        elif val > self.pool[0]:
            heapq.heapreplace(self.pool, val)

        return self.pool[0]

复杂度

  • Time complexity: O(k * logk);

运行结果

Python:
Runtime: 176 ms.
Your runtime beats 25.28 % of python3 submissions.
Memory Usage: 16 MB


Review

Scaling webapps for newbs & non-techies - by Wolfram Hempel

当我们的 网站/APP 用户与业务量爆炸式增长后,我们需要文中提到的方法以让我们的系统适配新的访问量。
文中介绍了网站的不同阶段的不同架构方式。

  1. 增加反向代理
    • 可以监控以保证我们的服务器还在正常运行
    • 将请求导向正确的程序中
    • 认证用户只能访问服务器中他们有权限的部分
    • 通过负载均衡,把请求导向适合的服务器
  2. 增加数据库集群
    只用一个数据库服务器来支持写入,由这个数据库服务器将数据更新到其他的读取数据库服务器。
  3. 微服务
    • 每一个微服务独立存在,可以单独规模化
    • 开发者独立开发各个微服务,他们只对各自的微服务生命周期负责
    • 每一个微服务拥有它们自己的资源,例如数据库
  4. 缓存 & CDN
    服务器的很大一部分请求压力是来自不经常变化的静态资源,使用缓存和 CDN 能很好的缓解服务器的压力
  5. 数据分片
    例如你的用户量是2亿,你使用 A 片来服务以 A 开头的所有用户...使用 Z 片来服务以 Z 开头的所有用户

Tip

本周了解了在 Linux 里遇到 %iowait 升高以及很多僵尸进程,而导致 CPU 使用率暴增的排查思路。其中使用到一些性能工具总结如下:

  1. perf可以查看系统调用的情况。当查到有问题的进程后,可以使用这个工具查找该进程具体调用的哪些函数导致了性能问题
  2. pstree可以用树状显示进程之间的关系
  3. dstat 吸收了 vmstat、iostat、ifstat 等几种工具的优点,可以同时观察系统的 CPU、磁盘I/O、网络以及内存使用情况
  4. strace是跟踪系统调用的工具,可以查看进程的系统调用情况

# ARTS 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×