TWpower Reading time ~1 minute

Post about removing duplicated elements in Python list


Environment and Prerequisite

  • Python


Remove Duplicated Elements

  • Insert to dictionary as key values and change those to list again.
  • By following below methods inserted order in list is preserved.
  • Different versions have different methods, so they should be used accordingly. Related things are in Reference.


Python 2.7 or higher

OrderedDict.fromkeys(iterable[, value])

  • Returns a dictionary using the given values ​​as key values. If there is a value, the value is set as value for all key values, otherwise it is None.
  • OrderedDict: Available starting with Python 2.7
  • Inserted elements order in iterable is preserved

Example

ex_list = [3, 4, 5, 6, 10, 1, 4, 5, 7, 8, 1, 5, 9]
from collections import OrderedDict
result = list(OrderedDict.fromkeys(ex_list))
print(result)

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

Example

ex_list = ['e', 'e', 'b', 'c', 'a', 'e', 'd', 'd', 'b', 'a']
from collections import OrderedDict
result = list(OrderedDict.fromkeys(ex_list))
print(result)

['e', 'b', 'c', 'a', 'd']


Python 3.7 or higher

dict.fromkeys(iterable[, value])

  • Returns a dictionary using the given values ​​as key values. If there is a value, the value is set as value for all key values, otherwise it is None.
  • Inserted elements order in iterable is preserved starting with Python 3.7
  • Partially supported in 3.6 implementation

Example

ex_list = [3, 4, 5, 6, 10, 1, 4, 5, 7, 8, 1, 5, 9]
result = list(dict.fromkeys(ex_list))
print(result)

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

Example

ex_list = ['e', 'e', 'b', 'c', 'a', 'e', 'd', 'd', 'b', 'a']
result = list(dict.fromkeys(ex_list))
print(result)

['e', 'b', 'c', 'a', 'd']


Reference

TWpower Reading time ~1 minute

Dockerfile로 도커 이미지를 빌드할 때 다운로드할 파일이 변경되었어도 캐싱된 레이어를 사용해 변경된 파일이 적용되지 않는 경우에 대해서 정리


환경

  • Linux
  • Docker


문제 및 해결 방법

문제 상황

  • Dockerfile를 통해서 도커 이미지를 빌드할 때 RUN에서 curl을 이용해 파일을 다운로드 받는 부분이 있다. 이때, 새로운 이미지 빌드시 파일이 변경되었음에도 처음에 캐싱된 레이어의 파일이 들어가서 이전 파일이 이미지에 포함되는 문제가 발생한다.

문제 상황 예시

  • 파일 확인
$ curl https://twpower.me/test.txt
test1
  • Dockerfile 예시
$ cat Dockerfile
FROM ubuntu:18.04
RUN apt-get update -y
RUN apt-get install curl -y
RUN curl https://twpower.me/test.txt -o test.txt
CMD cat test.txt
  • 도커 이미지 빌드
$ sudo docker build --tag test:1.0 .
  • 빌드된 이미지 실행
$ sudo docker run test:1.0
test1
  • 변경된 파일 확인
$ curl https://twpower.me/test.txt
test2
  • 이미지 다른 버전으로 빌드
  • 하단에 캐시 이용하는거 확인
$ sudo docker build --tag test:2.0 .
Sending build context to Docker daemon  2.048kB
Step 1/5 : FROM ubuntu:18.04
 ---> 56def654ec22
Step 2/5 : RUN apt-get update -y
 ---> Using cache
 ---> 47696d4f4d5f
Step 3/5 : RUN apt-get install curl -y
 ---> Using cache
 ---> 15080e39cb8b
Step 4/5 : RUN curl https://twpower.me/test.txt -o test.txt
 ---> Using cache
 ---> 75bbac2b003f
Step 5/5 : CMD cat test.txt
 ---> Using cache
 ---> 3ce1a5c10a5b
Successfully built 3ce1a5c10a5b
Successfully tagged test:2.0
  • 빌드된 이미지 실행
  • 파일은 변경되었으나 변경된 파일이 적용되지 않은 문제 발생!
$ sudo docker run test:2.0
test1
$ curl https://twpower.me/test.txt
test2


원인

  • Dockerfile에서는 명령어 한줄 한줄을 레이어(Layer)로 판단하며 해당 레이어(Layer)별로 캐싱을 진행하기 때문에 만약 특정줄에 해당하는 명령어와 이전 명령어들이 동일하다면 동일한 레이어(Layer)로 판단하기 때문에 캐싱되어 있는 부분을 가져오기 때문이다.
  • 위의 예제에서는 파일이 변경되었어도 명령어 RUN curl https://twpower.me/test.txt -o test.txt는 동일하다.
  • 공식 홈페이지 문서 https://docs.docker.com/develop/develop-images/dockerfile_best-practices/에 따르면 “A Docker image consists of read-only layers each of which represents a Dockerfile instruction. The layers are stacked and each one is a delta of the changes from the previous layer.”라고 나와있다.


해결 방법

  • --no-cache를 이용해 도커 이미지 빌드시 캐시를 사용하지 않도록 설정
$ sudo docker build --no-cache --tag test:3.0 .


참고자료

TWpower Reading time ~1 minute

Post about the case that changed file is not applied due to a cached layer even though the file to be downloaded is changed when building a docker image using Dockerfile


Environment and Prerequisite

  • Linux
  • Docker


Problem and Solution

Issue

  • When building a docker image through a Dockerfile, there is a part to download a file using curl in RUN. At this time, even though the file is changed when a new image is built, the file of the initially cached layer is included so the previous file is included in the image.

Issue Case Example

  • Check file
$ curl https://twpower.me/test.txt
test1
  • Dockerfile example
$ cat Dockerfile
FROM ubuntu:18.04
RUN apt-get update -y
RUN apt-get install curl -y
RUN curl https://twpower.me/test.txt -o test.txt
CMD cat test.txt
  • Build docker image
$ sudo docker build --tag test:1.0 .
  • Run the built image
$ sudo docker run test:1.0
test1
  • Check updated file
$ curl https://twpower.me/test.txt
test2
  • Build docker image with another version
  • Check that the cache is used in below
$ sudo docker build --tag test:2.0 .
Sending build context to Docker daemon  2.048kB
Step 1/5 : FROM ubuntu:18.04
 ---> 56def654ec22
Step 2/5 : RUN apt-get update -y
 ---> Using cache
 ---> 47696d4f4d5f
Step 3/5 : RUN apt-get install curl -y
 ---> Using cache
 ---> 15080e39cb8b
Step 4/5 : RUN curl https://twpower.me/test.txt -o test.txt
 ---> Using cache
 ---> 75bbac2b003f
Step 5/5 : CMD cat test.txt
 ---> Using cache
 ---> 3ce1a5c10a5b
Successfully built 3ce1a5c10a5b
Successfully tagged test:2.0
  • Run the built image
  • The file is changed but the changed file is not applied!
$ sudo docker run test:2.0
test1
$ curl https://twpower.me/test.txt
test2


Cause

  • In Dockerfile, each instruction line is considered as layer and cache is created per that layer. So if specific line and previous lines are same then, it is considered to be a same layer so it load layer from cache if it exists.
  • In above example, RUN curl https://twpower.me/test.txt -o test.txt is same but file is updated.
  • According to official document https://docs.docker.com/develop/develop-images/dockerfile_best-practices/ it says “A Docker image consists of read-only layers each of which represents a Dockerfile instruction. The layers are stacked and each one is a delta of the changes from the previous layer.”.


Solution Methods

  • Use --no-cache to disable the cache using when building docker images
$ sudo docker build --no-cache --tag test:3.0 .


Reference

TWpower Reading time ~1 minute

임시 변수를 사용하지 않고 값을 교체할 수 있는 XOR 교체 알고리즘에 대해 알아보자


환경

  • XOR
  • 논리 회로
  • 부울 대수


XOR 연산

XOR

  • XOR: XOR 연산이란 bit단위에서는 아래의 예시처럼 서로의 비트가 다르면 1 같으면 0의 결과를 나타내는 연산자입니다.
1^1 = 0
1^0 = 1
0^1 = 1
0^0 = 0

// Example in binary
10010101
XOR
10111100

==> 00101001

// Example in decimal
149
XOR
188

==> 41


XOR 교체 알고리즘

XOR 교체 알고리즘이란?

  • XOR 교체 알고리즘이란 임시 변수를 사용하지 않고 서로 다른 두 개의 변수를 XOR 비트 연산을 이용해 값을 교체하는 알고리즘이다.


XOR 교체 알고리즘 코드 및 예시

예시

의사코드

X := X XOR Y
Y := Y XOR X
X := X XOR Y

C++ 코드

#include <iostream>
#include <stdio.h>

using namespace std;

int main(){

    int x = 1;
    int y = 2;

    printf("x: %d y: %d\n", x, y);

    if (x != y){
        x = x^y;
        y = y^x;
        x = x^y;    
    }

    printf("x: %d y: %d\n", x, y);

    return 0;
}


증명

사용되는 법칙

  • 교환법칙: A ⊕ B = B ⊕ A
  • 결합법칙: (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)

증명

  • 아래의 식을 사용
1. X := X XOR Y
2. Y := Y XOR X
3. X := X XOR Y

R1, R2 are registers

0. R1 = X, R2 = Y

1. R1 <- R1 ⊕ R2 = X ⊕ Y
=> R1 = X ⊕ Y, R2 = Y

2. R2 <- R2 ⊕ R1 = Y ⊕ (X ⊕ Y) = Y ⊕ (Y ⊕ X) = (Y ⊕ Y) ⊕ X = 0 ⊕ X = X
=> R1 = X ⊕ Y, R2 = X

3. R1 <- R1 ⊕ R2 = X ⊕ Y ⊕ X = Y ⊕ X ⊕ X = Y ⊕ (X ⊕ X) = Y ⊕ 0 = Y
=> R1 = Y, R2 = X


사용 사례 및 범위

  • RAM이 매우 한정적인 임베디드 환경
  • Register pressure가 높은 곳


사용하지 않는 이유

  • 컴파일러 수준에서 최적화가 진행되기 때문에 임시 변수를 사용하는 방법이 더 빠르다.
  • 사용법을 모르는 사람에게는 모호하다.
  • 최신 컴퓨터 아키텍처는 명령어 파이프라인에 의해 명령어 수준의 병렬처리가 가능해서 임시 변수를 이용한 교체가 더 빠르다. XOR 교체 알고리즘은 반드시 순서대로 진행되어야 하기에 병렬처리가 어렵다.


참고자료

TWpower Reading time ~2 minutes

Post about XOR swap algorithm


Environment and Prerequisite

  • XOR
  • Logic Design
  • Boolean Algebra


XOR Operation

XOR

  • XOR: XOR operation is bitwise operation which result 1 if they are different bit, result 0 if they are same bit.
1^1 = 0
1^0 = 1
0^1 = 1
0^0 = 0

// Example in binary
10010101
XOR
10111100

==> 00101001

// Example in decimal
149
XOR
188

==> 41


XOR Swap Algorithm

What is XOR Swap Algorithm?

  • XOR Swap Algorithm is an algorithm that uses the XOR bitwise operation to swap values of distinct variables without using a temporary variable


XOR Swap Algorithm Code and Example

Example

Pseudocode

X := X XOR Y
Y := Y XOR X
X := X XOR Y

C++ Code

#include <iostream>
#include <stdio.h>

using namespace std;

int main(){

    int x = 1;
    int y = 2;

    printf("x: %d y: %d\n", x, y);

    if (x != y){
        x = x^y;
        y = y^x;
        x = x^y;    
    }

    printf("x: %d y: %d\n", x, y);

    return 0;
}


Proof

Used Properties

  • Commutativity: A ⊕ B = B ⊕ A
  • Associativity: (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)

Proof

  • Use below equation
1. X := X XOR Y
2. Y := Y XOR X
3. X := X XOR Y

R1, R2 are registers

0. R1 = X, R2 = Y

1. R1 <- R1 ⊕ R2 = X ⊕ Y
=> R1 = X ⊕ Y, R2 = Y

2. R2 <- R2 ⊕ R1 = Y ⊕ (X ⊕ Y) = Y ⊕ (Y ⊕ X) = (Y ⊕ Y) ⊕ X = 0 ⊕ X = X
=> R1 = X ⊕ Y, R2 = X

3. R1 <- R1 ⊕ R2 = X ⊕ Y ⊕ X = Y ⊕ X ⊕ X = Y ⊕ (X ⊕ X) = Y ⊕ 0 = Y
=> R1 = Y, R2 = X


Reasons for use in practice

  • Embedded system of which ram memory is very limited
  • In region with high register pressure


Reasons for avoidance in practice

  • Due to compiler level optimization, using temporary variable is faster than XOR swap.
  • It is opaque to anyone unfamiliar with the technique.
  • In modern architecture, using temporary variable is faster because of instruction pipelines. Instruction pipeline enables instruction level parallel processing. XOR swap inputs to each operation depend on the results of the previous operation so it cannot be done in parallel processing.


Reference