현재 위치

홈 ›› Forums ›› 이슈 ›› 토론, 토의

"자료구조의 향후 발전 방향?!" 란게 있을까요?

오호라의 이미지
글쓴이: 오호라 / 작성시간: 토, 2006/06/17 - 7:03오후

권총 맞고 다시 듣는 DS.

어제 기말시험문제중

1. 자료구조의 의의
2. 자료구조의 중요성
3. 자료구조의 향후 발전 방향

3번 문제가 이상했지만, 목구멍이 포도청이라. 따지듯 질문은 못하고 그냥 쓰기는 썼는데...

"자료구조의 향후 발전 방향"이 도대체 뭘까요?!

DS에 발전 가능성이 있을까요?! 큐, 스택, 링크드리스트, 테이블.. Real World의 수많은 개념들이 수십년동안 특별한 변함이 없고, 정렬분야도 수많은 정렬이 있지만, hoare's Quick Sort이후에 특별하게 두각을 보이는 Sorting이 없는 걸로 알고 있습니다.

DS같은 경우는 전공(학문분야)가 따로 없는 걸로 알고 있습니다. 대부분 대학에서도 DS를 따로 전공한 분들이 없는 걸로 알고 있습니다. 따로 공부를 한다기보다 본인들의 학부 및 연구실 짬밥(?)으로 DB, OS, PL..과 같이 석박사 학위가 있는 분들이 가르치시는 걸로 알고 있습니다.

도대체 향후 발전 방향이란 뭘까요?

Forums: 
토론, 토의
ohhara의 이미지

글쓴이: ohhara / 작성시간: 토, 2006/06/17 - 8:09오후

실제 하드웨어를 고려한 DS가 있을 수 있을 듯 합니다. 실제로 하드웨어는 여러가지 기술을 사용해서 계속 발전하고 있지만 학교에서 가르치는 DS는 그렇지 않은 경우가 있습니다. (요즘 가르치는 DS는 실제 하드웨어를 고려하고 있을 지도?)
예를 들어 sort같은 것을 가르칠 때도 memory에 access할 때 어떤 address의 memory라도 읽는 속도가 동일할 것이라는 가정을 하고 학교에서 가르치는 경우가 많이 있습니다. 하지만 실제로는 cache hit ratio가 얼마나 높은가에 따라 memory에 대해 읽기/쓰기의 횟수가 많은 sort가 memory에 대해 읽기/쓰기의 횟수가 적은 sort보다 성능이 더 빠를 수 있는 가능성이 얼마든지 존재합니다.
그리고 또 한가지 간과하는 것이 CPU가 한번에 한 가지 밖에 할 수 없다고 가정하는 경우가 많이 있습니다. 예를 들어 sort전용 chip을 설계해서 수많은 작업을 동시에 병렬로 처리하는 것에 대해서는 가르치지 않는 경우가 있습니다. 실제로 3d card를 사용해서 sort를 고속화하려는 시도가 요즘 진행되고 있는 듯 합니다.

제가 옛날에 배운 DS를 기준으로 얘기하고 있어서 혹시 요즘 DS는 또 다른 지도 모르겠군요. :)

Taeho Oh ( ohhara@postech.edu, ohhara@plus.or.kr ) http://ohhara.sarang.net
Postech ( Pohang University of Science and Technology ) http://www.postech.edu
PLUS ( Postech Laboratory for Unix Security ) http://www.plus.or.kr

Taeho Oh ( ohhara@postech.edu ) http://ohhara.sarang.net
Postech ( Pohang University of Science and Technology ) http://www.postech.edu
Alticast Corp. http://www.alticast.com

feanor의 이미지

글쓴이: feanor / 작성시간: 일, 2006/06/18 - 1:12오전

Cache hit를 고려하여 높은 성능을 내는 자료구조로 Judy가 있습니다.
http://judy.sourceforge.net/

홈페이지에 문서가 있으니까 읽어보세요.

skyul의 이미지

글쓴이: skyul / 작성시간: 토, 2006/10/21 - 8:48오후

1

--
서광열 소프트웨어 블로그: http://skyul.tistory.com 입니다.

june8th의 이미지

글쓴이: june8th / 작성시간: 토, 2006/06/17 - 10:29오후

키워드 cache oblivious 로 검색하면
메모리 구조 - 1차 캐쉬/2차 캐쉬/.../메인메모리/하드드라이브 - 를 고려한
알고리즘과 DS를 찾을 수 있습니다.

jj의 이미지

글쓴이: jj / 작성시간: 일, 2006/06/18 - 2:40오후

DS가 갖는 중요성을 생각해볼때 새로운 컴퓨팅환경을 반영하지 않을까싶군요. multi-core, concurrency, distributed 등이 키워드가 되지 않을까요? (너무 두리 뭉실한 대답??)

--
콘쏠의힘

--
Life is short. damn short...

익명사용자의 이미지

글쓴이: 익명사용자 / 작성시간: 일, 2006/06/18 - 7:33오후

바이오인포매틱스 분야에서도 자료구조에 대해 많은 연구가 있는것으로 압니다.
뭐 저야 잘은 모릅니다만..
20년이 지나도 DS에 대해서 여전히 새로운것이 나올것 같습니다.
관련 학술지 찾아보세요

rollin96의 이미지

글쓴이: rollin96 / 작성시간: 월, 2006/06/19 - 8:36오전

DS에 대한 정확한 정의를 저도 잘 모르겠지만요...
Data Structure 책이 자료 저장, 메모리 관리, 인덱싱 등을 모두 포함한다고 한다면...
Data Engineering쪽에서 하는 일들이 DS관련이라고 할 수 있겠죠. 새로운 H/W(Flash Drive 등등), p2p, web/XML, 분산 환경, 생명과학쪽의 sequence데이타, 다차원 데이타(공간 데이타, 멀티미디어 데이타) 등등 아직 다뤄야 할 문제는 많이 있죠. 스텍이나 힙같은 내용들은 고전물리학 정도에 대응되는 내용들이니 그 자체로 더이상 크게 바뀔 것은 없겠죠. 하지만 물리학이 고전물리학만으로 해결되지 않듯 데이타를 잘 쓰기 위해서는 이런저런 부분들을 생각 해야 겠죠.
ICDE(International Conference on Data Engineering), SIGMOD(SIG on Management of Data), VLDB(Very Large DB) 등등을 참조해 보심이...참고로 국내 DB쪽 학회도 몇개 있기는 한데...한국정보과학회나 한국정보처리학회, 데이타베이스연구회 논문의 경우 www.cseric.or.kr에 들어가시면 무료로 보실 수 있습니다.

수원의 이미지

글쓴이: 수원 / 작성시간: 화, 2006/06/20 - 5:27오후

정말 기말 고사 시험 문제거 저런 식으로 나왔나요?

자료구조의 의의라 ㅡㅡ;;;;

머랄까 참... 참... 머한 문제들이군요.. 제대로 표현은 못하겠음 ;;

헐 덧셈 틀려서 ㅡㅡ;; 에라 났네요 이런 ㅡㅡ;;

nike984의 이미지

글쓴이: nike984 / 작성시간: 수, 2006/06/21 - 6:46오전

이미 거진 10년 전 얘기들이지만
학부 1,2학년때 교양 과목 들어가면 시험때 종종 나오던 문제 스타일 같군요. ^^
칠판 정 중앙에 아주 큼지막하게 한 문장 띡 적어놓고 ~ 뭐뭐에 대해 기술하라~

출제자 입장에서는 참 편할지 몰라도 뭐랄까~ 문제 출제를 참 성의 없이 한다는 기분이 항상 들더군요.

또 저런 문제의 경우 일단 많이 쓰면 점수가 잘 나오더군요.

sanori의 이미지

글쓴이: sanori / 작성시간: 수, 2006/06/21 - 12:10오전

누구였는지 기억이 안 나는데, 유명한 사람이 Data Structures + Algorithms = Programs이라고 말한 적이 있습니다.

문제가 존재하는 한 algorithm과 같이 새로운 data structure는 계속 필요로 합니다.

보아하니 학부 4학년쯤 되시는 것 같으신데, 괜히 이상한 문제 만났다고 신경질 내시는 의도로 이 thread를 시작하신게 아니라면 computational geometry(계산기하학) 쪽 책을 한번 훑어보시길 추천합니다. 정말 지겨울 정도로 많은 data structure가 나옵니다. (그럼에도 불구하고 새로운 data structure가 계속 나옵니다.)

그리고, 제가 보기에는, 위의 문제는 수업시간에 들어왔는지, 들어왔다면 제대로 수업을 들었는지 확인하는 문제 같네요. 수업시간에 교수님이 몇 마디 하셨을 겁니다. (저라면 그렇게 문제 냅니다.)

-산오리

남동우의 이미지

글쓴이: 남동우 / 작성시간: 목, 2006/06/22 - 10:00오전

non-strict Functional Language (e.g. Haskell)에서는 무한데이터의 표현이 가능해 제어로 부터 데이터를 완전히 분리해 낼수 있는 표현력을 가지고 있습니다.[1]

함수형 패러다임 관점에서 자료구조를 해석하는 것[2]도 의미 있는 작업일 것 같습니다.

Quicksort in Haskell

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Quicksort in C

qsort( a, lo, hi ) int a[], hi, lo;
{
  int h, l, p, t;
 
  if (lo < hi) {
    l = lo;
    h = hi;
    p = a[hi];
 
    do {
      while ((l < h) && (a[l] <= p)) 
          l = l+1;
      while ((h > l) && (a[h] >= p))
          h = h-1;
      if (l < h) {
          t = a[l];
          a[l] = a[h];
          a[h] = t;
      }
    } while (l < h);
 
    t = a[l];
    a[l] = a[hi];
    a[hi] = t;
 
    qsort( a, lo, l-1 );
    qsort( a, l+1, hi );
  }
}

[1] http://www.md.chalmers.se/~rjmh/Papers/whyfp.html
[2] http://www.amazon.com/gp/product/0521663504/ref=si3_rdr_bb_product/104-0386571-0593563?%5Fencoding=UTF8
jachin의 이미지

글쓴이: jachin / 작성시간: 금, 2006/11/17 - 5:12오전

사회가 다변화되면서 많은 자료들이 범람하는 가운데, 자료의 형태가 다양해지는 것은 당연한 것이 아닐까요?

그런 가운데 자료구조가 발전하지 않는다면 인간이 그 많은 자료를 일일이 분석한다는 것이 쉽지 않겠지요.

그런 의미에서 자료구조는 인류문명의 발전이 끊이지 않는 한 무궁무진하게 발전할 수 있을거라 생각합니다.

과학분야에서 게놈구조에 대한 연구가 진행되고, 그것에 대한 분석이 끊이지 않는 것만 봐도 자료구조는 계속

발전하고 있다고 봅니다. 앞으로 사회적인 발전이 이뤄지면서 사회 과학이 발전하면, 환경과 지역적 조건에

따른 여러가지 자료를 분석하기 위해 또한 새로운 형태의 자료분석 방법이 생겨날 것이고 거기에 맞게 자료구조도

발전할 것입니다.
====
( - -)a 이제는 학생으로 가장한 백수가 아닌 진짜 백수가 되어야겠다.

둘러보기