Lucene, mail # dev - Re: Count of keys of an FST

Count of keys of an FST

Jason Rutherglen 2012-06-27, 20:36

The FST class has a number of methods that return counts, which one returns
the total number of keys that have been encoded into the FST?

Re: Count of keys of an FST

Dawid Weiss 2012-06-27, 20:48

I don't think there is one that you could use out of the box... but
maybe I'm wrong and it's stored in the header somewhere (don't have
the source in front of me).

To calculate it by hand the worst case is that you'll need a recursive
traversal, which would mean O(number of stored states) with
intermediate count caches or O(number of keys) without any caches and
memory overhead (just recursive traversal).

Dawid

On Wed, Jun 27, 2012 at 10:36 PM, Jason Rutherglen
<[EMAIL PROTECTED]> wrote:
> The FST class has a number of methods that return counts, which one returns
> the total number of keys that have been encoded into the FST?

---------------------------------------------------------------------

Re: Count of keys of an FST

Jason Rutherglen 2012-06-27, 20:50

Sounds like I should just count as the keys are added and store the count
separately.

On Wed, Jun 27, 2012 at 3:48 PM, Dawid Weiss
<[EMAIL PROTECTED]>wrote:

> I don't think there is one that you could use out of the box... but
> maybe I'm wrong and it's stored in the header somewhere (don't have
> the source in front of me).
>
> To calculate it by hand the worst case is that you'll need a recursive
> traversal, which would mean O(number of stored states) with
> intermediate count caches or O(number of keys) without any caches and
> memory overhead (just recursive traversal).
>
> Dawid
>
> On Wed, Jun 27, 2012 at 10:36 PM, Jason Rutherglen
> <[EMAIL PROTECTED]> wrote:
> > The FST class has a number of methods that return counts, which one
> returns
> > the total number of keys that have been encoded into the FST?
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [EMAIL PROTECTED]
> For additional commands, e-mail: [EMAIL PROTECTED]
>
>

Re: Count of keys of an FST

Dawid Weiss 2012-06-27, 20:53

If you need the count with constant time then yes, you should store it
separately. You could also make a transducer that would store it at
the root node as side-effect of values associated with keys, but it's
kind of ugly.

Please check the fst header though -- I'm not sure, maybe Mike wrote
it so that the node count/ keys count is in there.

Dawid

On Wed, Jun 27, 2012 at 10:50 PM, Jason Rutherglen
<[EMAIL PROTECTED]> wrote:
> Sounds like I should just count as the keys are added and store the count
> separately.
>
> On Wed, Jun 27, 2012 at 3:48 PM, Dawid Weiss <[EMAIL PROTECTED]>
> wrote:
>>
>> I don't think there is one that you could use out of the box... but
>> maybe I'm wrong and it's stored in the header somewhere (don't have
>> the source in front of me).
>>
>> To calculate it by hand the worst case is that you'll need a recursive
>> traversal, which would mean O(number of stored states) with
>> intermediate count caches or O(number of keys) without any caches and
>> memory overhead (just recursive traversal).
>>
>> Dawid
>>
>> On Wed, Jun 27, 2012 at 10:36 PM, Jason Rutherglen
>> <[EMAIL PROTECTED]> wrote:
>> > The FST class has a number of methods that return counts, which one
>> > returns
>> > the total number of keys that have been encoded into the FST?
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: [EMAIL PROTECTED]
>> For additional commands, e-mail: [EMAIL PROTECTED]
>>
>

---------------------------------------------------------------------

Re: Count of keys of an FST

Michael McCandless 2012-06-28, 10:37

I believe node and arc count are stored, but not key count. But check
the sources to be sure!

Mike McCandless

http://blog.mikemccandless.com

On Wed, Jun 27, 2012 at 4:53 PM, Dawid Weiss
<[EMAIL PROTECTED]> wrote:
> If you need the count with constant time then yes, you should store it
> separately. You could also make a transducer that would store it at
> the root node as side-effect of values associated with keys, but it's
> kind of ugly.
>
> Please check the fst header though -- I'm not sure, maybe Mike wrote
> it so that the node count/ keys count is in there.
>
> Dawid
>
> On Wed, Jun 27, 2012 at 10:50 PM, Jason Rutherglen
> <[EMAIL PROTECTED]> wrote:
>> Sounds like I should just count as the keys are added and store the count
>> separately.
>>
>> On Wed, Jun 27, 2012 at 3:48 PM, Dawid Weiss <[EMAIL PROTECTED]>
>> wrote:
>>>
>>> I don't think there is one that you could use out of the box... but
>>> maybe I'm wrong and it's stored in the header somewhere (don't have
>>> the source in front of me).
>>>
>>> To calculate it by hand the worst case is that you'll need a recursive
>>> traversal, which would mean O(number of stored states) with
>>> intermediate count caches or O(number of keys) without any caches and
>>> memory overhead (just recursive traversal).
>>>
>>> Dawid
>>>
>>> On Wed, Jun 27, 2012 at 10:36 PM, Jason Rutherglen
>>> <[EMAIL PROTECTED]> wrote:
>>> > The FST class has a number of methods that return counts, which one
>>> > returns
>>> > the total number of keys that have been encoded into the FST?
>>>
>>> ---------------------------------------------------------------------
>>> To unsubscribe, e-mail: [EMAIL PROTECTED]
>>> For additional commands, e-mail: [EMAIL PROTECTED]
>>>
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [EMAIL PROTECTED]
> For additional commands, e-mail: [EMAIL PROTECTED]
>

---------------------------------------------------------------------

Re: Count of keys of an FST

Jason Rutherglen 2012-06-28, 13:32

I looked at the sources and didn't see a key count.

Thanks Dawid and Mike.

On Thu, Jun 28, 2012 at 6:37 AM, Michael McCandless <
[EMAIL PROTECTED]> wrote:

> I believe node and arc count are stored, but not key count. But check
> the sources to be sure!
>
> Mike McCandless
>
> http://blog.mikemccandless.com
>
> On Wed, Jun 27, 2012 at 4:53 PM, Dawid Weiss
> <[EMAIL PROTECTED]> wrote:
> > If you need the count with constant time then yes, you should store it
> > separately. You could also make a transducer that would store it at
> > the root node as side-effect of values associated with keys, but it's
> > kind of ugly.
> >
> > Please check the fst header though -- I'm not sure, maybe Mike wrote
> > it so that the node count/ keys count is in there.
> >
> > Dawid
> >
> > On Wed, Jun 27, 2012 at 10:50 PM, Jason Rutherglen
> > <[EMAIL PROTECTED]> wrote:
> >> Sounds like I should just count as the keys are added and store the
> count
> >> separately.
> >>
> >> On Wed, Jun 27, 2012 at 3:48 PM, Dawid Weiss <
> [EMAIL PROTECTED]>
> >> wrote:
> >>>
> >>> I don't think there is one that you could use out of the box... but
> >>> maybe I'm wrong and it's stored in the header somewhere (don't have
> >>> the source in front of me).
> >>>
> >>> To calculate it by hand the worst case is that you'll need a recursive
> >>> traversal, which would mean O(number of stored states) with
> >>> intermediate count caches or O(number of keys) without any caches and
> >>> memory overhead (just recursive traversal).
> >>>
> >>> Dawid
> >>>
> >>> On Wed, Jun 27, 2012 at 10:36 PM, Jason Rutherglen
> >>> <[EMAIL PROTECTED]> wrote:
> >>> > The FST class has a number of methods that return counts, which one
> >>> > returns
> >>> > the total number of keys that have been encoded into the FST?
> >>>
> >>> ---------------------------------------------------------------------
> >>> To unsubscribe, e-mail: [EMAIL PROTECTED]
> >>> For additional commands, e-mail: [EMAIL PROTECTED]
> >>>
> >>
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: [EMAIL PROTECTED]
> > For additional commands, e-mail: [EMAIL PROTECTED]
> >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [EMAIL PROTECTED]
> For additional commands, e-mail: [EMAIL PROTECTED]
>
>

Re: Count of keys of an FST

Dawid Weiss 2012-06-28, 13:36

Let me know if you need that snippet of code to count the keys; or try
it yourself -- should be good practice :)

Dawid

On Thu, Jun 28, 2012 at 3:32 PM, Jason Rutherglen
<[EMAIL PROTECTED]> wrote:
> I looked at the sources and didn't see a key count.
>
> Thanks Dawid and Mike.
>
> On Thu, Jun 28, 2012 at 6:37 AM, Michael McCandless
> <[EMAIL PROTECTED]> wrote:
>>
>> I believe node and arc count are stored, but not key count. But check
>> the sources to be sure!
>>
>> Mike McCandless
>>
>> http://blog.mikemccandless.com
>>
>> On Wed, Jun 27, 2012 at 4:53 PM, Dawid Weiss
>> <[EMAIL PROTECTED]> wrote:
>> > If you need the count with constant time then yes, you should store it
>> > separately. You could also make a transducer that would store it at
>> > the root node as side-effect of values associated with keys, but it's
>> > kind of ugly.
>> >
>> > Please check the fst header though -- I'm not sure, maybe Mike wrote
>> > it so that the node count/ keys count is in there.
>> >
>> > Dawid
>> >
>> > On Wed, Jun 27, 2012 at 10:50 PM, Jason Rutherglen
>> > <[EMAIL PROTECTED]> wrote:
>> >> Sounds like I should just count as the keys are added and store the
>> >> count
>> >> separately.
>> >>
>> >> On Wed, Jun 27, 2012 at 3:48 PM, Dawid Weiss
>> >> <[EMAIL PROTECTED]>
>> >> wrote:
>> >>>
>> >>> I don't think there is one that you could use out of the box... but
>> >>> maybe I'm wrong and it's stored in the header somewhere (don't have
>> >>> the source in front of me).
>> >>>
>> >>> To calculate it by hand the worst case is that you'll need a recursive
>> >>> traversal, which would mean O(number of stored states) with
>> >>> intermediate count caches or O(number of keys) without any caches and
>> >>> memory overhead (just recursive traversal).
>> >>>
>> >>> Dawid
>> >>>
>> >>> On Wed, Jun 27, 2012 at 10:36 PM, Jason Rutherglen
>> >>> <[EMAIL PROTECTED]> wrote:
>> >>> > The FST class has a number of methods that return counts, which one
>> >>> > returns
>> >>> > the total number of keys that have been encoded into the FST?
>> >>>
>> >>> ---------------------------------------------------------------------
>> >>> To unsubscribe, e-mail: [EMAIL PROTECTED]
>> >>> For additional commands, e-mail: [EMAIL PROTECTED]
>> >>>
>> >>
>> >
>> > ---------------------------------------------------------------------
>> > To unsubscribe, e-mail: [EMAIL PROTECTED]
>> > For additional commands, e-mail: [EMAIL PROTECTED]
>> >
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: [EMAIL PROTECTED]
>> For additional commands, e-mail: [EMAIL PROTECTED]
>>
>

---------------------------------------------------------------------

Re: Count of keys of an FST

Jason Rutherglen 2012-06-28, 15:19

Thanks, it's done! :)

https://issues.apache.org/jira/browse/CASSANDRA-4324

On Thu, Jun 28, 2012 at 9:36 AM, Dawid Weiss
<[EMAIL PROTECTED]>wrote:

> Let me know if you need that snippet of code to count the keys; or try
> it yourself -- should be good practice :)
>
> Dawid
>
> On Thu, Jun 28, 2012 at 3:32 PM, Jason Rutherglen
> <[EMAIL PROTECTED]> wrote:
> > I looked at the sources and didn't see a key count.
> >
> > Thanks Dawid and Mike.
> >
> > On Thu, Jun 28, 2012 at 6:37 AM, Michael McCandless
> > <[EMAIL PROTECTED]> wrote:
> >>
> >> I believe node and arc count are stored, but not key count. But check
> >> the sources to be sure!
> >>
> >> Mike McCandless
> >>
> >> http://blog.mikemccandless.com
> >>
> >> On Wed, Jun 27, 2012 at 4:53 PM, Dawid Weiss
> >> <[EMAIL PROTECTED]> wrote:
> >> > If you need the count with constant time then yes, you should store it
> >> > separately. You could also make a transducer that would store it at
> >> > the root node as side-effect of values associated with keys, but it's
> >> > kind of ugly.
> >> >
> >> > Please check the fst header though -- I'm not sure, maybe Mike wrote
> >> > it so that the node count/ keys count is in there.
> >> >
> >> > Dawid
> >> >
> >> > On Wed, Jun 27, 2012 at 10:50 PM, Jason Rutherglen
> >> > <[EMAIL PROTECTED]> wrote:
> >> >> Sounds like I should just count as the keys are added and store the
> >> >> count
> >> >> separately.
> >> >>
> >> >> On Wed, Jun 27, 2012 at 3:48 PM, Dawid Weiss
> >> >> <[EMAIL PROTECTED]>
> >> >> wrote:
> >> >>>
> >> >>> I don't think there is one that you could use out of the box... but
> >> >>> maybe I'm wrong and it's stored in the header somewhere (don't have
> >> >>> the source in front of me).
> >> >>>
> >> >>> To calculate it by hand the worst case is that you'll need a
> recursive
> >> >>> traversal, which would mean O(number of stored states) with
> >> >>> intermediate count caches or O(number of keys) without any caches
> and
> >> >>> memory overhead (just recursive traversal).
> >> >>>
> >> >>> Dawid
> >> >>>
> >> >>> On Wed, Jun 27, 2012 at 10:36 PM, Jason Rutherglen
> >> >>> <[EMAIL PROTECTED]> wrote:
> >> >>> > The FST class has a number of methods that return counts, which
> one
> >> >>> > returns
> >> >>> > the total number of keys that have been encoded into the FST?
> >> >>>
> >> >>>
> ---------------------------------------------------------------------
> >> >>> To unsubscribe, e-mail: [EMAIL PROTECTED]
> >> >>> For additional commands, e-mail: [EMAIL PROTECTED]
> >> >>>
> >> >>
> >> >
> >> > ---------------------------------------------------------------------
> >> > To unsubscribe, e-mail: [EMAIL PROTECTED]
> >> > For additional commands, e-mail: [EMAIL PROTECTED]
> >> >
> >>
> >> ---------------------------------------------------------------------
> >> To unsubscribe, e-mail: [EMAIL PROTECTED]
> >> For additional commands, e-mail: [EMAIL PROTECTED]
> >>
> >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [EMAIL PROTECTED]
> For additional commands, e-mail: [EMAIL PROTECTED]
>
>