From: Kim Minh Kaplan <kaplan@kim-minh.com>
Subject: Re: threading algorithm in Gnus
Date: Sat, 11 Aug 2001 17:23:03 +0200 [thread overview]
Message-ID: <87r8uipqnc.fsf@mounette.mimosas.kim-minh.com> (raw)
In-Reply-To: <vafelqj7vtc.fsf@INBOX.auto.gnus.tok.lucy.cs.uni-dortmund.de>
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.
prev parent reply other threads:[~2001-08-11 15:23 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2001-08-10 15:56 Kai Großjohann
2001-08-11 15:23 ` Kim Minh Kaplan [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87r8uipqnc.fsf@mounette.mimosas.kim-minh.com \
--to=kaplan@kim-minh.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).