Broadcast Receiver


보내는 쪽은 하나이고 받는 쪽은 다수인 개념으로 Broadcast라는 용어를 통상 쓴다.

BroadcastReceiver클래스를 재정하여 사용 한다.

  • void onReceive (Context context, Intent intent)

메인 스레드에서 동작하기 때문에 간결하게 작성하고 신속하게 리턴해야한다.

시스템에서 응용프로그램으로 방송하는 것이 일반적이지만 응용 프로그램도 특별한 변화를 유발시켰다거나 특이한 변화를 발견했다면
다른 응용 프로그램에게 방송을 보낼 수 있다.
그래서 방송은 응용 프로그램끼리 통신하는 공식적인 수단으로 활용된다. 응용 프로그램이 방송할 때는 다음 메서드를 호출한다.

  • void sendBroadcast (Intent intent [, String receiverPermission])
  • void sendOrderdBroadcast (Intent intent, String receiverPermission)

일반 방송은 비동기적으로 동작하여 호출시 즉시 리턴한다. 수신자가 방송을 수신했는지의 여부는 관여하지 않으며 누가 먼저 방송을 받을지 알 수 없다. 비동기적이며 비순서적이므로 효율이 좋다.

BroadCast 발생과 수신

임의로 응용프로그램에서 BR을 발생시키는 코드이다.

public class DetectFree extends Activity {
	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.detectfree);
	}

	public void mOnClick(View v) {
		Intent intent = new Intent();
		intent.setAction("andexam.ver6.FREEWIFI");
		sendBroadcast(intent);
	}
}

수신하는 코드는 다음과 같다.

public class FreeBR extends BroadcastReceiver {
	public void onReceive(Context context, Intent intent) {
		Intent intent2 = new Intent(context, 
				andexam.ver6.c28_network.AsyncDownHtml.class);
		intent2.addFlags(Intent.FLAG_ACTIVITY_NEW_TASK);
		context.startActivity(intent2);
	}
}

매니패시트

<receiver android:name=".c29_br.FreeBR">
    <intent-filter>
        <action android:name="andexam.ver6.FREEWIFI" />
    </intent-filter>
</receiver>

BR이 수신되면 html을 다운받는 새로운 Activity를 실행하는 코드를 작성해 두었다.

동적 BR 등록

매니페스트에 등록하지 않고 코드상에서도 할 수 있다.
즉 필요할 때만 등록하고 해지 시킬 수 있다.

  • Intent registerReceiver (BroadcastReceiver receiver, IntentFilter filter)
  • void unregisterReceiver (BroadcastReceiver receiver)

등록 메서드로 BR 객체와 인텐트 필터를 직접 전달한다.

  • onResume() 등록
  • onPause() 해제

코드는 아래와 같다.

public class OnSaveZone extends Activity {
	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.onsavezone);
	}
	
	public void onResume() {
		super.onResume();
		IntentFilter filter = new IntentFilter();
		filter.addAction("andexam.ver6.SAVEZONE");
		registerReceiver(mSaveZoneBR, filter);
	}
	
	public void onPause() {
		super.onPause();
		unregisterReceiver(mSaveZoneBR);
	}

	BroadcastReceiver mSaveZoneBR = new BroadcastReceiver() {
		public void onReceive(Context context, Intent intent) {
			Toast.makeText(context, "아싸! 공짜다.", 
					Toast.LENGTH_LONG).show();
		}
	};
}

배터리 감시용 코드

public class WatchBattery extends Activity {
	TextView mStatus;

	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.watchbattery);

		mStatus = (TextView)findViewById(R.id.status);
	}
	
	public void onResume() {
		super.onResume();
		IntentFilter filter = new IntentFilter();
		filter.addAction(Intent.ACTION_BATTERY_CHANGED);
		filter.addAction(Intent.ACTION_BATTERY_LOW);
		filter.addAction(Intent.ACTION_BATTERY_OKAY);
		filter.addAction(Intent.ACTION_POWER_CONNECTED);
		filter.addAction(Intent.ACTION_POWER_DISCONNECTED);
		registerReceiver(mBRBattery, filter);
	}	

	public void onPause() {
		super.onPause();        
		unregisterReceiver(mBRBattery);
	}

	BroadcastReceiver mBRBattery = new BroadcastReceiver() {
		int Count = 0;
		public void onReceive(Context context, Intent intent) {
			String action = intent.getAction();
			Count++;
			if (action.equals(Intent.ACTION_BATTERY_CHANGED)) {
				onBatteryChanged(intent);
			}
			if (action.equals(Intent.ACTION_BATTERY_LOW)) {
				Toast.makeText(context, "배터리 위험 수준", Toast.LENGTH_LONG).show();
			}
			if (action.equals(Intent.ACTION_BATTERY_OKAY)) {
				Toast.makeText(context, "배터리 양호", Toast.LENGTH_LONG).show();
			}
			if (action.equals(Intent.ACTION_POWER_CONNECTED)) {
				Toast.makeText(context, "전원 연결됨", Toast.LENGTH_LONG).show();
			}
			if (action.equals(Intent.ACTION_POWER_DISCONNECTED)) {
				Toast.makeText(context, "전원 분리됨", Toast.LENGTH_LONG).show();
			}
		}

		public void onBatteryChanged(Intent intent) {
			int plug, status, scale, level, ratio;
			String sPlug = "";
			String sStatus = "";

			if (intent.getBooleanExtra(BatteryManager.EXTRA_PRESENT, false) == false){
				mStatus.setText("배터리 없음");
				return;
			}

			plug = intent.getIntExtra(BatteryManager.EXTRA_PLUGGED, 0);
			status = intent.getIntExtra(BatteryManager.EXTRA_STATUS, 
					BatteryManager.BATTERY_STATUS_UNKNOWN);
			scale = intent.getIntExtra(BatteryManager.EXTRA_SCALE, 100);
			level = intent.getIntExtra(BatteryManager.EXTRA_LEVEL, 0);
			ratio = level * 100 / scale;

			switch (plug) {
			case BatteryManager.BATTERY_PLUGGED_AC:
				sPlug = "AC";
				break;
			case BatteryManager.BATTERY_PLUGGED_USB:
				sPlug = "USB";
				break;
			default:
				sPlug = "Battery";
				break;
			}

			switch (status) {
			case BatteryManager.BATTERY_STATUS_CHARGING:
				sStatus = "충전중";
				break;
			case BatteryManager.BATTERY_STATUS_NOT_CHARGING:
				sStatus = "충전중 아님";
				break;
			case BatteryManager.BATTERY_STATUS_DISCHARGING:
				sStatus = "방전중";
				break;
			case BatteryManager.BATTERY_STATUS_FULL:
				sStatus = "만충전";
				break;
			default:
			case BatteryManager.BATTERY_STATUS_UNKNOWN:
				sStatus = "알 수가 없어";
				break;
			}

			String str = String.format("수신 회수:%d\n연결: %s\n상태:%s\n레벨:%d%%", 
					Count, sPlug, sStatus, ratio);
			mStatus.setText(str);
		}
	};
}


'Computer Science > Android Application' 카테고리의 다른 글

NDK 사용  (0) 2017.08.20
Preference  (0) 2017.08.20
Service  (0) 2017.08.16
Activity  (0) 2017.08.16
쓰레드 (Thread)  (0) 2017.08.04

Service


  • 백그라운드 데몬: 배경에서 계속 실행되는 프로세스이다. 클라이언트가 가동시켜 놓기만 하면 사용자의 명령이 없이도 지속적으로 실행된다. MP3 플레이어가 대표적인 예이다.

  • 바운드 서비스: 클라이언트를 위해 특정한 기능을 제공하는 역할을 한다. 자신의 기능을 메서드로 노출시키며 클라이언트는 메서드를 호출함으로써 서비스를 이용한다. 다른 운영체제의 COM, CORBAR에 대응되는 개념이다.

두 개의 서로다른 서비스는 Life Cycle에서 차이가 존재 한다.

백그라운드 데몬 형태 예제

백그라운드에서 동작하며 뉴스 데이터를 출력하는 예제

public class NewsService extends Service {
    boolean mQuit;

    public void onCreate() {
        super.onCreate();
    }

    public void onDestroy() {
        super.onDestroy();

        Toast.makeText(this, "Service End", Toast.LENGTH_SHORT).show();
        mQuit = true;
    }

    public int onStartCommand (Intent intent, int flags, int startId) {
        super.onStartCommand(intent, flags, startId);

        mQuit = false;
        NewsThread thread = new NewsThread(this, mHandler);
        thread.start();
        return START_STICKY;
    }

    public IBinder onBind(Intent intent) {
        return null;
    }

    class NewsThread extends Thread {
        NewsService mParent;
        Handler mHandler;
        String[] arNews = {
                "일본, 독도는 한국땅으로 인정",
                "번데기 맛 쵸코파이 출시",
                "춘천 지역에 초거대 유전 발견",
                "한국 월드컵 결승 진출",
                "국민 소득 6만불 돌파",
                "학교 폭력 완전 근절된 것으로 조사",
                "안드로이드 점유율 아이폰을 앞질렀다",
        };
        public NewsThread(NewsService parent, Handler handler) {
            mParent = parent;
            mHandler = handler;
        }
        public void run() {
            for (int idx = 0;mQuit == false;idx++) {
                Message msg = new Message();
                msg.what = 0;
                msg.obj = arNews[idx % arNews.length];
                mHandler.sendMessage(msg);
                try { Thread.sleep(5000);} catch (Exception e) { ; }
            }
        }
    }

    Handler mHandler = new Handler() {
        public void handleMessage(Message msg) {
            if (msg.what == 0) {
                String news = (String)msg.obj;
                Toast.makeText(NewsService.this, news, Toast.LENGTH_SHORT).show();
            }
        }
    };
}

매니페스트 등록 내용

<service android:name=".c30_service.NewsService" android:enabled="true">
    <intent-filter>
        <action android:name="andexam.ver6.NEWS" />
    </intent-filter>
</service>

주요 착안점

  • Service는 메인 스레드에서 실행되므로 긴 작업을 위해서 스레드를 별도로 생성함
  • Thread는 toast update가 불가능 하므로 handler를 이용해서 UI를 업데이트함
  • 원격 호출을 지원하지 않으므로 onBind는 null을 리턴한다.

서비스의 시작과 종료 방법
같은 패키지에 있는 서비스의 경우 서비스 클래스명으로 지정하는 것이 가장 간편하다.

  • ComponentName startService (Intent service)
  • boolean stopService (Intent service)

호출은 중첩되지 않으므로 몇 번을 시작했건 간에 stopService를 한 번만 호출해도 즉시 종료된다.

서비스는 유일한 이름이 있으므로 외부 패키지나 외부 프로그램에서도 호출 가능하다. 외부에서 다른 패키지에 속한 클래스를 직접 참조할 수 없으므로 이름을 사용하여 다음과 같이 호출한다.
itent = new Intent(“packageName.className”);
startService(intent);
하지만 5.0 이후로는 보안상 문제가 있어서 금지 되었다. Service intent must be explicit예외가 발생된다.

IntentService

비동기적으로 기능을 해결해주는 컴포넌트이다.
startService(Intent)로 요청하면 작업 스레드를 생성해서 해당 작업을 실행시켜 준다.

work queue processor패턴으로 일반적으로 이용되는 것이 IntentService이다.
즉, main thread에서 수행해야할 작업을 쉽게 offloading 하는 역할을 한다.

요약

  • The IntentService runs on a separate worker thread.
  • The IntentService is triggered using an Intent, it spawns a new worker thread and the method onHandleIntent() is called on this thread.
  • The IntentService cannot run tasks in parallel. Hence all the consecutive Intents will go into the message queue for the worker thread and will execute sequentially.
  • The IntentService stops the service after all start requests have been handled, so you never have to call stopSelf().
public class NewsService2 extends IntentService {
    public NewsService2() {
        super("NewsThread");
    }

    protected void onHandleIntent(Intent intent) {
        String[] arNews = {
                "4T SSD 10만원대 진입",
                "갤럭시 S8 판매 호조",
                "핵융합 발전소 건설 완료",
        };
        for (int idx = 0;idx < arNews.length;idx++) {
            Message msg = new Message();
            msg.what = 0;
            msg.obj = arNews[idx % arNews.length];
            mHandler.sendMessage(msg);
            try { Thread.sleep(5000);} catch (Exception e) { ; }
        }
    }

    Handler mHandler = new Handler() {
        public void handleMessage(Message msg) {
            if (msg.what == 0) {
                String news = (String)msg.obj;
                Toast.makeText(NewsService2.this, news, Toast.LENGTH_SHORT).show();
            }
        }
    };
}

Bind Service

Bind service는 특정 기능을 제공하는 메서드를 클라이언트에게 노출한다.
클라이언트는 서비스에 연결하여 메서드를 호출함으로써 통신을 수행하며 자신이 직접 구현하지 않은 기능을 사용한다.

연산을 처리하는 부분

public class CalcService extends Service {
    public class CalcBinder extends Binder {
        CalcService getService() { return CalcService.this; }
    }

    CalcBinder mBinder = new CalcBinder();

    public IBinder onBind(Intent intent) {
        return mBinder;
    }

    public int getLCM(int a, int b) throws RemoteException {
        int i;
        for (i = 1; ;i++) {
            if (i % a == 0 && i % b == 0) break;
        }
        return i;
    }

    public boolean isPrime(int n) throws RemoteException {
        int i;
        for (i = 2;i < n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

onBind를 호출하는 부분

public class CalcClient extends Activity {
    CalcService mCalc;
    TextView mResult;
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.calcclient);

        mResult = (TextView)findViewById(R.id.result);
    }

    public void mOnClick(View v) {
        switch (v.getId()) {
            case R.id.btnLCM:
                int LCM = 0;
                try {
                    LCM = mCalc.getLCM(6, 8);
                } catch (RemoteException e) {
                    e.printStackTrace();
                }
                mResult.setText("6과 8의 최소 공배수 = " + LCM);
                break;
            case R.id.btnPrime:
                boolean prime = false;
                try {
                    prime = mCalc.isPrime(7);
                } catch (RemoteException e) {
                    e.printStackTrace();
                }
                mResult.setText("7의 소수 여부 = " + prime);
                break;
        }
    }

    public void onResume() {
        super.onResume();
        Intent intent = new Intent(this, CalcService.class);
        bindService(intent, srvConn, BIND_AUTO_CREATE);
    }

    public void onPause() {
        super.onPause();
        unbindService(srvConn);
    }

    ServiceConnection srvConn = new ServiceConnection() {
        public void onServiceConnected(ComponentName className, IBinder binder) {
            mCalc = ((CalcService.CalcBinder)binder).getService();
        }

        public void onServiceDisconnected(ComponentName className) {
            mCalc = null;
        }
    };
}


클라이언트에서 서비스에 연결하거나 해제할 때 다음 메서드를 호출하여 바인딩한다. 바인딩이란 클라이언트와 서비스를 연결하는 동작이다.

  • boolean bindService(Intent service, ServiceConnection conn, int flags)
  • void unbindService (ServiceConnection conn)

bindService의 첫 번째 인수는 같은 패키지에 있으면 클래스명으로 지정하고 외부에 있다면 서비스의 액션명을 사용한다.
두 번째 인수 conn은 서비스가 연결, 해제될 때의 동작을 정의하는 연결 객체이다.
서비스를 사용하는 클라이언트는 ServiceConnection 인터페이스를 구현하는데 클라이언트와 서비스가 연결되거나 해제될 때 호출되는 콜백 메서드를 정의한다. 아래의 코드가 이에 해당한다.

    ServiceConnection srvConn = new ServiceConnection() {
        public void onServiceConnected(ComponentName className, IBinder binder) {
            mCalc = ((CalcService.CalcBinder)binder).getService();
        }

        public void onServiceDisconnected(ComponentName className) {
            mCalc = null;
        }
    };

onResume()에서 bindService(intent,srvConn,BIND_AUTO_CREATE)를 하기 때문에 해당 callback method를 구현해야 한다.
만약 그냥 별도의 anonymous class 생성 없이 activity에 구현 했다고 하면 this가 된다.

마지막 인수 flag는 서비스 바인딩 바익을 지정하는데 통상 BIND_AUTO_CREATE로 지정하여 서비스를 자동으로 가동시킨다.

아주 복잡한 기능들을 공통으로 서비스에 작성해두고 이것을 원격으로 콜하는 방식으로 구현할 수 있다.

완전 원격 서비스

서비스는 로컬에서뿐만 아니라 원격으로도 호출할 수 있는데 그렇게 하려면 자신의 메서드 목록을 인터페이스로 정의해야 한다.
이는 단순히 메서드의 원형을 선언하는 것과 수준이 다른데 원격에서 호출되는 메서드는 응용 프로그램의 경계를 넘어서 인수를 전달해야 하는 어려움이 있다. 각 응용프로그램이 사용하는 메모리가 완전히 분리되어 있어 통상의 방법으로는 인수를 넘기기 어렵다.

따라서 전달할 수 있는 인수의 타입은 자바기본 타입이나 Parcelable정도로 제한되며 그 외에도 몇 가지 제약이 존재한다.

자바 수준에서 인터페이스를 직접 정의하기는 대단히 어려워 원격 인터페이스를 정의하는 AIDL이라는 별도의 언어를 제공한다.

interface A{
    int getLCM();
    boolean isPrime();
}

위와 같이 인터페이스안에 노출할 메서드의 선언문만 작성해 두면 AIDL 컴파일러가 이 인터페이스를 구현하는 자바 파일을 생성해 준다.

예전에 구현했던 내용
네이버 블로그 포스트


'Computer Science > Android Application' 카테고리의 다른 글

Preference  (0) 2017.08.20
Broadcast Receiver  (0) 2017.08.16
Activity  (0) 2017.08.16
쓰레드 (Thread)  (0) 2017.08.04
이벤트 (Event)  (0) 2017.08.04

Activity


엑티비티 생성과 호출

코드

public class CallActivity extends Activity {
	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.callactivity);
	}

	public void mOnClick(View v) {
		Intent intent = new Intent(this, SubActivity.class);
		startActivity(intent);
	}
}
<activity android:name=".c17_activity.CallActivity" android:label="CallActivity" />
  • name의 경우 액티비티의 패키지명을 포함한 풀 경로를 지정하되 같은 패키지에 속해 있을 때는 앞에 . 을 찍거나 클래스명만 적어도 무방하다.

Intent

생성자의 종류

  • 1 Intent (): 잘 사용 안함
  • 2 Intent (Intent o)
  • 3 Intent (String action [, Uri uri])
  • 4 Intent (Context packageContext, Class<?> cls): 서브 액티비티 호출할 때 사용
  • 5 Intent (String action, Uri uri, Context packageContext, Class<?> cls)

4 번째 구조로 만든 intent이다. Explicit Intent라고 한다.

Intent intent = new Intent(this, SubActivity.class)
startActivity(intent);

Implicit Intent

  • Action
    • ACTION_CALL // Activity // 통화를 시작한다.
    • ACTION_BATTERY_LOW // BR // 배터리가 부족하다.

거의 왠만한 액션들은 모두 정의가 되어 있다. String 타입으로 define 되어 있는 것이다.
사용자가 개인적으로 정의해서 사용할 수도 있다. 그 경우 중복을 막기위해서 package name을 앞에 붙인다.
액션을 조사하거나 변경 할때는 gecAction setAction을 사용 한다.

  • Data: 목적어에 해당 한다.
  • Type: 자동으로 판별이 가능하다.
    • http:// 웹페이지
    • te: 전화번호
    • jpg 이미지
  • Category: 여러개를 줄 수 있다.
  • Component: 이 속성이 지정되면 Explicit로 바뀐다.
  • Extras: 추가적인 정보를 전달 할 때 사용 한다. 키와 값의 쌍으로 저장되어 컴포넌트에게 전달 되며 리턴 용도로도 사용된다. 이름만 중복되지 않으면 얼마든지 많은 정보를 전달할 수 있다.
    • putExtra로 여러 벌 오버로딩 되어 있으므로 저장되는 정보 타입을 그냥 넣어주면 알아서 맞게 동적 로딩 된다.
    • getIntExtra getStringExtra등으로 제공된다.
  • Flags: 액티비티를 띄울 방법이나 액티비티를 관리하는 방법 등에 대한 옵션 정보가 저장된다.

액티비티간의 통신

값의 전달

  • Intent putExtra (String name, int value)
  • Intent putExtra (String name, String value)
  • Intent putExtra (String name, boolean value)

값 읽기

  • int getIntExtra (String name, int deafultValue)
  • String getStringExtra (String name)
  • boolean getBooleanExtra (String name, boolean defaultValue)

리턴값을 돌려줘야 할 경우 다음의 메서드를 사용 한다.

  • void startActivityForResult (Intent intent, int requestCode)
    • 두 번째 인수가 하나 더 추가되는데 호출한 대상을 나타내는 식별자이며 리턴 시에 누구에 대한 리턴인지 구분할 때 사용한다.

호출된 액티비티가 종료되면 다음의 메서드가 호출 된다.

  • void onActivityResult (int requestCode, int resultCode, Intent data)
    • requestCode는 액티비티를 호출할 때 전달한 요청코드이며 requestCode는 액티비티의 실행 결과이다.

예제코드
호출하는 부분

public class CommActivity extends Activity {
	TextView mText;
	final static int ACT_EDIT = 0;
	
	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.commactivity);

		mText = (TextView)findViewById(R.id.text);
	}
	
	public void mOnClick(View v) {
		switch (v.getId()) {
		case R.id.btnedit:
			Intent intent = new Intent(this, ActEdit.class);
			intent.putExtra("TextIn", mText.getText().toString());
			startActivityForResult(intent,ACT_EDIT);
			break;
		}
	}
	
	protected void onActivityResult (int requestCode, int resultCode, Intent data) {
		switch (requestCode) {
		case ACT_EDIT:
			if (resultCode == RESULT_OK) {
				mText.setText(data.getStringExtra("TextOut"));
			}
			break;
		}
	}
}

처리하는 부분

public class ActEdit extends Activity {
	EditText mEdit;

	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.actedit);

		mEdit = (EditText)findViewById(R.id.stredit);

		Intent intent = getIntent();
		String text = intent.getStringExtra("TextIn");
		if (text != null) {
			mEdit.setText(text);
		}
	}

	public void mOnClick(View v) {
		switch (v.getId()) {
		case R.id.btnok:
			Intent intent = new Intent();
			intent.putExtra("TextOut", mEdit.getText().toString());
			setResult(RESULT_OK,intent);
			finish();
			break;
		case R.id.btncancel:
			setResult(RESULT_CANCELED);
			finish();
			break;
		}
	}
}
  • getIntent
  • void setResult(int resultCode, Intent data)
  • getStringExtra

Implicit Intent

public class CallOther extends Activity {
	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.callother);
	}

	public void mOnClick(View v) {
		Intent intent;
		switch (v.getId()) {
		case R.id.web:
			intent = new Intent(Intent.ACTION_VIEW, 
					Uri.parse("http://www.google.com"));
			startActivity(intent); 
			break;
		case R.id.dial:
			intent = new Intent(Intent.ACTION_DIAL, Uri.parse("tel:015-123-4567"));
			startActivity(intent);
			break;
		case R.id.picture:
			intent = new Intent(Intent.ACTION_VIEW);
			String sd = Environment.getExternalStorageDirectory().getAbsolutePath();
			Uri uri = Uri.fromFile(new File(sd + "/test.jpg"));
			intent.setDataAndType(uri, "image/jpeg");
			startActivity(intent);
			break;
		case R.id.other:
			intent = new Intent(Intent.ACTION_MAIN);
			intent.setComponent(new ComponentName("exam.memo", "exam.memo.Memo"));
			//intent.setClassName("exam.memo", "exam.memo.Memo");
			startActivity(intent);
			break;
		}
	}
}

액티비티 라이프 사이클

엑티비티의 라이프 사이클은 아래와 같다.


  • onCreate: 액티비티를 초기화한다. 중지했다가 재시작하는 경우라면 액티비티의 이전 상태 정보인 Bundle이 전달되며 이 정보대로 재초기화한다.

  • onRestart: 재시작될 때 호출된다. 특별히 할일은 없다.

  • OnResume: 사용자와 상호작용을 하기 직전에 호출된다. 이 단계에서 스택의 제일 위로 올라온다.

  • onPause: another activity comes into the foreground. 단순히 Pause고 곧 있다가 실행이 될 때를 의미한다. 요즘 멀티 엑티비티가 되면서 더 빈번하게 차이점이 생기는 문제이다. 포커스는 잃었지만 사용자에게 보이는 상태이다. 위쪽에 다른 엑티비티가 있지만 화면 전체를 다 가리지 않았거나 반투명한 경우가 이에 해당한다. 즉 뭔가 다이얼로그 창 같은게 위에 있는 상태이다. 살아 있는 상태와 같지만 시스템에 의해 강제 종료될 수 있다. 그리고 다른 액티비티가 실행 될 때도 onPause 이후에 onCreate가 수행 되므로 너무 오랜시간을 작업해서는 안된다. 즉, 이 단계에서 미저장한 데이터가 있으면 저장하고 애니메이션은 중지해야 한다. 이 메서드가 리턴되어야 새 액티비티가 활성화되므로 시간을 너무 오래 끌어서는 안 된다.

  • onStop: The activity is no longer visible. 이 상태에서는 액티비티가 완전히 가려져서 사용자에게 보이지 않는 상태이다. 이 상태에서는 액티비티가 백그라운드에 있는것으로 간주 된다. 정지되어 있는 동안 액티비티 인스턴스 및 멤버 변수와 같은 모든 상태 정보가 유지되지만, 어떠한 코드도 실행할 수 없다.

  • onDestory: 액티비티가 파괴될 때 호출된다. 시스템에 의해 강제로 종료되는 것인지 아니면 finish 메서드 호출에 의해 스스로 종료하는 것인지 isFinishing 메서드로 조사할 수 있다. 대부분의 앱은 이 메서드를 구현할 필요가 없다. 왜냐하면 액티비티와 함께 지역 클래스 참조가 소멸되고 액티비티가 onPause() 및 onStop 중에 대부분 정리 작업을 수행하기 때문이다. 하지만 액티비티가 onCreate 중에 생성한 백그라운드 스레드 또는 제대로 닫지 않으면 메모리 누수를 야기할 수 있는 다른 장시간 실행되는 리소스를 포함하는 경우 onDestroy중에 액티비티를 중단시켜야 한다. finish()를 호출한 경우 onPuase onStop을 거치지 않고 즉시 onDestroy를 호출 한다.

호출 순서 분석
각각의 callback 함수에 logcat으로 메시지를 출력하게 한후 새로운 액티비티를 실행해서 lifecycle을 분석 한다.

public class ActParent extends Activity {
	static final String TAG = "ActParent"; 

	public void onCreate(Bundle savedInstanceState) {
		Log.i(TAG, "onCreate");
		super.onCreate(savedInstanceState);
		setContentView(R.layout.actparent);
	}
	
	public void mOnClick(View v) {
		Log.i(TAG, "startActivity");
		Intent intent = new Intent(this, ActChild.class);
		startActivity(intent);
	}
	
	public void onStart() {
		super.onStart();
		Log.i(TAG, "onStart");
	}

	public void onResume() {
		super.onResume();
		Log.i(TAG, "onResume");
	}

	public void onPause() {
		super.onPause();
		Log.i(TAG, "onPause");
	}

	public void onRestart() {
		super.onRestart();
		Log.i(TAG, "onRestart");
	}

	public void onStop() {
		super.onStop();
		Log.i(TAG, "onStop");
	}

	public void onDestroy() {
		super.onDestroy();
		Log.i(TAG, "onDestroy");
	}
}
public class ActChild extends Activity {
	static final String TAG = "ActChild"; 

	public void onCreate(Bundle savedInstanceState) {
		Log.i(TAG, "onCreate");
		super.onCreate(savedInstanceState);
		setContentView(R.layout.actchild);
	}
	
	public void onStart() {
		super.onStart();
		Log.i(TAG, "onStart");
	}

	public void onResume() {
		super.onResume();
		Log.i(TAG, "onResume");
	}

	public void onPause() {
		super.onPause();
		Log.i(TAG, "onPause");
	}

	public void onRestart() {
		super.onRestart();
		Log.i(TAG, "onRestart");
	}

	public void onStop() {
		super.onStop();
		Log.i(TAG, "onStop");
	}

	public void onDestroy() {
		super.onDestroy();
		Log.i(TAG, "onDestroy");
	}
}

실행 결과 분석

또 다른 예제로 Rotation했을 때를 분석 한다.

나중에 핸들러, 스레드, 연기된 러너블등이 개입하면 좀 더 복잡해 진다.

상태 저장

Rotation으로 테스트 한다. 쉽게 강제 종료를 시뮬레이션 할 수 있다.

시스템은 액티비티를 종료하기 직전에 onSaveInstanceState 메서드를 호출하여 정보를 저장할 기회를 제공한다.
인수로 Bundle객체를 전달하는데 Bundle은 문자열로 된 이름과 임의 타입의 값을 저장하는 일종의 맵이다.

인텐트의 Extras 멤버가 바로 Bundle 타입이며 임의의 정보를 원하는 만큼 저장할 수 있다.
따라서 onSaveInstanceState를 재정의하여 저장하고자 하는 값을 번들에 저장해 두고 종료한다.

아무리 강제종료 되어도 onSaveInstanceState는 한번 호출되니 이곳에서 Bundle에 key와 value 쌍으로 데이터를 저장하면 된다.

아래 그림은 공식 홈페이지에서 발췌 한 것이다. 이것만으론 이해하기 어려워서 추가적인 실험도 아래와 같이 진행 했다.

시스템은 액티비티 중지 작업을 시작할 때 onSaveInstanceState()(1)를 호출한다. 따라서 Activity 인스턴스가 재생성되어야 하는 경우 저장하고자 하는 추가 상태 데이터를 지정할 수 있다. 액티비티가 소멸되고 동일한 인스턴스가 재생성되어야 하는 경우, 시스템은 onCreate() 메서드(2) 및 onRestoreInstanceState() 메서드(3) 모두에 (1)에서 정의된 상태 데이터를 전달한다.

onSaveInstanceState 호출 시점

rotation을 할 경우 onPause이후에 호출 된다.

08-20 14:04:58.340 10849-10849/andexam.ver6 I/SaveState2: onPause
08-20 14:04:58.341 10849-10849/andexam.ver6 I/SaveState2: onSaveInstanceState
08-20 14:04:58.341 10849-10849/andexam.ver6 I/SaveState2: onStop
08-20 14:04:58.341 10849-10849/andexam.ver6 I/SaveState2: onDestroy

home버튼을 누를 경우 onPause이후에 호출 된다.

08-20 14:09:00.965 10849-10849/andexam.ver6 I/SaveState2: onPause
08-20 14:09:00.996 10849-10849/andexam.ver6 I/SaveState2: onSaveInstanceState
08-20 14:09:00.996 10849-10849/andexam.ver6 I/SaveState2: onStop

back버턴을 눌러서 destropy를 호출시키면 실행 되지 않는다.

08-20 14:08:39.397 10849-10849/andexam.ver6 I/SaveState2: onPause
08-20 14:08:39.709 10849-10849/andexam.ver6 I/SaveState2: onStop
08-20 14:08:39.709 10849-10849/andexam.ver6 I/SaveState2: onDestroy

phone call일 때도 호출되지 않는다.

  • onPause-> onResume

onRestoreInstance 호출 시점

rotation할 때는 onStart이후에 호출된다.

08-20 14:04:58.352 10849-10849/andexam.ver6 I/SaveState2: onStart
08-20 14:04:58.352 10849-10849/andexam.ver6 I/SaveState2: onRestoreInstanceState
08-20 14:04:58.353 10849-10849/andexam.ver6 I/SaveState2: onResume

home버튼을 누르고 다시 시작 했을 때는 실행 되지 않는다.

08-20 14:10:34.761 10849-10849/andexam.ver6 I/SaveState2: onRestart
08-20 14:10:34.762 10849-10849/andexam.ver6 I/SaveState2: onStart
08-20 14:10:34.762 10849-10849/andexam.ver6 I/SaveState2: onResume

phone call일 때도 호출되지 않는다.

  • onPause-> onResume

뭔가 애매한대 reference문서의 가이드 라인은 아래와 같다.

void onRestoreInstanceState (Bundle savedInstanceState)

  • This method is called between onStart() and onPostCreate(Bundle).

void onSaveInstanceState (Bundle outState)

  • If called, this method will occur before onStop(). There are no guarantees about whether it will occur before or after onPause().

저장 복구 패턴 1

	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);

		if (savedInstanceState == null) {
			x = 50;
		} else {
			x = savedInstanceState.getInt("x");
		}
		y = 50;
		vw = new MyView(this);
		vw.setFocusable(true);
		vw.setFocusableInTouchMode(true);
		setContentView(vw);
	}

	public void onSaveInstanceState(Bundle outState) {
		super.onSaveInstanceState(outState);
		outState.putInt("x", x);
	}

onCreate에서 하지 않고 onRestoreInstanceState에서 수행 해도 된다.
onRestoreInstanceState는 내부 적으로 복원할 저장 상태가 있을 경우에만 호출되므로 Bundle null인지 확인할 필요는 없다.

	public void onRestoreInstanceState(Bundle outState) {
		super.onRestoreInstanceState(outState);
		x = outState.getInt("x");
	}

앱이 종료 되었다가 실행되어도 값을 저장하고 있으려면, 실행 시간 동안만 유지되는 Bundle에 저장해서는 안된다.
이 때는 Preference를 이용해서 저장한다.

public class SaveState3 extends Activity {
	private MyView vw;
	int x;
	int y;

	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);

		if (savedInstanceState == null) {
			x = 50;
		} else {
			x = savedInstanceState.getInt("x");
		}
		SharedPreferences pref = getSharedPreferences("SaveState",0);
		y = pref.getInt("y", 50);
		vw = new MyView(this);
		vw.setFocusable(true);
		vw.setFocusableInTouchMode(true);
		setContentView(vw);
	}

	protected void onPause() {
		super.onPause();
		SharedPreferences pref = getSharedPreferences("SaveState",0);
		SharedPreferences.Editor edit = pref.edit();
		edit.putInt("y", y);
		edit.commit();
	}

	public void onSaveInstanceState(Bundle outState) {
		outState.putInt("x", x);
	}
}

객체 저장

객체를 신속하게 저장 할 때는 자바의 Serialization을 사용 한다.
사용하는 메서드는 다음과 같다.

  • void putSerializable (String key, Serializable value)
  • Serializable getSerializable (String key)

이름과 객체만 전달하면 저장 및 복구가 자동으로 수행된다.
저장 하려고 하는 객체는 interface Serializable 키워드만 상속 받으면 된다.
하지만 interface인대도 구현할 매서드가 존재하지 않는다. 이러한 interface Marker Interface라고 부른다.
이렇게 하는 이유는 다중상속을 가능하게하고 추후에 instanceof에 의해서 해당 class가 Serilalizable에서 파생되었는지 알아내고 그에 대한 처리를 하기 위함이다.

코드

	public void onSaveInstanceState(Bundle outState) {
		super.onSaveInstanceState(outState);
		outState.putSerializable("Curve", arVertex);
	}

	public class Vertex implements Serializable {
		private static final long serialVersionUID = 100L;
		Vertex(float ax, float ay, boolean ad) {
			x = ax;
			y = ay;
			draw = ad;
		}
		float x;
		float y;
		boolean draw;
	}
	

또 다른 방법 Parcelable인터페이스를 구현하는 방법
Parcel은 원래 프로세스간의 통신을 위한 메시지 저장 장치인데 번들이 꾸러미 입출력 기능을 제공하므로 같은 프로세스의 세션간 데이터 저장 및 복구에도 사용 가능하다.

저장 대상인 클래스는 Parcelable 인터페이스를 상속받아야 하며,
describeContents() writeToParcel을 구현 해야한다.

class Vertex implements Parcelable {
	Vertex(float ax, float ay, boolean ad) {
		x = ax;
		y = ay;
		draw = ad;
	}
	float x;
	float y;
	boolean draw;

	public int describeContents() {
		return 0;
	}

	public void writeToParcel(Parcel dest, int flags) {
		dest.writeFloat(x);
		dest.writeFloat(y);
		dest.writeBooleanArray( new boolean[] {draw} );
	}
	
	public static final Parcelable.Creator<Vertex> CREATOR = new Creator<Vertex>() {
		public Vertex createFromParcel(Parcel source) {
			int x = source.readInt();
			int y = source.readInt();
			boolean[] td = new boolean[1];
			source.readBooleanArray(td);
			return new Vertex(x, y, td[0]);
		}

		public Vertex[] newArray(int size) {
			return new Vertex[size];
		}
		
	};
}
  • describeContents() 별다른 기능이 없으믈 0을 리턴한다.
  • writeToParcel이 부분을 구현 해야 한다.
    boolean타입에 대해서는 단일값 입출력 메서드를 제공하지 않으므로 배열 형태로 포장해서 출력 해야 한다.

CREATOR라는 이름의 정적 객체는 저장된 정보를 Parcel로 부터 읽어들여 객체를 생성하는 역할을 한다.

생성 방법

  • publci static final Parcelable.Creator CREATOR = new Creator()
  • T createFromParcel (Parcel source)
    • 해당 메서드는 source로 부터 정수 두 개와 논리값 하나를 순서대로 읽어 Vertex 객체 하나를 생성한다.
  • Vertex[] newArray(int size)
    • newArray 메서드는 전달된 크기대로 배열을 생성하여 리턴한다.

참고문헌

  1. d.android: 액티비티 재생성
  2. d.android: 액티비티 시작
  3. 안드로이드 정복 4판, 김상형


'Computer Science > Android Application' 카테고리의 다른 글

Broadcast Receiver  (0) 2017.08.16
Service  (0) 2017.08.16
쓰레드 (Thread)  (0) 2017.08.04
이벤트 (Event)  (0) 2017.08.04
Gradle  (0) 2016.06.03

Ch 09 Recursion and Dynamic Programming


재귀적 방법

  • 상향식과 하향식으로 나눠 진다.

동적 프로그래밍의 예: 피보나치 수
중간과정을 저장하면 그게 동적 프로그래밍이다.

$n^2$ 복잡도의 일반 코드

int fibonacci(int i){
	if(i==0) return 0;
	if(i==1) return 1;
	return fibonacci(i-1) + fibonacci(i-2);
}

Time complexity를 $O(n)$으로 줄이는 코드

int[] fib = new int[max];
int fibonacci(int i){
	if (i==0) return 0;
	if (i==1) return 1;
	if (fib[i] != 0) return fib[i]; // 캐시된 결과 반환
	fib[i] = fibonacci(i-1) + fibonacci(i-2); // 계산 결과 캐시
	return fib[i];
}

동적 프로그래밍을 구현 할 때의 전략은 다음과 같다.

  • 재귀함수를 먼저 구현
  • 캐쉬 부분을 구현


Ch02 LinkedList


2.1 정렬되지 않은 linkedList에서 중복된 값을 삭제하는 코드를 작성 한다.

해법1
set자료 구조에 하나씩 저장하면서 순회하는 방식을 사용한다.
단 한번의 순회로 모두 처리 할 수 있다.
복잡도는 O(n)이다.

def remove_dups(ll):
    if ll.head is None:
        return

    current = ll.head
    seen = set([current.value])
    while current.next:
        if current.next.value in seen:
            current.next = current.next.next
        else:
            seen.add(current.next.value)
            current = current.next

    return ll

실행결과

# 제거 전
1 -> 6 -> 1 -> 4 -> 3 -> 2 -> 4 -> 2 -> 2 -> 5 -> 5 -> 4 -> 2 -> 3 -> 8 -> 6 -> 2 -> 0 -> 1 -> 6 -> 3 -> 6 -> 2 -> 2 -> 6 -> 2 -> 1 -> 6 -> 2 -> 4 -> 2 -> 4 -> 7 -> 8 -> 4 -> 4 -> 3 -> 8 -> 5 -> 5 -> 0 -> 7 -> 7 -> 4 -> 1 -> 1 -> 1 -> 8 -> 5 -> 0 -> 7 -> 5 -> 9 -> 3 -> 0 -> 9 -> 2 -> 0 -> 4 -> 0 -> 0 -> 3 -> 1 -> 3 -> 5 -> 1 -> 0 -> 0 -> 5 -> 9 -> 7 -> 7 -> 0 -> 3 -> 3 -> 1 -> 7 -> 5 -> 5 -> 9 -> 7 -> 4 -> 2 -> 4 -> 6 -> 5 -> 3 -> 2 -> 9 -> 9 -> 8 -> 5 -> 1 -> 7 -> 4 -> 1 -> 8 -> 4 -> 3 -> 9

# 제거 후
1 -> 6 -> 4 -> 3 -> 2 -> 5 -> 8 -> 0 -> 7 -> 9

제약사항

  • temporary buffer를 허용하지 않는다.

해법
버퍼를 사용할 수 없다면 두 개의 포인터를 사용해 순회하여 문제를 해결할 수 있다. current라는 포인터로는 연결 리스트를 순회하고, runner로는 그 뒤에 중복이 있는지 확인 하는 것이다.

하지만 하나의 current node에 대해서 반복을 수행을 계속 해야 하므로 공간 복잡도는 O(1)이 되지만, 시간 복잡도는 O(N^2)이 된다.

def remove_dups_followup(ll):
    if ll.head is None:
        return

    current = ll.head
    while current:
        runner = current
        while runner.next:
            if runner.next.value == current.value:
                runner.next = runner.next.next
            else:
                runner = runner.next
        current = current.next

    return ll.head

실행결과

# 제거 전
1 -> 7 -> 8 -> 1 -> 5 -> 7 -> 8 -> 4 -> 9 -> 6 -> 5 -> 9 -> 0 -> 3 -> 8 -> 8 -> 9 -> 3 -> 2 -> 8 -> 7 -> 6 -> 7 -> 9 -> 9 -> 8 -> 5 -> 8 -> 9 -> 5 -> 1 -> 2 -> 6 -> 5 -> 6 -> 9 -> 2 -> 9 -> 2 -> 4 -> 4 -> 0 -> 8 -> 1 -> 5 -> 9 -> 9 -> 5 -> 0 -> 2 -> 9 -> 8 -> 0 -> 6 -> 1 -> 2 -> 1 -> 3 -> 0 -> 7 -> 6 -> 8 -> 1 -> 4 -> 5 -> 0 -> 2 -> 4 -> 9 -> 9 -> 9 -> 5 -> 3 -> 8 -> 0 -> 5 -> 7 -> 2 -> 8 -> 0 -> 3 -> 2 -> 8 -> 0 -> 0 -> 8 -> 2 -> 9 -> 0 -> 5 -> 3 -> 6 -> 8 -> 2 -> 1 -> 7 -> 8 -> 3 -> 7 -> 6

# 제거 후
1 -> 7 -> 8 -> 5 -> 4 -> 9 -> 6 -> 0 -> 3 -> 2

2.2 단방향 Linked List에서 k번째 요소를 찾는 코드를 구현 해야 한다.

해법1
재귀함수를 이용하는 방법

순회하고 매번 index를 저장하기 때문에 O(n)의 복잡도를 가지게 된다. 해당 위치에서 값을 출력하고 index는 return하는 방법으로 구현 했다.

def recursive_kth_to_last(ll, k):
    if ll is None:
        return 0
    i = recursive_kth_to_last(ll.next, k) + 1

    if i is k:
        print(ll.value)
    return i

실행결과

# 생성된 linked list
71 -> 83 -> 3 -> 2 -> 59 -> 25 -> 33 -> 40 -> 21 -> 93

# 뒤에서 3번 째 index라고 하면
40 #

해법2
순환적(iterarive) 방법으로 해결할 수 있다.
직관적이지는 않지만 좀 더 최적인 방법은, 순환적으로 푸는 것이다. 두 개의 포인터 p1과 p2를 사용한다. p1이 리스트 시작 노드를 가리키게 한 다음, p2를 k 노드만큼 움직여서 p1과 p2가 k 노드만큼 떨어져 있도록 만든다. 그런 다음, p1과 p2를 보조를 맞춰 같이 이동시킨다. p2는 LENGTH-k번 후에 연결 리스트의 맨 마지막 노드에 도달할 것이다. 바로 그 시점에, p1은 LENGTH-k번 노드, 그러니까 뒤에서부터 k번째 노드를 가리키게 된다.

코드

def kth_to_last(ll, k):
    runner = current = ll.head
    for i in range(k):
        if runner is None:
            return None
        runner = runner.next

    while runner:
        current = current.next
        runner = runner.next

    return current

실행결과

11 -> 11 -> 83 -> 92 -> 74 -> 2 -> 80 -> 97 -> 76 -> 88
97

2.3 Delete Middle Node

중간 노드를 삭제하는 알고리즘을 구현 한다. 즉 head나 tail을 제외한 아무 노드나 삭제 할 수 있어야 한다.

그렇다고 정확히 middle일 필요도 없다.

example
input: the node c from the linked list a->b->c->d->e->f
result: nothing is returned, but the new linked list looks like a->b->d->e->f

python에서는 쉽게 구현이 가능하다.

def delete_middle_node(node):
    node.value = node.next.value
    node.next = node.next.next

ll = LinkedList()
ll.add_multiple([1, 2, 3, 4])
middle_node = ll.add(5)
ll.add_multiple([7, 8, 9])

print(ll)
delete_middle_node(middle_node)
print(ll)

실행결과

1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9
1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9

2.4 x값을 갖는 노드를 기준으로 연결 리스트를 나누는 코드를 작성하라. x 보다 작은 값을 갖는 노드가 x와 같거나 더 큰 값을 갖는 노드들보다 앞쪽에 오도록 하면 된다.

연결리스트를 사용하면 쉽게 해결 된다.
x를 기준으로 작은 값을 저장하는 것과 그렇지 않은것을 저장 하는 것으로 나누면 된다.

index를 1개만 이용해서 앞에서 부터 채우게 하면 좀 더 메모리를 절약할 수 있다.

def partition(ll, x):
    current = ll.tail = ll.head

    while current:
        nextNode = current.next
        current.next = None
        if current.value < x:
            current.next = ll.head
            ll.head = current
        else:
            ll.tail.next = current
            ll.tail = current
        current = nextNode
        
    # Error check in case all nodes are less than x
    if ll.tail.next is not None:
        ll.tail.next = None


ll = LinkedList()
ll.generate(10, 0, 99)
print(ll)
partition(ll, ll.head.value)
print(ll)

실행결과
partition 46으로 선택했을 때의 결과이다.

46 -> 53 -> 52 -> 69 -> 48 -> 3 -> 23 -> 59 -> 2 -> 91
2 -> 23 -> 3 -> 46 -> 53 -> 52 -> 69 -> 48 -> 59 -> 91

2.5 Sum Lists

  • 2개의 연결 리스트가 있고 각각은 싱글 digit을 포함하고 있다. 그리고 이 숫자는 역순으로 정렬되어 있다. 즉 1의 자리숫자가 맨 앞에 있다는 뜻이 된다. 이 두개의 연결 리스트를 더해서 그 결과를 반환하는 코드를 작성하라.

Example
Input: (7->1->6) + (5->9->2). That is, 617 + 295
Output: 2->1->9. That is 912.

코드

def sum_lists(ll_a, ll_b):
    n1, n2 = ll_a.head, ll_b.head
    ll = LinkedList()
    carry = 0
    while n1 or n2:
        result = carry
        if n1:
            result += n1.value
            n1 = n1.next
        if n2:
            result += n2.value
            n2 = n2.next

        ll.add(result % 10)
        carry = result // 10

    if carry:
        ll.add(carry)

    return ll

실행 결과

5 -> 3 -> 7 -> 7
8 -> 6 -> 8
3 -> 0 -> 6 -> 8

Follow up problem

  • 길이가 맞지 않는 경우
  • 계산결과를 head에 붙여서 처리하는 방식으로 구현

코드

def sum_lists_followup(ll_a, ll_b):
    # Pad the shorter list with zeros
    if len(ll_a) < len(ll_b):
        for i in range(len(ll_b) - len(ll_a)):
            ll_a.add_to_beginning(0)
    else:
        for i in range(len(ll_a) - len(ll_b)):
            ll_b.add_to_beginning(0)

    # Find sum
    n1, n2 = ll_a.head, ll_b.head
    result = 0
    while n1 and n2:
        result = (result * 10) + n1.value + n2.value
        n1 = n1.next
        n2 = n2.next

    # Create new linked list
    ll = LinkedList()
    ll.add_multiple([int(i) for i in str(result)])

    return ll

실행결과

뒤에서 부터 1의 자리로 생각 하기 때문에 결과가 다르다.

5 -> 3 -> 7 -> 7
8 -> 6 -> 8
6 -> 2 -> 4 -> 5

2.6 주어진 연결 리스트가 회문(palindrome)인지 검사하는 함수를 작성하라

palindrome이라 함은 앞에서 보다 뒤에서 보다 같은 구조를 뜻한다.

0->1->2->1->0

해법1: 뒤집어 비교한다.

  • 포인트는 절반만 비교한다는 것이다.

해법2: 순환적(iterative) 접근법

  • 리스트 앞 절반을 뒤집는 것을 스택을 사용해서 구현 한다.
  • 연결리스트의 길이를 알 경우 절반만 push 하면 된다 (홀수인 경우에도 올바르게 처리 해줘야 한다).
  • 길이를 모를 경우 fast runner slow runner를 적절히 조합해서 사용 한다.

해법3: 재귀적 접근법

코드

def is_palindrome(ll):
    fast = slow = ll.head
    stack = []

    while fast and fast.next:
        stack.append(slow.value)
        slow = slow.next
        fast = fast.next.next

    if fast:
        slow = slow.next

    while slow:
        top = stack.pop()

        if top != slow.value:
            return False

        slow = slow.next

    return True


ll_true = LinkedList([1, 2, 3, 4, 5, 4, 3, 2, 1])
print(is_palindrome(ll_true))
ll_false = LinkedList([1, 2, 3, 4, 5, 6, 7, 8, 9])
print(is_palindrome(ll_false))

실행 결과

True
False


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch 09 Recursion and Dynamic Programming  (0) 2017.08.23
Ch01 Array and Strings  (0) 2017.08.10
Sorting  (0) 2017.08.06
Graph Search  (0) 2017.08.06
String  (0) 2017.07.31

Ch01 Array and Strings


1.1 문자열에 포함된 다른 문자들이 전부 유일한지를 검사하는 알고리즘 구현. 다른 자료구조를 사용할 수 없는 상황에서의

문자가 a~z로 총 26개라면 int 변수 1개로 count해서 이를 판별할 수 있다.

Code

public class QuestionB {

	/* Assumes only letters a through z. */
	public static boolean isUniqueChars(String str) {
		if (str.length() > 26) { // Only 26 characters
			return false;
		}
		int checker = 0;
		for (int i = 0; i < str.length(); i++) {
			int val = str.charAt(i) - 'a';
			if ((checker & (1 << val)) > 0) return false;
			checker |= (1 << val);
		}
		return true;
	}
	
	public static void main(String[] args) {
		String[] words = {"abcde", "hello", "apple", "kite", "padle"};
		for (String word : words) {
			System.out.println(word + ": " + isUniqueChars(word));
		}
		String a = "abcde";
	}
}

1.2 Permuation을 확인 하는 방법, Anagram 이랑 동일

정렬된 Algorihtm을 가지고 비교 한다.

Sroting을 해서 비교하는 방법이다.

public class QuestionA {	
	public static String sort(String s) {
		char[] content = s.toCharArray();
		java.util.Arrays.sort(content);
		return new String(content);
	}
	
	public static boolean permutation(String s, String t) {
		return sort(s).equals(sort(t));
	}	
	
	public static void main(String[] args) {
		String[][] pairs = {{"apple", "papel"}, {"carrot", "tarroc"}, {"hello", "llloh"}};
		for (String[] pair : pairs) {
			String word1 = pair[0];
			String word2 = pair[1];
			boolean anagram = permutation(word1, word2);
			System.out.println(word1 + ", " + word2 + ": " + anagram);
		}
	}
}

Ascii 코드를 이용한 방법이다.

public class QuestionB {	
	public static boolean permutation(String s, String t) {
		if (s.length() != t.length()) return false; // Permutations must be same length
		
		int[] letters = new int[128]; // Assumption: ASCII
		for (int i = 0; i < s.length(); i++) {
			letters[s.charAt(i)]++;
		}
		  
		for (int i = 0; i < t.length(); i++) {
			letters[t.charAt(i)]--;
		    if (letters[t.charAt(i)] < 0) {
		    	return false;
		    }
		}
		  
		return true; // letters array has no negative values, and therefore no positive values either
	}
	
	public static void main(String[] args) {
		String[][] pairs = {{"apple", "papel"}, {"carrot", "tarroc"}, {"hello", "llloh"}};
		for (String[] pair : pairs) {
			String word1 = pair[0];
			String word2 = pair[1];
			boolean anagram = permutation(word1, word2);
			System.out.println(word1 + ", " + word2 + ": " + anagram);
		}
	}
}

1.3 URLify 모든 빈 공간을 %20으로 채워라

예제
input: "Mr John Smith "
Output: "Mr%20John%20Smith"

뒷 쪽에 충분한 Margin이 있으므로 뒤에서 부터 앞으로 작업하는 것이 일반적인 방법이다.

two scan approach를 채택 한다.

  • 첫 번째에서는 number of spaces를 카운트 한다. 그 다음 3배를 해서 최종적으로 얼마나 많은 추가 character가 필요한지 알 수 있다.
  • 두 번째에서는 실제 string의 순서를 조절하게 된다. 즉 space가 있으면 %20을 채우고 no space면 orignal character를 채운다.
# O(N)
import unittest

def urlify(string, length):
    '''function replaces single spaces with %20 and removes trailing spaces'''
    new_index = len(string)

    for i in reversed(range(length)):
        if string[i] == ' ':
            # Replace spaces
            string[new_index - 3:new_index] = '%20'
            new_index -= 3
        else:
            # Move characters
            string[new_index - 1] = string[i]
            new_index -= 1

    return string

class Test(unittest.TestCase):
    '''Test Cases'''
    # Using lists because Python strings are immutable
    data = [
        (list('much ado about nothing      '), 22,
         list('much%20ado%20about%20nothing')),
        (list('Mr John Smith    '), 13, list('Mr%20John%20Smith'))]

    def test_urlify(self):
        for [test_string, length, expected] in self.data:
            actual = urlify(test_string, length)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()

문자열 압축 (String Compression)

# O(N)
import unittest

def string_compression(string):
    compressed = []
    counter = 0

    for i in range(len(string)):
        if i != 0 and string[i] != string[i - 1]:
            compressed.append(string[i - 1] + str(counter))
            counter = 0
        counter += 1

    # add last repeated character
    compressed.append(string[-1] + str(counter))

    # returns original string if compressed string isn't smaller
    return min(string, ''.join(compressed), key=len)


class Test(unittest.TestCase):
    '''Test Cases'''
    data = [
        ('aabcccccaaa', 'a2b1c5a3'),
        ('abcdef', 'abcdef')
    ]

    def test_string_compression(self):
        for [test_string, expected] in self.data:
            actual = string_compression(test_string)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()

Rotate Matrix

Matrix를 Rotation 하게 된다. 외부에서 안으로 진행하는 방식으로 처리 한다.

# O(NxN)
import unittest


def rotate_matrix(matrix):
    '''rotates a matrix 90 degrees clockwise'''
    n = len(matrix)
    for layer in range(n // 2):
        first, last = layer, n - layer - 1
        for i in range(first, last):
            # save top
            top = matrix[layer][i]

            # left -> top
            matrix[layer][i] = matrix[-i - 1][layer]

            # bottom -> left
            matrix[-i - 1][layer] = matrix[-layer - 1][-i - 1]

            # right -> bottom
            matrix[-layer - 1][-i - 1] = matrix[i][- layer - 1]

            # top -> right
            matrix[i][- layer - 1] = top
    return matrix


class Test(unittest.TestCase):
    '''Test Cases'''
    data = [
        ([
            [1, 2, 3, 4, 5],
            [6, 7, 8, 9, 10],
            [11, 12, 13, 14, 15],
            [16, 17, 18, 19, 20],
            [21, 22, 23, 24, 25]
        ], [
            [21, 16, 11, 6, 1],
            [22, 17, 12, 7, 2],
            [23, 18, 13, 8, 3],
            [24, 19, 14, 9, 4],
            [25, 20, 15, 10, 5]
        ])
    ]

    def test_rotate_matrix(self):
        for [test_matrix, expected] in self.data:
            actual = rotate_matrix(test_matrix)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()

1.7 M x N 행렬의 한 원소가 0일 경우 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성

생각1
단순히 발견하는 0의 행과 열을 0으로 변경하면서 진행하면 금방 전부다 0이 되어 버린다.

생각2
추가적인 공간 O(MN)에 0의 위치를 기록하고 그 다음 해당 열과 행을 0으로 초기화 하는 방법이 있다.

생각3
그런데 정말로 O(MN) 만큼의 공간이 필요한가? 그렇지 않다. 같은 행과 열의 모든 원소의 값을 0으로 만들 것이므로, 0인 원소가 정확히 몇 번째 행에 몇 번째 열의 원소였는지 알 필요는 없다. 우리는 그저 어떤 행 안에 0 값을 갖는 원소가 있다는 사실만 기록하면 되고, 어떤 열 안에 0값을 갖는 원소가 있다는 사실만 기록하면 된다. 어차피 그 행과 열의 모든 원소를 0으로 만들 것인데, 왜 정확한 위치를 기록해야 하는가.

코드는 아래와 같다. 0이 있는 행과 열을 추적하기 위한 배열을 두 개 사용 했다. 그런 다음, 이 배열의 갑에 따라서 행과 열을 전부 0으로 만들도록 했다.

코드

# O(MxN)
import unittest


def zero_matrix(matrix):
    m = len(matrix)
    n = len(matrix[0])
    rows = []
    cols = []

    for x in range(m):
        for y in range(n):
            if matrix[x][y] == 0:
                rows.append(x)
                cols.append(y)

    for row in rows:
        nullify_row(matrix, row)

    for col in cols:
        nullify_col(matrix, col)

    return matrix


def nullify_row(matrix, row):
    for i in range(len(matrix[0])):
        matrix[row][i] = 0


def nullify_col(matrix, col):
    for i in range(len(matrix)):
        matrix[i][col] = 0


class Test(unittest.TestCase):
    '''Test Cases'''
    data = [
        ([
            [1, 2, 3, 4, 0],
            [6, 0, 8, 9, 10],
            [11, 12, 13, 14, 15],
            [16, 0, 18, 19, 20],
            [21, 22, 23, 24, 25]
        ], [
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [11, 0, 13, 14, 0],
            [0, 0, 0, 0, 0],
            [21, 0, 23, 24, 0]
        ])
    ]

    def test_zero_matrix(self):
        for [test_matrix, expected] in self.data:
            actual = zero_matrix(test_matrix)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()

1.8 한 단어가 다른 단어에 포함된 문자열인지 판별하는 isSubstring이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌을 때, s2가 s1을 회전시킨 결과인지 판별하는 코드를 isSubstring을 한 번만 호출하도록 하여 작성하라.

s2가 s1을 회전시켜 얻은 문자열이라면, 회전된 지점이 어딘지를 알아봐야 한다.
가령 waterbottle을 회전시켜 erbbottlewat을 얻어다고 해보자.
회전시킬 때, s1을 x와 y의 두 부분으로 나눈 다음 다시 배열하여 s2를 얻었을 것이다.

s1 = xy = waterbottle
x = wat
y = erbottle
s2 = yx = erbottlewat

하지만 중요한점은 x와 y를 나눈 지점이 어디인가 상관없이, yx는 언제나 xyxy의 부분 문자열이다. 다시 말해서, s2는 언제나 s1s1의 부분 문자열이란 이야기이다.

즉, isSubstring(s1s1,s2)인지 알아보면 된다는 것이다.

# O(N)
import unittest


def is_substring(string, sub):
    return string.find(sub) != -1


def string_rotation(s1, s2):
    if len(s1) == len(s2) != 0:
        return is_substring(s1 + s1, s2)
    return False


class Test(unittest.TestCase):
    '''Test Cases'''
    data = [
        ('waterbottle', 'erbottlewat', True),
        ('foo', 'bar', False),
        ('foo', 'foofoo', False)
    ]

    def test_string_rotation(self):
        for [s1, s2, expected] in self.data:
            actual = string_rotation(s1, s2)
            self.assertEqual(actual, expected)

if __name__ == "__main__":
    unittest.main()


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch 09 Recursion and Dynamic Programming  (0) 2017.08.23
Ch02 LinkedList  (0) 2017.08.11
Sorting  (0) 2017.08.06
Graph Search  (0) 2017.08.06
String  (0) 2017.07.31

rpy2와 Pandas를 활용한 R object 변환


Rdata파일을 읽어와서 Robject를 다루는 방법을 기술한다.
필요한 package들은 아래와 같다.

from rpy2.robjects import r
from rpy2.robjects import pandas2ri
import pandas as pd
pandas2ri.activate()

위와 같이 robjects를 다루는 r pandas r을 연결해주는 pandas2ri 두 개의 package가 필요하다.

로딩 방법

# Object를 생성 한다.

r.load("./Rdata/num10FclassDf10PassTrain.Rdata")

실행 결과

R object with classes: ('character',) mapped to:
<StrVector - Python:0x7fc114f787c8 / R:0x2cdfbd8>
['num10FclassDf10PassTrain']

데이터 출력

r['num10FclassDf10PassTrain']

실행결과

R object with classes: ('list',) mapped to:
<ListVector - Python:0x7fc115095bc8 / R:0x265d9f0>
[Matrix, Matrix, Matrix, ..., Matrix, Matrix, Matrix]
  acquaintanceSeula: <class 'rpy2.robjects.vectors.Matrix'>
  R object with classes: ('matrix',) mapped to:
<Matrix - Python:0x7fc1150877c8 / R:0x4072ca0>
[       1,        1,        1, ...,        1,        1,        1]
  ikhee: <class 'rpy2.robjects.vectors.Matrix'>
  R object with classes: ('matrix',) mapped to:
<Matrix - Python:0x7fc1150b7308 / R:0x407a9d0>
[       1,        2,        1, ...,        1,        1,        2]
  Jemin: <class 'rpy2.robjects.vectors.Matrix'>
  R object with classes: ('matrix',) mapped to:
<Matrix - Python:0x7fc1153085c8 / R:0x40843b0>
[       2,        1,        1, ...,        1,        2,        2]
  ...
  acquaintanceSeula: <class 'rpy2.robjects.vectors.Matrix'>
  R object with classes: ('matrix',) mapped to:
<Matrix - Python:0x7fc11530c048 / R:0x432ead0>
[       1,        2,        2, ...,        2,        2,        2]
  ikhee: <class 'rpy2.robjects.vectors.Matrix'>
  R object with classes: ('matrix',) mapped to:
<Matrix - Python:0x7fc114efff08 / R:0x434e400>
[       1,        1,        1, ...,        2,        2,        2]
  Jemin: <class 'rpy2.robjects.vectors.Matrix'>
  R object with classes: ('matrix',) mapped to:
<Matrix - Python:0x7fc114eff888 / R:0x4354790>
[       1,        1,        3, ...,        1,        1,        2]

ri2py로 데이터형 변환

pandas2ri.ri2py(r['num10FclassDf10PassTrain'][0])

데이터 프레임으로 변경하는 방법

df1 = pd.DataFrame(pandas2ri.ri2py(r['num10FclassDf10PassTrain'][0]), columns=['AppName', "Title", "Hours", "Days", "RecentPhoneUsage", "Proximity", "Priority", "Activity", "PhoneStatus", "SeenTime", "class"])
df1.head()

참고문헌

https://pandas.pydata.org/pandas-docs/stable/r_interface.html


Sorting


Bubble

시간복잡도는 $O(N^2)$이다.
공간복잡도는 $O(1)$

def bubbleSort(n, a):
    cumulatedNumSwap = 0
    for i in range(0, n):
        numSwap = 0
        for j in range(0, n-1):
            if a[j] > a[j+1]:
                temp = a[j]
                a[j] = a[j+1]
                a[j+1] = temp
                numSwap += 1
        cumulatedNumSwap += numSwap
        if numSwap == 0:
            break
    return cumulatedNumSwap, a

if __name__ == "__main__":
    a = [2, 1, 3, 1, 2]
    numSwap, sortedA = bubbleSort(len(a), a)

    print("Array is sorted in %d swaps."%numSwap)
    print("First Element: %d"%sortedA[0])
    print("Last Element: %d"%sortedA[-1])

Insertion

Time Complexity:

  • best: $O(n)$
  • worst: $O(n^2)$
    Space Complexity: $O(1)$

간단한 삽입정렬

def InsertionSort(input):
    for i in range(len(input)-1):
        for j in range(i+1,len(input)):
            if(input[j] < input[i]):
                input[i], input[j] = input[j], input[i]
    return input
import random

def InsertionSort(input):

    for idx, valueToInsert in enumerate(input):
        # select the hole position where number is to be inserted
        holePosition = idx

        # check if previous no. is larger than value to be inserted
        while holePosition > 0 and input[holePosition-1] > valueToInsert:
            input[holePosition - 1], input[holePosition] = input[holePosition], input[holePosition-1]
            holePosition = holePosition - 1

    return input

if __name__ == "__main__":
    A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
    print(A)
    InsertionSort(A)
    print(A)

실행결과

[84, 59, 97, 41, 6, 93, 80, 62, 19, 37, 83, 24, 86, 95, 46]
[6, 19, 24, 37, 41, 46, 59, 62, 80, 83, 84, 86, 93, 95, 97]

Selection

Time complexity: $O(n^2)$
Space complexity: $O(1)$

import random
def selectionSort(input):
    for i in range(len(input) - 1):
        # assume the min is the first element
        idx_min = i
        j = i + 1

        # test against elements after i to find the smallest
        while j < len(input):
            if(input[j] < input[idx_min]):
                # found new minimum; remember its index
                idx_min = j
            j = j + 1

        if idx_min is not i:
            # swap
            input[idx_min], input[i] = input[i], input[idx_min]

    return input

if __name__ == "__main__":
    A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
    print(A)
    selectionSort(A)
    print(A)

실행결과

[72, 10, 31, 7, 51, 11, 97, 9, 45, 54, 35, 26, 61, 55, 13]
[7, 9, 10, 11, 13, 26, 31, 35, 45, 51, 54, 55, 61, 72, 97]

Merge

worst와 average모두 $O(n \log n)$인 엄청나게 좋은 알고리즘이다.
하지만 공간 복잡도는 $O(n)$을 메모리는 많이 사용 합니다.
그래도 기본적인 Dvide and Conquer를 적용한 알고리즘이기에 확실히 알고 넘어가면 좋다.

위키피디아에 나온 그림으로 나타낸 동작 방법은 아래와 같다.

$T(n)=2T\left(\frac{n}{2}\right)+n$
$\begin{aligned}
T(n)&=2\left(2T\left(\frac{n}{4}\right)+\frac{n}{2}\right)+n \newline
&=4T\left(\frac{n}{4}\right)+n+n\newline
&=…\newline
&\approx O(\underbrace{n+n+…+n}_{\log n})\newline
&=O(n\log n)
\end{aligned}$

코드는 아래와 같다.

import random

# Time Complexity O(nLogn)
# Space Complexity O(n)

def mergeSort(A):
    ### Base case ###

    if len(A) <= 1:
        return A

    ### A를 반으로 쪼개서 recursive call을 해 주고 정렬된 반쪽짜리들을 받아옵니다.
    left = mergeSort(A[:int(len(A)/2)])
    right = mergeSort(A[int(len(A)/2):])

    ### 여기서부터 두 개의 쪼개졌던 list를 합치는 Merge 부분입니다.
    ### 여기서 포인트는 정렬된 상태로 돌아왔기 때문에 앞에서부터 순차적으로 한번만 돌면 정렬시킬 수 있다는 것입니다.
    i, j, k = 0, 0, 0
    while i<len(left) and j<len(right):
        if left[i] < right[j]:
            A[k] = left[i]
            i += 1
        else:
            A[k] = right[j]
            j += 1
        k += 1
    if i == len(left): #만약 left의 원소를 모두 채웠고, right가 남아있을 때.
        while j<len(right):
            A[k] = right[j]
            j += 1
            k += 1
    elif j == len(right): #만약 right의 원소를 모두 채웠고, left가 남아있을 때.
        while i<len(left):
            A[k] = left[i]
            i += 1
            k += 1
    return A #마지막으로 정렬된 list를 리턴합니다.

if __name__ == "__main__":

    A=[random.randint(1,100) for _ in range(10)]
    print("unsorted List:")
    print(A)
    print("Sorted List:")
    print(mergeSort(A))

실행결과

unsorted List:
[94, 22, 47, 26, 28, 29, 33, 53, 5, 54]
Sorted List:
[5, 22, 26, 28, 29, 33, 47, 53, 54, 94]

참고자료
https://smlee729.github.io/python/algorithm/2015/03/03/1-merge-sort.html

Quick

분할 정복 알고리즘으로 Sorting한다.
Merge Sort와 다르게 분할 할 때 복잡하고 병합할 때는 복잡하지 않다.

평균 시간 복잡도는 $O(nlogn)$이다. 메모리 측면에서 좀 더 효율 적이다. 따라서 실제로 동작하는 속도가 좀 더 빠르다.
$$T(n)\approx n+2T(\frac{n}{2})$$

하지만, 최악의 상황인 이미 정렬이 완료된 List를 정렬할 경우 $T(n)=n+T(n-1)$으로 분할 된다.
왜냐하면 pivot이 가장 큰 값이라면 left side n-1개가 존재하고 이 부분을 계속 quick sort로 recursive하게 호출이 발생하기 때문이다. 결국 $O(n^2)$의 복잡도를 가진다.

Pivot이 Median값이라면 merge sort와 같은 복잡도를 가진다. 최악의 경우를 피하는 방법은 통상 random choice를 이용한다.

import random

# 아까 말씀드렸다시피, pivot을 선택한 후에(parition 함수의 결과값으로 pivot의 최종 index가 나옵니다.) recursive call로 쪼갭니다.
def quicksort(A, start, end):
    if start < end:
        p = partition(A, start, end)
        quicksort(A, start, p - 1)
        quicksort(A, p + 1, end)


# 이제 pivot을 뽑는 과정을 알아봅시다.
def partition(A, start, end):
    pivot = end
    wall = start
    # 나머지 원소들은 A[hi]와 비교하면서 재정렬합니다.
    for i in range(start, end):
        if A[i] < A[pivot]:
            #swap
            A[i], A[wall] = A[wall], A[i]
            wall += 1
    A[pivot], A[wall] = A[wall], A[pivot] # 마지막으로 pivot을 자신보다 큰 원소들의 첫번째 원소와 바꿔줍니다. (전반부, 후반부를 나누기 위해서)
    return wall

if __name__ == "__main__":
    A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
    print(A)
    quicksort(A, 0, len(A)-1)
    print(A)


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch02 LinkedList  (0) 2017.08.11
Ch01 Array and Strings  (0) 2017.08.10
Graph Search  (0) 2017.08.06
String  (0) 2017.07.31
HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31

Graph Search


아래와 같은 Graph가 있다고 가정한다.

Depth Frist Search (DFS)

  • 임의의 노드n을 선택
  • n을 방문했다고 표시
  • n의 방문하지 않은 인접 vertex를 방문한다.

Breadth First Search (BFS)

  • 노드 n부터 시작하고, 방문했다고 표시하면서 큐에 삽입
  • 큐가 empty일때까지 계속 반복하면서,
  • 큐에서 첫번째 원소를 뽑는다. 그리고 뽑은 원소의 방문하지 않은 이웃들을 방문했다고 표시 후에 큐의 끝에 지어넣는다.
class graph:
    def __init__(self, vertexList, edgeList):
        self.vertexList = vertexList
        self.edgeList = edgeList
        self.adjacentList = [[] for id in range(len(vertexList))]
        for edge in edgeList:
            self.adjacentList[edge[0]].append(edge[1])

def recursiveDFS(graph,node, visited=[]):
    visited.append(node)
    for neighbor in graph.adjacentList[node]:
        if neighbor not in visited:
            recursiveDFS(graph, neighbor, visited)
    return visited

# queue에 insert 할 때 넣는 방법
def BFS(graph,node, visited=[]):
    queue = [node] # 맨 처음 버텍스를 삽입 한다.
    visited.append(node) # 방문한 리스트에 맨 처음 버텍스를 넣는다.
    while queue: # 큐가 비었는지 확인 한다
        current = queue.pop() # 큐에서 데이터를 꺼내온다.
        for neighbor in graph.adjacentList[current]: # 인접 vertex에서 값을 하나 가져온다.
            if not neighbor in visited: # 현재 인접 노드의 값이 방문한 것이 아닌지 확인 한다.
                queue.insert(0,neighbor)
                visited.append(neighbor)
    return visited

# queue에 pop할 때 visit 하는 방법
def BFS2(graph,node, visited=[]):
    queue = [node]
    #visited.append(node)

    while queue:
        current = queue.pop()
        for vertex in graph.adjacentList[current]:
            if vertex not in visited:
                queue.insert(0, vertex)
        visited.append(current)
    return visited



if __name__ == "__main__":

    # Depth First Search (DFS)
    vertexList = ['0', '1', '2', '3', '4', '5', '6']
    edgeList = [(0, 1), (0, 2), (1, 0), (1, 3), (2, 0), (2, 4), (2, 5), (3, 1), (4, 2), (4, 6), (5, 2), (6, 4)]

    graphObj = graph(vertexList, edgeList)
    print("vertex list")
    print(graphObj.vertexList)
    print("edge list")
    print(graphObj.edgeList)
    print("adjacent list")
    print(graphObj.adjacentList)

    print("DFS Traverse:")
    print(recursiveDFS(graphObj,0))
    print("BFS Traverse:")
    print(BFS(graphObj,0))

실행결과

vertex list
['0', '1', '2', '3', '4', '5', '6']
edge list
[(0, 1), (0, 2), (1, 0), (1, 3), (2, 0), (2, 4), (2, 5), (3, 1), (4, 2), (4, 6), (5, 2), (6, 4)]
adjacent list
[[1, 2], [0, 3], [0, 4, 5], [1], [2, 6], [2], [4]]
DFS Traverse:
[0, 1, 3, 2, 4, 6, 5]
BFS Traverse:
[0, 1, 2, 3, 4, 5, 6]

참고자료
https://smlee729.github.io/python/network%20analysis/2015/04/09/1-networkx-dfs-bfs.html


'Computer Science > Coding Interview' 카테고리의 다른 글

Ch01 Array and Strings  (0) 2017.08.10
Sorting  (0) 2017.08.06
String  (0) 2017.07.31
HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31
Binary Search Tree  (0) 2017.07.31

쓰레드 (Thread)


Thread 생성 기법

Thread를 생성하는 방법은 아래 2가지 이다.

Thread()
Thread(Runnable runnable)

첫 번째 방법인 Thread의 경우 run에 해당 기능을 구현한다.

// Activity

BackThread thread = new BackThread():
thread.setDaemon(true);
thread.start();

class BackThread extends Thread {
	public void run(){
		while(true){
			mValue++;
			try {Thread.sleep(1000);} catch {InterruptedException e){;}
		}
	}
}

두 번째 방법인 Runnable은 interface 내부에 run을 구현 하는 방식이다.

Back Runnable runnable = new BackRunnable();
Thread thread = new Thread(runnable);
thread.setDeamon(true); // main thread가 종료 될 때만 종료된다 라는 의미이다.
thread.start();

class BackRunnable implements Runnable {
	public void run(){
		while(true){
			mBackValue ++;
			try {Thread.sleep(1000);} catch (interruptedException e) {;}
		}
	}
}

구지 복잡하게 자바에서 Runnable Interface를 지원하는 이유는 다중상속을 지원하지 않는 특성상
Thread만 구현 하고 싶을 때 Runnable을 이용하라는 의미이다.

Thread간의 통신 Handler

Handler 클래스로 표현되는 핸들러는 Tread간에 메시지 Runnable 객체를 통해 메시지를 주고 받는 장치이다.

  • 핸들러는 생성하는 Thread에 부착 된다. 부착된 Thread의 메시지큐를 통해서 다른 Thread와 통신 한다.
  • Handler는 Message를 MessageQueue에 넣는 기능과 MessageQueue에서 꺼내 처리하는 기능을 함께 제공한다.

Handler 생성자 이해

  • Handler()
  • Handler(Handler.Callback callback)
  • Handler(Looper looper)
  • Handler(Looper looper, Handler.Callback callback)

메시지 수신에 사용되는 메서드

  • void handleMessage (Message msg)
    인수 Message는 아래와 같은 추가 필드를 가진다.
  • int what: 메시지의 의미를 설명한다. 의미가 정해져 있지는 않으며 핸들러별로 지역적이므로 다른 핸들러와 충돌할 위험은 없다.
  • int arg1: 메시지의 추가 정보이다.
  • int arg2: 메시지의 추가 정보이다.
  • Object obj: 정수만으로 메시지를 기술할 수 없을 때 임의의 객체를 보낸다.
  • Messenger replyTo: 메시지에 대한 응답을 받을 객체를 지정한다.

메시지를 보내는 쪽에서는 전달하고자 하는 내용을 Message 객체에 저장하여 핸들러로 전송한다.
사용되는 메서드는 다음과 같다.

  • boolean Handler.sendEmptyMessage (int what)
  • boolean Handler.sendMessage (Message msg)
  • boolean Handler.sendEmptyMessageAtTime(int what, long uptimeMillis)
  • boolean Handler.sendMessageAtTime(Message msg, long uptimeMillis)
  • boolean sendMessageAtFrontOfQueue (Message msg)

실행 코드인 Runnable object를 전송하는 메서드는 다음과 같다.

  • boolean Handler.post(Runnable r)
  • boolean Handler.postDelayed(Runnable r, long delayMillis)
  • boolean Handler.postAtTime(Runnable r, Object token, long uptimeMillis)
  • boolean Handler.postAtTime(Runnable r, long uptimeMillis)
  • boolean Handler.postAtFrontofQueue(Runnable r)

메시지 전송 예제

public class HandlerTest extends Activity {
	int mMainValue = 0;
	int mBackValue = 0;
	TextView mMainText;
	TextView mBackText;

	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.threadtest);

		mMainText = (TextView)findViewById(R.id.mainvalue);
		mBackText = (TextView)findViewById(R.id.backvalue);

		BackThread thread = new BackThread();
		thread.setDaemon(true);
		thread.start();
	}

	public void mOnClick(View v) {
		mMainValue++;
		mMainText.setText("MainValue : " + mMainValue);
	}

	class BackThread extends Thread {
		public void run() {
			while (true) {
				mBackValue++;
				mHandler.sendEmptyMessage(0);
				try { Thread.sleep(1000); } catch (InterruptedException e) {;}
			}
		}
	}

	Handler mHandler = new Handler() {
		public void handleMessage(Message msg) {
			if (msg.what == 0) {
				mBackText.setText("BackValue : " + mBackValue);
			}
		}
	};
}

Runnable 객체 전송 예제
위 예제와 다르게 실행 객체를 전송하므로 mHandler는 구체적으로 정의할 필요 없이 생성만 해두면
내부 Runnable Code가 실행 된다.

public class HandlerTest extends Activity {
	int mMainValue = 0;
	int mBackValue = 0;
	TextView mMainText;
	TextView mBackText;

	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.threadtest);

		mMainText = (TextView)findViewById(R.id.mainvalue);
		mBackText = (TextView)findViewById(R.id.backvalue);

		BackThread thread = new BackThread();
		thread.setDaemon(true);
		thread.start();
	}

	public void mOnClick(View v) {
		mMainValue++;
		mMainText.setText("MainValue : " + mMainValue);
	}

	class BackThread extends Thread {
		public void run() {
			while (true) {
				mBackValue++;
				mHandler.post(new Runnable() {
					public void run() {
						mBackText.setText("BackValue : " + mBackValue);
					}
				});
				try { Thread.sleep(1000); } catch (InterruptedException e) {;}
			}
		}
	}

	Handler mHandler = new Handler();
}

위 예제에서는 Anonymous class 기법이 사용 되었다.

// non-anonymous class
Runnable runUpdate = new Runnable(){
	public void run() {
		mBackText.setText();
	}
};
mHandler.post(runUpdate);

// anonymous class
mHandler.post(new Runnable(){
	public void run() {
		mBackText.setText();
	}
};

runOnUiThread를 통한 Main UI Thread와의 통신

  • runOnUiThread 메서드 호출 위치가 UI 스레드라면 Runnable은 즉시 실행된다.

  • 작업 스레드에서 runOnUiThread가 호출 되었다면 자동으로 UI 스레드 큐를 찾아서 Runnable을 그 뒤에 붙여 준다. 즉, RunnableHandler.post를 하지 않아도 내부적으로 이와 동일한 작업을 해주는 것이다. mHandler가 없어도 상관 없기 때문에 훨씬 간편하다.

익명 class를 runnable로 runOnUiThread로 전달하는 예제

//* runOnUiThread 메서드로 익명 임시 객체 전달
public class HandlerTest extends Activity {
	int mMainValue = 0;
	int mBackValue = 0;
	TextView mMainText;
	TextView mBackText;

	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.threadtest);

		mMainText = (TextView)findViewById(R.id.mainvalue);
		mBackText = (TextView)findViewById(R.id.backvalue);

		BackThread thread = new BackThread();
		thread.setDaemon(true);
		thread.start();
	}

	public void mOnClick(View v) {
		mMainValue++;
		mMainText.setText("MainValue : " + mMainValue);
	}

	class BackThread extends Thread {
		public void run() {
			while (true) {
				mBackValue++;
				runOnUiThread(new Runnable() {
					public void run() {
						mBackText.setText("BackValue : " + mBackValue);
					}
				});
				try { Thread.sleep(1000); } catch (InterruptedException e) {;}
			}
		}
	}
}

Activity 외부에 Thread가 선언된 좀 더 일반적인 경우

public class HandlerTest extends Activity {
	int mMainValue = 0;
	TextView mMainText;
	TextView mBackText;
	BackThread mThread;

	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.threadtest);

		mMainText = (TextView)findViewById(R.id.mainvalue);
		mBackText = (TextView)findViewById(R.id.backvalue);
		mThread = new BackThread(mHandler);
		mThread.setDaemon(true);
		mThread.start();
	}

	public void mOnClick(View v) {
		mMainValue++;
		mMainText.setText("MainValue : " + mMainValue);
	}

	Handler mHandler = new Handler() {
		public void handleMessage(Message msg) {
			if (msg.what == 0) {
				mBackText.setText("BackValue : " + msg.arg1);
			}
		}
	};
}

class BackThread extends Thread {
	int mBackValue = 0;
	Handler mHandler;

	BackThread(Handler handler) {
		mHandler = handler;
	}

	public void run() {
		while (true) {
			mBackValue++;
			Message msg = new Message();
			msg.what = 0;
			msg.arg1 = mBackValue;
			mHandler.sendMessage(msg);
			try { Thread.sleep(1000); } catch (InterruptedException e) {;}
		}
	}
}

지금 까지 예제와 다른점은 분리된 파일에 각각의 코드가 정의 되었다고 가정하므로
BackThread Class의 생성자를 통해서 main activity handler를 넘겨 주어야 한다는 점이다.
Message에도 좀 더 구체적으로 값을 넣어서 보내줘야 Main Activity Handler에서 처리가 가능하다.

성능향상을 위해서 obtain함수를 이용해서 message를 생성 할 수 있다.
Cache에 있는 이전에 생성한 Message를 재사용하는 방식이다.

class BackThread extends Thread {
	int mBackValue = 0;
	Handler mHandler;

	BackThread(Handler handler) {
		mHandler = handler;
	}

	public void run() {
		while (true) {
			mBackValue++;
			Message msg = Message.obtain(mHandler, 0, mBackValue, 0);
			mHandler.sendMessage(msg);
			try { Thread.sleep(1000); } catch (InterruptedException e) {;}
		}
	}
}

Looper (루퍼)

서로 다른 thread는 message를 이용해서 통신한다.

  • Message Queue: 메시지가 차곡차곡 쌓이는 것을 말한다.
  • Looper: 큐에서 메시지를 꺼내 핸들러로 전달하는 것을 담당한다. 단, MainThread는 기본적으로 Looper를 가지고 있기 때문에 따로 구현할 필요는 없다. WorkingThread의 경우에만 직접 구현하면 된다.
  • Handler: 메시지를 받기도하고 보내기도 한다.

응용프로그램을 시작할 때 생성되는 메인 스레드는 루퍼를 가지고 있으며 이미 동작하므로 이 경우는 루퍼나 메시지 큐의 존재에 대해 상세히 몰라도 상관없다. 핸들러를 만들어 놓고 전달되는 메시지를 처리하기만 하면 된다.

루퍼를 직접 프로그래밍해야 하는 경우는 작업 스레드가 메시지를 받아야 할 때이다.

백그라운드 스레드는 Looper가 없다. 백그라운드 스레드에서 기본 핸들러 생성자 Handler()를 사용하면 따라서 에러가 발생한다.
Can't create handler inside thread that has not called Looper.prepare라는 메시지가 나온다.

Looper가 실행하는 관련 함수는 다음과 같다.

static void prepare()
static void loop()
void quit()
  • prepare는 현재 스레드를 위한 루퍼를 준비한다. 내부적으로 메시지를 저장하는 MessageQueue를 생성하고 그외 메시지 전송에 필요한 조치를 한다.
  • loop는 큐에서 메시지를 꺼내 핸들러로 전달하는 루프를 생성 한다.
  • quit는 루프의 종료롤 나타낸다.

다음은 관련된 스레드와 루퍼를 구하는 메서드

Thread getThread()  
static Looper getMainLooper()  
static Looper myLooper() 
  • getThread: 루퍼와 연결된 스레드를 구한다.
  • getMainLooper: 응용프로그램 수준에서의 주 루퍼를 반환
  • myLooper: 현재 스레드의 루퍼를 구한다. 모든 스레드가 루퍼가 있는것은 아니므로 null이 리턴될 수도 있다.

다음 예제 코드는 메인 스레드와 작업 스레드가 메시지를 통해 양방향으로 통신하는 예를 보여준다.
메인에서 메시지를 보내 연산을 시키고 스레드가 연산 결과를 리턴할 때도 메시지를 사용한다.

Main Thread와 Working Thread 모두 Looper가 존재하는 코드

public class LooperTest extends Activity {
	int mMainValue = 0;
	TextView mMainText;
	TextView mBackText;
	EditText mNumEdit;
	CalcThread mThread;

	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.loopertest);

		mMainText = (TextView)findViewById(R.id.mainvalue);
		mBackText = (TextView)findViewById(R.id.backvalue);
		mNumEdit = (EditText)findViewById(R.id.number);

		mThread = new CalcThread(mHandler);
		mThread.setDaemon(true);
		mThread.start();
	}

	public void mOnClick(View v) {
		Message msg;
		switch (v.getId()) {
		case R.id.increase:
			mMainValue++;
			mMainText.setText("MainValue : " + mMainValue);
			break;
		case R.id.square:
			msg = new Message();
			msg.what = 0;
			msg.arg1 = Integer.parseInt(mNumEdit.getText().toString());
			mThread.mBackHandler.sendMessage(msg);
			break;
		case R.id.root:
			msg = new Message();
			msg.what = 1;
			msg.arg1 = Integer.parseInt(mNumEdit.getText().toString());
			mThread.mBackHandler.sendMessage(msg);
			break;
		}
	}

	Handler mHandler = new Handler() {
		public void handleMessage(Message msg) {
			switch (msg.what) {
			case 0:
				mBackText.setText("Square Result : " + msg.arg1);
				break;
			case 1:
				mBackText.setText("Root Result : " + ((Double)msg.obj).doubleValue());
				break;
			}
		}
	};
}

class CalcThread extends Thread {
	Handler mMainHandler;
	Handler mBackHandler;

	CalcThread(Handler handler) {
		mMainHandler = handler;
	}

	public void run() {
		Looper.prepare();
		mBackHandler = new Handler() {
			public void handleMessage(Message msg) {
				Message retmsg = new Message();
				switch (msg.what) {
				case 0:
					try { Thread.sleep(200); } catch (InterruptedException e) {;}
					retmsg.what = 0;
					retmsg.arg1 = msg.arg1 * msg.arg1;
					break;
				case 1:
					try { Thread.sleep(200); } catch (InterruptedException e) {;}
					retmsg.what = 1;
					retmsg.obj = new Double(Math.sqrt((double)msg.arg1));
					break;
				}
				mMainHandler.sendMessage(retmsg);
			}
		};
		Looper.loop();
	}
}
  • 메인스레드 작업스레드의 핸들러를 객체를 통해서 바로 호출한다.
  • 작업스레드 메인스레드의 핸들러를 객체 생성시 생성자를 통해서 받아서 그것을 통해서 호출한다.

중요한점은 이러한 메시지기반 통신 방법은 스레드 간의 통신 장치일 뿐이다. 그 이상인 응용프로그램간의 통신에는 사용할 수 없다.
공식적으로 응용프로그램 레벨에서의 통신은 Intent BR을 사용해야 한다.

작업 스케줄링

메시지큐

메시지큐에 메시지를 전달하고 원하는 시간에 꺼내서 처리 될 수 있도록 한다.

// 절대 시간
boolean sendMessageAtTime (Message msg, long uptimeMillis)
boolean postAtTime (Runnable r, long uptimeMillis)

// 상대 시간
boolean sendMessageDelayed (Message msg, long delayMillis)
boolean postDelayed (Runnable r, long delayMillis)

아래와 같은 예제를 만들 수 있다.

// 러너블 전달 
public class Post extends Activity {
	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.upload);
	}

	public void mOnClick(View v) {
		new AlertDialog.Builder(this)
		.setTitle("질문")
		.setMessage("업로드 하시겠습니까?")
		.setPositiveButton("", new DialogInterface.OnClickListener() {
			public void onClick(DialogInterface dialog, int whichButton) {
				mHandler.postDelayed(new Runnable() {
					public void run() {
						doUpload();
					}
				},10);
			}
		})
		.setNegativeButton("아니오", null)
		.show();
	}

	Handler mHandler = new Handler();

	void doUpload() {
		for (int i = 0; i < 20; i++) {
			try { Thread.sleep(100); } catch (InterruptedException e) {;}
		}
		Toast.makeText(this, "업로드를 완료했습니다.", 0).show();
	}
}

위 예제는 Handler의 메시지 큐에 메시지를 전달 하는 것이다.
Runnable로 전달 하기 때문에 따로 Handler내부를 구현할 필요는 없다.

//* 뷰의 postDelayed 호출
public class Post extends Activity {
	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.upload);
	}

	public void mOnClick(View v) {
		new AlertDialog.Builder(this)
		.setTitle("질문")
		.setMessage("업로드 하시겠습니까?")
		.setPositiveButton("", new DialogInterface.OnClickListener() {
			public void onClick(DialogInterface dialog, int whichButton) {
				Button btnUpload = (Button)findViewById(R.id.upload);
				btnUpload.postDelayed(new Runnable() {
					public void run() {
						doUpload();
					}
				},10);
			}
		})
		.setNegativeButton("아니오", null)
		.show();
	}

	void doUpload() {
		for (int i = 0; i < 20; i++) {
			try { Thread.sleep(100); } catch (InterruptedException e) {;}
		}
		Toast.makeText(this, "업로드를 완료했습니다.", 0).show();
	}
}

위 예제는 더 재밌는 것으로 View에 있는 스레드 큐를 사용 한다.
메인 View에 메시지큐가 있다는 것이다.

ANR (Application Not Responding)

Application Not Reponsding (ANR)이 발생하는 조건은 아래 두 가지이다.

  • 응용프로그램이 5초 이상 사용자의 입력에 반응하지 않을 때
  • 브로드캐스트 리시버 (BR)가 10초 내로 리턴하지 않을 때
public class ANR2 extends Activity {
	boolean bUploading = false;
	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.anr);
	}
	
	public void mOnClick(View v) {
		switch (v.getId()) {
		case R.id.btnincrease:
			TextView textCounter=(TextView)findViewById(R.id.txtcounter);
			int count = Integer.parseInt(textCounter.getText().toString());
			textCounter.setText(Integer.toString(count + 1));
			break;
		case R.id.btnupload:
			if (bUploading) return;
			Thread uploadThread = new Thread() {
				public void run() {
					doUpload();
					mCompleteHandler.sendEmptyMessage(0);
				}
			};
			bUploading = true;
			uploadThread.start();
			break;
		}
	}

	public Handler mCompleteHandler = new Handler() {
		public void handleMessage(Message msg) {
			bUploading = false;
			Toast.makeText(ANR2.this, "업로드를 완료했습니다.", 0).show();
		}
	};
	
	void doUpload() {
		for (int i = 0; i < 100; i++) {
			try { Thread.sleep(100); } catch (InterruptedException e) {;}
		}
	}
}

위 코드는 두 가지로 나눠 지는데
첫 번째는 장기간 걸리는 작업을 Thread를 생성해서 doUpload()를 호출 했다는 점이다.
두 번째는 최종적인 결과 메시지 반환을 main thread의 handler호출로 처리 했다는 점이다.

StricMode

ANR 디버깅을 위해서 사용 하는 것으로 재미있는 기능 같다.

LogTime working을 Progress bar로 표현 하기

public class LongTime4 extends Activity {
	int mValue;
	TextView mText;
	ProgressDialog mProgress;
	boolean mQuit;
	UpdateThread mThread;

	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.longtime);

		mText=(TextView)findViewById(R.id.text);
	}
	
	@SuppressWarnings("deprecation")
	public void mOnClick(View v) {
		mValue = 0;
		showDialog(0);
		mQuit = false;
		mThread = new UpdateThread();
		mThread.start();
	}

	@SuppressWarnings("deprecation")
	protected Dialog onCreateDialog(int id) {
		switch (id) {
		case 0:
			mProgress = new ProgressDialog(this);
			mProgress.setProgressStyle(ProgressDialog.STYLE_HORIZONTAL);
			mProgress.setTitle("Updating");
			mProgress.setMessage("Wait...");
			mProgress.setCancelable(false);
			mProgress.setButton("Cancel", new DialogInterface.OnClickListener() {
				public void onClick(DialogInterface dialog, int whichButton) {
					mQuit = true;
					dismissDialog(0);
				}
			});
			return mProgress;
		}
		return null;
	}

	Handler mHandler = new Handler() {
		@SuppressWarnings("deprecation")
		public void handleMessage(Message msg) {
			mValue = msg.arg1;
			mText.setText(Integer.toString(mValue));
			if (mValue < 100) {
				mProgress.setProgress(mValue);
			} else {
				mQuit = true;
				dismissDialog(0);
			}
		}
	};

	class UpdateThread extends Thread {
		public void run() {
			while (mQuit == false) {
				mValue++;
				Message msg = mHandler.obtainMessage();
				msg.arg1 = mValue;
				mHandler.sendMessage(msg);
				try { Thread.sleep(50); } catch (InterruptedException e) {;}
			}
		}
	}
}

AsyncTask

백그라운드 작업을 하기 위해서는 스레드, 핸들러 등을 각각 만들어야 하고 작업 중에 핸들러를 주기적으로
호출해야 하는 번거로움이 있다.

이것을 간편하게 해주는 Helper 함수 AsyncTask이다.
AsyncTask는 내부적으로 작업 스레드를 생성하며 필요할 때마다 UI 스레드에서 실행되는 콜백 메서드를 호출한다.
콜백 메서드에서 정해진 작업만 처리하면 간단하게 백그라운드 작업을 수행할 수 있다.

AsyncTask자체는 추상 클래스이므로 파생 클래스를 생성하고 콜백 메서드를 구현해야 한다.

Generic parameters를 사용한다.

  • Params: 실행할 때 전달할 인수의 타입이다. 즉 배경 작업거리이다.
  • Progress: 매 작업 단계마다 진행 상태를 표기하는 타입이다.
  • Result: 작업의 결과로 리턴될 타입이다.

콜백 함수들은 아래와 같다.
doInBackground 메서드만 wroking thread에서 수행된다.
나머지 모든 메서드들은 Main UI 스레드에서 실행 된다.

  • void onPreExecute()
    • 작업이 시작되기 전에 호출되며 UI 스레드에서 실행 된다.
    • 계산을 위한 초기화나 프로그래스 대화상자를 준비하는 등의 작업을 수행한다.
  • Result doInBackground(Params... params)
    • 배경 작업을 수행하며 분리된 스레드에서 실행된다.
    • execute 메서드로 전달한 작업거리가 params 인수로 전달되는데 여러 개의 인수를 전달할 수 있으므로 배열이다.
    • 하나의 인수만 필요하다면 params[0]만 사용하면 된다.
    • 작업중에 publishProgress 메서드를 호출하여 작업 경과를 UI 스레드로 보고한다.
    • 최종적으로 작업된 결과를 Result 타입으로 리턴한다.
  • void onProgressUpdate(Progress... values)
    • doInBackground에서 publishProgress 메서드를 호출할 때 작업 경과 표시를 위해 호출되며 UI 스레드에서 실행된다. 프로그래스바에 진행 상태를 표시하는 역할을 한다.
  • void onPostExecute(Result result)
    • 백그라운드 작업이 끝난 후 UI 스레드에서 실행된다. 인수로 작업의 결과가 전달되는데 취소되었거나 예외가 발생했으면 null을 리턴 한다.
  • void onCancelled()
    • cancel 메서드로 작업을 취소했을 때 호출되며 UI 스레드에서 실행 된다.

아래의 메서드들은 만드시 UI 스레드에서 호출해야 하는 것들이다.

  • AsyncTask <Params, Progress, Result> execute (Params... params)
    • 인수로 작업거리에 해당하는 값을 넘겨주되 같은 타입의 인수 여러 개를 동시에 넘길 수 있다.
    • 이 호출에 의해 AsyncTask의 각 메서드가 순서대로 호출되어 배경 작업을 수행한다.
    • 스레드 내에서 적당한 때에 콜백 메서드를 호출하므로 UI 스레드에서 콜백 메서드를 직접 호출해서는 안 된다.
    • 리턴되는 AsyncTask 객체는 메인 스레드에서 참조 가능하며 다음 메서드로 작업을 관리한다.
  • boolean cancel (boolean mayIntteruptIfRunning)
  • boolean isCancelled()
    • 작업을 취소하라고 지시한다.
    • 작업 취소가 항상 성공적이지 않으며 실패할 수도 있는데 이미 완료되었거나 취소되었을 때 또는 기타의 이유로 취소할 수 없는 경우도 있다. 만약 작업을 아직 시작하기 전이라면 취소는 성공한 것으로 평가된다.
    • 인수는 작업을 실행중인 스레드를 중지할 것인가 지정한다.
    • isCancelled 메서드는 정상 종료되지 않고 취소되었는지 조사한다.
  • Result get ([long timeout, TimeUnit unit])
    • 작업이 완료되기까지 대기하며 작업 결과를 돌려 받는다.
    • 필요할 경우 대기할 타임아웃값을 지정한다.
  • AsyncTask.Status getStatus()
    • 작업의 현재 상태를 조사한다.
    • 아직 시작하지 않은 상태이면 PENDING이 리턴되며 이미 실행중이면 RUNNING, 작업이 완료되었으면 FINISHED가 리턴된다.

전체적인 메서드 실행 흐름은 아래와 같다.

AsyncTask의 작성 코드는 아래와 같다.

package andexam.ver6.c19_thread;

import andexam.ver6.*;
import andexam.ver6.c19_thread.LongTime4.*;
import android.app.*;
import android.content.*;
import android.os.*;
import android.view.*;
import android.widget.*;

public class LongTime5 extends Activity {
	int mValue;
	TextView mText;
	ProgressDialog mProgress;

	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.longtime);

		mText = (TextView)findViewById(R.id.text);
	}
	
	public void mOnClick(View v) {
		new AccumulateTask().execute(100);
	}

	class AccumulateTask extends AsyncTask<Integer, Integer, Integer> {
		@SuppressWarnings("deprecation")
		protected void onPreExecute() {
			mValue = 0;
			mProgress = new ProgressDialog(LongTime5.this);
			mProgress.setProgressStyle(ProgressDialog.STYLE_HORIZONTAL);
			mProgress.setTitle("Updating");
			mProgress.setMessage("Wait...");
			mProgress.setCancelable(false);
			mProgress.setProgress(0);
			mProgress.setButton("Cancel", new DialogInterface.OnClickListener() {
				public void onClick(DialogInterface dialog, int whichButton) {
					cancel(true);
				}
			});
			mProgress.show();
		}
		
		protected Integer doInBackground(Integer... arg0) {
			while (isCancelled() == false) { 
				mValue++;
				if (mValue <= 100) {
					publishProgress(mValue);
				} else {
					break;
				}
				try { Thread.sleep(50); } catch (InterruptedException e) {;}
			}
			return mValue;
		}
		
		protected void onProgressUpdate(Integer... progress) {		 
			mProgress.setProgress(progress[0]);	 
			mText.setText(Integer.toString(progress[0]));	 
		}
		
		protected void onPostExecute(Integer result) { 
			mProgress.dismiss();
		}
		
		protected void onCancelled() {
			mProgress.dismiss();
		}
	}
}

결국 실행 흐름과 코드를 가지고 이해해 보면,
메인 스레드와 작업 스레드를 알아서 안드로이드 시스템이 스위칭하면서 백그라운드 작업과 UI 갱신을 순서대로 실행하는 구조이다.

결국 기존 방식과 유사하되 각 단계에서 해당하는 부분이 AsyncTask의 콜백 메서드로 정형화되어 있다는 점만 다르다.
doInBackground메서드는 작업 스레드에 해당하며 onProgressUpdate는 핸들러에 해당하는 셈이다.
doInBackground내부에서 publishProgress를 실행함으로써 Progress Bar Update한다.

대화상자를 클래스 내부에서 Cancel버튼을 추가하여 생성 한다.

스레드와 핸들러를 직접 만들지 않아도 된다는 점에서 구조가 깔끔해 보이지만 약간 이해하는데 어려움이 있을 수도 있다.
전달 가능한 인수의 개수는 제한이 없지만 타입이 하나로 고정되어 범용성에 약간 제약이 있다.

하지만 많은 Open app code에서 해당 기능으로 구현을 많이 하므로 남의 코드를 이해하기 위해서는 익숙해질 필요가 있다.

참고문헌

안드로이드 정복 4판, 김상


'Computer Science > Android Application' 카테고리의 다른 글

Service  (0) 2017.08.16
Activity  (0) 2017.08.16
이벤트 (Event)  (0) 2017.08.04
Gradle  (0) 2016.06.03
Android Plot Libraries  (0) 2016.01.22

이벤트 (Event)


이벤트를 받아서 처리하는 각각의 방법들에 대해서 다룬다.

1. 콜백 메서드 재정의

가장 쉬운 방법으로 상속을 받아서 해당 callback함수를 재정의해서 사용하는 방식이다.

단점

  • 메서드 재정의하기 위해 반드시 슈퍼 클래스를 상속받아야 한다. MyButton등을 매번 만들어야 하는 번거로움이 있다.
  • 모든 이벤트에 대해서 콜백 메서드가 존재하는 것은 아니다.

Code

//* 1.핸들러 메소드 재정의 - 상속을 받아야만 재정의 가능하다.
public class HandleEvent extends Activity {
	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		View vw = new MyView(this);
		setContentView(vw);
	}

	class MyView extends View {
		public MyView(Context context) {
			super(context);
		}

		public boolean onTouchEvent(MotionEvent event) {
			super.onTouchEvent(event);
			if (event.getAction() == MotionEvent.ACTION_DOWN) {
				Toast.makeText(HandleEvent.this,"Touch Event Received",
						Toast.LENGTH_SHORT).show();
				return true;
			}
			return false;
		}
	}
}

2. 리스너 인터페이스 구현

3. 액티비티가 리스너 구현

4. 뷰가 리스너 구현

5. 익명 내부 클래스 사용

2번 째 방법에서 파생된 기법으로 리스너 하나를 위해 클래스를 일일이 선언하기 번거롭다는 점을 해결한 것이다.
TouchListenerClass onTouch 메서드 구현을 위한 것이며 오로지 TouchListener객체 하나만을 위해 선언한 것이다.
더 이상의 메서드를 추가할 필요도 없고 객체를 두 개 이상 만들 필요도 없다.

객체 지향 언어이다 보니 메서드가 홀로 존재할 수 없으며 클래스 안에 넣어야 하고 객체를 생성한 후 등록하는 번거러운 과정을 거쳐야 한다.
자바는 이런 경우를 위해 언어 차원에서 익명 내부 클래스라는 문법을 제공 한다.
상위 클래스나 인터페이스의 메서드 하나를 재정의하기 위해 클래스를 선언하는 경우, 그리고 그 클래스의 객체가 단하나만 필요한 경우는 굳이 클래스를 선언할 필요 없이 상속과 재정의를 동시에 할 수 있다.

익명 클래스의 구현 예

public class HandleEvent extends Activity {
	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		View vw = new View(this);
		vw.setOnTouchListener(TouchListener);
		setContentView(vw);
	}

	View.OnTouchListener TouchListener = new View.OnTouchListener() {
		public boolean onTouch(View v, MotionEvent event) {
			if (event.getAction() == MotionEvent.ACTION_DOWN) {
				Toast.makeText(HandleEvent.this,"Touch Event Received",
						Toast.LENGTH_SHORT).show();
				return true;
			}
			return false;
		}
	};
}

인터페이스의 인스턴스인 것 처럼 보이지만 실제로는 그렇지 않다.
인터페이스 자체는 구현이 없으므로 객체를 생성하지 못하기 때문이다.

익명 내부 클래스를 정의하는 문법을 간략하게 소개하면 다음과 같다.

# 축약된 코드
Interface obj = new Interface(){
	메서드 구현
};

6. 익명 내부 클래스의 임시 객체 사용

public class HandleEvent extends Activity {
	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		View vw = new View(this);
		vw.setOnTouchListener(new View.OnTouchListener() {
			public boolean onTouch(View v, MotionEvent event) {
				if (event.getAction() == MotionEvent.ACTION_DOWN) {
					Toast.makeText(HandleEvent.this,"Touch Event Received",
							Toast.LENGTH_SHORT).show();
					return true;
				}
				return false;
			}
		});
		setContentView(vw);
	}
}

5번과의 개념적 차이는 아래와 같다.

# 이름 있는 객체 사용
Class obj = new Class();
Method(obj);

# 임시 객체 사용
Method (new Class());

임시 객체를 사용하면 클래스 선언, 객체 생성문이 필요 없으므로 액티비티가 생성될 때인 onCreate에서 이벤트 등록 및 구현이 모두 가능하여 코드가 아주 짧아진다.

7. Java8에서의 Lambda를 이용한 방법

https://mayojava.github.io/android/java/using-java8-lambda-expressions-in-android/


'Computer Science > Android Application' 카테고리의 다른 글

Activity  (0) 2017.08.16
쓰레드 (Thread)  (0) 2017.08.04
Gradle  (0) 2016.06.03
Android Plot Libraries  (0) 2016.01.22
Android wear app  (0) 2015.08.25

Confusion Matrix in python


Tensorflow를 이용한 prediction 결과를 평가하기 위해서 Confusion Matrix을 이용한다.
단순 Accuracy에 대해서는 어느정도 문제가 발생하기 때문이다.
아래의 두 package를 각각 이용할 수도 있다.

scikit

scikit package를 이용한 방법이 존재한다.

특정 값만 표시해 줄 수도 있고 Confusion Matrix를 표현할 수도 있다.

# Import packages
from sklearn.metrics import classification_report
from sklearn.metrics import precision_score
from sklearn.metrics import recall_score

# Data
y_true = [1, 1, 0, 1, 0]
y_pred = [1, 1, 1, 0, 0]
target_names = ['false', 'true']
print(classification_report(y_true, y_pred, target_names=target_names))
precision_score(y_true, y_pred, average='binary',pos_label=1)
recall_score(y_true, y_pred, average='binary',pos_label=1)

실행 결과

	      precision    recall  f1-score   support

false       0.50      0.50      0.50         2
true       0.67      0.67      0.67         3

avg / total       0.60      0.60      0.60         5

precision: 0.66666666666666663
recall: 0.66666666666666663

Pandas

import pandas as pd

y_true = pd.Series([2, 0, 2, 2, 0, 1, 1, 2, 2, 0, 1, 2])
y_pred = pd.Series([0, 0, 2, 1, 0, 2, 1, 0, 2, 0, 2, 2])

pd.crosstab(y_true, y_pred, rownames=['True'], colnames=['Predicted'], margins=True)

Result

Predicted  0  1  2  All
True                   
0          3  0  0    3
1          0  1  2    3
2          2  1  3    6
All        5  2  5   12


String


Reverse

input = list("abcdefg")

mid = int(len(input)/2)
left = 0
right = len(input)-1

while left < right:
    input[left], input[right] = input[right], input[left]
    left += 1
    right -= 1

print(input)

Super Reduced String

  • pair string을 줄이는 작업을 수행 한다.
def super_reduced_string(S):
    LS = list(S)
    i = 0
    while i < len(LS)-1:
        if LS[i]==LS[i+1]:
            del LS[i]
            del LS[i]
            i = 0
            if len(LS) == 0:
                return 'Empty String'
        else:
            i+=1
    return ''.join(LS)

CamelCase

eBay, iPhone처럼 중간에 띄어쓰기 없이 대소문자로만 단어를 구분하는 것을 말한다.

이렇게 표시된 unique한 단어가 몇개인지 찾아서 출력 해야 한다.

#!/bin/python3

import sys
import string

s = input().strip()

sl = list(s)

i = 0
count = 1
while i < len(sl):
    if sl[i].isupper():
        count += 1
    i += 1

print(count)

한줄 코드

print(sum(map(str.isupper, input())) + 1)

Sliding Window

https://scipher.wordpress.com/2010/12/02/simple-sliding-window-iterator-in-python/

Two Characters

번갈아 가면서 두개의 서로다른 character를 배열 해야 한다.

  • (o) xyxyx or yxyxy
  • (x) xxyy or xyyx

들어온 입력에 대해서 가능한한 가장 긴 두개의 charater로만 생성 가능한 그리고 번갈아 가면서(alternating)으로 만들 수 있는 string을 반환하는게 목적이다.

불가능 하다면 0을 리턴 한다.

예제

10
beabeefeab

해설

  • If we delete e and f, the resulting string is babab. This is a valid as there are only two distinct characters (a and b), and they are alternating within the string.
  • If we delete a and f, the resulting string is bebeeeb. This is not a valid string because there are three consecutive e's present.
  • If we delete only e, the resulting string is babfab. This is not a valid string because it contains three distinct characters.
  • Thus, we print the length of babab, which is , as our answer.
import sys

def validate(inp):
    for i in range(len(inp)-1):
        if inp[i+1]==inp[i]:
            return False
    return True    
    

s_len = int(input().strip())
s = input().strip()

ans = 0
chtoindex = []
for ch in set(s):
    chtoindex.append((ch, len([j for j, x in enumerate(s) if x == ch])))
    

for i, pack in enumerate(chtoindex[:-1]):
    char_i, lenchar_i = pack[0], pack[1]
    for j, otherpack in enumerate(chtoindex[i+1:]):
        char_j, lenchar_j = otherpack[0], otherpack[1]
        if abs(lenchar_i-lenchar_j)<2:
            c = [cha for cha in s if cha is char_i or cha is char_j]
            if validate(c):
                ans = max(ans, lenchar_j+lenchar_i)
print(ans)

참고자료

문자열관련 Python 유용함수 모음 블로그


'Computer Science > Coding Interview' 카테고리의 다른 글

Sorting  (0) 2017.08.06
Graph Search  (0) 2017.08.06
HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31
Binary Search Tree  (0) 2017.07.31
HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30

HackerRank- Trees: Is This a Binary Search Tree


해당 트리가 이진 탐색 트리인지 확인 하는 문제이다.

단순히 특정 노드의 자식들 값이 부모보다 작은지 큰지를 가지고 판단할 경우 아래의 경우에 문제가 발생 한다.

이유는 4의 경우 root 보다 큰대도 불구하고 자식 노드의 자식으로 분류되어 있다.
즉, 더 윗 부분의 부모 노드에서 판단하는 부분이 제외 되기 때문에 문제가 발생 한다.

방법1

  • 재귀적으로 최소 최대 값을 확인하며 루프를 도는 방법
  • 일단 데이터에 음수가 없다는 가정에서 출발 한다.
def checkBST(root):
    return(check_in_order(root,[-1]))
    
def check_in_order(root,prev):
    result = True
    if root.left is not None:
        result &= check_in_order(root.left,prev)
    if prev[0] >= root.data:
        return False
    prev[0] = root.data
    if root.right is not None:
        result &= check_in_order(root.right,prev)
    return result

방법2

  • Inorder traversal을 해서 확인하는 방법.
  • 올바른 Binary Search라면 출력이 순차적이게 된다.
  • 해당 문제에서 보면 중독된 노드는 이진탐색트리로 허용하지 않으니 그 문제에 대한 해결을 필요로 한다.
""" Node is defined as
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
"""

def checkBST(root):
    # traversal by inOrder 
    resList = []
    resList = inOrder(root,resList)
    sortedList = sorted(resList)
    
    if len(set(resList)) != len(resList):
        return False
    
    if len([i for i, j in zip(resList, sortedList) if i == j]) == len(resList):
        return True
    else:
        return False
    
def inOrder(node,resList):
    if node.left is not None:
        resList = inOrder(node.left, resList)
    resList.append(node.data)
    if node.right is not None:
        resList = inOrder(node.right, resList)
    return resList


'Computer Science > Coding Interview' 카테고리의 다른 글

Graph Search  (0) 2017.08.06
String  (0) 2017.07.31
Binary Search Tree  (0) 2017.07.31
HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
Stacks: Balanced Brackets  (0) 2017.07.30

Binary Search Tree

Traverse 방식

pre order traverse (depth-first traverse라고도함.)

  • visit the root
  • traverse the left subtree
  • traverse the right subtree

사용처는 byte-stream으로 tree 정보를 다른 곳으로 전송 할 때 사용 한다.

in-order traverse (symmetric traverse)

  • visit left
  • visit parent
  • visit right

순차적으로 데이터를 출력 할 때 사용 한다.

post order traverse

  • visit left
  • visit right
  • visit root

노드를 지워야 할 때 사용한다.

구현 코드

생성한 트리의 모습은 아래와 같다.

class Node:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, value):
        if value <= self.data:
            if self.left is None:
                self.left = Node(value)
            else:
                self.left.insert(value)
        elif value > self.data:
            if self.right is None:
                self.right = Node(value)
            else:
                self.right.insert(value)
        else:
            self.data = value

    def inOrder(self):
        if self.left is not None:
            self.left.inOrder()
        print(self.data)
        if self.right is not None:
            self.right.inOrder()

    def preOrder(self):
        print(self.data)
        if self.left is not None:
            self.left.preOrder()
        if self.right is not None:
            self.right.preOrder()

    def postOrder(self):
        if self.left is not None:
            self.left.postOrder()
        if self.right is not None:
            self.right.postOrder()
        print(self.data)

if __name__ == "__main__":
    char = None
    root = Node(4)
    root.insert(3)
    root.insert(6)
    root.insert(2)
    root.insert(1)
    root.insert(5)
    root.insert(7)
    root.insert(8)

    print("inOrder traversal:")
    root.inOrder()
    print("preOrder traversal:")
    root.preOrder()
    print("PostOrder traversal:")
    root.postOrder()

참고문헌

한글로 설명된 깔끔한 블로그
설명 잘 되어 있는 외국 사이트


'Computer Science > Coding Interview' 카테고리의 다른 글

String  (0) 2017.07.31
HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31
HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30

HackerRank Queues: A Tale of Two Stacks


입력

  • q, 쿼리의 숫자
  • 쿼리 타입, 1만 뒤에 추가적인 값이 따라온다.

쿼리 타입

  • 1: x를 enqueue 한다.
  • 2: dequeue
  • 3: print 1개만

이 challenge에서는 반드시 queue를 두개의 stack을 이용해서 구현하라고 한다.
이게 front에서 팝이랑 삽입이 모두 이뤄져야 하기 때문에 통상의queue랑은 다르다.

List를 이용한 직접 작성한 Queue

class MyQueue(object):
    def __init__(self):
        self.q = [] 
        self.right = 0
        
    def peek(self):
        if self.q:
            return self.q[0]
        
    def pop(self):
        if self.q:
            self.q.pop()
            self.right -= 1
                
    def put(self, value):        
        self.q.insert(self.right,value)
        self.right += 1

새로운 queue

Class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        self.items.pop()

    def print_queue(self):
        print(self.items)

    def is_empty(self):
        return self.items == []

    def size(self):
        return len(self.items)

어려운 Test Case

10
1 76
1 33
2
1 23
1 97
1 21
3
3
1 74
3

정답

33
33
33

정답

class MyQueue(object):
    def __init__(self):
        self.old_to_new = []
        self.new_to_old = []
   
    def peek(self):
        if not self.new_to_old:
            while self.old_to_new:
                self.new_to_old.append(self.old_to_new.pop())
        val = self.new_to_old.pop()
        self.new_to_old.append(val)
        return val
       
    def pop(self):
        if not self.new_to_old:
            while self.old_to_new:
                self.new_to_old.append(self.old_to_new.pop())
        return self.new_to_old.pop()
       
    def put(self, value):
        self.old_to_new.append(value)


        
queue = MyQueue()
t = int(input())
for line in range(t):
    values = map(int, input().split())
    values = list(values)
    if values[0] == 1:
        queue.put(values[1])        
    elif values[0] == 2:
        queue.pop()
    else:
        print(queue.peek())


'Computer Science > Coding Interview' 카테고리의 다른 글

HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31
Binary Search Tree  (0) 2017.07.31
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30
HackerRank MergeSort Counting Inversions  (0) 2017.07.29

Stacks: Balanced Brackets


bracket은 (), {}, [] 이 세가지를 모두 포함한다.
이것을 매칭하는 문제이다.

구현코드

def is_matched(expression):
    stack = []
    for bracket in expression:
        if bracket in ['[', '{', "("]:
            stack.append(bracket)
        else:
            if stack:
                if bracket == ']':
                    leftBracket = stack.pop()
                    if leftBracket != '[':
                        return False
                elif bracket == '}':
                    leftBracket = stack.pop()
                    if leftBracket != '{':
                        return False
                elif bracket == ')':
                    leftBracket = stack.pop()
                    if leftBracket != '(':
                        return False
            else:
                return False
    return True

t = int(input().strip())
for a0 in range(t):
    expression = list(input().strip())
    if is_matched(expression) == True:
        print("YES")
    else:
        print("NO")

실행결과

# Input
3
{[()]}
{[(])}
{{[[(())]]}}

# Output
YES
NO
YES
  • 하지만 이 방법은 runtime issue를 발생 시킨다.

새로운 솔루션

def is_matched(expression):
    stack = []
    for bracket in expression:
        if bracket == '{':
            stack.append('}')
        elif bracket == '[':
            stack.append(']')
        elif bracket == '(':
            stack.append(')')
        else:
            if len(stack) == 0 or bracket != stack[-1]:
                return False
            stack.pop()
    return len(stack) == 0

t = int(input().strip())
for a0 in range(t):
    expression = input().strip()
    if is_matched(expression) == True:
        print("YES")
    else:
        print("NO")

Dictionary를 이용한 방법

Advantage

  • 다른 bracket을 필요로 하다면 쉽게 확장이 가능하다.
  • if-else 또는 switch case를 다중으로 작성할 필요가 없다.
  • O(1) call time을 가진다 (hash table이니 당연한 말이긴 하다).
def is_matched(expression):
    stack = []
    dicty = {'(':')', '[':']', '{':'}'}
    for x in expression:
        if x in dicty:
            stack.append(dicty[x])
        elif stack and x == stack[-1]:
            stack.pop()
        else:
            return False
            
    return not stack

t = int(input().strip())
for a0 in range(t):
    expression = input().strip()
    if is_matched(expression) == True:
        print("YES")
    else:
        print("NO")


'Computer Science > Coding Interview' 카테고리의 다른 글

Binary Search Tree  (0) 2017.07.31
HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30
HackerRank MergeSort Counting Inversions  (0) 2017.07.29
Binary Search  (0) 2017.07.28

HackerRank Data Structure


Stack

class Stack:
    def __init__(self):
        self.data = []

    # for print
    def __iter__(self):
        return self

    def __str__(self):
        values = [x for x in self]
        return ' -> '.join(values)

    def push(self, data):
        self.data.append(data)

    def pop(self):
        if len(self.data) is not 0:
            return self.data.pop()
        else:
            print("stack is empty")

    def print_stack(self):
        print(self.data)

if __name__ == "__main__":

    myStack = Stack()
    myStack.push(1)
    myStack.push(2)
    myStack.push(3)
    myStack.push(4)
    myStack.print_stack()

    print(myStack.pop())
    print(myStack.pop())

    myStack.print_stack()

실행 결과

[1, 2, 3, 4]
4
3
[1, 2]

Queue

class Queue:

    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        self.items.pop()

    def print_queue(self):
        print(self.items)

if __name__ == "__main__":
    queue = Queue()
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    queue.enqueue(4)
    queue.print_queue()
    queue.dequeue()
    queue.print_queue()

실행결과

[4, 3, 2, 1]
[4, 3, 2]

LinkedList

class Node(object):
    def __init__(self, data=None, next_node=None, prev_node=None):
        self.data = data
        self.next = next_node
        self.prev = prev_node

    def __str__(self):
        return str(self.data)

class LinkedList:
    def __init__(self, data=None):
        self.head = None
        self.tail = None
        if data is not None:
            self.insert(data)

    # for print
    def __iter__(self):
        current = self.head
        while current:
            yield current
            current = current.next

    def __str__(self):
        values = [str(x) for x in self]
        return ' -> '.join(values)

    def __len__(self):
        result = 0
        node = self.head
        while node:
            result += 1
            node = node.next
        return result

    def insert(self, data):
        if self.head is None:
            self.tail = self.head = Node(data)
        else:
            self.tail.next = Node(data)
            self.tail = self.tail.next
        return self.tail

    def delete(self, data):
        if self.head is None:
            print("It is empty!")
            return
        elif self.head.data is data:
            self.head = self.head.next
        else:
            current = self.head
            while current.next is not None:
                if current.data is data:
                    print("Delete the number: %d"%(data))
                    current.data = current.next.data
                    current.next = current.next.next
                    return
                current = current.next
            print("It is not founded")


if __name__ == "__main__":
    ll = LinkedList()
    ll.insert(1)
    ll.insert(2)
    ll.insert(3)
    ll.insert(4)
    ll.insert(5)
    print(ll)
    ll.delete(3)
    ll.delete(6)
    print(ll)

실행 결과

1 -> 2 -> 3 -> 4 -> 5
Delete the number: 3
It is not founded
1 -> 2 -> 4 -> 5


'Computer Science > Coding Interview' 카테고리의 다른 글

HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank MergeSort Counting Inversions  (0) 2017.07.29
Binary Search  (0) 2017.07.28
HackerRank: Basic Problems  (0) 2017.07.25

HackerRank MergeSort Counting Inversions


스왑의 횟수를 찾아내는 것이다.

Input

  • 횟수
  • 숫자 리스트 길이
  • 실제 숫자 리스트 (공백으로 구분)

Bubble Sort 솔루션

속도 문제로 Timeout문제를 발생 시킴

def count_inversions(n,a,numSwap=0):
    cumulatedNumSwap = 0
    for i in range(0,n):
        numSwap = 0
        for j in range(0,n-1):
            if a[j] > a[j+1]:
                temp = a[j]
                a[j] = a[j+1]
                a[j+1] = temp
                numSwap += 1
        cumulatedNumSwap += numSwap
        if numSwap == 0:
            break
    return cumulatedNumSwap


t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())
    arr = list(map(int, input().strip().split(' ')))
    numSwap = 0
    numSwap = count_inversions(n,arr,numSwap)
    print(numSwap)
    

출력결과

#input
2
5
1 1 1 2 2
5
2 1 3 1 2

#output
0
4

MergeSort 솔루션

  • MergeSort 자체는 문제가 아니다.
  • Count를 할 때 count += mid - i + 1;이렇게 해야 한다는 점이 가장 어려운 부분이다.
  • 과도하게 문제가 꼬여 있다.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    
public static long countInversions(int[] arr){
        
        return mergeSort(arr, 0, arr.length - 1);
    }
    
    public static long mergeSort(int[] arr, int start, int end){
        if(start == end)
            return 0;
        int mid = (start + end) / 2;
        long count = 0;
        count += mergeSort(arr, start, mid); //left inversions
        count += mergeSort(arr, mid + 1, end);//right inversions
        count += merge(arr, start, end); // split inversions.
        return count;
    }
    
    public static long merge(int[] arr, int start, int end){
        int mid = (start + end) / 2;
        int[] newArr = new int[end - start + 1];
        int curr = 0;
        int i = start;
        int j = mid + 1;
        long count = 0;
        while(i <= mid && j <=end) {
            if(arr[i] > arr[j]) {
                newArr[curr++] = arr[j++];
                count += mid - i + 1; // Tricky part.
            }
            else
                newArr[curr++] = arr[i++];          
        }
         // Leftover elements here.
        while(i <= mid) {
            newArr[curr++] = arr[i++];    
        }
        
        while(j <= end) {
            newArr[curr++] = arr[j++];
        }
     
        System.arraycopy(newArr, 0, arr, start, end - start + 1); // Usual stuff from merge sort algorithm with arrays.
        return count;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            int n = in.nextInt();
            int arr[] = new int[n];
            for(int arr_i=0; arr_i < n; arr_i++){
                arr[arr_i] = in.nextInt();
            }
            System.out.println(countInversions(arr));
        }
    }
}


'Computer Science > Coding Interview' 카테고리의 다른 글

HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30
Binary Search  (0) 2017.07.28
HackerRank: Basic Problems  (0) 2017.07.25

Binary Search


input = [1,2,3,4,5,6,7,8,9,10]

target = 1
index = 0

min = 0
max = len(input) -1
mid = int(len(input)/2)

step = 1
while (target != input[mid]):
    if input[mid] < target:
        min = mid +1
    else:
        max = mid -1

    mid = int((max+min)/2)
    step +=1

print("target index: %d, steps: %d"%(mid, step))

Points

  • length -1
  • min은 +1
  • max는 -1
    +를 안할 경우 mid값이 변동이 없어서 마지막 위치에 있는 target 값을 못찾는다.
    -를 안할 경우 왼쪽에 있는 값을 step 3번에 찾을 수 있는 것을 4번에 찾는다. int() 때문에 버림이 적용되우 int가 축소 되기 때문에 -를 안해도 지장이 별로 없는 것 같다.


'Computer Science > Coding Interview' 카테고리의 다른 글

HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30
HackerRank MergeSort Counting Inversions  (0) 2017.07.29
HackerRank: Basic Problems  (0) 2017.07.25

HackerRank: Basic Problems


Solution Type

  • Approximate solution
    하나의 정답만 있지 않은 문제를 말한다.
    예를 들면, Image processing이나 computer vision이 이쪽 문제에 해당 한다.

1. Array: Left Rotation

def array_left_rotation_ext(a, n, k):
    for i in range(0,k):
        # change array
        temp = a [0]
        for j in range(0,n):
            if j+1 != n:
                a[j] = a[j+1]
        a[n-1] = temp
    return a
        
def array_left_rotation(a, n, k):
    return a[k:] + a[:k]
    

n, k = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
answer = array_left_rotation(a, n, k);
print(*answer, sep=' ')

첫 번째 함수는 시간이 너무 오래 걸려서 time-out 걸린다.

2. Strings: Making Anagrams

import string


def number_needed(a, b):
    for char in list(string.ascii_lowercase):
        al.append(a.count(char))
        bl.append(b.count(char))
    return sum(abs(x-y) for (x, y) in zip(al, bl))

a = input().strip()
b = input().strip()

al = []
bl = []

print(number_needed(a, b))

Input (stdin)

cde
abc

Your Output (stdout)

4

Expected Output

4

3. Hash Tables: Ransom Note

def ransom_note(magazine, ransom):
    d = {}
    for word in magazine:
        d.setdefault(word, 0)
        d[word] += 1
    
    for word in ransom:
        if word in d:
            d[word] -= 1
        else:
            return False
    return all([x >= 0 for x in d.values()])    

m, n = map(int, input().strip().split(' '))
magazine = input().strip().split(' ')
ransom = input().strip().split(' ')
answer = ransom_note(magazine, ransom)
if(answer):
    print("Yes")
else:
    print("No")

실행결과

6 4
give me one grand today night
give one grand today

Yes
6 5
two times three is not four
two times two is four

No

4. Linked Lists: Detect a Cycle

head point

cycle = true
no cycle = false

"""
Detect a cycle in a linked list. Note that the head pointer may be 'None' if the list is empty.

A Node is defined as: 
 
    class Node(object):
        def __init__(self, data = None, next_node = None):
            self.data = data
            self.next = next_node
"""
def has_cycle(head):
    i = 0
    if head.next == None:
        return False
    
    prev_head = head.next
    next_head = head.next
    
    while next_head != None:
        if i > 100 :
            return True      
        next_head = prev_head.next
        prev_head = next_head
        i += 1
    return False

실행 결과

0
1

5. Sorting: Bubble Sort

n = int(input().strip())
a = list(map(int, input().strip().split(' ')))

cumulatedNumSwap = 0

for i in range(0,n):
    numSwap = 0
    for j in range(0,n-1):
        if a[j] > a[j+1]:
            temp = a[j]
            a[j] = a[j+1]
            a[j+1] = temp
            numSwap += 1
    cumulatedNumSwap += numSwap
    if numSwap == 0:
        break

print("Array is sorted in %d swaps."%cumulatedNumSwap)
print("First Element: %d"%a[0])
print("Last Element: %d"%a[n-1])

In

3
3 2 1

Out

Array is sorted in 3 swaps.
First Element: 1
Last Element: 3

6. Sorting: Comparator

입력값

n // 플레이어 숫자
줄 바꾸고
공백을 두고 플레이어의 이름과 스코어

from functools import cmp_to_key

def cmp_to_key(key):
    return key

class Player:
    def __init__(self, name, score):
        self.name = name
        self.score = score
        
    def comparator(self):
        return(-self.score, self.name)

#--- reference code
n = int(input())
data = []
for i in range(n):
    name, score = input().split()
    score = int(score)
    player = Player(name, score)
    data.append(player)
    
data = sorted(data, key=cmp_to_key(Player.comparator))
for i in data:
    print(i.name, i.score)

input

5
amy 100
david 100
heraldo 50
aakansha 75
aleksa 150

output

aleksa 150
amy 100
david 100
aakansha 75
heraldo 50

7. oddNumbers (smaple test)

l과 r 사이의 숫자에서 odd number만 구해서 list로 반환

# Complete the function below.

def  oddNumbers(l, r):
    oddNumbers=[]
    i = l
    if l % 2 != 0:
        while (i <= r):
            oddNumbers.append(i)
            i+=2
    else:
        i +=1
        while (i<=r):
            oddNumbers.append(i)
            i+=2
    return oddNumbers

실행 결과

3,9
3, 5, 7, 9

8. find number (sample test)

# Complete the function below.

def  findNumber(arr, k):
    for i in arr:
        if i == int(k):
            return "YES"
        else :
            return "NO"

속도 문제가 Fail난다.

def  findNumber(arr, k):
    if k in arr :
        return "YES"
    else :
        return "NO"

속도 문제가 없다.

9. Recursion: Fibonacci Numbers

$$fibonacci(0)=0$$
$$fibonacci(1)=1$$
$$fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)$$

간단한 구현 (단, timeout 걸림)

def fibonacci(n):
    # Write your code here.
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
    
n = int(input())
print(fibonacci(n))

memory 방식: python dictionary 자료구조를 이용해서 처리한다.

memory = {}
def fibonacci(n):
    if n < 2:
        return n
    if not n in memory.keys():
        memory[n] = fibonacci(n-1) + fibonacci(n-2)
    return memory[n]
    
n = int(input())
print(fibonacci(n))

one line lambda code

fibonacci = lambda n:pow(2<<n,n+1,(4<<2*n)-(2<<n)-1)%(2<<n)

10. Bit Manipulation: Lonely Integer

하나만 Unique하게 나타나고 나머진 모두 2번 나타나게 된다.

#!/bin/python3

import sys

def lonely_integer(a):
    uniqueList = [0 for i in range(101)]
    for number in a:
        uniqueList[number] += 1
    
    return uniqueList.index(1)

n = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split(' ')]
print(lonely_integer(a))

시간 복잡도 O(3n)
공간 복잡도 O(n)

실행결과

# in
1
1
# out
1

# in
9
4 9 95 93 57 4 57 93 9
# out 
95

좀 더 좋은 방법

XOR개념을 이용해서 중복되면 0가 되는 특성을 활용한다.
시간복잡도 O(n)
공간복잡도 O(1)

def lonely_integer(a):
    result = 0
    for i in a:
        result ^= i
    return result

11. Binary Search: Ice Cream Parlor

아이스크림을 사먹는 문제이다.

  • t는 여행 횟수를 의미한다.
    그다음 가각에 대해서 인자가 3개이다.
  • n
  • 각각의 맛에 대한 가격, i 번째가 가격을 의미한다.
t = int(input().strip())
for a0 in range(t):
    m = int(input().strip())
    n = int(input().strip())
    a = list(map(int, input().strip().split(' ')))
 
    # effective cost
    costList = {}
    for i, cost in enumerate(a):
        firUser = cost
        secUser = m - cost
        if secUser in costList.keys():
            print(costList[secUser]+1,i+1)
        else:
            costList[cost] = i

output

# input
2
4
5
1 4 5 3 2
4
4
2 2 4 3


# output
1 4
1 2

해당 문제는 딱히 Binary Search를 사용할 필요가 없다. 그냥 Hash로 사용할 경우 O(n)에 복잡도로 처리가 가능하다.
그저 과거의 cost에 각각의 index를 추가하고 그것에 현재 cost 차액만큼 값이 있는지 확인하면 된다.
ID도 점점 커지므로 딱히 순서를 고려할 필요도 없다.

참고자료
TwoSum


'Computer Science > Coding Interview' 카테고리의 다른 글

HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30
HackerRank MergeSort Counting Inversions  (0) 2017.07.29
Binary Search  (0) 2017.07.28

Handling Class Imbalance with R


실제 데이터에 머신러닝을 적용하려고 하다보면 한 쪽의 class가 과도하게 큰 문제인 class imbalance 문제에 직면하게 된다.

Method to improve performance on imbalanced data

  • Class weights: impose a heavier cost when errors are made in the minority class

  • Down-sampling: randomly remove instances in the majority class

  • Up-sampling: randomly replicate instances in the minority class

  • Synthetic minority sampling technique (SMOTE): down samples the majority class and synthesizes new minority instances by interpolating between existing ones

SMOTE를 그림으로 설명하면 아래와 같다.

Imbalanced Classification in R

class imbalance 문제를 해결할 수 있는방법은 ROSE DMwR 페키지를 사용하는 것이다.
여기서 사용하는 예제는 Binary Classification문제를 다룬다.

  • ROSE: Random over smapling examples packages 이다. 이것은 artifical data를 샘플링 방법에 기반해서 생성 하게 된다.
install.packages("ROSE")
library(ROSE)

내부적으로 ROSE 페키지는 imbalanced data의 하나인 hacide.train hacide.test를 보유하고 있다.

SMOTE 방법

oversampling 방법은 너무 중복된 값이 많이 생성되고 undersampling은 중요한 데이터를 너무 많이 잃어 버린다.
ROSE는 이러한 문제를 해결 한다.

구현 코드

library(ROSE)

data(hacide) # imbalanced data
str(hacide.train)
str(hacide.test)


# check table
table(hacide.train$cls)
table(hacide.test$cls)

# check classes distribution
prop.table(table(hacide.train$cls))
prop.table(table(hacide.test$cls))


# only 2% of data is positive. 
# it is a severely imbalanced data set.

library(rpart)
treeimb <- rpart(cls ~ ., data = hacide.train)
pred.treeimb <- predict(treeimb, newdata = hacide.test)

# check model accuracy 
accuracy.meas(hacide.test$cls, pred.treeimb[,2])
roc.curve(hacide.test$cls, pred.treeimb[,2], plotit = F)


# over sampling
data_balanced_over <- ovun.sample(cls~., data = hacide.train, method = "over", N=1960)$data
# N refers to number of observations in the resulting balanced set.

table(data_balanced_over$cls)

# under sampling
data_balanced_under <- ovun.sample(cls~., data = hacide.train, method = "under", N=40)$data

# under and over smapling (both)
# the minority class is oversampled with replacement and majority class is undersampled without replacement
data_balanced_both <- ovun.sample(cls ~ ., data = hacide.train, method = "both", p=0.5, N=1000, seed = 1)$data
table(data_balanced_both$cls)

data.rose <- ROSE(cls ~ ., data = hacide.train, seed = 1)$data
table(data.rose$cls)


#build decision tree models
tree.rose <- rpart(cls ~ ., data = data.rose)
tree.over <- rpart(cls ~ ., data = data_balanced_over)
tree.under <- rpart(cls ~ ., data = data_balanced_under)
tree.both <- rpart(cls ~ ., data = data_balanced_both)

#make predictions on unseen data
pred.tree.rose <- predict(tree.rose, newdata = hacide.test)
pred.tree.over <- predict(tree.over, newdata = hacide.test)
pred.tree.under <- predict(tree.under, newdata = hacide.test)
pred.tree.both <- predict(tree.both, newdata = hacide.test)

#AUC ROSE
roc.curve(hacide.test$cls, pred.tree.rose[,2])

#AUC Oversampling
roc.curve(hacide.test$cls, pred.tree.over[,2])

#AUC Undersampling
roc.curve(hacide.test$cls, pred.tree.under[,2])

#AUC Both
roc.curve(hacide.test$cls, pred.tree.both[,2])

실행결과

> roc.curve(hacide.test$cls, pred.tree.rose[,2])
Area under the curve (AUC): 0.989
> roc.curve(hacide.test$cls, pred.tree.over[,2], add.roc=TRUE)
Area under the curve (AUC): 0.798
> roc.curve(hacide.test$cls, pred.tree.under[,2], add.roc=TRUE)
Area under the curve (AUC): 0.876
> roc.curve(hacide.test$cls, pred.tree.both[,2], add.roc=TRUE)
Area under the curve (AUC): 0.798

결론적으로 SMOTE방법을 구현한 ROSE package를 이용한 방법이 가장 정확도가 높게 나온다.

참고문헌

[1] Wicked Good Data
[2] Silicon Valley Data Science blog post

[3] SMOTE Implementation in Python
[4] https://www.analyticsvidhya.com/blog/2016/03/practical-guide-deal-imbalanced-classification-problems/

[5] http://machinelearningmastery.com/tactics-to-combat-imbalanced-classes-in-your-machine-learning-dataset/


'AI > Machine Learning with R' 카테고리의 다른 글

Feature Selection with Caret (Auto)  (0) 2016.11.20
Caret의 이해  (0) 2016.03.06
Cross Validation  (0) 2016.02.26
Ensemble method: Bagging (bootstrap aggregating)  (0) 2015.11.19
Bootstrapping  (0) 2015.11.19

Week 10: Online Learning


Online Learning을 사용하는 경우는 아래와 같다.

  • 연산량이 너무 많을 때
  • 데이터가 스트리밍 이여서 새로운 데이터 대해서 계속 해서 학습 해야할 때 또는 데이터가 사용자에 의해서 계속 생성 될 때

알고리즘

Repeat forever {
Get (x,y) corresponding to a user.
update $\theta$ using (x,y)
$\theta_{j}$ := $\theta_j$ -\alpha ($h_{\theta}$(x)-y)$x_j$ (j=0,...,n)
}

결국 fixed training데이터를 사용하지 않게 된다.
또한 한번 training에 사용 했던 데이터는 다시 쓰지 않는다.

p(y = 1|x; θ)
Probability that y =1, given x, parameterized by θ

사용 예

  • shipping service를 사용자가 선택 할지 안할지에 대한 정보를 웹사이트 데이터로 구축해서 누적 한다.
  • product search를 할 때 사용자가 선택한 옵션에 맞추어서 가장 인기있는 phone 10개를 보여주고 그것에대한 선호도를 선택하게 한다. 이러한 결과는 즉시 다시 학습에 사용 될 수 있다.

Quiz


Tensorflow Object Detection API (SSD, Faster-R-CNN)


2017.6.15에 Google에서 Tensorflow로 구현된Object Detection코드를 공개 했다. 말은 API라고 적혀 있지만 그냥 구현 코드이다. 지원하는 모델은 아래와 같다.

  • Single Shot Multibox Detector (SSD) with MobileNet
  • SSD with Inception V2
  • Region-Based Fully Convolutional Networks (R-FCN) with ResNet 101
  • Faster R-CNN with Resnet 101
  • Faster RCNN with Inception Resnet v2

설치 및 테스팅

일단 TF관련 예제를 구글이 만들어 놓은곳은 모두 modelsgithub에 있다.

git clone https://github.com/tensorflow/models.git

클론한 다음 object detection으로 들어간 다음Jupyter Notebook으로object_detection_tutorial.ipynb을 실행 한다.

코드를 정상적으로 실행 하기 위해선 아래의 작업을 수행해 줘야 한다.

dependencies

  • Protobuf 2.6
  • Pillow 1.0
  • lxml
  • tf Slim (which is included in the "tensorflow/models" checkout)
  • Jupyter notebook
  • Matplotlib
  • Tensorflow

Ubuntu 16.04 기준

sudo apt-get install protobuf-compiler python-pil python-lxml
sudo pip install jupyter
sudo pip install matplotlib

sudo pip install pillow
sudo pip install lxml
sudo pip install jupyter
sudo pip install matplotlib

Protobuf 컴파일

clone한 models에서 실행 한다.

# From tensorflow/models/
protoc object_detection/protos/*.proto --python_out=.

실행하면 아래와 같이 python코드들이 생성된다.

jemin@jemin-desktop:~/tf_examples/models/object_detection/protos$ ls
BUILD                         losses_pb2.py
__init__.py                   matcher.proto
__pycache__                   matcher_pb2.py
anchor_generator.proto        mean_stddev_box_coder.proto
anchor_generator_pb2.py       mean_stddev_box_coder_pb2.py
argmax_matcher.proto          model.proto
argmax_matcher_pb2.py         model_pb2.py
bipartite_matcher.proto       optimizer.proto
bipartite_matcher_pb2.py      optimizer_pb2.py
box_coder.proto               pipeline.proto
box_coder_pb2.py              pipeline_pb2.py
box_predictor.proto           post_processing.proto
box_predictor_pb2.py          post_processing_pb2.py
eval.proto                    preprocessor.proto
eval_pb2.py                   preprocessor_pb2.py
faster_rcnn.proto             region_similarity_calculator.proto
faster_rcnn_box_coder.proto   region_similarity_calculator_pb2.py
faster_rcnn_box_coder_pb2.py  square_box_coder.proto
faster_rcnn_pb2.py            square_box_coder_pb2.py
grid_anchor_generator.proto   ssd.proto
grid_anchor_generator_pb2.py  ssd_anchor_generator.proto
hyperparams.proto             ssd_anchor_generator_pb2.py
hyperparams_pb2.py            ssd_pb2.py
image_resizer.proto           string_int_label_map.proto
image_resizer_pb2.py          string_int_label_map_pb2.py
input_reader.proto            train.proto
input_reader_pb2.py           train_pb2.py
losses.proto

Add Libraries to PYTHONPATH

slim 디렉터리를 append시키기 위함이다.

# From tensorflow/models/
export PYTHONPATH=$PYTHONPATH:`pwd`:`pwd`/slim

Testing the Installation
최종적으로 설치가 정상적으로 되었는지 아래의 명령어로 확인한다.

python object_detection/builders/model_builder_test.py

.......
----------------------------------------------------------------------
Ran 7 tests in 0.013s

OK

기타

  • Tensorflow 1.2.1 버전
  • Jupyter 5.4.0
  • Python 3.5.2

Troubleshooting

  • Load a Tensorflow model into memory 부분에서 에러가 발생하면 python3으로 커널을 변경하면 해결 된다.

실행 결과

COCO 이미지 두개를 불러와서 바운딩 박스를 치면 아래와 같다.

with detection_graph.as_default():
  with tf.Session(graph=detection_graph) as sess:
    for image_path in TEST_IMAGE_PATHS:
      image = Image.open(image_path)
      # the array based representation of the image will be used later in order to prepare the
      # result image with boxes and labels on it.
      image_np = load_image_into_numpy_array(image)
      # Expand dimensions since the model expects images to have shape: [1, None, None, 3]
      image_np_expanded = np.expand_dims(image_np, axis=0)
      image_tensor = detection_graph.get_tensor_by_name('image_tensor:0')
      # Each box represents a part of the image where a particular object was detected.
      boxes = detection_graph.get_tensor_by_name('detection_boxes:0')
      # Each score represent how level of confidence for each of the objects.
      # Score is shown on the result image, together with the class label.
      scores = detection_graph.get_tensor_by_name('detection_scores:0')
      classes = detection_graph.get_tensor_by_name('detection_classes:0')
      num_detections = detection_graph.get_tensor_by_name('num_detections:0')
      # Actual detection.
      (boxes, scores, classes, num_detections) = sess.run(
          [boxes, scores, classes, num_detections],
          feed_dict={image_tensor: image_np_expanded})
      # Visualization of the results of a detection.
      vis_util.visualize_boxes_and_labels_on_image_array(
          image_np,
          np.squeeze(boxes),
          np.squeeze(classes).astype(np.int32),
          np.squeeze(scores),
          category_index,
          use_normalized_coordinates=True,
          line_thickness=8)
      plt.figure(figsize=IMAGE_SIZE)
      plt.imshow(image_np)


Convolutional Neural Network for CIFAR-10


CIFAR-10은 RGB 32x32짜리 이미지이다.
이미지 카테고리는 아래와 같다. 10개여서 CIFAR-10인것이다.

airplane, automobile, bird, cat, deer, dog, frog, horse, ship, truck.

공식 사이트는 다음과 같다.
CIFAR-10 dataset

큰 이미지로 바로 테스트 하기 어렵기 때문에 일단 작은 이미지로 modeling을하고 테스팅을 해본다.

Higlights of the Tutorial

핵심 기술은 모두 AlexNet paper에 나온 것들이다.

  • convolution
  • rectified linear activations
  • max pooling
  • local response normalization

Model Architecture

기본적으로 Alex Krizhevsky의 모델을 따르며 위에 계층만 약간 튜닝한 형태를 가진다.

몇시간 동안 트레이닝을 했을 때의 최대 정확도는 86%이다.

코드의 구성

  • cifar10_input.py Reads the native CIFAR-10 binary file format.
  • cifar10.py Builds the CIFAR-10 model.
  • cifar10_train.py Trains a CIFAR-10 model on a CPU or GPU.
  • cifar10_multi_gpu_train.py Trains a CIFAR-10 model on multiple GPUs.
  • cifar10_eval.py Evaluates the predictive performance of a CIFAR-10 model.

Model Training

Prediction을 위해서 n-way classification을 수행 한다.
multinomial logistic regression 또는 softmax regression으로 알려져 있다.

  • batch size는 128로 수행
  • learning rate $10^5$

Launching and Training the Model

아래의 명령어로 실행 한다.

python3 cifar10_train.py

맨 처음에는 이미지 데이터가 없기 때문에 다운로드 부터 시작한다. 데이터 셋은 약 160MB이다.

모델링은 약 몇시간 걸린다.

레퍼런스 성능은 아래와 같다.

System        | Step Time (sec/batch)  |     Accuracy
------------------------------------------------------------------
1 Tesla K20m  | 0.35-0.60              | ~86% at 60K steps  (5 hours)
1 Tesla K40m  | 0.25-0.35              | ~86% at 100K steps (4 hours)

default가 1000k steps니 왠만하면 값을 주고 training하는것이 좋다.
GTX 1080 기준으로 1 step당 0.05인것 같다.

2017-03-03 17:26:35.188576: step 353720, loss = 0.16 (2436.1 examples/sec; 0.053 sec/batch)
2017-03-03 17:26:35.725523: step 353730, loss = 0.14 (2291.4 examples/sec; 0.056 sec/batch)
2017-03-03 17:26:36.253775: step 353740, loss = 0.18 (2391.7 examples/sec; 0.054 sec/batch)
2017-03-03 17:26:36.781440: step 353750, loss = 0.15 (2413.0 examples/sec; 0.053 sec/batch)
2017-03-03 17:26:37.313428: step 353760, loss = 0.15 (2395.6 examples/sec; 0.053 sec/batch)

결국 128 batch size로 1 step당 0.05초 정도 소요된다.

Evaluating a Model

Testing을 위해서 10,000장의 의미지를 사용 한다.

python cifar10_eval.py

레퍼런스 기준으로 precision 1 = 0.860이라고 한다.

jemin@jemin-desktop:~/tf_examples/models/tutorials/image/cifar10$ python3 cifar10_eval.py
2017-05-18 14:15:00.822222: I tensorflow/core/common_runtime/gpu/gpu_device.cc:887] Found device 0 with pro                           perties:
name: GeForce GTX 1080
major: 6 minor: 1 memoryClockRate (GHz) 1.797
pciBusID 0000:01:00.0
Total memory: 7.92GiB
Free memory: 7.66GiB
2017-05-18 14:15:00.822247: I tensorflow/core/common_runtime/gpu/gpu_device.cc:908] DMA: 0
2017-05-18 14:15:00.822253: I tensorflow/core/common_runtime/gpu/gpu_device.cc:918] 0:   Y
2017-05-18 14:15:00.822258: I tensorflow/core/common_runtime/gpu/gpu_device.cc:977] Creating TensorFlow dev                           ice (/gpu:0) -> (device: 0, name: GeForce GTX 1080, pci bus id: 0000:01:00.0)
2017-05-18 14:15:02.951141: precision @ 1 = 0.866

참고 문헌

Tensorflow tutorial, convolutional neural networks
CNN
Convolutional Neural Networks


가산 명사(단수)

  • every 모든
  • either 어느 한쪽에
  • neither 어느 ~도 ~않다.

단, every와 another는 특정하 숫자와 함께 오면 복수 명사 앞에 올 수 있다.

  • every 2 weeks
  • another 3 years


가산명사(복수) 

  • one of ~중 하나
  • each of ~의 각각
  • both 둘 다의
  • numerous 많은
  • various 다양한
  • a variety of 다양한 ~ 복수 동사
  • several 몇몇의
  • a couple of 몇몇의
  • a number of 많은
  • few 거의 없는
  • fewer 더 적은
  • a few 적은


불가산 명사 앞

  • little 거의 없는
  • a little 적은
  • less 더 적은
  • much 많은
  • a great deal of 많은
  • a large amount of 많은


모든 명사 앞

  • no 어떤 ~ 도 아니다
  • all
  • more 더 많은
  • most 대부분의 (형용사)
  • some 몇몇의, 어떤
  • any 어떤
  • lots of 많은 ~
  • a lot of 많은
  • plenty of 많은
  • other 다른


한정사의 사용


가산/불가산 모두 다 다되더라도 뒤의 명상의 형태는 가산이면 복수 불가산이면 단수이다. 

한정사가 복수를 의미하는지 잘 봐야 한다.


  • All students are
  • All information is



한정사의 지시대명사/ 지시형용사 용법


위의 수량의 표현 한정사들은 대명사로도 쓰인다. 

단, every, other는 안된다.

  • All of the students = All the students / All students
  • Some of the students = some students


핵심은 of the를 항상 같이 써줘야 한다.

그리고 다시 한정사로 돌아갈 때 보통은 the를 빼지만

All과 both는 문장의 의미에 따라 the를 붙이기도 한다.




Almost (거의 ~한)의 올바른 사용

  • Almost Americans like pizza (x)
  • Almost all Americans like pizza (o)
  • Most Americans like pizza (o)
  • [격식] The majority of Americans like pizza. (o)



'영어 > 영문법' 카테고리의 다른 글

as + p.p (~한 대로, ~한 대로인)  (0) 2017.01.18
end up with ~  (0) 2017.01.14
It turns out  (0) 2017.01.14
Difference between Occur and Incur  (0) 2016.12.23
not only but also 와 as well as 사용법 및 차이점  (2) 2016.06.19

rJava load 에러



JDK를 업데이트 하면 발생한다.


JAVA_HOME 환경변수를 다시 설정해 준다.


cmd에서 확인 방법


echo %JAVA_HOME%


환경변수가 잘 변경 되었는지 위 방법을 통해서 알 수 있다. 

'AI > R Basic' 카테고리의 다른 글

R Factor 검색  (0) 2017.11.13
RStudio v1.1 Released  (0) 2017.10.10
Swapping columns in a matrix  (0) 2017.03.31
R Notebook  (0) 2016.11.02
R Markdown  (0) 2016.11.02

Swapping columns in a matrix


그냥 간단하게 column을 swapping한다면

m[, c(1,2)] <- m[,c(2,1)]

하지만 위에 처럼 하게 되면 column의 이름이 swap되지 않는다.

아래와 같이 수행해야 column 이름까지 모두 함께 변경 된다.

m <- m[, c(2, 1, 3:ncol(m))]


'AI > R Basic' 카테고리의 다른 글

RStudio v1.1 Released  (0) 2017.10.10
rJava load 에러  (0) 2017.04.16
R Notebook  (0) 2016.11.02
R Markdown  (0) 2016.11.02
Data를 그룹별로 요약 (Summarizing data)  (0) 2016.10.27

2017 H-1B Visa petition


H-1B Visa petition 시즌이 4월 3일 시작 된다.


기술 숙련자라면 미국에서 일하기 위한 통로로 가장 사랑하는 루트가 바로 H-1B 비자이다.


2016 작년에만 그것은 85,000+이상의 비자 신청이 당도 했다. 그리고 최종적으로 236,000 petition이 제출 되었다.


일단 $1,225 수수료를 내면 premium processing으로써 H-1B petition이 15일 안에 심사 된다. 만약 lottery에서 선택 된다면 말이다.

그래서 이러한 premium processing의 비율은 59%에 달한다.


non-premium visa petition은 8개월이나 시간이 걸리기 때문이다. 이것은 그들이 승인한 시점으로 처리가 8개월 걸린다는 것이다.


문제는 H-1B 비자가 숙련된 worker에게 할당 되는 것이 아니라는 점이다. 이것은 Big outsourcing firm들에 의해서 남용 되고 있다. 그들이 대부분의 할당양을 채우기 때문이다.


http://money.cnn.com/2017/03/29/technology/h1b-visa-premium-processing/index.html


Complaint #1: Visas aren't given to only the most highly trained workers


Complaint #2: H-1Bs allow employers to import cheap labor


Complaint #3: Startups get the short end of the stick



http://money.cnn.com/2017/02/21/technology/h1b-visa-program-flawed/index.html?iid=EL

Hands on TensorBoard TensorFlow Dev Summit-2017


그냥 TensorFlow를 이용해서 Graph를 생성하게 되면 복잡한 모양을 나타낸다.

아래 예제에서 사용할 전체 코드는 구글 개발자가 작성한 코드를 동작하도록 약간 수정한 버전이 저의 아래 github에 있습니다.
https://github.com/leejaymin/TensorFlowLecture/blob/master/7.TensorBoard/mnist.py

아래와 같이 사용할경우 scoping이 없어서 복잡한 tensorBoard를 생성한다.

def conv_layer(input, size_in, size_out, name="conv"):
    w = tf.Variable(tf.truncated_normal([5, 5, size_in, size_out], stddev=0.1))
    b = tf.Variable(tf.constant(0.1, shape=[size_out]))
    conv = tf.nn.conv2d(input, w, strides=[1, 1, 1, 1], padding="SAME")
    act = tf.nn.relu(conv + b)
    tf.summary.histogram("weights", w)
    tf.summary.histogram("biases", b)
    tf.summary.histogram("activations", act)
    return tf.nn.max_pool(act, ksize=[1, 2, 2, 1], strides=[1, 2, 2, 1], padding="SAME")

Cleaning the Graph

  • Node Names
  • Name Scopes

Scope과 name을 설정한 코드는 아래와 같다.

def conv_layer(input, size_in, size_out, name="conv"):
  with tf.name_scope(name):
    w = tf.Variable(tf.truncated_normal([5, 5, size_in, size_out], stddev=0.1), name="W")
    b = tf.Variable(tf.constant(0.1, shape=[size_out]), name="B")
    conv = tf.nn.conv2d(input, w, strides=[1, 1, 1, 1], padding="SAME")
    act = tf.nn.relu(conv + b)
    tf.summary.histogram("weights", w)
    tf.summary.histogram("biases", b)
    tf.summary.histogram("activations", act)
    return tf.nn.max_pool(act, ksize=[1, 2, 2, 1], strides=[1, 2, 2, 1], padding="SAME")

Variable과 Placeholder에도 Name을 넣어 줘야 한다.

x = tf.placeholder(tf.float32, shape=[None, 784], name="x")
x_image = tf.reshape(x, [-1, 28, 28, 1])
tf.summary.image('input', x_image, 3)
y = tf.placeholder(tf.float32, shape=[None, 10], name="labels")

각각의 연산 step에도 scoping을 작성해 주어야 한다.

  with tf.name_scope("train"):
    train_step = tf.train.AdamOptimizer(learning_rate).minimize(xent)

  with tf.name_scope("accuracy"):
    correct_prediction = tf.equal(tf.argmax(logits, 1), tf.argmax(y, 1))
    accuracy = tf.reduce_mean(tf.cast(correct_prediction, tf.float32))
    tf.summary.scalar("accuracy", accuracy)

그다음 TensorBoard를 생성하면 좀 더 깔끔하게 그룹핑 되어서 그려지는것을 볼 수 있다.

Hyperparameter Search

  • What about different learning rates ?
  • What about different model architectures ?

TensorBoard를 통해서 각각의 모델을 비교할 수 있다.
서로 다른 hyperparameter를 assign하고 이것을 비교해서 나타낼 수 있다.

아래와 같이 조건을 주고 여러번 실행 하면 된다.

def main():
  # You can try adding some more learning rates
  for learning_rate in [1E-4]:

    # Include "False" as a value to try different model architectures
    for use_two_fc in [True]:
      for use_two_conv in [True]:
        # Construct a hyperparameter string for each one (example: "lr_1E-3,fc=2,conv=2)
        hparam = make_hparam_string(learning_rate, use_two_fc, use_two_conv)
        print('Starting run for %s' % hparam)

	    # Actually run with the new settings
        mnist_model(learning_rate, use_two_fc, use_two_conv, hparam)

Embedding Visualizer

high dimensional data를 3D-mentional data로 projection 시키는 것을 말한다.

Embedding과 관련된 코드는 아래와 같다.

  embedding = tf.Variable(tf.zeros([1024, embedding_size]), name="test_embedding")
  assignment = embedding.assign(embedding_input)

  config = tf.contrib.tensorboard.plugins.projector.ProjectorConfig()
  embedding_config = config.embeddings.add()
  embedding_config.tensor_name = embedding.name
  embedding_config.sprite.image_path = LOGDIR + 'sprite_1024.png'
  embedding_config.metadata_path = LOGDIR + 'labels_1024.tsv'

  # Specify the width and height of a single thumbnail.
  embedding_config.sprite.single_image_dim.extend([28, 28])
  tf.contrib.tensorboard.plugins.projector.visualize_embeddings(writer, config)

각각을 file writer를 이용해서 기록하게 된다.

    if i % 500 == 0:
      sess.run(assignment, feed_dict={x: mnist.test.images[:1024], y: mnist.test.labels[:1024]})
      saver.save(sess, os.path.join(LOGDIR, "model.ckpt"), i)

500번 실행 될 때 마다 saver를 이용해서 기록을 하게 된다.
model checkpoint는 모든 variable들과 임베딩 variable들을 포함하는 정보들을 가지고 있으며 이것을 아래의 경로에 저장하게 된다.
tensorbard --logdir /tmp/mnist_tutorial

아래 그림은 임베딩 후에 PCA를 수행한 것이다.

컬러를 넣어보면 아래와 같다. PCA결과 749이 유사한 것을 알 수 있다.
Top 3 컴포넌트만 표현한 것이다.

T-SNE를 이용해서 분석하면 local similarity를 판단할 수 있다.

이러한 유사도가 높은 이미지들은 생성한 classifier가 잘못된 분류를 할 확률도 높아지게 된다.
Embedding visualization은 image에서도 유용하지만 vocabulary에 대해서도 유용하다.
아래는 smart-reply에 대한 embedding 결과이다.

Future for TensorBoard

  • TensorFlow Debugger Integration
  • Plugins
  • domain specific visualization
  • Org-scale TensorBoard

참고자료


+ Recent posts