Hacker News 의견

• Krapivin이 Yao의 추측을 모른 채로 돌파구를 마련했음

  • Balatro의 개발자는 기존 덱 빌더를 모른 채로 수상 경력의 덱 빌더 게임을 만들었음
  • 문제 접근의 최선의 방법은 이전의 유사한 노력들을 모른 채로 하거나 무시하는 것일 수 있음
  • 현재 세계는 너무 상호 연결되어 있어, 이전의 사고의 틀에 빠지기 쉬움
  • 인터넷은 훌륭하지만, 사고의 세계를 동질화시키는 경향이 있음

• 멋진 결과지만, 컴퓨터 과학 추측이라고 불려야 할 것 같음

• 이 구현을 가진 GitHub 저장소를 아는 사람이 있는지 궁금함

• 멋지지만, 이 글의 "유명인화" 스타일이 약간 불편함

  • 대학 환경에서 다양한 포즈를 취한 젊은이의 사진을 여러 장 볼 필요가 있었는지 의문임
  • 컴퓨터 성공의 생존자를 미화하여 더 많은 참여를 유도하기 위한 La La Land의 버전이 필요한 것 같음

• 새로운 해시 테이블에서 최악의 경우 쿼리와 삽입에 필요한 시간이 (log x)²에 비례함

  • 팀의 결과가 즉각적인 응용으로 이어지지 않을 수 있음
  • 왜 즉각적인 응용으로 이어지지 않는지 이해가 안 됨
  • 실제 사용 사례 분석이 순수한 수학적 접근보다 해시 구현을 더 잘 조정할 수 있는 상황인지 궁금함

• 이 기사를 읽는 것은 Monty-Hall 문제의 설명을 읽는 것과 같음

  • 결론이 상식을 거스르는 것 같지만 증명 가능함
  • 해시 테이블의 충만도와 상관없이 일정한 평균 쿼리 시간을 달성할 수 있다는 사실은 저자들조차도 예상하지 못했음

• 최근의 좋은 테스트임

  • 깊은 연구가 이 결과를 복사하지 않고 나올 수 있는지 보자
  • gpt4, Gemini 2, Claude는 운이 없었음
  • 인간 주도의 컴퓨터 과학은 여전히 안전함

• 'Tiny pointers'의 간단한 구현을 가진 사람이 있는지 궁금함

  • 내 마음은 증명보다 코드/의사 코드가 먼저임

• <i>Scooby Doo</i>의 악당이 항상 말했듯이:

  • <i>"그리고 그 성가신 아이들이 아니었다면, 난 성공했을 텐데!"</i>

• 논문을 대충 읽어보니, 그들이 사용한 주요 차이점은 해시 테이블 삽입 알고리즘이 첫 번째 빈 슬롯을 탐욕적으로 채우는 대신 더 멀리 탐색한다는 것임

  • 테이블이 매우 가득 차 있어도 빈 슬롯을 효율적으로 찾는 증명 가능한 탐색 순서를 결합함
  • 해시 테이블이 덜 가득 찼을 때 삽입이 느려지지만, 마지막 남은 빈 슬롯을 찾지 못하는 최악의 시나리오를 피할 수 있음

• 흥미로운 이론적 결과지만, 실제로는 필요한 것보다 더 큰 테이블을 할당하는 현재의 '트릭'이 더 나은 해결책일 것 같음

  • 예를 들어, Rust의 hashbrown은 테이블의 1/8(12.5%)을 비워두어 메모리를 조금 더 사용하지만 삽입/조회가 매우 빠름