React Native Android Cookie Problem

背景

 最近使用react native 来写一个公司内部使用的app,使用fetch去登陆,发现在android平台上无法获取cookie,iOS平台上却可以。即使是response.headers.get()也获得不了相关信息。于是上网google并且阅读源码,终于找到了问题出现的原因和解决方案。

问题原因

 我们查看native reactfetch.js的代码,发现它的底层是使用XmlHttpRequest来实现的,然后再次找到’XmlHttpRequest’的相关源码,发现了三个文件XMLHttpRequest.android.js,XMLHttpRequest.ios.jsXMLHttpRequestBase.js。我们主要研究了android相关的文件。
 先看’XMLHttpRequest.android.js’。它继承了XMLHttpRequestBase

class XMLHttpRequest extends XMLHttpRequestBase {

  _requestId: ?number;

  constructor() {
    super();
    this._requestId = null;
  }

  sendImpl(method: ?string, url: ?string, headers: Object, data: any): void {
    var body;
    if (typeof data === 'string') {
      body = {string: data};
    } else if (data instanceof FormData) {
      body = {
        formData: data.getParts().map((part) => {
          part.headers = convertHeadersMapToArray(part.headers);
          return part;
        }),
      };
    } else {
      body = data;
    }
    //RCTNetWorking是android的native module,使用okhttp实现,我们之后会看到相关的代码
    this._requestId = RCTNetworking.sendRequest(
      method,
      url,
      convertHeadersMapToArray(headers),
      body,
      this.callback.bind(this)//这里是调用native module的回调,具体callback实现在XMLHttpRequestBase中。
    );
  }

  abortImpl(): void {
    this._requestId && RCTNetworking.abortRequest(this._requestId);
  }
}

 通过源码,我们可以了解,XMLHttpRequest就是通过Android Native Module 来发送网络请求的,然后会回调到callback函数中。我们接下来看看一下callback函数.

  callback(status: number, responseHeaders: ?Object, responseText: string): void {
    if (this._aborted) {
      return;
    }
    this.status = status;
    this.setResponseHeaders(responseHeaders || {});
    this.responseText = responseText;
    this.setReadyState(this.DONE);
  }

 这里我们发现callback回调有三个参数,status,responseHeadersresponseText,那么为什么在外层的fetch会拿不到header中的cookie呢?这里就需要研究android native module的实现啦。
RCTNetworking对应的java文件为NetworkingModule.java,找到这个文件,直接看sendRequest函数。

@ReactMethod
public void sendRequest(
    String method,
    String url,
    int requestId,
    ReadableArray headers,
    ReadableMap data,
    final Callback callback) {
   
  //....... 无关代码省略
  mClient.newCall(requestBuilder.build()).enqueue(
      new com.squareup.okhttp.Callback() {
        @Override
        public void onFailure(Request request, IOException e) {
          if (mShuttingDown) {
            return;
          }
          callback.invoke(0, null, e.getMessage());
        }

        @Override
        public void onResponse(Response response) throws IOException {
          if (mShuttingDown) {
            return;
          }
          // TODO(5472580) handle headers properly
          String responseBody;
          try {
            
            responseBody = response.body().string();
          } catch (IOException e) {
            // The stream has been cancelled or closed, nothing we can do
            //这里是重点,我们发现第二个参数本该传递header,但是现在确实传的null,导致上层的js代码无法获得header!!!!
            callback.invoke(0, null, e.getMessage());
            return;
          }
          callback.invoke(response.code(), null, responseBody);
        }
      });
}

####解决方案
 在fetch或者XMLHttpRequest拿不到头部信息的问题找到了,那么如何让react native android实现cookie呢?
 方案有两套,一是:callback.invoke时把头部信息传递上去,让js层去做cookie的相关逻辑;二是:给Okhttp添加CookieHandlerOkhttp自己管理Cookie
 第二套方案是我在github上看到的github相关讨论和code,相关代码在github上已经被merge到master上去啦,相信不久之后,新版本的React Native Android就可以把这个坑填上啦。

Share

Window和WindowManager解析

 这几天阅读了《Android开发艺术探索》的关于Window和WindowManager的章节,特此写一片博文来整理和总结一下学到的知识.
 说到Window,大家都会想到所有的视图,包括Activity,Dialog,Toast,它们实际上都是附加在Window上的,Window是这些视图的管理者.今天我们就来具体将一下这些视图是如何附加在Window上的,Window有是如何管理这些视图的.

Window的属性和类别

 当我们通过WindowManager添加Window时,可以通过WindowManger.LayoutParams来确定Window的属性和类别.其中Flags参数标示Window的属性,我们列出几个比较常见的属性:

  • FLAG_NOT_FOCUSABLE 这个参数表示Window不需要获取焦点,也不需要接收任何输入事件

  • FLAG_NOT_TOUCH_MODAL 这个参数表示当前Window区域之外的点击事件传递给底层Window,区域之内的点击事件自己处理,一般默认开启

  • FLAG_SHOW_WHEN_LOCKED 这个属性可以让Window显示在锁屏界面上
     Window不仅有属性,还有类型.Type参数表示Window的类型,分别为应用Window(activity对应的),子window(dialog对应的),和系统Window(Toast和系统通知栏).Window是分层的,每个window都有z-ordered,层级大的window会覆盖层级小的window,其大小关系为系统window>子window>应用window.所以系统window总会显示在最上边,但是使用系统window是需要声明相应的权限的.这一点需要注意.

    WindowManager

     我们先来看一下WindowManager的接口,对其接口函数的了解有助于我们更好的理解Window的类别和属性.
     WindowManger实现了ViewManager这个接口,所提供的主要函数只有三个:

        public void addView(View view, ViewGroup.LayoutParams params);
        public void updateViewLayout(View view, ViewGroup.LayoutParams params);
        public void removeView(View view);
    

 而且通过阅读源码,我们会发现所有的操作都是交由WindowManagerGloalal来进行.之后的小节我会依次介绍.这一节先讲一下它的比较重要的成员变量.

// 存储所有window所对应的view
    private final ArrayList<View> mViews = new ArrayList<View>();
    // 存在window所对应的viewRootImpl
    private final ArrayList<ViewRootImpl> mRoots = new ArrayList<ViewRootImpl>();
    // 存储了所有window对应的布局参数
    private final ArrayList<WindowManager.LayoutParams> mParams =
            new ArrayList<WindowManager.LayoutParams>();
    // 存储了那些正在被删除的view对象,调用了removeVIew,但是没有完成的
    private final ArraySet<View> mDyingViews = new ArraySet<View>();

Window的添加过程

 这是WindowManagerGlobal的对应接口

	public void addView(View view, ViewGroup.LayoutParams params,
            Display display, Window parentWindow) 

 创建ViewRootImpl,并将View添加到相应的列表中

	// 创建ViewRootImpl,然后将下述对象添加到列表中
	root = new ViewRootImpl(view.getContext(), display);
        view.setLayoutParams(wparams);//设置Params
        mViews.add(view);//window列表添加
        mRoots.add(root);//ViewRootImpl列表添加
        mParams.add(wparams);//布局参数列表添加

 通过ViewRootImpl来更新界面完成window的添加过程

	// 添加啦!!!!!!!!这是通过ViewRootImpl的setView来完成
	root.setView(view, wparams, panelParentView);

 在ViewRootImpl的setView函数中,会调用requestLayout来完成异步刷新,然后在requestLayout
中调用scheduleTraversals来进行view绘制.

	@Override
    	public void requestLayout() {
        if (!mHandlingLayoutInLayoutRequest) {
            checkThread();
            mLayoutRequested = true;
            scheduleTraversals(); // 实际View绘制的入口
        }
    }

 最后通过WindowSession来完成Window的添加过程,它是一个Binder对象,通过IPC调用来添加window.
 所以,Window的添加请求就交给WindowManagerService去处理,在其内部为每个应用保留一个单独的Session.

Window的删除过程

    public void removeView(View view, boolean immediate) {
        if (view == null) {
            throw new IllegalArgumentException("view must not be null");
        }

        synchronized (mLock) {
            int index = findViewLocked(view, true); //先找到view的index
            View curView = mRoots.get(index).getView();
            removeViewLocked(index, immediate);
            if (curView == view) {
                return;
            }

            throw new IllegalStateException("Calling with view " + view
                    + " but the ViewAncestor is attached to " + curView);
        }
    }

 removeView先通过findViewLocked来查找待删除的View的索引,然后用removeViewLocked来做进一步删除.


    private void removeViewLocked(int index, boolean immediate) {
        ViewRootImpl root = mRoots.get(index); //获得当前的view的viewRootImpl
        View view = root.getView();

        if (view != null) { //先让imm下降
            InputMethodManager imm = InputMethodManager.getInstance();
            if (imm != null) {
                imm.windowDismissed(mViews.get(index).getWindowToken());
            }
        }
        boolean deferred = root.die(immediate); //die方法只是发送一个请求删除的消息之后就就返回
        if (view != null) {
            view.assignParent(null);
            if (deferred) {
                mDyingViews.add(view);//加入dyingView
            }
        }
    }

 在WindowManager中提供了两种删除接口removeVIew()和removeViewImmediate(),它们分别表示异步和同步删除.而异步操作中会调用die函数,来发送一个MSG_DIE消息来异步删除,ViewRootImpl的Handler会调用doDie(),而如果是同步删除,那么就直接调用doDie(),然后在removeView函数中把View添加到mDyingViews中.

Window的更新

	public void updateViewLayout(View view, ViewGroup.LayoutParams params) {
       	.....
	final WindowManager.LayoutParams wparams = (WindowManager.LayoutParams)params;
        view.setLayoutParams(wparams);
        synchronized (mLock) {
            int index = findViewLocked(view, true);
            ViewRootImpl root = mRoots.get(index);
            mParams.remove(index);
            mParams.add(index, wparams);
            root.setLayoutParams(wparams, false);//这是主要的方法
        }
    }

 在setLayoutParams中会调用scheduleTraversals来重新绘制.

Window的创建过程

 不同类型的Window的创建过程不同,这里我只来讲一下Activity的Window的创建过程.在Window的启动过程中,会调用attach()函数来为其关联运行过程中所依赖的一系列上下文环境变量.

    mWindow = PolicyManager.makeNewWindow(this);
    mWindow.setCallback(this);

 Window对象是通过PolicyManager的makeNewWindow方法实现的,由于Activity实现了Window的Callback接口,因此当Window接收到外界的状态改变时就会回调Activity的对应方法.而我们去追寻Window的具体实现类,会发现它就是PhoneWindow,而Activity中最常用的setContentView方法的具体操作都是在PhoneWindow的相应方法中实现的.

 如果没有DecorView,那么就创建它.DecorView是一个FrameLayout,是Activity中的顶级View,一般包括标题栏和内容栏,而且内容栏的id为android.R.id.content,而DecorView的创建过程由installDecor完成,内部会通过generateDecor方法来直接创建DecorView

	if (mContentParent == null) { //如何没有DecorView,那么就新建一个
            installDecor();
        } else if (!hasFeature(FEATURE_CONTENT_TRANSITIONS)) {
            mContentParent.removeAllViews();
        }
  	if (mDecor == null) {
            mDecor = generateDecor(); //直接new出一个DecorView返回
            ......
        }
        if (mContentParent == null) {
            //[window] 这一步也是很重要的.
            mContentParent = generateLayout(mDecor); 
            .......
            }
        .......

 而在generateLayout中

	//根据不同的style生成不同的decorview啊
        View in = mLayoutInflater.inflate(layoutResource, null);
        // 加入到deco中,所以应该是其第一个child
        decor.addView(in, new ViewGroup.LayoutParams(MATCH_PARENT, MATCH_PARENT));
        mContentRoot = (ViewGroup) in; 
        //给DecorView的第一个child是mContentView
        // 这是获得所谓的content
        ViewGroup contentParent = (ViewGroup)findViewById(ID_ANDROID_CONTENT);

 将View添加到DecorView的mContentParent中,这步只需要一条语句就可,具体内部细节就不说啦.

	//第二步,将layout添加到mContentParent
        mLayoutInflater.inflate(layoutResID, mContentParent);

 然后就是回调Acitivity的onContentChanged方法通知Activity视图已经改变了.


	final Callback cb = getCallback();
        if (cb != null && !isDestroyed()) {
            cb.onContentChanged();
        }

 经历了上述三个步骤,DecorView已经创建并初始化完毕,并且Activity的布局文件已经成功添加到DecorView的mContentParent中,但是DecorView并没有添加到WindowManager中去,也无法接收外界的输入,只有到Acitivity的makeVisible()被调用时,DecorView才真正完成了添加和显示过程.


    //DecorView正式添加并显示
    void makeVisible() {
       if (!mWindowAdded) {
            ViewManager wm = getWindowManager();
            wm.addView(mDecor, getWindow().getAttributes());
            mWindowAdded = true;
        }
        mDecor.setVisibility(View.VISIBLE);
    }

总结

 这篇博文主要是读书笔记式的总结,本来想写一些自己的东西,但是研究的太浅,并且语言组织上还是有不足,以后还需要注意和继续努力啦.

Share

生活学习记录一:RxJava+实习感悟

 很久之前就希望自己可以把生活中的点滴都化为文字,记录下来了,今天就写下第一篇博文吧.希望有个好的开始,然后坚持下去.
 前一段时间,在腾讯员工的微信群中看到了有关RxJava和eventBus的对比文章的分享,于是趁着周末,研究一下最近很火的RxJava的使用.
 在学习RxJava的过程中主要参考了下列的几篇文章:

  • 给android开发者的RxJava详解 ,这是我主要学习的一篇,大多数有关RxJava的知识都是从这里获得的.

  • Rx revisit ,作者主要讲述了Netflix开发Rx系列的原由,Observable和Iterator的区别

  • Implementing an Event Bus With RxJava - RxBus ,主要讲述了Observer pattern和Pub-sub pattern的区别,和如何使用RxJava去模仿EventBus.

  • 知乎-RxJava和EventBus的区别 ,看看知友的回答

  • Awesome-RxJava, github的有关Rx的文章集合
     阅读了那么多的文章,并且写了一些例子,但是还是感觉没有领会到RxJava的精髓.还需要在正式的项目中使用,才可以算是正在的入了门.
     最近的实习也不是很顺利,出现了很多的问题.不过这也很好,在扇贝的实习所学习到的和在腾讯实习正好是相互补充的.在腾讯实习时,可能是大家都比较忙,代码的质量由开发者自己保证,mentor也不会太认真的帮你进行reivew.而在扇贝则是不太一样,要求比较高的代码的质量,涉及的一些规则和原则其实我也都知道,但是在实际的开发过程中,开始时,代码质量还可以保持在较高的水平,但是随之开发的进行,需求的修改,debug,代码就开始有了”腐烂”的气味.知道原则而不是在实际过程中使用就等于不知道.所以,在单纯的编码方面你还是需要更加的谨慎.
     而在腾讯,大家都比较关注新技术,喜欢紧跟技术潮流,在软件工程的各个流程都做的很好,但是代码方面都是依靠个人保证.
     而且在实习阶段中,我也越发的感觉与公司其他员工的交流和沟通特别重要,不管是日常事务还是工作事务.你需要融入公司的这个大家庭里去啊.

Share

Gson源码分析二

 承接上一篇博文Gson源码分析,这篇博文主要总结一下Gson中涉及Java反射逻辑的部分。

一个Gson例子

 Gson可以解析用户自定义的对象,当然你也可以使用public GsonBuilder registerTypeAdapter(Type type, Object typeAdapter)来完全按照自己的方式来解析,但是Gson其实已经为解析自定义类型对象做了适配,除非特殊需求,我们一般不需要定义自己的TypeAdapter。比如下边这个例子

class MyType{
    private int i = 1;
    private String name = "test";

    public MyType() {
        super();
    }
    public MyType(int id,String name) {
        this();
    }
}
.....
 MyType type = new MyType();
 System.out.println(gson.toJson(type));

 这样就可以将MyType对象与JSON格式字符串进行相互转换了,不得不说这是十分方便的。而且通过ExcluderFieldNamingStragety我们还可以对Gson的转换过程进行一定的控制。
 更为厉害的是,Gson对相对泛型和复杂的对象支持的很好,比如ArrayList<MyType>对象,也可以直接通过Gson进行转换。

Gson反射基础

 这一部分主要讲解一下Java相关的反射基础和Gson对其进行的扩展。
 我们都知道Java泛型是类型擦除的,也就是说在运行期间,我们无法通过反射获得泛型对象的类型,那Gson是如何解析类似于ArrayList<MyType>这样的对象的类型的呢?
 上篇博文中讲到了Gson中使用TypeToken来代表对象的类型,其创建时会使用到$Gson$Types这个对象,我们现在就来好好研究一下这个对象。

public static Type canonicalize(Type type) {
    if (type instanceof Class) {  //如果就是Class
      Class<?> c = (Class<?>) type;
        // c.getComponetType()就是返回数组对象的类型比如
      return c.isArray() ? new GenericArrayTypeImpl(canonicalize(c.getComponentType())) : c;
      // ????!!!! loop for ever ????
    } else if (type instanceof ParameterizedType) {  //多级泛型 HashMap<K,T>
      ParameterizedType p = (ParameterizedType) type;
      return new ParameterizedTypeImpl(p.getOwnerType(),
          p.getRawType(), p.getActualTypeArguments());
    } else if (type instanceof GenericArrayType) {   //数组泛型
      GenericArrayType g = (GenericArrayType) type;
      return new GenericArrayTypeImpl(g.getGenericComponentType());
    } else if (type instanceof WildcardType) {   // includes ?  , ? extends Number , ? super T
      WildcardType w = (WildcardType) type;
      return new WildcardTypeImpl(w.getUpperBounds(), w.getLowerBounds());
    } else {
      // type is either serializable as-is or unsupported
      return type;
    }
  }

 这里的ParameterizedType,GenericArrayType,WildcardType还有之后会出现的TypeVariable是一个重点啊,他们都是Type的子接口,代表所有类型的公共高阶接口。详细的解释在这里有转载博文
 还需要进一步的实验啊,以后再来补充这一部分。还有关于如何处理泛型类型擦除的逻辑。

###ReflectiveTypeAdapterFacotry
 在上边博文中我们说过,Gson会使用TypeToken来代表转换对象的类型,然后找到对应类型的TypeAdapter,但是对于用户自定义的类型,Gson是如何处理的呢?
 Gson的TypeAdapters中有一个可以处理自定义类型的TypeAdapterFactory,它就是ReflectiveTypeAdapterFactory,它也是这篇博文的重点内容。

 private final ConstructorConstructor constructorConstructor; //构造函数
  private final FieldNamingStrategy fieldNamingPolicy; //命名规则
  private final Excluder excluder; //排除器

 上述是其成员变量,文章开头所说的用户控制Gson的转换过程就是通过这三个对象实现的,我接下来会一一讲解。
 我们知道在Gson中通过TypeToken获得相应的TypeAdapter的逻辑如下

 for (TypeAdapterFactory factory : factories) {
        TypeAdapter<T> candidate = factory.create(this, type);
          System.out.print("1 ");
        if (candidate != null) {
            System.out.println(candidate.toString()+type.toString());
          call.setDelegate(candidate);
          typeTokenCache.put(type, candidate);
          return candidate;
        }
      }

 可以看出只要对应的facotry的create返回的对象不为null,就认为找到了对应的factory了,那我们在来看一下ReflectiveTypeAdapterFactory的create函数

public <T> TypeAdapter<T> create(Gson gson, final TypeToken<T> type) {
    Class<? super T> raw = type.getRawType();
    if (!Object.class.isAssignableFrom(raw)) {  
    //如果Object都不是raw的最高类型,表示raw不是Object的子类啦 
	 return null; // it's a primitive!
    }
    ObjectConstructor<T> constructor = constructorConstructor.get(type);
    return new Adapter<T>(constructor, getBoundFields(gson, type, raw));
  }

 ObjectConstrutor是为了构造器,为了创建一个相应的对象,主要是fromJson时使用的,而getBoundFields是为了获得对象的Filed类型。

    final InstanceCreator<T> typeCreator = (InstanceCreator<T>) instanceCreators.get(type); //no-args和type一一对应啊
    if (typeCreator != null) {
      return new ObjectConstructor<T>() {  //这就是最基础的Constructor啊
        public T construct() {
          return typeCreator.createInstance(type);
        }
      };
    }

    // Next try raw type match for instance creators
    @SuppressWarnings("unchecked") // types must agree
    final InstanceCreator<T> rawTypeCreator =
        (InstanceCreator<T>) instanceCreators.get(rawType);
    if (rawTypeCreator != null) {
      return new ObjectConstructor<T>() {
        public T construct() {
          return rawTypeCreator.createInstance(type);
        }
      };
    }

    ObjectConstructor<T> defaultConstructor = newDefaultConstructor(rawType); //默认的构造函数
    if (defaultConstructor != null) {
      return defaultConstructor;
    }


    ObjectConstructor<T> defaultImplementation = newDefaultImplementationConstructor(type, rawType);
    if (defaultImplementation != null) {
      return defaultImplementation;
    }

    // finally try unsafe
    return newUnsafeAllocator(type, rawType);
  }

 这段代码就是为了获得对应类型的构造器对象,在newDefaultConstructor会使用反射getDeclaredConstructor来获得默认的构造器。然后我在来看一下getBoundFields

 //获得成员变量吧
  private Map<String, BoundField> getBoundFields(Gson context, TypeToken<?> type, Class<?> raw) {
    Map<String, BoundField> result = new LinkedHashMap<String, BoundField>();
    if (raw.isInterface()) { //interface没有field啦
      return result;
    }

    Type declaredType = type.getType();
    while (raw != Object.class) { //从当前类型一直遍历到最高类型,把所有的对象的成员遍历都收集到
      Field[] fields = raw.getDeclaredFields();
      for (Field field : fields) {  //遍历所有的field
        boolean serialize = excludeField(field, true);//是否需要序列化,就是是否需要转换成Json
        boolean deserialize = excludeField(field, false);//是否需要从Json中转换过来
        if (!serialize && !deserialize) {
          continue;
        }
        field.setAccessible(true);
          //获得Field的type
        Type fieldType = $Gson$Types.resolve(type.getType(), raw, field.getGenericType());//获得Field的Type
        BoundField boundField = createBoundField(context, field, getFieldName(field),
            TypeToken.get(fieldType), serialize, deserialize); //之后详细解释
        BoundField previous = result.put(boundField.name, boundField);
        if (previous != null) {
          throw new IllegalArgumentException(declaredType
              + " declares multiple JSON fields named " + previous.name);
        }
      }
      type = TypeToken.get($Gson$Types.resolve(type.getType(), raw, raw.getGenericSuperclass()));
      raw = type.getRawType();
    }
    return result;
  }
   static abstract class BoundField {
    final String name;
    final boolean serialized;
    final boolean deserialized;

    protected BoundField(String name, boolean serialized, boolean deserialized) {
      this.name = name;
      this.serialized = serialized;
      this.deserialized = deserialized;
    }

 其实这一段代码逻辑很简单,主要就是遍历所有的成员遍历,大家可以看我的注释,其中涉及Type的操作我还没有搞懂….,但是createBoundField也是很重要的。

private ReflectiveTypeAdapterFactory.BoundField createBoundField(
      final Gson context, final Field field, final String name,
      final TypeToken<?> fieldType, boolean serialize, boolean deserialize) {
    final boolean isPrimitive = Primitives.isPrimitive(fieldType.getRawType());
    // special casing primitives here saves ~5% on Android...
    //其实就是创建一个BoundField的子类
    return new ReflectiveTypeAdapterFactory.BoundField(name, serialize, deserialize) {
      final TypeAdapter<?> typeAdapter = getFieldAdapter(context, field, fieldType);//获得子类的TypeAdapter<?>这是解析自定义类型对象的关键一步
      @SuppressWarnings({"unchecked", "rawtypes"}) // the type adapter and field type always agree
      @Override void write(JsonWriter writer, Object value)
          throws IOException, IllegalAccessException {
        Object fieldValue = field.get(value);
        TypeAdapter t =
          new TypeAdapterRuntimeTypeWrapper(context, this.typeAdapter, fieldType.getType());
        t.write(writer, fieldValue); //使用TypeAdapter进行写入
      }
      @Override void read(JsonReader reader, Object value)
          throws IOException, IllegalAccessException {
        Object fieldValue = typeAdapter.read(reader);
        if (fieldValue != null || !isPrimitive) {
          field.set(value, fieldValue);
        }
      }
      public boolean writeField(Object value) throws IOException, IllegalAccessException {
        if (!serialized) return false;
        Object fieldValue = field.get(value);
        return fieldValue != value; // avoid recursion for example for Throwable.cause
      }
    };
  }

 接下来我们就来看一下对应的TypeAdapter private Adapter(ObjectConstructor<T> constructor, Map<String, BoundField> boundFields),主要看其read和write方法。其中两个方法最后其实都是调用了BoundField的read和write方法,我们就只看read方法啦。

 @Override public T read(JsonReader in) throws IOException {
      if (in.peek() == JsonToken.NULL) {
        in.nextNull();
        return null;
      }

      T instance = constructor.construct(); //新建对象

      try {
        in.beginObject();//读出一个{
        while (in.hasNext()) {
          String name = in.nextName();//获得一个属性的name
          BoundField field = boundFields.get(name);//获得Field对象
          if (field == null || !field.deserialized) {//如果为null或者不需要解序列化
            in.skipValue();
          } else {
            field.read(in, instance);//使用BoundField进行write,可以参考createBoundField
          }
        }
      } catch (IllegalStateException e) {
        throw new JsonSyntaxException(e);
      } catch (IllegalAccessException e) {
        throw new AssertionError(e);
      }
      in.endObject();
      return instance;
    }

 这样对已自定义对象就可以自由的和JSON格式进行相互转换啦。但是有些同学可能会问了ArrayList<MyType>是如何转换的呢?那我们就要研究CollectionTypeAdapterFactory了,如果你去internal/bind文件夹下查看,你会发现很多类似的类。下边就贴出来其create函数

 public <T> TypeAdapter<T> create(Gson gson, TypeToken<T> typeToken) {
    Type type = typeToken.getType();

    Class<? super T> rawType = typeToken.getRawType();
    if (!Collection.class.isAssignableFrom(rawType))//看是否是Collection的子类 {
      return null;
    }

    Type elementType = $Gson$Types.getCollectionElementType(type, rawType);//获得element的Type就是List<T>的T的类型,同学们可能会疑问泛型不是类型擦除了吗?你可以阅读一下$Gson$Types中的代码,自行了解一下,我暂时还没有完全搞懂
    //之后就和ReflectiveTypeAdapterFactory的逻辑类似啦
    TypeAdapter<?> elementTypeAdapter = gson.getAdapter(TypeToken.get(elementType));
    ObjectConstructor<T> constructor = constructorConstructor.get(typeToken);

    @SuppressWarnings({"unchecked", "rawtypes"}) // create() doesn't define a type parameter
    TypeAdapter<T> result = new Adapter(gson, elementType, elementTypeAdapter, constructor);
    return result;
  }

 感觉关于TypeToken$Gson$Type还是没有完全明白,所以并没有过多涉及,大家如果发现神马问题,或者有好的建议,欢迎大家批判和指教。

Share

Gson源码分析

 最近研究了google开源的Json库Gson,在这里进行总结一下,应该会分为3篇博客。第一篇主要讲一下Gson的整个框架吧;第二篇主要总结一下Gson关于反射的部分;最后一篇会总结一下JsonWriter和JsonReader,主要是Json对象的处理啦。

Gson

 Gson是可以转换Java对象为JSON表示的java库,也可以将JSON转换为Java对象,并且可以转换你没有源代码的预设的复杂对象
 现在有一些JSON转换库,但是大多数都需要你在class中设置annotation;如果没有class的源代码你就无法实现转换,而且大多数无法支持全部的Java范型。Gson把实现上述作为设计的主要目标。
 Gson的目标

  • 提供简单的toJson(),和fromJson来实现Java对象和JSON数据的相互转换
  • 运行预先存在的无法修改的对象与Json的转换
  • 支持Java范型
  • 运行用户自定义对象的结构
  • 支持复杂对象的处理

框架描述

框架类图
 这是Gson库的类图,没有将所有类都表现上去,只是画了几个比较主要的类和我研究过的类。这篇文章就主要梳理一下这个框架,研究一下几个比较主要的函数的流程和各个对象的协作。

1.GsonBuilder

 GsonBuilder是Gson对象的Builder类啦,我们可以先看一下Gson对象的构造函数的复杂度啦,所以如果希望配置Gson,就只有使用Builder模式啦,这也是Java设计模式中所推荐的

Gson(final Excluder excluder, final FieldNamingStrategy fieldNamingPolicy,
      final Map<Type, InstanceCreator<?>> instanceCreators, boolean serializeNulls,
      boolean complexMapKeySerialization, boolean generateNonExecutableGson, boolean htmlSafe,
      boolean prettyPrinting, boolean serializeSpecialFloatingPointValues,
      LongSerializationPolicy longSerializationPolicy,
      List<TypeAdapterFactory> typeAdapterFactories)

  GsonBuilder文件中的注释也有说明:

使用这个对象去配置你的Gson对象,当你希望修改默认配置时

 我们现在可以依次介绍一下GsonBuilder的成员变量或者说是其所依赖的类型吧。

  • Exculder 是用来配置一些你不希望被转换成JSON格式的对象的成员变量的,比如你只希望自己的对象中所有public的成员变量被转换为JSON格式,那么就需要使用到这个对象,添加规则去除去所有非pulbic的成员变量。

  • LongSerializationPolicy

  • FieldNamingStragety

  • InstanceCreator

  • TypeAdapterFactory

2.Gson

 Gson对象就是我们最常使用的对象啦,它有一系列的fromJson,toJson的成员函数供我们调用,这篇文章的一个重点就是梳理同这两类函数的逻辑。
 我们先来看一下Gson的构造函数吧。构造函数名和参数列表在前边已经列出来啦,构造函数中就是将参数列表中的对象配置为成员变量,不过要注意的是对TypeAdapterFactory的操作啦。


	....
    List<TypeAdapterFactory> factories = new ArrayList<TypeAdapterFactory>();

    // built-in type adapters that cannot be overridden
    factories.add(TypeAdapters.JSON_ELEMENT_FACTORY);
    factories.add(ObjectTypeAdapter.FACTORY);
    ..... //还有很多基本的TypeAdapterFactory
    // the excluder must precede all adapters that handle user-defined types
    factories.add(excluder);

    // user's type adapters
    factories.addAll(typeAdapterFactories);

    // type adapters for basic platform types
    factories.add(TypeAdapters.STRING_FACTORY); //里边是一些基本类型的adapter啦
       ......
    this.factories = Collections.unmodifiableList(factories);

 Gson内置了很多基本类型和对象的转换组件,类型为TypeAdapter,可以通过相应的TypeAdapterFactory来获得,所以这里factories就预先加载了很多基本类型转换组件的Factory,然后factories.addAll(typeAdapterFactories)是添加构造函数中传入的用户自定义的TypeAdapterFactory
fromJsontoJson这两类函数我们在介绍完所有的类之后在解析吧。

3.TypeAdapter

 这是一个抽象类,提供了两个抽象函数作为hook函数来让用户重载,分别是public abstract void write(JsonWriter out, T value) throws IOException;public abstract T read(JsonReader in) throws IOException;一读一写,用户如果要解析自己自定义的对象,就可以继承这个类,然后实现上述两个方法,并在GsonBuilder中使用GsonBuilder registerTypeAdapter(Type type, Object typeAdapter) 来注册这个转换类,然后Gson就可以对你的自定义对象进行转换啦。需要注意的是,这里的转换完全由你自己控制,所以可定制性比较强。在介绍TypeAdapters`时,我们会介绍几个简单的TypeAdapter的实现。

4.TypeAdapterFactory

 这是一个接口,自定义了一个函数:<T> TypeAdapter<T> create(Gson gson, TypeToken<T> type);,具体的实现方法,我们可以在后边的TypeAdapters类中看到.

5.TypeAdapters

 这个类中定义了几乎所有的基础类型的TypeAdapter和Factory,我们现在挑出一个来研究一下。这是一个URL对象的JSON转换器啦。

public static final TypeAdapter<URL> URL = new TypeAdapter<URL>() {
    @Override
    public URL read(JsonReader in) throws IOException {
      if (in.peek() == JsonToken.NULL) {
        in.nextNull();
        return null;
      }
      String nextString = in.nextString(); //读出in中的内容
      return "null".equals(nextString) ? null : new URL(nextString);//根据读出的内容,创建URL对象
    }
    @Override
    public void write(JsonWriter out, URL value) throws IOException {
      out.value(value == null ? null : value.toExternalForm()); //写入内容
    }
  };

  public static final TypeAdapterFactory URL_FACTORY = newFactory(URL.class, URL);//创建Facotry啦

  我们可以看到,这是一个URL的转换器,JsonReaderJsonWriter后边会介绍到,现在你就可以把他们当做类似于StringBuilder一类的Json的生成器和解释器。

6.TypeToken

 TypeToken可以看做是对Java范型的扩展,大家都知道Java范型是有类型擦除效果的,无法获得其真实类型。而这个类就是为了处理这种情况的,我们从文件中的注释也可以了解到。具体的内容,我们希望在Gson相关的第二篇博文中再详细说明,主要就是涉及围绕TypeToken的一系列的Gson对范型的支持和处理。
 而在Gson对象中,TypeToken主要是用于根据Type来获得相应的TypeAdapter。

其他类

 还有很多其他的类没有介绍,其中有些不太重要,我也没有太多了解,另外一些我会在接下去的两篇博文中详细介绍。

转换流程

 接下来,我们就主要理通Gson两个最重要的函数的逻辑,之后的两篇博文会详细介绍其中的重要的细节,这篇博文就只诉说每一步大致的作用啦。

1 fromJson()

 函数名为fromJson的函数比较多,我们只看下边这个

 @SuppressWarnings("unchecked")
  public <T> T fromJson(JsonReader reader, Type typeOfT) throws JsonIOException, JsonSyntaxException {
    boolean isEmpty = true;
    boolean oldLenient = reader.isLenient();
    reader.setLenient(true);
    try {
      reader.peek();
      isEmpty = false;
      // 反射部分的精髓,主要的就是TypeToken和TypeAdapter啦
      TypeToken<T> typeToken = (TypeToken<T>) TypeToken.get(typeOfT);  //1:工厂方法,其中调用typeToken的构造器
      TypeAdapter<T> typeAdapter = getAdapter(typeToken); //2:通过type来获得Adapter啊
      T object = typeAdapter.read(reader);//3:通过typeAdapter来转换对象
      return object;
    } catch (EOFException e) {
      /*
       * For compatibility with JSON 1.5 and earlier, we return null for empty
       * documents instead of throwing.
       */
      if (isEmpty) {
        return null;
      }
      throw new JsonSyntaxException(e);
    } catch (IllegalStateException e) {
      throw new JsonSyntaxException(e);
    } catch (IOException e) {
      // TODO(inder): Figure out whether it is indeed right to rethrow this as JsonSyntaxException
      throw new JsonSyntaxException(e);
    } finally {
      reader.setLenient(oldLenient);
    }
  }

 如同代码中标注的一样,fromJson中大致分为3个比较重要的步奏.

  • TypeToken typeToken = (TypeToken) TypeToken.get(typeOfT); 获得要转换类型对应的TypeToken对象,主要涉及的Gson中范型和反射的部分逻辑,我们第二篇博文再讲

  • TypeAdapter typeAdapter = getAdapter(typeToken); //通过type来获得Adapter啊,这个我们先来看一下getAdapter函数,就是找出TypeToken所对应的TypeAdapter对象,用于下一步的解析。

    @SuppressWarnings("unchecked")
      public <T> TypeAdapter<T> getAdapter(TypeToken<T> type) {
        TypeAdapter<?> cached = typeTokenCache.get(type);  // typeTokenCache?? 创造adapter是很麻烦的事情吗?有cache
        if (cached != null) {
          return (TypeAdapter<T>) cached;
    
        }
    
        Map<TypeToken<?>, FutureTypeAdapter<?>> threadCalls = calls.get();  //threadLocal get
        boolean requiresThreadLocalCleanup = false; //是否需要清理threadLocal中的数据
        if (threadCalls == null) {
          threadCalls = new HashMap<TypeToken<?>, FutureTypeAdapter<?>>();
          calls.set(threadCalls);
          requiresThreadLocalCleanup = true;
        }
    
        // the key and value type parameters always agree
        FutureTypeAdapter<T> ongoingCall = (FutureTypeAdapter<T>) threadCalls.get(type);
        if (ongoingCall != null) {
          return ongoingCall;
        }
    
        try {
          FutureTypeAdapter<T> call = new FutureTypeAdapter<T>();
          threadCalls.put(type, call);
    
          for (TypeAdapterFactory factory : factories) {
            TypeAdapter<T> candidate = factory.create(this, type);  // 通过factory 来创建TypeAdapter啊,由于需要遍历list比较麻烦
            if (candidate != null) {
              call.setDelegate(candidate);
              typeTokenCache.put(type, candidate);
              return candidate;
            }
          }
         ....
        } finally {
          threadCalls.remove(type);
    	  ....
        }
      }
    
    • T object = typeAdapter.read(reader);//3:通过typeAdapter来转换对象,具体过程,和JsonReader,JsonWriter的原理,第三篇博文再进行讲述

      2 toJson

       其实toJson和fromJson很像,就是获得相应的TypeAdapter,只不过这次调用的是write方法。这里就不累赘多说啦。

      总结

       博客还未写完,代码还没有看透…..
Share

Android-Async-Http 源码解析

 前几天去参加一个面试,被问到了一些android 网络方面的知识,发现自己在这个方面还有些不足,需要自我补充一下相关的知识,于是最近找了些开源的网络模块的第三方库来阅读,主要是想深入了解一下http协议和相关的代码框架组织问题。这篇博客就总结一下自己阅读android-async-http的一些体会和学习吧。

简介

 介绍android async http 的相关事项,主要是翻译github上的话吧
 这段是官网翻译,大家请随意跳过,详细介绍请转到[http://loopj.com/android-async-http/]
 android-async-http是建立在Apache HttpClient之上的基于回调的异步android http client,它使用Handler机制,请求在UI线程之外发生,但是回调逻辑在UI线程中进行执行

特点(部分):

  • 执行异步request,在匿名回调中处理response
  • Http 请求 发生在UI线程之外
  • 使用ThreadPool来负载多线程消耗
  • GET/POST params 生成器
  • 支持文件断点续传
  • 支持自动重试
  • 支持流式Json数据上传
  • 可以处理重定向和请求循环
  • 自动的gzip压缩
  • 支持cookie
  • 可以通过BaseJsonResponseHandler和Jackson Json , Gson 和其他Json第三方库进行集成

基本使用


  AsyncHttpClient client = new AsyncHttpClient();
  
  client.get("https://www.google.com", new       AsyncHttpResponseHandler() {   
      
      @Override
      public void onStart() {
          // 请求开始发生的回调    
      }
 
      @Override
      public void onSuccess(int statusCode, Header[] headers, byte[] responseBody) {
          // 成功获得response的回调
      }
 
      @Override
      public void onFailure(int statusCode, Header[] headers, byte[] responseBody, Throwable
  error)
  {
          // 失败的回调 :(
      }
 
      @Override
      public void onRetry(int retryNo) {
          // 请求被重试时的回调
      }
 
      @Override
      public void onProgress(long bytesWritten, long totalSize) {
          // 请求发生过程中的回调
      }
 
      @Override
      public void onFinish() {
          // 完成请求时的对调,未知成功还是失败
      }
  }); 

源码解析

主要类类图
 上图就是android-async-http的主要类的类图,我们下面就来一个一个类解析一下

AsyncHttpClient

 先看AsyncHttpClient,它是这个http库的核心类之一,封装了发生http请求的所有逻辑,可以说它是这个库的中心类。它的构造函数如下:

      public AsyncHttpClient(SchemeRegistry schemeRegistry) {
        // http param
        BasicHttpParams httpParams = new BasicHttpParams();

        // connect params builder ?????
        ConnManagerParams.setTimeout(httpParams, connectTimeout);
        ConnManagerParams.setMaxConnectionsPerRoute(httpParams, new ConnPerRouteBean(maxConnections));
        ConnManagerParams.setMaxTotalConnections(httpParams, DEFAULT_MAX_CONNECTIONS);

        // httpConnectionParams
        HttpConnectionParams.setSoTimeout(httpParams, responseTimeout);
        HttpConnectionParams.setConnectionTimeout(httpParams, connectTimeout);
        HttpConnectionParams.setTcpNoDelay(httpParams, true);
        HttpConnectionParams.setSocketBufferSize(httpParams, DEFAULT_SOCKET_BUFFER_SIZE);

        HttpProtocolParams.setVersion(httpParams, HttpVersion.HTTP_1_1);

        ClientConnectionManager cm = createConnectionManager(schemeRegistry, httpParams);
        Utils.asserts(cm != null, "Custom implementation of #createConnectionManager(SchemeRegistry, BasicHttpParams) returned null");


        //thread poll
        threadPool = getDefaultThreadPool();

        /**
         * weakHashMap context:这是不会出现内存泄露
         * synchronizedMap 是建立一个线程安全的map加一个同步锁啊。
         */
        requestMap = Collections.synchronizedMap(new WeakHashMap<Context, List<RequestHandle>>());

        clientHeaderMap = new HashMap<String, String>();


        httpContext = new SyncBasicHttpContext(new BasicHttpContext());
        // 默认的apache的httpclient
        httpClient = new DefaultHttpClient(cm, httpParams);

        // 请求拦截器啊
        httpClient.addRequestInterceptor(new HttpRequestInterceptor() {
            @Override
            public void process(HttpRequest request, HttpContext context) {
                // 预处理,声明浏览器支持的编码类型啊
                if (!request.containsHeader(HEADER_ACCEPT_ENCODING)) { //加上GZIP的头部
                    request.addHeader(HEADER_ACCEPT_ENCODING, ENCODING_GZIP);
                }

                // 对于默认的clientHeader进行遍历,比较,添加
                for (String header : clientHeaderMap.keySet()) {
                    if (request.containsHeader(header)) {  //如果包含
                        Header overwritten = request.getFirstHeader(header);
                        log.d(LOG_TAG,
                                String.format("Headers were overwritten! (%s | %s) overwrites (%s | %s)",
                                        header, clientHeaderMap.get(header),
                                        overwritten.getName(), overwritten.getValue())
                        );

                        //remove the overwritten header
                        request.removeHeader(overwritten);
                    }
                    request.addHeader(header, clientHeaderMap.get(header)); //写入clientHeaderMap中的值
                }
            }
        });

        // response拦截器,对gzip进行解压缩啊
        httpClient.addResponseInterceptor(new HttpResponseInterceptor() {

            @Override
            public void process(HttpResponse response, HttpContext context) {
                final HttpEntity entity = response.getEntity(); //
                if (entity == null) {
                    return;
                }
                final Header encoding = entity.getContentEncoding();
                if (encoding != null) {
                    for (HeaderElement element : encoding.getElements()) { //遍历头部信息
                        if (element.getName().equalsIgnoreCase(ENCODING_GZIP)) {
                            response.setEntity(new InflatingEntity(entity)); //InflatingEntity 这是解压gzip的
                            break;
                        }
                    }
                }
            }
        });

        // 另外一个模块的请求拦截器 ???? 身份认证的
        httpClient.addRequestInterceptor(new HttpRequestInterceptor() {
            @Override
            public void process(final HttpRequest request, final HttpContext context) throws HttpException, IOException {
                AuthState authState = (AuthState) context.getAttribute(ClientContext.TARGET_AUTH_STATE);
                CredentialsProvider credsProvider = (CredentialsProvider) context.getAttribute(
                        ClientContext.CREDS_PROVIDER);
                HttpHost targetHost = (HttpHost) context.getAttribute(ExecutionContext.HTTP_TARGET_HOST);

                if (authState.getAuthScheme() == null) {
                    AuthScope authScope = new AuthScope(targetHost.getHostName(), targetHost.getPort());
                    Credentials creds = credsProvider.getCredentials(authScope);
                    if (creds != null) {
                        authState.setAuthScheme(new BasicScheme());
                        authState.setCredentials(creds);
                    }
                }
            }
        }, 0);

        // 重试Handler,用于重新发送请求
        httpClient.setHttpRequestRetryHandler(new RetryHandler(DEFAULT_MAX_RETRIES, DEFAULT_RETRY_SLEEP_TIME_MILLIS));
    }

 在构造函数中,AsyncHttpClient主要是初始化了threadPool作为发生请求的线程池,httpContext作为发生请求的网络context,还有最为重要的httpClient,它的类型是Apache的DefaultHttpClient,然后设置了设计gzip压缩和身份认证的请求拦截器和回应拦截器,具体逻辑代码中都有注释。
 AsyncHttp中还有一个我认为是整个库精髓所在的函数,如果你理解了这个函数,那么整个库的代码框架和思想其实你就已经知道了。它就是sendRequest(),AsyncHttp的关于网络请求的方法,比如get,post,head,最终都是调用了这个函数。在这个函数中,其他几个比较主要的类都有出现。

 /**
     *
     * 这是这里的重点啊,创建一个request放在队列中,等待一个thread去执行
     * Puts a new request in queue as a new thread in pool to be executed
     *
     * @param client          HttpClient to be used for request, can differ in single requests
     * @param contentType     MIME body type, for POST and PUT requests, may be null
     * @param context         Context of Android application, to hold the reference of request
     * @param httpContext     HttpContext in which the request will be executed
     * @param responseHandler ResponseHandler or its subclass to put the response into
     * @param uriRequest      instance of HttpUriRequest, which means it must be of HttpDelete,
     *                        HttpPost, HttpGet, HttpPut, etc.
     * @return RequestHandle of future request process
     */
    protected RequestHandle sendRequest(DefaultHttpClient client, HttpContext httpContext, HttpUriRequest uriRequest, String contentType, ResponseHandlerInterface responseHandler, Context context) {
        if (uriRequest == null) {
            throw new IllegalArgumentException("HttpUriRequest must not be null");
        }

        if (responseHandler == null) {
            throw new IllegalArgumentException("ResponseHandler must not be null");
        }

        if (responseHandler.getUseSynchronousMode() && !responseHandler.getUsePoolThread()) {
            throw new IllegalArgumentException("Synchronous ResponseHandler used in AsyncHttpClient. You should create your response handler in a looper thread or use SyncHttpClient instead.");
        }

        if (contentType != null) {
            if (uriRequest instanceof HttpEntityEnclosingRequestBase && ((HttpEntityEnclosingRequestBase) uriRequest).getEntity() != null && uriRequest.containsHeader(HEADER_CONTENT_TYPE)) {
                log.w(LOG_TAG, "Passed contentType will be ignored because HttpEntity sets content type");
            } else {
                uriRequest.setHeader(HEADER_CONTENT_TYPE, contentType);
            }
        }

        responseHandler.setRequestHeaders(uriRequest.getAllHeaders());
        responseHandler.setRequestURI(uriRequest.getURI());

        // runnable
        AsyncHttpRequest request = newAsyncHttpRequest(client, httpContext, uriRequest, contentType, responseHandler, context);

        threadPool.submit(request);

        // Handler 持有Request的弱引用,可以对其执行操作
        RequestHandle requestHandle = new RequestHandle(request);

        if (context != null) {  //如果此时context为不为空
            List<RequestHandle> requestList;
            // Add request to request map
            synchronized (requestMap) {  // 需要添加到context作为键的List中去
                requestList = requestMap.get(context);
                if (requestList == null) {
                    requestList = Collections.synchronizedList(new LinkedList<RequestHandle>());
                    requestMap.put(context, requestList);
                }
            }

            requestList.add(requestHandle);

            // 每次发送请求的时候进行一轮runnable删除
            Iterator<RequestHandle> iterator = requestList.iterator();
            while (iterator.hasNext()) {
                if (iterator.next().shouldBeGarbageCollected()) {
                    iterator.remove();
                }
            }
        }

        return requestHandle; //返回句柄啊
    }

 我们可以看到在函数中

  • 使用传入的参数和对象本身的成员变量来构造了一个AsynHttpRequest(本身继承Runnable,之后详细介绍),将其放入threadPool中
  • 然后生成RequestHandler对象来持有这个请求(用户可以通过RequestHandler对请求进行各类操作,比如取消),需要注意的是这个Handler并不是android的Handler,而是供用户操纵Request的句柄类
  • 然后更新requestMap,这是一个android Context作为主键的map,主要是记录各个Context的网络请求,需要注意的是这里使用的是WeakHashMap,防止内存泄露
  • 添加Handler到requestList中,然后遍历requestList删除需要垃圾回收的对象
  • 最后返回requestHandler。
AsyncHttpRequest

 这个类是Runnable的子类,主要是用来进行发送请求和重试这套逻辑,而且ResponseHandlerInterface中的大多数回调函数都是在此对象中回调的。我们主要看一下它的run(),makeRequest()makemakeRequestWithRetries()方法

@Override
    public void run() {
        if (isCancelled()) {  //如果run的时候是取消状态,那么就关闭了
            return;
        }

        // Carry out pre-processing for this request only once.
        if (!isRequestPreProcessed) {  //必须进行一次预处理
            isRequestPreProcessed = true;
            onPreProcessRequest(this);
        }

        if (isCancelled()) {
            return;
        }

        responseHandler.sendStartMessage();  // 回调handler,已经开始

        if (isCancelled()) {
            return;
        }

        // 进行带重试的请求
        try {
            makeRequestWithRetries();
        } catch (IOException e) {
            if (!isCancelled()) {
                responseHandler.sendFailureMessage(0, null, null, e);
            } else {
                AsyncHttpClient.log.e("AsyncHttpRequest", "makeRequestWithRetries returned error", e);
            }
        }

        if (isCancelled()) {
            return;
        }

        responseHandler.sendFinishMessage();

        if (isCancelled()) {
            return;
        }

        // Carry out post-processing for this request.
        onPostProcessRequest(this);

        isFinished = true;
    }

 可以看出,在run中,根据发送网络请求的不同阶段调用了一系列的回调函数,其中比较重要的是responseHandler.sendFinishMessage(),在这里会回调函数进行解析response;在各个阶段开始前都有调用isCancelled()进行判断是否request被取消了。
 接下来是makeRequest(),在其中就调用了HttpClient.execute(request,context)进行正式的发送请求。

private void makeRequest() throws IOException {
        if (isCancelled()) {
            return;
        }

        // Fixes #115
        if (request.getURI().getScheme() == null) {
            // subclass of IOException so processed in the caller
            throw new MalformedURLException("No valid URI scheme was provided");
        }

        if (responseHandler instanceof RangeFileAsyncHttpResponseHandler) {
            ((RangeFileAsyncHttpResponseHandler) responseHandler).updateRequestHeaders(request);
        }

        HttpResponse response = client.execute(request, context);

        if (isCancelled()) {
            return;
        }

        // Carry out pre-processing for this response.
        responseHandler.onPreProcessResponse(responseHandler, response);

        if (isCancelled()) {
            return;
        }

        // The response is ready, handle it.
        responseHandler.sendResponseMessage(response);

        if (isCancelled()) {
            return;
        }

        // Carry out post-processing for this response.
        responseHandler.onPostProcessResponse(responseHandler, response);
    }

RequestHandler

 持有AsyncHttpRequest一个弱引用的句柄类,主要的功能是可以让客户端取消AsyncHttpRequest请求

AsyncHttpResponseHandler

 实现ResponseHandlerInterface的一个类,也是我们经常会用到的一个类,在android-async-http中有很多类都实现了ResponseHandlerInterface或者继承了这个类,比如BianryHttpResponseHandler,FileAsyncHttpResponseHandler,每个类都对应不同的网络请求的返回数据资源,有些可能是专门用于文件下载的,有些是解析json的,大家可以自己去了解各个类的作用。
 android-sync-http发送网络请求可以同步也可以异步,而且异步会在相应的thread中进行回调,其中涉及的逻辑就在这些类中。这个类也可以控制发送请求所使用的线程。

/**
     * Creates a new AsyncHttpResponseHandler with a user-supplied looper. If
     * the passed looper is null, the looper attached to the current thread will
     * be used.
     *
	 * 如果调用了这个,那么就不是异步,而且是在当前线程中调用了
     * @param looper The looper to work with
     */
    public AsyncHttpResponseHandler(Looper looper) {
        this.looper = looper == null ? Looper.myLooper() : looper;

        // Use asynchronous mode by default.
        setUseSynchronousMode(false);

        // Do not use the pool's thread to fire callbacks by default.
        setUsePoolThread(false);
    }

&emsp;大家可以发现构造函数传入了一个Looper,相信对android Handler机制比较了解的同学立即就知道这个库的异步调用是如何在当前线程中进行回调的了吧。这个类实现的回调函数中大多数都是进行sendMessage(obtainMessage(FAILURE_MESSAGE, new Object[]{statusCode, headers, responseBody, throwable}));这样的调用。

 protected void sendMessage(Message msg) {   // 如果是同步就自己处理,否则交由handler处理
        if (getUseSynchronousMode() || handler == null) {
            handleMessage(msg);
        } else if (!Thread.currentThread().isInterrupted()) { // do not send messages if request has been cancelled
            Utils.asserts(handler != null, "handler should not be null!");
            handler.sendMessage(msg);
        }
    }

 这就是发生message的函数,发现如果同步模式,那么就调用自己的handleMessage处理,否则交由构造函数中的Looper生成的handler进行处理,其实最终处理的还是这个对象的handlerMessage方法,但是是在另外一个Looper所在的线程中执行的。
&emsp;其实这个类中还有两个涉及http response解析的方法也是很重要的,就是sendResponseMesssage(HttpResponse response)getResponseData(HttpEntity entity),可是我对http协议不太了解,也害怕说错了,这里就只附上源码吧,上边有我的注释

// 获得网络请求返回进行处理
    @Override
    public void sendResponseMessage(HttpResponse response) throws IOException {
        // do not process if request has been cancelled
        if (!Thread.currentThread().isInterrupted()) {  //thread isInterrupted means that request is cancelled
            StatusLine status = response.getStatusLine(); // 状态行
            byte[] responseBody; // 回复体
            responseBody = getResponseData(response.getEntity());
            // additional cancellation check as getResponseData() can take non-zero time to process
            if (!Thread.currentThread().isInterrupted()) {
                if (status.getStatusCode() >= 300) {
                    sendFailureMessage(status.getStatusCode(), response.getAllHeaders(), responseBody, new HttpResponseException(status.getStatusCode(), status.getReasonPhrase()));
                } else {
                    sendSuccessMessage(status.getStatusCode(), response.getAllHeaders(), responseBody);
                }
            }
        }
    }

    /**
     * Returns byte array of response HttpEntity contents
	 * 解析http的response
     *
     * @param entity can be null
     * @return response entity body or null
     * @throws java.io.IOException if reading entity or creating byte array failed
     */
    byte[] getResponseData(HttpEntity entity) throws IOException {
        byte[] responseBody = null;
        if (entity != null) {
            InputStream instream = entity.getContent(); // 获得输入流
            if (instream != null) {
                long contentLength = entity.getContentLength(); // 获得size
                if (contentLength > Integer.MAX_VALUE) {
                    throw new IllegalArgumentException("HTTP entity too large to be buffered in memory");
                }
                int buffersize = (contentLength <= 0) ? BUFFER_SIZE : (int) contentLength; // contentLength有可能为负数吗
                try {
                    ByteArrayBuffer buffer = new ByteArrayBuffer(buffersize); // byte array的buffer类
                    try {
                        byte[] tmp = new byte[BUFFER_SIZE];
                        long count = 0;
                        int l;
                        // do not send messages if request has been cancelled
                        while ((l = instream.read(tmp)) != -1 && !Thread.currentThread().isInterrupted()) {
                            count += l;
                            buffer.append(tmp, 0, l);
                            sendProgressMessage(count, (contentLength <= 0 ? 1 : contentLength));
                        }
                    } finally {
                        AsyncHttpClient.silentCloseInputStream(instream);
                        AsyncHttpClient.endEntityViaReflection(entity);
                    }
                    responseBody = buffer.toByteArray();
                } catch (OutOfMemoryError e) {
                    System.gc();
                    throw new IOException("File too large to fit into available memory");
                }
            }
        }
        return responseBody;
    }

总结

 android-async-http 算是源代码量最小的一个网络库了,当然它还有些却缺点,比如没有缓存机制,我看github中已经有人给它加上了缓存,大家也可以自己尝试一下,并且更好的是,这个库可以与其他的第三方库进行集成,大家可以打造属于自己的网络请求+处理数据的框架。

Share

初识Dagger2

 要使用Dagger2,首先要了解的就是控制反转和依赖注入这两个概念。

一、控制反转

 在wiki词条中,控制反转如下定义:In software engineering, inversion of control (IoC) describes a design in which custom-written portions of a computer program receive the flow of control from a generic, reusable library. A software architecture with this design inverts control as compared to traditional procedural programming: in traditional programming, the custom code that expresses the purpose of the program calls into reusable libraries to take care of generic tasks, but with inversion of control, it is the reusable code that calls into the custom, or task-specific, code.

 其中主要的含义就是客户端代码(custom-writen)可以控制一般性的可复用库的控制流(flow of control),比如组件对象的创建的控制权。
 控制反转和传统编程的对比:

  • IoC模式:调用类只依赖于接口,而不依赖于具体的实现类,减少了耦合。控制权交给了容器,在运行时才由容器决定将具体的实现动态的“注入”到调用类的对象中。
  • 传统编程:决定使用哪个具体的实现类的控制权在调用类本身,在编译阶段就确定了。

 所以,所谓的“控制反转”概念就是对组件对象控制权的转移,从程序代码本身转移到了外部容器。而依赖注入则是控制反转实现的一种方式。

二、依赖注入

 先说依赖,依赖就是你两个代码模块的耦合(a dependency is a coupling between two modules of your code),一般来说,当对象A中还有类型为B的成员变量时,我们就可以说A依赖于B,二者就相互耦合,至于是何种耦合,那就要依情况而定。

 如果要避免这种依赖,我们可以设计一个interface IB,让B实现IB,然A依赖于IB,这就是所谓的依赖倒置原则。

 但是对于对象的创建,我们是无法规避所谓的依赖的,当你在一个对象中创建了另外一个类型的对象(new),就会产生依赖。所以在设计模式中,会有一系列的创建型模式来减少这类的依赖。

 从我现在对工厂模式和依赖注入的理解,二者在减少依赖这个方面的贡献应该是相同的,但是依赖注入可以减少你自己手写的代码。而依赖于反射的依赖注入在效率上会有所下降。

  A dependency is an object) that can be used (a service)). An injection is the passing of a dependency to a dependent object (a client)) that would use it. The service is made part of the client’s state).[1]
Passing the service to the client, rather than allowing a client to build or find the service, is the fundamental requirement of the pattern.
 依赖注入的基本原则是:应用组件不应该负责查找资源或者其他依赖的协作对象。配置对象的工作应该由IoC容器负责,“查找资源”的逻辑应该从应用组件的代码中抽取出来(比如new出来应用组件对象),交给IoC容器负责,这样可以让程序准从依赖导致原则。

三、Dagger2

 Dagger2 是google从Dagger1中fork的一个分支。从一开始,Dagger2所秉承的观念就是使用代码自动生成和手写代码(类似于javabean的写一些有固定前缀的函数或者类,接口)来实现依赖注入。所以,Dagger2就有以下几点比较特殊的地方

  • 完全未使用反射,图的验证,配置和预处理都是在编译阶段完成。
  • 由于是通过生成代码来实现依赖注入,所以更容易调试和回溯异常路径,可以提供完整的调用函数栈。
  • 更高的性能,根据google的数据,性能提高了13%。
  • 不太灵活和动态,因为没有使用反射。

四、Dagger2使用

 具体的说明文档请查阅http://google.github.io/dagger/,这个demo在我的github上[https://github.com/ztelur/DaggerProject]

 这里只展示android上一个demo,解释各个注释的含义和一些常见的问题

  1 @Inject
按照标注的元素的不同,这个注释的作用不同

  • 标注元素为构造函数,当程序需要这个类型的对象时,就会
    调用这个构造函数,从而生成相应的对象,如果构造函数有参数,Dagger2会在调用构造函数之前先去获得这些对象,所以你要保证它的参数也提供了可以被Dagger2调用的构造函数
    标注在构造函数上
  • 标注元素为成员变量,这就标示,这个成员变量需要Dagger2来进行注入,也就是说Dagger2来初始化它,通常你需要调用Component.void injectSomeType(SomeType someType)这个方法来让Dagger进行自动化注入。
    标注在成员变量上
    inject函数

 2.@Module
module是拥有可以提供依赖的函数的类,我们定义一个类,标注为module,然后Dagger2就知道哪里可以找到构建一个对象所需要的依赖啦。而且module被设计为可以被分割和组合的模式,有益于模块的划分。

 3.@Provide:
在标注为module的类中的函数可以标注为provide,标示可以提供相应的依赖,函数的前缀必须为provides.
module和provide
 4.@Component
这是Dagger2依赖注入的核心模块,类似于一个注入器的角色。它是@Inject和@Module的桥梁。我们必须创建一个interface,标注为Component,然后列出所有它需要的Module。component中还可以提供一些方法来获得一些对象。component可以有scope,比如Application的生命周期,activity的生命周期,这一块我还没有搞清楚…..

 5.@Singleton
这是标示一个单例的注释,可以和provide共同标注一个函数,标示这个函数返回的对象都是单例的,也可以和component一起标注一个component,标示这个component的scope是全局的。
component
 6.Lazy injections
这个不是一个标注,而是一个可以推迟初始化的容器,比如你依赖一个对象B(@Inject B mB),但是你希望当你第一次使用它的时候在初始化,所以你就可以用Lazy(@Inject Lazy<B> mB)

五、Dagger2常见问题

  1. 如何在gradle上配置Dagger2:可以参考http://stackoverflow.com/questions/22976251/how-to-configure-dagger-gradle
  2. 程序包javax.annotation包不存在,找不到Generated:需要在Gradle中添加provided 'javax.annotation:jsr250-api:1.0'依赖

  3. 对于private的成员变量的注入问题:Dagger2是不支持private的成员变量的直接注入的。解决方法有两个:一个是换成protected,或者使用构造函数inject.但是这两种方法都没有良好的解决android平台中Activity,Application等类的注入问题.
    http://stackoverflow.com/questions/16598123/android-dagger-dependency-injection-fails-on-private-fields

  4. 对于第三方对象的注入问题
    https://github.com/google/dagger/issues/128#issuecomment-86702574
  5. 自定义scope问题:这个问题我一直没有搞懂,希望了解的同学帮助一下.
    http://stackoverflow.com/questions/29923376/dagger2-custom-scopes-how-do-custom-scopes-activityscope-actually-work
    http://stackoverflow.com/questions/28411352/what-determines-the-lifecycle-of-a-component-object-graph-in-dagger-2
    http://stackoverflow.com/questions/29923376/dagger2-custom-scopes-how-do-custom-scopes-activityscope-actually-work

六、后续

 这篇只是介绍关于Dagger2的背景知识和基本使用,之后我想研究一下Dagger2的源代码,和使用Dagger2对apk大小的影响。希望可以把这个系列做好吧。

#####Reference:

Share

体验编程之美 饮料供应问题

动态编程,贪婪算法,实际问题的建模过程

现实问题描述

  公司水房提供很多种类饮料,已经统计获得大家对每种饮料的满意程度;STC负责给公司提供饮料,每天的总容量为V,每种饮料的单个容量都是2的方幂,比如王老吉,都是2的三次方为8升的;STC的存货也是有限的,这会是每种饮料的购买量上限。统计数据中使用饮料名字,容量,数量,满意度来描述一中饮料,问如何保证最大的满意度啊。

问题建模

  我刚看到这道题目的时候,其实是很困惑的,完全不知道该如何下手。因为之前刷leetocde算法题目时,每个题目是使用编程域的语言进行描述的,比如:复制一个具有随机指针的链表。而这道题却是一个完全现实问题域描述,这样我们就需要进行建模,将这个实际问题转换为之前比较常见的算法问题。

  假设ST提供n种饮料,用(Si,Vi,Ci,Hi,Bi) (对应饮料的名字,容量,可能的最大数量,满意度,实际购买量)来标示第i中饮料,其中可能的最大数量指如果仅买这种饮料的可能最大数量,比如对第i种饮料,Ci=V/Vi;

  基于现实域的描述,我们有以下两个公式:

  • 饮料的总数量 V= (V0B0)+(V1B1)+……….(Vn*Bn); A

  • 总满意度为 H=(H0B0)+(H1B1)+………(Hn*Bn); B

  那么题目的要求就是,在满足饮料总数量为V的基础上,求解最大的总满意度。

动态编程

 对于最优解问题,首先考虑到动态编程啦!用Opt(V’,i)来标示从第i,i+1,……n-1,n种饮料中,计算出总量为V’的方案中满意度之和的最大值。

 然后我们思考一下最优子结构的推到公式啊。Opt(V’,n)=max{kHi+Opt(V’-Vik,i-1)} (k=0,1,2,Ci),简单描述一下就是先将V‘分成两份,一份是Si饮料容量,大小为KVi;另外一份是其他的饮料的容量,大小为V’-Vik,其中k表示这种饮料的数量。然后取不同的k值,范围为0到Ci,求最大的满意度。

 我们来列出动态编程的初始化条件:

  • Opt(0,0)=0

  • Opt(x,n)=-INF

对动态编程的优化

  动态编程算法的一个变形是备忘录法,备忘录法也是用一个表格来保存每个子问题的答案,并通过记忆化搜索来避免计算一些不可能到达的状态,简单来说,就是避免重复计算子问题,第一次遇到子问题的时候进行计算,然后保存结果,之后再次遇到时,直接取出结果使用。
  动态编程和备忘录法的区别就是:动态编程是自下到上,而备忘录法是自顶向下的,而且备忘录法可以进行多次查询,花费了存储空间,来提高整体查询效率。

贪婪算法

  一般来说,如果你发现了最优子结构和重复子问题,就可以使用动态编程了,但是如果你发现了下边这条更加特殊的性质,你就可以使用贪婪算法.
  这个特性就是贪心选择性质:我们可以通过局部最优(贪心)选择来构造全局最优,换句话说,当进行选择时,我们直接做出在当前问题中看来最优的选择,而不必考虑子问题的解,这就是贪婪和动态编程的区别,动态编程的每一步选择通常依赖于子问题的解,而贪婪不需要。
  回到饮料供应问题,可以设想,将饮料按照满意度大小进行排序,优先最大量供应满意度最大的饮料是否就能得出这个问题的最优解呢?答案是肯定的,我们可以对这性质进行证明。
  这篇文章只是分析了饮料供应问题的算法原理,并没有给出具体代码,大家可以自己动手编写一下啊,理论和实践并行啊。

Share

西方文化和精神概述

    自由,契约,宪政,理性,博爱
    有些时候,我总会处于一种莫名的状态中:认定了要去一件事情,却总是在一天一天拖延下去,像是生活有太大的惯性,无法做出改变一样。
    想写下这篇文章很久啦,一直都没有动笔的勇气和时间。说没有勇气可能有点矫情,但只从大学以来,除了“感人至深”的入党申请书之外,无论是笔,或者键盘,我都没有让思想从我指尖流淌出去,固化成文章;说没有时间可能有点做作,显得自己很忙似的,但可能时间都花费到了其他地方去了吧?
    这个学期我选修了王雄老师的《西方文化和精神》课程,期间了解了整个西方文化精神的起源,发展,和形成的过程。对于工科生的我,实在是受到了太多的震撼!
    以下的观点多是来自我的课程笔记和一些记忆,如有错误,请多包含。
    开头当然要请出我们的马克思啦,马克思认为等到未来生产力高度发达了,无产阶级必然会夺取政权,获得解放。但是马克思过度夸大了阶级形成的外部因素,忽略了无产阶级意识的形成的重要性。一个阶级的自我意识是不会自动形成的,必然需要重大的事件或者人物去推动(不符合毛概欧),比如毛主席在第一次国共合作时主要推动的农民运动讲习所,就是要激发农民阶级的自我意识。
    那资产阶级的自我意识是如何形成的呢?
    西方资产阶级自我意识即西方文化和精神的发展过程大概为:古希腊古罗马阶段,中世纪基督教,文艺复兴,宗教改革,启蒙运动。从每个阶段中我们都可以提取出西方文化的一级词汇,也就是最能代表西方文化和精神的词汇,比如说启蒙运动宣扬的自由,理性,契约,宪政。
    我不会在这里过多的阐述这些阶段中所涌现的具体人物以及他们的思想,他们早已如同头顶星空一般,虽你不常仰头惊叹其浩瀚壮阔。
    我主要会讲很令人惊奇的思想。第一个是个人主义和集体主义的区别。这两个词不是好与坏的主义,而是两种不同的价值观,个人主义不等于自私,而是强调集体的存在在于保障个人的权益,而群体主义不用说,大家应该都感受到。一个比较典型的场景就是:一个村长,一心为了村民,希望大家都变得富有,但是他总是大包大揽,喜欢自己把所有事情都管起来,他总是对大家说:你们不用管,你们不用管,我全部做的好好的给你们还不行吗?马克思也曾经说过:人类社会的自由和发展是由每个人的自由和发展为基础和前提的。这两种主义和自由主义还有群体功利主义也是有区别的,但是我也搞不清楚它们的区别。
     第二个是关于上帝是否存在的问题。这首先要从启蒙运动讲起啦,启蒙运动推崇理性,并且崇拜理性所带来的科学进步,社会发展。但是两次世界大战和近代社会人们关系的异化让人们开始反思理性。人之间关系的异化有很多的体现,比如卡夫卡的《变形计》,《城堡》。而且不仅人和人的关系异化了,人和机器的关系好像也改变了,从而导致双层的异化。机器本来是人类发明并用来帮助人类的,但现在人们好像是被机器约束了,而不是人来约束机器。卓别林的《摩登时代》和富士康事件可能都体现这个主题。好像还有一本不错的书专门讲述这个问题,叫做《单向度的人》那么人们是如何反思的呢?首先就是关于上帝是否存在的问题。人们认为宗教的思想是和理性思想完全不同的两种思维方式,宗教的思想是先验的,讲究天启和惯性思维,那么使用纯粹理性的思维去否定宗教的存在是否合理呢?好像是有点方枘圆凿。如果你使用纯粹的理性思维如何去证明上帝是不存在的呢?卡尔·波普尔好像也对此做出解释,他认为真理是可以被证伪的,无法被证伪的就不是真理,体现了对科学和非科学的区分啊。他还对马克思理论做个一个三段式推理,也是很有趣的。
    除了上边所说的人的异化,启蒙运动所标榜的真理蜕变了,高尚的价值理性蜕变成了工具理性,不在于追求知识和理性作为最高标准,而是追求效率和福利作为最高目标,但是提高了效率,人们自己的感受呢?
    第三个是关于中国文化的问题。首先中国的哲学中对于方法论的认识始终没有得到发展,始终处于一种神秘主义的阶段,比如说老子的“道可道,非常道”,还有禅宗的顿悟。他们都没有述说知识和思想的具体来源,并且认为有些知识不能写出来,只能自己领悟。这种哲学无疑对中国的科技发展产生了很大的影响。而在西方,无论是莎士比亚的《工具论》还是培根的《新工具》都给给出了获取知识和真理的可以循序的方法和道路。培根不经会写小短文,还是现代实验科学的奠基人啊!然后是我们对教育的理解,当然这是古代中国思想的体现,它强调老师到学生的继承,而缺乏反思性。而西方则相反,比如弗洛伊德的学生中反对他学说的两个学生最终都取得了巨大的成功。
    第四个是对于悲剧的理解。鲁迅说悲剧就是把有价值的东西毁灭给你看,那西方的观点呢?悲剧一般有三个层面,第一个是命运悲剧,代表性作品就是索罗克勒斯的《Antigon》和《Oedipus》.正真的悲剧不是对与错的争斗,比如《白毛女》,而是选择的悲剧,是好与好的争斗。比如《Antigon》;而《Oedipus》就是讲述杀父妻母的故事,这是一种人生的境遇,无论如何努力,都无法逃脱的命运,所以俄狄甫斯最后刺瞎双目,自我流放。第二等是性格悲剧,莎士比亚的悲剧都是如此,都是因由个人的性格所导致的悲剧,比如软弱的哈姆雷特;第三等就是社会悲剧,也就到了人与人的异化关系问题,比如《白毛女》,《雷雨》,《玩偶之家》。
    大概就这么多啦。

Share

体会编程之美,找出最大的k个数

 今日上课无事,偶尔看到《编程之美》的一道题目,如何找出n个数中的最大的k个数,不仅惊奇于其提供的多种解法,而且感叹其中很多解法都是之前的我们熟悉解法的变种。废话不多说,我们来依次看一下不同的解法和相应的分析

思路一

  1. 使用排序算法先对n个数进行排序,然后取最大的k个数。
  2. 先找出n个数中最大值,然后在找出n-1个数中的最大值,一直进行,知道找出k个数。

 我们来分析一下两种方法的效率,如果使用快排进行排序,那么时间复杂度就是O(nlog2n),而第二个方法的时间复杂度为O(kn),所以二者的效率高低取决于k相对于log2n的大小,如果k>log2n,那么使用第一种方法比较好,反之,便是使用第二种方法比较好。

思路二

 使用顺序统计量的思路:在一个有n个元素组成的集合中,第i个顺序统计数就是该集合中第i小的元素。对《算法导论》中利用快排查找n个数中中位数的算法进行修改。
在本问题中,假设N个数存储在数组S中,我们从数组S中随机找出一个元素X,从而把数组分为Sa和Sb,Sa中的元素都大于等于X,Sb中的元素都是小于X
  这个时候有
  1 .Sa中的元素个数小于k,Sa中的所有的数和Sb中的最大的k-|Sa|个元素为数组S中最大的k个数
  2 .Sa中的元素大于或者等于k,则需返回Sa中的最大的k个元素。
 这也是二分法思想的体现。

思路三

 使用动态编程的思想,并且解决上述解法中都要多次读取n个数的问题,当n大到一定程度之后,这样会很耗费时间。
主要思想就是维持一个规模为k的数据结构,存储最大的k个值,然后依次遍历n个数,如果发现比数据结构中数小的值,就对数据结构进行更新,遍历结束之后,数据结构中就是n个数中的最大的n个数
 如果使用数组来表示数据结构,那么时间复杂度就是O(kn),但如果使用最小堆来表示,那么时间复杂读就是O(nlog2k)。

思路四

 上述的思路都是基于n个数相互比较的解法,如同《算法导论》中的想法,我们可以使用其他方式的比较来获得n个数的大小关系。所以,如果n个数都是在一个整数范围之内,我们可以修改计数排序和基数排序来找出最大的k个数。

Share