Skip to content

Latest commit

 

History

History
67 lines (46 loc) · 7.22 KB

ARTS02-0331.md

File metadata and controls

67 lines (46 loc) · 7.22 KB

ARTS Week 2

Algorithm

  • code

https://github.com/drejrnal/arts/blob/master/Artsweektwo/AddOperations.java

  • solution 本题有两个点需要注意
    • 首先本题中字符串中的单个数字是可以组合的，并不是在每个数字间插入运算符，因此在递归过程中需要充分考虑各种长度的数字组合，所以在程序中首先就要考虑最终的表达式由那些数字组成，再考虑在这些数字间安插符号。
    • 另外一个点是在递归过程中记录已形成表达式计算出的结果，这样在递归Base Case中只需要O(1)的时间判断此次递归是否是成功的，否则需要O(n)，超出时间复杂度，另外由于乘法具有较高优先级，还需要记录递归前一过程的计算因数，例如2 + 3 * 5 当到达* 5这一层时还需要保留3这个值，这样就可以通过减3在加上3 * 5计算出当前过程的正确值。 综上递归函数的参数包括（字符串到达位置，当前参与计算的值，上一层参与的值，上一层为止计算出的结果，当前形成的表达式）

Review

java servlet是用于响应HTTP请求的Java对象，它是运行在servlet容器中的。servlet容器、web应用和servlet间的关系是一个servlet容器中包含多个web应用，一个web应用中包含多个servlet。servlet容器接收每个HTTP请求并找到请求对应的servlet并分配。servlet中可以通过httpservletRequest得到请求的session，并进而得到servletContext。

public class MyServeletInitializer implements WebApplicationInializer{
    @Override
    public void onStartUp(ServletContext servletcontext) throws ServletException{
      Dynamic myServlet = servletcontext.addServlet("myservlet",Myservlet.class);
      myServlet.addMapping("/custom/**");
    }
}

servlet也有自己的生命周期，在请求到来时，servlet容器加载servlet class并创建实例，通常情况下容器会创建一个实例，这样面对多个HTTP请求时注意servlet并发问题。在实现servlet时要注意不要访问成员变量或静态变量，即使变量本身是线程安全的也需要避免对于引用变量的重新赋值。总之Java并发中需要注意的问题此时都应该考虑到。servlet实例创建完之后就可以通过service方法处理客户端的get、post、put等HTTP请求。

在spring MVC中，有一个核心调度器：DispatcherServlet，它根据HandlerMapping或HandlerAdapter将每一个请求代理给特定的bean，另外还有一个重要的web组件是WebApplicationContext,它包括servlet及servlet关联的servletContext，应用程序在访问WebApplicationContext时需要借助ServletContext查找。Root WebApplicationContext通常包含所有servlet实例共享的资源比如Repositories、Services，这些bean也能被特定的servlet WebApplication-context继承并覆盖。

Spring MVC DispatcherServlet在处理请求时首先会查看WebApplicationContext看是否有请求需要用到的属性，然后就会将请求按需要分配给各种Resolver，如果找到了一个对应的Handler，那么与这个handler相关联的execution chain就会执行，期间如果应用中设置了Interceptor，请求便会在相应断点处执行拦截器设置的操作，最后会将已经生成的模型交给ViewResolver渲染。

Tips

Java并发中的tricks

  • 将一个键或值放入HashTable、syncronizedMap或者ConcurrentHashMap中可以安全将他发布给其他使用容器的线程
  • 将某个元素或对象放入BlockingQueue或者ConcurrentLinkedQueue，可以将元素安全地发布给任何访问容器的线程
  • 在没有额外同步的情况下，任何线程都可以被安全使用发布不可变对象。
  • 对于volatile使用，注意当某一变量的写入操作依赖自身当前值的时候，这个变量就不能用volatile修饰；volatile虽然可以解决变量可见性问题，却不能解决原子性问题。
  • 局部变量在线程自身的占空间内，因此具有栈封闭性，但是要注意栈中引用不能溢出。

Share

并发编程的思考（阶段性总结）

这周看了一些与并发编程相关的书籍和资料，发现虽然不同语言并发编程的结构和方式有些差别外，整个并发编程的具体概念和模型还是来源于操作系统课程当中的进程、线程管理、通信。于是根据书中的内容和自己的思考，整理如下，与大家分享。

现如今单芯片处理器包含了多个处理器核，所以在用户级并发的表达方式可帮助利用计算中的硬件并行性。线程作为表达并发的工具，代表的是程序中的活动单元（模块）。通常线程也常用作某些软件结构的并发抽象。例如在文件服务器、Web服务器这样的软件实体上会有一个分配器模型。当分配器线程收到工作请求时会将其分配到工作线程池中的某个线程。当请求数量突破服务器能够处理的容量时，通过请求队列将并发的工作稳定下来。在流水线模型中，流水线的每个阶段处理一个线程。

  • 并发编程的范式

就像系统提供了一个包含程序员需要的常用数学库，系统也提供了函数库来支持线程抽象。为支持线程作为一种编程抽象，需要有创建线程、终止线程、与其他线程通信、并在线程间进行同步的操作。在C语言中，我们在main()过程中创建多个线程，线程的入口可以是任何用户定义的过程；在Java中通过继承Thread或实现Runnable接口创建一个线程。

当操作系统实例化一个进程时，会为每一个进程创建唯一的内存空间（虚拟地址空间），其包含了每个程序特定的代码，堆栈和全局数据。线程在这个空间中漫游，多个线程间并无保护，因此为了保证同一地址空间下多个线程间的纪律，就需要同步或互斥的手段约束线程。在c语言中可以采用信号量的概念解决线程间同步或通信问题，Java则是采用管程这种更加面相对象的模型来提供并发支持。

线程具有生命周期，总体上包含运行态、阻塞态和终止态；不同编程语言实现又会对某些状态进行细分，例如阻塞态可以是在某一条件变量上阻塞，又可以是程序显式调用sleep、wait进行线程切换。

  • 并发程序中的原子性和可见性

在多处理器模型中由于每个处理器有自己的缓存，因此必须保证线程间的可见性；在单处理器模型中，由于处理器只能在指令级架构保证指令的原子性，并不能保证一组指令的原子性，所以指令的交错执行会导致程序出现意外或错误。

再同时读取和更新两个相关值的时候，无法以原子的方式完成。但是，由于不可变对象可提供一种弱形式的原子性，每当需要一组相关数据以原子方式执行某个操作时，就可以考虑创建一个不可变的类来包含这些数据。因为当线程获得一个不可变对象的引用后，就不必担心另一个线程修改这个对象。