염산하

러트거스 대학교의 학부생 앤드류 크라피빈(Andrew Krapivin)이 해시 테이블 설계에서 획기적인 발견을 통해 40년 된 컴퓨터 과학 추측을 뒤집었습니다[1][3]. 그의 혁신적인 접근 방식은 데이터 검색 시간을 크게 단축시켰으며, 데이터베이스, 알고리즘 및 저장 시스템에 중요한 영향을 미칠 것으로 예상됩니다[1].

획기적인 발견

크라피빈은 "Tiny Pointers"라는 논문을 읽던 중 영감을 받아 새로운 종류의 해시 테이블을 개발했습니다[7]. 처음에 그의 지도교수인 마틴 파라치-콜턴(Martín Farach-Colton)은 이 발견에 회의적이었지만, 카네기 멜론 대학의 윌리엄 쿠즈마울(William Kuszmaul)과 함께 연구를 검증한 결과, 크라피빈이 단순히 새로운 해시 테이블을 만든 것이 아니라 40년 된 추측을 완전히 뒤집었다는 사실을 확인했습니다[7].

이 발견은 1985년 튜링상 수상자인 앤드류 야오(Andrew Yao)가 제시한 추측을 반박했습니다. 야오는 특정 속성을 가진 해시 테이블에서 개별 요소나 빈 공간을 찾는 최선의 방법은 무작위로 잠재적 위치를 탐색하는 '균일 프로빙(uniform probing)'이라고 주장했습니다[3][5].

기술적 혁신

크라피빈의 해시 테이블은 기존 방식과 비교해 현저히 빠른 검색 시간을 제공합니다. 해시 테이블의 '가득 참' 정도를 측정하는 데 사용되는 'x'라는 수치가 있습니다. 예를 들어, x가 100이면 테이블이 99% 차 있고, x가 1,000이면 99.9% 차 있음을 의미합니다[5].

기존 해시 테이블에서는 최악의 경우 삽입 시간(마지막 남은 공간을 채우는 시간)이 'x'에 비례했습니다. 그러나 크라피빈의 해시 테이블은 최악의 경우 쿼리 및 삽입 시간이 (log x)²에 비례하여 'x'보다 훨씬 빠릅니다[2][5].

이 새로운 접근 방식은 두 가지 주요 혁신을 포함합니다:

퍼널 해싱(Funnel Hashing): 해시 테이블을 기하학적 크기 감소를 가진 여러 하위 배열로 분할하는 전략으로, 최악의 경우 예상 프로브 복잡도 O(log²(1/δ))를 달성합니다(여기서 δ는 로드 팩터)[4].
탄력적 해싱(Elastic Hashing): 비탐욕적 접근 방식으로, 평균 쿼리 시간이 해시 테이블의 가득 참 정도와 상관없이 일정한 상수가 됩니다[7].

광범위한 영향

이 혁신은 해시 테이블을 사용하는 다양한 분야에 중요한 영향을 미칠 것으로 예상됩니다:

데이터베이스: 더 빠른 쿼리 처리와 전반적인 성능 향상[5]
캐싱 시스템: 웹 브라우저, 운영 체제, 콘텐츠 전송 네트워크에서 더 빠른 로딩 시간[5]
컴파일러: 특히 대규모 프로그램에서 컴파일 과정 가속화[5]
네트워크 라우팅: 더 빠른 라우팅 결정과 네트워크 성능 향상[5]
암호화: 암호화 알고리즘의 성능 향상[5]

이 발견은 단순히 야오의 추측을 반박한 것뿐만 아니라, 해시 테이블의 검색 속도에 대한 새로운 한계를 제시했습니다. 특히 놀라운 점은 평균 검색 시간이 해시 테이블의 가득 참 정도와 상관없이 일정하다는 것입니다[7].

워털루 대학의 세페르 아사디(Sepehr Assadi)는 "단순히 야오의 추측을 반박한 것이 아니라, 그의 질문에 대한 최선의 해결책을 발견했다"고 평가했습니다[7].

Sources [1] Breaking a 40-Year-Old Computer Science Theory! Andrew Krapivin ... https://www.linkedin.com/posts/othmaneoukbil_breaking-a-40-year-old-computer-science-theory-activity-7296000218511097856--uqp [2] Undergrad accidentally shreds 40-year hash table gospel https://www.theregister.com/2025/02/13/hash_table_breakthrough/ [3] Undergraduate Disproves 40-Year-Old Conjecture, Invents New ... https://ground.news/article/undergraduate-disproves-40-year-old-conjecture-invents-new-kind-of-hash-table [4] Hash table algorithm achieved a major breakthrough ... - LinkedIn https://www.linkedin.com/pulse/hash-table-algorithm-achieved-major-breakthrough-student-florent-liu-tsxme [5] Revolutionizing Hash Tables: An Undergraduate's Breakthrough https://atlassc.net/2025/02/12/revolutionizing-hash-tables-an-undergraduate-s-breakthrough [6] Tiny Pointers the Secret to Super-Fast Hash Tables. - CIO Bulletin https://www.ciobulletin.com/database-management/tiny-pointers-the-secret-to-super-fast-hash-table [7] Undergraduate Disproves 40-Year-Old Conjecture, Invents ... - WIRED https://www.wired.com/story/undergraduate-upends-a-40-year-old-data-science-conjecture/ [8] Undergraduate Upends a 40-Year-Old Data Science Conjecture https://www.reddit.com/r/programming/comments/1in5hkt/undergraduate_upends_a_40yearold_data_science/ [9] Tiny Pointers | Hacker News https://news.ycombinator.com/item?id=43023634 [10] Undergraduate Disproves 40-Year-Old Conjecture, Invents New ... https://news.ycombinator.com/item?id=43388296 [11] 해시 테이블 내 검색 속도 향상을 입증한 학부생 연구 - GeekNews https://news.hada.io/topic?id=19168 [12] Undergrad Andrew Krapivin solved a 40-year data science puzzle ... https://www.instagram.com/nerdontour/reel/DGJsTdSiWdu/undergrad-andrew-krapivin-solved-a-40-year-data-science-puzzle-creating-a-faster/ [13] [PDF] Optimal Bounds for Open Addressing Without Reordering - arXiv https://arxiv.org/pdf/2501.02305.pdf [14] Undergraduate shows that searches within hash tables can be much ... https://news.ycombinator.com/item?id=43002511 [15] Sometime in the fall of 2021, Andrew Krapivin, an ... - Instagram https://www.instagram.com/quantamag/p/DF5coWIxeeQ/ [16] Rutgers University Computer Science Department on Instagram https://www.instagram.com/rutgerscomputerscience/p/DGBR92WpI-Z/ [17] Uniform hashing is optimal - Association for Computing Machinery https://dl.acm.org/doi/pdf/10.1145/3828.3836 [18] An even faster hash table | MetaFilter https://www.metafilter.com/207613/An-even-faster-hash-table [19] Andre Zayarni's Post - LinkedIn https://www.linkedin.com/posts/zayarni_the-𝐇𝐚𝐬𝐡-𝐓𝐚𝐛𝐥𝐞𝐬-are-fundamental-activity-7302253552830185473-TFF2 [20] Optimal Bounds for Open Addressing Without Reordering - arXiv https://arxiv.org/html/2501.02305v1 [21] [PDF] Uniform Hashing is Optimal - Stanford University http://i.stanford.edu/pub/cstr/reports/cs/tr/85/1038/CS-TR-85-1038.pdf [22] Hash table - Wikipedia https://en.wikipedia.org/wiki/Hash_table [23] A Realistic Approach to Hash Table Algorithm Optimization - arXiv https://arxiv.org/html/2502.10977v1 [24] Undergraduate Upends a 40-Year-Old Data Science Conjecture https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/ [25] Undergraduate Upends a 40-Year-Old Data Science Conjecture https://soylentnews.org/article.pl?sid=25%2F02%2F11%2F1210226 [26] Hash Table Conjecture Upended by Undergraduate Researcher https://www.youtube.com/watch?v=-ukUQN3FmZg [27] [PDF] A Realistic Approach to Hash Table Algorithm Optimization - arXiv https://www.arxiv.org/pdf/2502.10977.pdf

염산하

@[email protected]

https://social.lansky.name/@hn50/114249656367574275

#!/usr/bin/env -S uv run --script
# /// script
# dependencies = ["ipython", "httpx", "loguru"]
# ///
import httpx
import IPython
from loguru import logger

...

Hacker News 50

@[email protected]

Self-contained Python scripts with uv

Link: http://blog.dusktreader.dev/2025/03/29/self-contained-python-scripts-with-uv/
Discussion: https://news.ycombinator.com/item?id=43519669

#python

Hacker News 50

@[email protected]

Self-contained Python scripts with uv

Link: http://blog.dusktreader.dev/2025/03/29/self-contained-python-scripts-with-uv/
Discussion: https://news.ycombinator.com/item?id=43519669

#python

두번의 봄 | Twice Spring

@[email protected]

여러분, 대한민국에 자전거법이 생긴지도 벌써 30년이 다 되어가고요, 자전거도로 법제화가 된지도 30년이 넘어가거든요? 그런데 왜 자전거도로에서 걸어다녀도 된다느니, 자전거도로에서 유모차 끌 맛 안 난다느니 하는 명백한 불법행위 조장을 하고 다니시는지 좀 그러네요. https://lgh0428.tistory.com/444

염산하

@[email protected] · Reply to Woojin Kim's post

@me 해탈하셨군요...

염산하

@[email protected]

해커스 펍이 왕성한 이 때, 혼자 조용히 저는 @hollo 가 좋아요 ㅎㅎ

염산하

@[email protected] · Reply to AK's post

@ak 영화 메멘토가 떠오르는 내용이네요. 영화에선 누군가 의도적으로 조작한 기억도 섞이고 점점 산으로...

AK

@[email protected]

AI가 생성한 내용을 내 지식관리시스템(위키 등)에 복붙하면 그건 내 지식일까 아닐까?

2008년 경에 The extended mind (1998, Andy Clark and David Chalmers)라는 짧은 에세이를 읽었는데 여기서 본 내용이 참고할만 하다.

저자들은 장기기억 상실을 앓고 있는 사람이 수첩에 모든 걸 기록하고 항상 이를 참고한다면 그 수첩에 담긴 글들은 "확장된 기억"이라고 주장한다. 더 나아가서, 수첩의 내용이 단순히 "기억"이 아니라 "믿음extended dispositional belief"이기 위해서 필요한 기준을 추가로 제시한다.

해당 정보가 그 사람의 삶에 항상 함께하며 참고해야하는 상황이 오면 거의 반드시 참고하여 행동한다.
참고하고 싶을 때 어려움 없이 참고할 수 있어야 한다.
일단 그 정보를 참고하면 이를 의심없이 수용한다.
그 정보가 거기에 담긴 이유는 과거 언젠가 내가 내용을 신뢰했기 때문이다.

AI가 생성한 내용을 검토 없이 복붙했다면 이는 4번을 만족하지 못하고, 이에 따라 3번에도 문제가 생긴다. 따라서 검토 없는 복붙은 좋은 전략이 아닐 뿐 아니라 내 지식관리시스템을 망칠 가능성이 크다.

참고로 에세이의 저자들은 이 중 마지막 기준에 논쟁의 여지가 있다고 말하긴 한다. 무의식적으로 믿음이 형성되는 경우, 기억 조작이 일어난 경우 등이 있기 때문. 그런데 KMS 맥락에선 4번이 중요하다고 봐도 되겠다.

Jaeyeol Lee

@[email protected]

Hackers' Pub을 포함하여 페디버스에 입문한 여러분 중 누군가는 막막한 생각이 들 수도 있습니다. 특히 지인의 Pool이 없는 상황이거나 혹은 Fediverse라는 개념 자체가 낯설 수록이요.

먼저 인스턴스라는 개념도 낯설게 느껴지거니와, 어떤 사람을 팔로할 지도 아예 생태계에 쌩으로 입문하는 입장에서는 시작을 하는 것 자체가 난해합니다.

Hackers' Pub을 포함한 ActivityPub 프로토콜을 사용하는 서비스들의 장점은 Bluesky, Mastodon, Misskey 어디에든 걸쳐있는 사람들과 하나로 연결되는 경험을 누릴 수 있다고 언급한 적은 있었습니다만, 이러한 장점을 어떻게 누릴 수 있는지도 알기는 어려울 겁니다.

보통은 트위터나 혹은 다른 알고리즘 기반의 추천을 해주는 여러 서비스들은 좋아하는지 취향에 맞는지와는 상관없이 일단 추천하긴 하지만, 페디버스는 국내 생태계 한정으로는 추천을 하기가 쉽지 않은 것 또한 사실이긴 합니다. 하지만, 해외개발자 Pool은 굉장히 넓은 것이 자명합니다. 물론, 이것도 역시 추천을 하기가 쉽지 않습니다. 여러분이 혹시 단골로 찾아보는 개발자 블로그가 있다면 Mastodon 계정이 보이는 경우를 최소 두 자릿수는 준하게 보실 수 있을 것이긴 합니다.

아무튼, 페디버스 생태계에도 소프트웨어 종사자인 여러분이 읽을만한 피드는 준비되어 있습니다. 팔로해볼 수 있는 여러 계정들을 예시로 들어서 소개해볼까 합니다.

개발자들이 모여있는 인스턴스

어떤 마스토돈 인스턴스를 이용할 수 있는지는 **여기**에도 잘 설명되어 있습니다. 개인적으로 추천하는 마스토돈 인스턴스는 아래와 같습니다.

국내

silicon.moe -- 이공계열에 종사하는 사람들을 위한 한국어권 마스토돈 인스턴스입니다.

해외

hachyderm.io -- IT 업계 종사자를 위한 마스토돈 인스턴스입니다. 대부분의 유명한 개발자들이 여기에 몰려있다고 봐도 됩니다.
emacs.ch -- Emacs 에디터를 사용하는 사람들을 위한 마스토돈 인스턴스입니다.
functional.cafe -- 함수형 개발자를 위한 마스토돈 인스턴스입니다.
genserver.social -- Erlang/Elixir 개발자를 위한 Akkoma 인스턴스입니다.
ruby.social -- Ruby 개발자를 위한 마스토돈 인스턴스입니다.
mtd.pythonasia.org -- 아시아권의 Python 개발자를 위한 마스토돈 인스턴스입니다.
fosstodon.org -- 오픈소스 개발자를 위한 마스토돈 인스턴스입니다. Python Software Foundation, Libre Office 등 오픈소스 프로젝트의 공식계정들이 많이 있습니다.
hci.social -- HCI 연구자들을 위한 마스토돈 인스턴스입니다. Princeton HCI에서 운영하고 있습니다.
vt.social -- 개발 분야 버츄얼 유튜버를 위한 마스토돈 인스턴스입니다. Asahi Lina, Luna가 공동 운영하고 있습니다.

Who to follow

Twitter/Threads에서는 자체적인 추천 알고리즘을 통해 어떤 계정을 팔로하면 괜찮을지 제안을 하기도 합니다. 하지만, 마스토돈은 그런 기능 쪽으로는 미비하다시피합니다.

개발 관련 정보를 구독하고 싶은 분들의 입장에서는 굉장히 치명적일 수도 있습니다. 아래에서는 어떤 개발자에게든 팔로할 것을 권장하는 계정들을 소개합니다.

개발 관련 뉴스

Geeknews Bot -- GeekNews의 피드를 실시간으로 받아볼 수 있습니다.
Hackernews
- Hacker News 500 -- Hacker News 에서 500 포인트 받은 글들을 볼 수 있습니다.
- Hacker News 100 -- Hacker News 에서 100 포인트 받은 글들을 볼 수 있습니다.
- Hacker News 50 -- Hacker News 에서 50 포인트 받은 글들을 볼 수 있습니다.
Lobsters -- Lobsters는 Hacker News 보다는 좀 더 소프트웨어 개발/컴퓨터 사이언스에 초점이 맞춰진 글들이 올라옵니다.
- Twitter 공식 계정도 있었지만, 트위터의 Bot 관련 정책 변경으로 인해 2023년 5월 3일부로 운영이 중단되었습니다.
discu.eu Weekly newsletter - 각종 분야별로 newsletter를 받아볼 수 있습니다.
- Python weekly, Haskell weekly 등등의 마스토돈 공식 계정이 있습니다.

오픈소스 컨트리뷰터

Hong minhee -- Hackers' Pub, Hollo, Fedify 등 v페디버스 생태계에서 다양하고 재밌는 것들을 개발하고 계시는 분입니다.
Eugen Rochko -- Mastodon 코어 컨트리뷰터입니다.
Rob Pike -- Golang을 개발하신 그 분 맞습니다.
Asahi Lina -- Asahi Linux에 기여하는 모습을 생중계하는 버츄얼 유튜버입니다.