From: Konstantin Osipov <kostja.osipov@gmail.com>
To: Nikita Pettik <korablev@tarantool.org>
Cc: tarantool-patches@dev.tarantool.org, v.shpilevoy@tarantool.org
Subject: Re: [Tarantool-patches] [PATCH] rfc: multi-directional iterators
Date: Sat, 25 Apr 2020 12:00:27 +0300 [thread overview]
Message-ID: <20200425090027.GA8860@atlas> (raw)
In-Reply-To: <d50042fa51c71b79c88c4e3e8965fba836b2ae1c.1580071900.git.korablev@tarantool.org>
* Nikita Pettik <korablev@tarantool.org> [20/01/26 23:58]:
> +Cons (-):
> + - obviously the main drawback of this approach is time complexity -
> + it doesn't seem to be way faster than simple full-scan (the more key parts
> + with different iterating order are declared, the slower process will be).
This is not true. Getting to the next distinct element in a tree is O(log(distance
between elements)) of the tree, not O(distance between elements).
Actually it's quite evident that for BPS it's best to use this
option, the main issue with the implementation is that
multi-directional iterators require more state (they need to
remember a stack of positions), than a single-directional one (it
only has one position, the current one).
--
Konstantin Osipov, Moscow, Russia
next prev parent reply other threads:[~2020-04-25 9:00 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-01-26 20:54 Nikita Pettik
2020-01-27 19:34 ` Konstantin Osipov
2020-01-27 19:38 ` Konstantin Osipov
2020-04-25 9:00 ` Konstantin Osipov [this message]
2020-04-24 10:10 Aleksandr Lyapunov
2020-04-25 9:03 ` Konstantin Osipov
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=20200425090027.GA8860@atlas \
--to=kostja.osipov@gmail.com \
--cc=korablev@tarantool.org \
--cc=tarantool-patches@dev.tarantool.org \
--cc=v.shpilevoy@tarantool.org \
--subject='Re: [Tarantool-patches] [PATCH] rfc: multi-directional iterators' \
/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
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox