파이썬에서 set과 list의 속도차이를 알고 싶어 진행한 실험이다.

테스트환경은

CPU : 3900X

RAM : 128GB

이며

간단한 테스트를 위해 python idle환경에서 테스트하였다.

 

코드는 list와 set에 10억번의 랜덤값을 집어넣은 후

max, min, in을 각각 실행하여 실행시간을 측정하는 방법이다.

코드는 다음과 같다.

대표적으로 iteration을 이용하는 max와 min함수의 실행시간을 측정하였고

탐색함수 in의 실행시간을 측정하였다.

 

결과는 다음과 같다.

결과는 위를 보면 알 수 있듯이

iteration의 경우 list가 14~16초로 압도적으로 빨랐다.

set의 경우 233초로 매우 긴 시간이 걸림을 확인할 수 있다.

 

하지만

in 함수의 경우

list는 8초

set은 0초(!!)라는 엄청난 시간차이를 보여준다.

 

결론

in함수를 많이 사용하는 코드는 set으로

iteration을 많이 사용하는 코드는 list로 짜자.

 

여담

랜덤한 실수 10억개는

메모리를 100기가나 잡아먹는다....

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from flask import Flask
from flask_sqlalchemy import SQLAlchemy
import os
from werkzeug.security import generate_password_hash, check_password_hash
from datetime import datetime
import pandas as pd
 
#create app and db
app = Flask(__name__)
app.config['SECRET_KEY'= 'dlfldhsjfk'
print(os.path.join(os.path.abspath(os.path.dirname(__file__)), "practice.db"))
app.config["SQLALCHEMY_DATABASE_URI"= "postgresql://postgres:password@localhost:5432"
app.config['SQLALCHEMY_TRACK_MODIFICATIONS'= False
db = SQLAlchemy(app)
 
class Users(db.Model):
    __table_name__ = "users"
 
    pk = db.Column(db.BigInteger, primary_key=True, autoincrement=True)
    username = db.Column(db.String(100), nullable=False)
    email = db.Column(db.String(120), unique=True, nullable=False)
    password = db.Column(db.String(100), nullable=False)
 
    def __init__(self, username, email, password, **kwargs):
        self.username = username
        self.email = email
        self.password = generate_password_hash(password)
 
    def check_password(self, password):
        return check_password_hash(self.password, password)
 
    def __repr__(self):
        return f"<User('{self.pk}', '{self.username}', '{self.email}')>"
 
@app.route("/")
def hello():
    db.create_all()
    return "db init finish!"
 
@app.route("/<name>-<email>-<password>")
def set_person(name, email, password):
    user = Users(username=name, email=email, password=password)
    db.session.add(user)
    db.session.commit()
    pd.read_sql("select * from users", db)
    print(pd.head())
    return f"User : {name}, {email}, {password} is added"
 
app.run()
 
 
cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(n, results):
    win = {x:set() for x in range(1, n+1)}
    lose = {x:set() for x in range(1, n+1)}
    for winner, loser in results:
        win[winner].add(loser)
        lose[loser].add(winner)
    for i in range(1, n+1):
        for winner in lose[i]:
            win[winner].update(win[i])
        for loser in win[i]:
            lose[loser].update(lose[i])
    
    answer = 0
    for i in range(1, n+1):
        if len(win[i]) + len(lose[i]) == n-1:
            answer += 1
    return answer
cs

이거 이상으로 좋은 알고리즘이 안떠오른다.....

파이썬에서 set은 내부적으로 hash를 이용해서 구현되어 있다.

덕분에 indexing이 안되고

indexing이 안되기 때문에 slicing이 안되지만

검색(in 함수 등)은 빠르다.

 

파이썬에서 list는 내부적으로 동적배열과 비슷하게 동작한다.

끝부분의 추가와 삭제는 빠르게 동작하지만

list.pop(0)은 O(n)으로 매우 느리게 동작한다.

indexing이 가능하기 때문에 slicing도 가능하고

순차적으로 접근하는 iteration이 set보다 조금 빠르다.

 

set과 list 모두 interation이 가능하나 list가 더 빠르게 동작한다.

1. c style의 %operator - 가장 느림

1
2
3
animal = "강아지"
text = "나는 %s가 좋아"%animal
print(text)
cs

 

2. str.format - 중간정도 속도

1
2
3
animal = "강아지"
text = "나는 {}가 좋아".format(animal)
print(text)
cs

 

3. f-string - 가장 빠름

1
2
3
animal = "강아지"
text = f"나는 {animal}가 좋아"
print(text)
cs

 

결론 쓰기도 편하고 가독성도 좋고 빠르기도 한 f-string을 쓰자

'컴퓨터 > 파이썬팁' 카테고리의 다른 글

python set vs list interation and in funciton speed test  (1) 2020.03.25
파이썬 set과 list의 특징  (0) 2020.03.17
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
26
27
28
29
def dist_bfs(adj_matrix):
    from collections import deque
    visited = set()
    queue = deque([1])
    dist_list = [50001 for x in range(len(adj_matrix))]
    dist_list[0= 0
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            queue += adj_matrix[node] - visited
            for x in adj_matrix[node]:
                dist_list[x-1= min(dist_list[x-1], dist_list[node-1]+1)
    return dist_list
 
def solution(n, edge):
    adj_matrix = {key : set() for key in range(1,n+1)}
    for a,b in edge:
        adj_matrix[a].add(b)
        adj_matrix[b].add(a)
    dist_list = dist_bfs(adj_matrix)
    
    max_dist = max(dist_list)
    answer = 0
    for x in dist_list:
        if x == max_dist:
            answer += 1
    return answer
cs

여기서 주의해야할 점은 매우 빈번히 연산되는 visited를 set으로 해야한다는 점이다.

파이썬 내부적으로 list가 set보다 iteration에서는 빠르지만

탐색(in함수)에서는 set이 훨씬 빠르다.

부산대학교 학식에서 원하는 메뉴(소세지 야채 볶음 등) 혹은 원하는 키워드가 등장하면

카카오톡 알림을 주는 토이 프로젝트를 구현하려고 합니다.

기술 스펙은 다음과 같습니다.

-구동사양 : 라즈베리4 4GB

-주 언어 : python

모두들 python에 익숙한 상태여서 러닝커브가 없는 파이썬을 선택하였습니다.

-프레임워크 : Flask

라즈베리파이에서 간단한 웹서버를 돌리기 위해 러닝커브가 적은 Flask를 선택하였습니다.

-데이터베이스 : PostgreSQL

이렇게 간단한 프로젝트는 txt파일로 메뉴를 관리해도 되지만 데이터베이스도 건드려보자! 싶어서 찾아보았습니다.

다양한 데이터베이스가 있었지만 대용량 트랜잭션에도 안정적이라 평가받는 postgreSQL을 선택하였습니다.

한국어로 된 좋은 자료가 없어서(제가 못찾아서...)

https://youtu.be/qw--VYLpxG4

이 자료를 이용하여 공부하였습니다.

쉬운 영어로 제작되어서 듣는데 거북함은 없을거에요^^

- 데이터베이스 연결도구 : sqlalchemy

psycopg2와 sqlalchemy 둘 다 쓸 수 있었지만

판다스를 통해서 데이터베이스를 불러오는 기능 중 read_sql_table을 쓸 수 있는 sqlalchemy를 선택하였습니다.

어차피 둘다 연결도구로만 쓰고 판다스의 read_sql만 사용할 수 있어서

기능이 한개라도 많은 녀석을 사용하는 것이 더 나았습니다.

-기타 : 카카오톡 플러스친구와 챗봇 신청

 

이제부터 쓰는 글은 위 기술 스택을 공부했다는 가정하에 적겠습니다.

def compute_gcd(num1, num2):
    if num1%num2 == 0:
        return num2
    return compute_gcd(num2, num1 % num2)

def fillingprime(N):	#에라토네스의 체~N
    raw = set([x for x in range(N+1)])
    raw -= set(range(0,2))
    for i in range(2, int(max(raw)**0.5)+1):
        raw -= set(range(i*2, max(raw)+1, i))
    return list(raw)​
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstdlib>

using namespace std;

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
}


vector<long long> prime;

void fillingPrime(long long N) {
	vector<int> raw(N + 1);

	for (int i = 2; i < N; i++) {
		raw[i] = i;
	}
	for (long long i = 2; i*i < N; i++) {	//에라토네스의 체
		if (raw[i] == 0)	continue;
		for (int j = i + i; j < N; j += i) {
			raw[j] = 0;
		}
	}
	for (int i = 2; i < N; i++) {
		if (raw[i] != 0)
			prime.push_back(raw[i]);
	}
}
vector<long long> split(string& s, char delimiter) {
	vector<long long> int_tokens;
	string token;
	istringstream tokenStream(s);
	while (getline(tokenStream, token, delimiter)) {
		stringstream ss(token);	//each element, string to int
		long long n;
		ss >> n;
		int_tokens.push_back(n);
	}
	return int_tokens;
}
#include <iostream>
#include <algorithm>
#include <string>
#define null 0

using namespace std;


class node {
private:
	char x;
	node* left;
	node* right;
public:
	node(char data = ' ', node* _left = null, node* _right = null) {
		if (data == '.') {
			data = null;
		}
		else {
			x = data;
		}
		left = _left;
		right = _right;
	}
	void print() {
		cout << this->x;
		return;
	}
	node* getleft() {
		return this->left;
	}
	node* getright() {
		return this->right;
	}
	void setleft(node* data) {
		this->left = data;
		return;
	}
	void setright(node* data) {
		this->right = data;
		return;
	}
	void preorder(node* current) {
		if (current == null) return;
		else {
			cout << current->x;
			preorder(current->getleft());
			preorder(current->getright());
		}
	}
	node* find(node* current, char data) {
		if (current == null) return null;
		else {
			if (current->x == data)	return current;
			else {
				if (find(current->left, data) == null) {
					find(current->right, data) == null;
				}
			}
		}
	}
};

int main() {
	node t = node();
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		char root, lc, rc;
		cin >> root >> lc >> rc;
		if (root == 'A') {
			node lt = node(lc);
			node rt = node(rc);
			t = node(root, &lt, &rt);
		}
		else {
			node* temp = new node;
			temp = t.find(&t, root);
			node templ = node(lc);
			temp->setleft(&templ);
			node tempr = node(rc);
			temp->setright(&tempr);
		}
	}
	t.preorder(&t);
	cout << endl;
	return 0;
}

이 코드가 오류가 난다.

백준 1991을 풀다가 발견한 에러인데

생성자에 조건문 같이 제어문을 사용하면 에러가 발생하는 것 같다

마지막에 setleft를 통해서 값을 설정하려고 할때 this를 지정하는 것이 temp값으로 고정되어야하는데

다른 값으로 튀는 경우가 있었다.

왜 인지는 구글링해도 모르겠다.

한시간 날렸다....

그래서 기록한다

다른 사람들은 이런 문제를 겪지 않기를!!

 

https://developer.nvidia.com/cuda-80-ga2-download-archive

 

CUDA Toolkit 8.0 - Feb 2017

Select Target Platform Click on the green buttons that describe your target platform. Only supported platforms will be shown. Operating System Architecture Distribution Version Installer Type Do you want to cross-compile? Yes No Select Host Platform Click

developer.nvidia.com

여기서 cuda toolkit 8.0을 다운받았다.

그리고 sudo bash cuda_8.0.61_375.26_linux.run 으로 실행시켰다.

그러니 뜨는 오류

using unsupported compiler

 

이거의 해결방법은 간단하다.

sudo bash cuda_8.0.61_375.26_linux.run --override

로 해결할 수 있다.

 

그러나 이후에도 설치가 안됐는데 로그파일을 살펴보니

InstallUtils.pm이 없다는 오류가 있었다.

해결법을 찾아서 구글링하던 도중

https://devtalk.nvidia.com/default/topic/983777/can-t-locate-installutils-pm-in-inc/

불러오는 중입니다...

여기에서 해답을 찾았다.

결론만 말하자면

sudo sh ./cuda-l*.run --tar mxvf

을 하여 run파일의 압축을 푼 후

sudo cp InstallUtils.pm /usr/lib/x86_64-linux-gnu/perl-base/

로 파일을 복사한 후

export $PERL5LIB

로 export를 잡아준 후

sudo bash cuda_8.0.61_375.26_linux.run --override

명령어로 설치를 진행하면 잘 된다.

+ Recent posts