From: Alexey Tourbin <at@altlinux.ru>
To: ALT Linux Team development discussions <devel@lists.altlinux.org>
Subject: Re: [devel] contents_index trie
Date: Sat, 1 Nov 2008 21:01:36 +0300
Message-ID: <20081101180136.GM8739@altlinux.org> (raw)
In-Reply-To: <20081101154207.GA21180@mw.office.seiros.ru>
[-- Attachment #1: Type: text/plain, Size: 873 bytes --]
On Sat, Nov 01, 2008 at 06:42:07PM +0300, Денис Смирнов wrote:
> On Tue, Oct 28, 2008 at 10:50:13AM +0300, Алексей Турбин wrote:
>
> Правильно ли я понимаю что речь идет о задаче создания чего-то вроде cdb,
> с некоторыми уточнениями:
> - нет key/data, есть только key
> - поддерживается единственная операция "проверить на существование данный
> key"
> - нужно обеспечить минимальное количество pagefaults при выполнении этой
> операции
>
> Я правильно понял?
Нет, имееется в виду trie. Это дерево. С каждым ключом ассоциировано
значение _и_ последующие вложенные ключи. Так что идёт доступ по
составному ключу, типа ["usr","bin","perl"]->"perl-base". То есть
значение ключа "накапливается", а дополнительный переход на каждом этапе
выполняется рекурсивно (хвостовая рекурсия с "остатком" составного ключа).
http://en.wikipedia.org/wiki/Trie
[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]
next prev parent reply other threads:[~2008-11-01 18:01 UTC|newest]
Thread overview: 53+ messages / expand[flat|nested] mbox.gz Atom feed top
2008-10-26 10:16 [devel] kill Sisyphus noarch? Igor Vlasenko
2008-10-26 10:20 ` Mikhail Gusarov
2008-10-26 12:02 ` Alexey Tourbin
2008-10-26 12:04 ` Mikhail Gusarov
2008-10-26 12:14 ` Alexey Tourbin
2008-10-26 13:22 ` Sergey Bolshakov
2008-10-26 13:24 ` Mikhail Gusarov
2008-10-26 12:27 ` Alexey Tourbin
2008-10-26 12:29 ` Mikhail Gusarov
2008-10-26 12:41 ` Alexey Tourbin
2008-10-26 12:46 ` Mikhail Gusarov
2008-10-26 12:52 ` Alexey Tourbin
2008-10-26 12:58 ` Mikhail Gusarov
2008-10-26 18:15 ` Igor Vlasenko
2008-10-26 18:18 ` Mikhail Gusarov
2008-10-26 18:43 ` Igor Vlasenko
2008-10-28 6:27 ` [devel] contents_index trie Alexey Tourbin
2008-10-28 6:31 ` Mikhail Gusarov
2008-10-28 7:04 ` Alexey Tourbin
2008-10-28 7:19 ` Mikhail Gusarov
2008-10-28 7:50 ` Alexey Tourbin
2008-10-28 7:51 ` Alexey Tourbin
2008-10-28 8:09 ` Mikhail Gusarov
2008-11-01 15:42 ` Денис Смирнов
2008-11-01 18:01 ` Alexey Tourbin [this message]
2008-11-01 18:07 ` Alexey Tourbin
2008-11-01 20:45 ` Alexey Tourbin
2008-11-01 21:19 ` Alexey Tourbin
2008-10-26 18:41 ` [devel] kill Sisyphus noarch? Alexey Tourbin
2008-10-26 18:30 ` Pavlov Konstantin
2008-10-26 18:44 ` Mikhail Gusarov
2008-10-26 19:16 ` Andrey Rahmatullin
2008-10-26 18:08 ` [devel] noarch/base Dmitry V. Levin
2008-10-26 14:30 ` [devel] kill Sisyphus noarch? Anton Farygin
2008-10-26 14:42 ` Kirill A. Shutemov
2008-10-26 14:56 ` Mikhail Gusarov
2008-10-26 17:27 ` Kirill A. Shutemov
2008-10-26 17:28 ` Mikhail Gusarov
2008-10-26 17:34 ` Kirill A. Shutemov
2008-10-26 17:34 ` Led
2008-10-26 17:35 ` Mikhail Gusarov
2008-10-26 17:38 ` Kirill A. Shutemov
2008-10-26 17:38 ` Mikhail Gusarov
2008-10-26 19:14 ` Kirill A. Shutemov
2008-10-26 19:14 ` Mikhail Gusarov
2008-10-26 18:26 ` Pavlov Konstantin
2008-10-26 17:42 ` Led
2008-10-26 17:45 ` Mikhail Gusarov
2008-10-26 13:20 ` Sergey Bolshakov
2008-10-26 13:26 ` Mikhail Gusarov
2008-10-26 14:33 ` Anton Farygin
2008-10-26 10:26 ` Igor Vlasenko
2008-10-26 12:08 ` Alexey Tourbin
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=20081101180136.GM8739@altlinux.org \
--to=at@altlinux.ru \
--cc=devel@lists.altlinux.org \
/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
ALT Linux Team development discussions
This inbox may be cloned and mirrored by anyone:
git clone --mirror http://lore.altlinux.org/devel/0 devel/git/0.git
# If you have public-inbox 1.1+ installed, you may
# initialize and index your mirror using the following commands:
public-inbox-init -V2 devel devel/ http://lore.altlinux.org/devel \
devel@altlinux.org devel@altlinux.ru devel@lists.altlinux.org devel@lists.altlinux.ru devel@linux.iplabs.ru mandrake-russian@linuxteam.iplabs.ru sisyphus@linuxteam.iplabs.ru
public-inbox-index devel
Example config snippet for mirrors.
Newsgroup available over NNTP:
nntp://lore.altlinux.org/org.altlinux.lists.devel
AGPL code for this site: git clone https://public-inbox.org/public-inbox.git