From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.emacs.gnus.general/37710 Path: main.gmane.org!not-for-mail From: Kim Minh Kaplan Newsgroups: gmane.emacs.gnus.general Subject: Re: threading algorithm in Gnus Date: Sat, 11 Aug 2001 17:23:03 +0200 Organization: Getup'aaa Interactive Message-ID: <87r8uipqnc.fsf@mounette.mimosas.kim-minh.com> References: NNTP-Posting-Host: coloc-standby.netfonds.no Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Trace: main.gmane.org 1035173078 15269 80.91.224.250 (21 Oct 2002 04:04:38 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Mon, 21 Oct 2002 04:04:38 +0000 (UTC) Return-Path: Return-Path: Original-Received: (qmail 6941 invoked from network); 11 Aug 2001 15:23:06 -0000 Original-Received: from quimby.gnus.org (195.204.10.139) by gnus.org with SMTP; 11 Aug 2001 15:23:06 -0000 Original-Received: (from news@localhost) by quimby.gnus.org (8.9.3/8.9.3) id RAA16924 for ding@gnus.org; Sat, 11 Aug 2001 17:22:53 +0200 (CEST) Original-To: ding@gnus.org Original-Path: not-for-mail Original-Newsgroups: gnus.ding Original-NNTP-Posting-Host: 213.41.77.73 Original-X-Trace: quimby.gnus.org 997543373 28788 213.41.77.73 (11 Aug 2001 15:22:53 GMT) Original-X-Complaints-To: usenet@quimby.gnus.org Original-NNTP-Posting-Date: 11 Aug 2001 15:22:53 GMT X-Attribution: KMK User-Agent: Gnus/5.090004 (Oort Gnus v0.04) Emacs/20.7 Original-Lines: 21 Xref: main.gmane.org gmane.emacs.gnus.general:37710 X-Report-Spam: http://spam.gmane.org/gmane.emacs.gnus.general:37710 Kai Großjohann writes: > Does anybody know what is the threading algorithm used in Gnus? What > is its complexity? It seems to be pretty fast... Gnus uses uses a symbol table to build the thread tree. It is called `gnus-newsgroup-dependencies'. Each article is entered in this table through `gnus-dependencies-add-header'. The symbol's name is the message ID. The symbol's value is a list (HEADER CHILD1 ...) where HEADER is a vector as defined in "nnheader.el" and each CHILDx is the symbol's value of each child. This part is constant time complexity. Then the header goes through a loop on each of its parents to break any threading loops (these loops cause article not to be displayed). This is an O(n) on the depth of the thread. These are the part at the center of the threads construction. I never had to look at the other parts. I suppose there are some other parts where complexity is added. Kim Minh.